Recent questions tagged data-structures / GATE Overflow for GATE CSE

0 votes

0 answers

1531

Hash table
Consider a hash table with 'm' slots that uses chaining for collision resolution. the table is initially empty. What is probability that after 4 keys are inserted then atleast a chain of size 3 is created? (assume simple uniform hashing is used) a. m-1 b. m-4 c. m-3(m-1) d. 3m-1

Consider a hash table with 'm' slots that uses chaining for collision resolution. the table is initially empty. What is probability that after 4 keys are inserted then at...

Desert_Warrior

742 views

Desert_Warrior asked Mar 11, 2016

0 votes

2 answers

1532

Select a data structure that you have seen previously, and discuss its strengths and limitations.
Select a data structure that you have seen previously, and discuss its strengths and limitations.

Select a data structure that you have seen previously, and discuss its strengths and limitations.

Anurag_s

2.9k views

Anurag_s asked Mar 4, 2016

2 votes

1 answer

1533

IITM2012
1. What is equivalence relation? 2. How can u represent equivalence. relation with a data structure? 3. Which data structure? how efficient? How can u test for. equivalence efficiently?

1. What is equivalence relation? 2. How can u represent equivalence. relation with a data structure? 3. Which data structure? how efficient? How can u test for. equivalen...

Rajesh Pradhan

1.6k views

Rajesh Pradhan asked Feb 22, 2016

65 votes

9 answers

1534

GATE CSE 2016 Set 1 | Question: 38
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$ ... integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.

Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &...

Sandeep Singh

24.0k views

Sandeep Singh asked Feb 12, 2016

56 votes

4 answers

1535

GATE CSE 2016 Set 1 | Question: 37
An operator $delete(i)$ for a binary heap data structure is to be designed to delete the item in the $i$-th node. Assume that the heap is implemented in an array and $i$ refers to the $i$-th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root ... $O(d)$ but not $O(1)$ $O(2^d)$ but not $O(d)$ $O(d \ 2^d)$ but not $O(2^d)$

An operator $delete(i)$ for a binary heap data structure is to be designed to delete the item in the $i$-th node. Assume that the heap is implemented in an array and $i$...

Sandeep Singh

15.3k views

Sandeep Singh asked Feb 12, 2016

143 votes

12 answers

1536

GATE CSE 2016 Set 1 | Question: 41
Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing ... = Pop(S); Enqueue (Q, x); end end The maximum possible number of iterations of the while loop in the algorithm is _______.

Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Simi...

Sandeep Singh

34.9k views

Sandeep Singh asked Feb 12, 2016

61 votes

4 answers

1537

