# Recent questions and answers in DS In order to reverse the elements of stack of size N, first pop off the elements one by one from the stack and enqueue them into the queue, then dequeue the elements one by one from the queue and push them back onto the stack. What is time complexity of the above operation? $\Theta$ (N) $\Theta$ (N^2) $\Theta$ (N^3) $\Theta$(logN)
How many n node binary trees with items 1,2,...,n have identical postorder and inorder traversals? 0 1 n n!
Please solve the following question: Evaluate the Infix expression /-*25*12-119 ?
In Mid Square Method(Hashing), we square the given number and then use appropriate bits from the middle. Can we have so many answers for a particular question? On what basis we choose the middle digit? What if the square is 4 digit 1234, then what will be the middle value? Will it be 23 or 2 or 3. Please explain.
Assume a scenario in which min-max heap has the following property: An almost complete binary tree where each node at an even level in the tree is less than all of its descendants and each of the node at an odd level in the tree is greater than all of its descendants. The worst-case ... log n) respectively (d) Ο(n) for max and Ο(log n) for min or Ο(n) for min and Ο(log n) for max respectively
The worst case running time to search for an element in a balanced binary search tree with n2^n elements is A. Theta (nlogn) B. Theta (n2^n) C. Theta (n) D. Theta (logn) I am confused about the term balanced here because though we know about AVL trees but ... an AVL tree here? And ofcourse I am also curious to know how to solve this question. I will be grateful for your opinions. Regards, Ananya
Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct? $t>2n-2$ ... $t>n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$ $t>\lceil \log_2(n)\rceil \text{ and } t\leq n$
1 vote
I have a very generic doubt about the Trees concept in Data structures subject, Are Trees in the subject implicitly assumed to be directed unless mentioned otherwise? Say for example, with Binary Trees or K-ary Trees the degree of child nodes are taken to be 0 without explicitly stating that the Tree is directed, Am I missing something.
In avl tree can we take base case for minimum height as n(1)=2 rather than n(0)=1 in the recurrence relation : n(h)=2n(h-1)+1 where h is height of the tree.
Assume that node L, whose key is KL, is a leaf node of binary Search tree ‘T’ having total number of nodes grater than 2 and that its parents node P with key KP, then KP is smallest key grater than KL KP is the longest key smaller than KL Either (a) or (b) Only (a) but not (b)
1 vote
​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
Consider a complete binary tree with $7$ nodes. Let $A$ denote the set of first $3$ elements obtained by performing Breadth-First Search $\text{(BFS)}$ starting from the root. Let $B$ denote the set of first $3$ elements obtained by performing Depth-First Search $\text{(DFS)}$ starting from the root. The value of $\mid A-B \mid$ is _____________
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$? $\Theta(n\log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta (1)$
Consider the following sequence of operations on an empty stack.$\textsf{push}(54);\textsf{push}(52);\textsf{pop}();\textsf{push}(55);\textsf{push}(62);\textsf{s}=\textsf{pop}();$ ... $\textsf{s+q}$ is ___________.
An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$. Which of the following ... and $y$ is a descendent of $u$ in $T$, then all paths from $x$ to $y$ in $G$ must pass through $u$.
https://gateoverflow.in/4208/gate2000-2-19 The above is the link of the question. In the question it is given that DFS results in a DFS tree T. Does this strictly imply that the graph is connected? Because if not then we can even have a disconnected graph as a counter example
Que Consider a circular queue which is of capacity 100 elements and is implemented on an array a[0...99], at a particular instant the front pointer is pointing to index 20 and the rear is pointing at index 10 the number of elements present in the queue is. 10 90 91 None
Why b option is incorrect Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is ... then u is a leaf in T (D) If {u,v} is not an edge in G then u and v must have the same parent in T
https://gateoverflow.in/57653/cormen-2nd-edition-exercise-11-2-1 WHY WE CANT DO LIKE THIS …...NUMBER OF COLLISIONS(X) : 0 1 2 3 4 …………………...N-1 P(X): 0/M 1/M 2/M…………………… … ………….(N-1)/M
https://gateoverflow.in/86224/gate1990-13a for tym complexity ..is it like …..n times we need to search position so O(nlogn) n insertion so O(n) and only two rotation so O(logn)...because i m not rotating for each iteration just doing at last so overall O(nlogn)...please look...
Maximum no of elements which can be inserted in a queue which is implemented using a circular queue on an array of size 10. Answer given was: (9) The maximum number of elements which can be stored in a circular queue of array of size n is n-1
Q. Let Q denote a queue containing 16 numbers and S be an empty stack. Head(Q) returns the element at the head of queue Q without removing it from Q. similarly Top(S) returns the element at the top of S without removing it from S. consider the algorithm given below ... ,x); else x:=Pop(S); Enqueue(Q,x); end end The maximum possible number of iteration of the while loop in the algorithm is_________
Suppose that a tree T has N1 vertices of degree 1, 2 vertices of degree 2 , 4 vertices of degree 3 And 3 vertices of degree 4. Number of vertices in the tree is ? Answer given is 21
Maximum number of node at level I is 2^I. Prove
What are the total number of nodes in a binary tree of height K ?
The degree of a node is the no. of children it has. Show that in any binary tree the number of leaves is 1 more than the no. of nodes of degree 2.
Prove by Induction that if T us a binary tree with n internal nodes, I its internal path lane and P its external path lane then E=I+2n, where n>=0
Prove that Maximum no. of node at level I is 2^I
Prove by Induction that if T is a binary tree with n internal nodes, I (its internal path lane) and P (its external path lane), then E=I+2n where n>=0
The average successful search time taken by binary search on a sorted array of 10 items is ___________
Suppose we have to insert the following sequence of keys into an empty binary search tree: 5, 7, 45, 60, 50, 23, 15, 54 What would be the height of binary search tree?
I gave a madeeasy subject-wise test of programming and ds, and it had the following question copied from a quiz of Illinois Institute of Technology CS Dept (Source: http://www.cs.iit.edu/~iraicu/teaching/EECS211/quiz4-sol.pdf) Multiple Select Question(as modified by madeeasy, the ... root and another to the leaf), so shouldn't option A be incorrect, as 2 nodes out of 3 don't have multiple links?
1 vote
The post order traversal of a heap is ACEDBHIGF. The possible pre-order traversal is: 1. ABCDEFGHI FBEACDGHI FBEADCGHI ABDCEFGIH
When inorder traversal of a tree is given by OBAXVRZPW, the preorder traversal will yield: 1. XABOVZRWP 2. XABOVZRPW 3. XOBAZRPWV 4. XOBAVRZPW