GATE CSE 2016 Set 1 | Question: 10
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($n$ refers to the number of items in the queue) ? Both operations can be performed in $O(1)$ ... both operations will be $\Omega (n)$. Worst case time complexity for both operations will be $\Omega (\log n)$

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($n$ refers to ...

Sandeep Singh

23.4k views

Sandeep Singh asked Feb 12, 2016

65 votes

6 answers

1538

GATE CSE 2016 Set 2 | Question: 36
Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right subtree using New-order; Visit the left subtree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given ... $1 \ 7 \ 6 * + \ 2 \ 5 \ 4 \ 3 \ * \ - \wedge -$

Consider the following New-order strategy for traversing a binary tree:Visit the root;Visit the right subtree using New-order;Visit the left subtree using New-order;The N...

Akash Kanase

16.8k views

Akash Kanase asked Feb 12, 2016

168 votes

17 answers

1539

GATE CSE 2016 Set 2 | Question: 40
The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is _________. Note: The height of a tree with a single node is $0$.

The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is _________.No...

Akash Kanase

50.0k views

Akash Kanase asked Feb 12, 2016

73 votes

5 answers

1540

GATE CSE 2016 Set 2 | Question: 34
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0$. The maximum depth at which integer $9$ can appear is _________.

A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the h...

Akash Kanase

25.9k views

Akash Kanase asked Feb 12, 2016

97 votes

6 answers

1541

GATE CSE 2016 Set 2 | Question: 15
$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations ... together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$

$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is...

Akash Kanase

34.4k views

Akash Kanase asked Feb 12, 2016

1 votes

1 answer

1542

data structure
what is abstract data type ? please explain with example.

what is abstract data type ? please explain with example.

indrajeet

436 views

indrajeet asked Feb 5, 2016

0 votes

1 answer

1543

Data structure used in TSP

Mayurk

1.0k views

Mayurk asked Feb 3, 2016

0 votes

3 answers

1544

how many recursive calls are there in tower of hanoi, is it 2^n-1 or 2^(n+1)-1??

Arpit Tripathi

3.2k views

Arpit Tripathi asked Feb 2, 2016

2 votes

2 answers

1545

Linked list

Sourabh Kumar

3.0k views

Sourabh Kumar asked Jan 31, 2016

0 votes

1 answer

1546

MadeEasy Test Series: Programming & DS - Binary Search Trees
Q). Find the number of trees that are possible .If we construct a binary search tree by successively inserting $5$ distinct items int an initially empty tree. a). $4$ b). $10$ c). $14$ d). $20$ I used the formula 2n!/(n+1)!*n!. Is it right ? also the ans given is 14,but I am getting 7.

Q). Find the number of trees that are possible .If we construct a binary search tree by successively inserting $5$ distinct items int an initially empty tree.a). $4$b). $...

UK

740 views

UK asked Jan 29, 2016

2 votes

3 answers

1547

MadeEasy Test Series: Programming & DS - Infix Postfix
Consider the following expression with infix notation A * B - (C + D) * (E / 5) ^ F What is the maximum height of the operator stack during conversion from infix to postfix ? a) 3 b) 4 c) 5 d) 6

Consider the following expression with infix notationA * B - (C + D) * (E / 5) ^ F What is the maximum height of the operator stack during conversion from infix to postfi...

Tushar Shinde

3.7k views

Tushar Shinde asked Jan 28, 2016

2 votes

3 answers

1548

Virtual Gate Test Series: Programming & DS - AVL Tree
Insert the given values in the order in initially empty $\text{AVL}$ tree. $\text{34,21,10,27,24,43,15,6}$ What is the value at the root of the tree$?$

Insert the given values in the order in initially empty $\text{AVL}$ tree.$\text{34,21,10,27,24,43,15,6}$What is the value at the root of the tree$?$

learncp

794 views

learncp asked Jan 26, 2016

1 votes

2 answers

1549

Binary Search tree
A binary search tree was constructed by inserting following elements into an initially empty binary tree. 50, 27, 16, 88, 34, 65, 52, 77, 93, 4, 12, 29, 44, 92 Preorder and postorder traversals of the resultant binary search tree were stored in arrays ... present in these to array A and B ___________. Everything is ok here,, But not getting how length of LCS is calculated here.

A binary search tree was constructed by inserting following elements into an initially empty binary tree. 50, 27, 16, 88...

Akanksha Kesarwani

3.5k views

Akanksha Kesarwani asked Jan 23, 2016

1 votes

1 answer

1550

MadeEasy Test Series: Programming & DS - Linked Lists
Here, what will be the Head->Next , I am confused is it first element 50 or second element 29.

Here, what will be the Head->Next , I am confused is it first element 50 or second element 29.

Pradip Nichite

749 views

Pradip Nichite asked Jan 22, 2016

5 votes

5 answers

1551

Number of nodes in heap of height 'h'
The number of nodes of height $h$ in any $n$-element heap is ________. $h$ $2^{h}$ ceil $\left[\frac{n}{2^{h}}\right]$ ceil $\left[\frac{n}{2^{h+1}}\right]$ Answer is given as D, But I think it should be C. Because, even if you take height=1 then possible nodes are 3 and 2.

The number of nodes of height $h$ in any $n$-element heap is ________.$h$$2^{h}$ceil $\left[\frac{n}{2^{h}}\right]$ceil $\left[\frac{n}{2^{h+1}}\right]$Answer is given as...

Tushar Shinde

14.1k views

Tushar Shinde asked Jan 19, 2016

6 votes

5 answers

1552

What is the time complexity to construct binary search tree when inorder and postorder traversal of tree is given?

nilamd

6.8k views

nilamd asked Jan 18, 2016

10 votes

5 answers

1553

MadeEasy Test Series: Programming & DS - Binary Tree
The number of ways we can insert elements { 1, 2, 3, .... 7 } to make an AVL tree, so that it does not have any rotation are _______ ?

The number of ways we can insert elements { 1, 2, 3, .... 7 } to make an AVL tree, so that it does not have any rotation are _______ ?

Tushar Shinde

4.2k views

Tushar Shinde asked Jan 18, 2016

4 votes

1 answer

1554

What's the difference between Binary tree height, level and depth?
What's the difference between Binary tree height, level and depth? Sometimes it's confusing! Does there definition change according to question also, if mentioned?

What's the difference between Binary tree height, level and depth? Sometimes it's confusing!Does there definition change according to question also, if mentioned?

Shashank Chavan

11.2k views

Shashank Chavan asked Jan 18, 2016

1 votes

7 answers

1555

The maximum number of nodes on level i of a binary tree
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is In the following answers, the operator '^' indicates power a) 2^i-1 b)2^i c)2^i+1 d)2^(i+1/2)

Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on lev...

Akanksha Kesarwani

102k views

Akanksha Kesarwani asked Jan 16, 2016

2 votes

1 answer

1556

worst case possible height of an AVL tree .
What is the worst case possible height of an AVL tree?? a. 2logn (Assume base of log is 2) b. 1.44log n (Assume base of log is 2) c. Depends upon implementation d. Theta(n)

What is the worst case possible height of an AVL tree??a. 2logn (Assume base of log is 2) b. 1.44log n (Assume base of log is 2)c. Depends upon implementationd. Thet...

Akanksha Kesarwani

8.1k views

Akanksha Kesarwani asked Jan 15, 2016

0 votes

2 answers

1557

Ace Test Series: Programming & DS - Binary Search Trees
I am stuck after JAN. It is not getting balanced even after 2 rotations. Can somebody help?

I am stuck after JAN. It is not getting balanced even after 2 rotations. Can somebody help?

Tushar Shinde

956 views

Tushar Shinde asked Jan 15, 2016

0 votes

1 answer

1558

depth of the binary tree with n node?

monali

799 views

monali asked Jan 11, 2016

0 votes

0 answers

1559

How to form a recurrence for finding the height of a weight balanced binary tree?
A weight balanced tree is a binary tree in which for each node, the no. of nodes in the left subtree is atleast half and at most twice the no. of nodes in the right sub tree. So how to approach for forming a recurrence for finding the height of this weight balanced binary tree ?

A weight balanced tree is a binary tree in which for each node, the no. of nodes in the left subtree is atleast half and at most twice the no. of nodes in the right sub t...

radha gogia

435 views

radha gogia asked Jan 10, 2016

0 votes

0 answers

1560

Array implementation of matrix
If tthere are two lower triangular matrix A and B.A and transpose B are stored in C. by storing only non zero elements.what should be the dimension of C. And A[i][j]= C[i][j] B[i][j]= C[i][j+1] is also written in notes i dont know its a part of ques. or solution I m not getting it what is actually asked here?

If tthere are two lower triangular matrix A and B.A and transpose B are stored in C. by storing only non zero elements.what should be the dimension of C.And A[i][j]= C[i]...

khushtak

348 views

khushtak asked Jan 10, 2016

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true