search
Log In
Quick search syntax
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users 2021 Aug 02 - 08
  1. SarathBaswa

    6 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021

Recent questions and answers in DS

0 votes
1 answer 8 views
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)
answered Jul 26 in DS asqwer 633 points 8 views
0 votes
1 answer 12 views
How many n node binary trees with items 1,2,...,n have identical postorder and inorder traversals? 0 1 n n!
answered Jul 25 in DS asqwer 633 points 12 views
0 votes
2 answers 15 views
Please solve the following question: Evaluate the Infix expression /-*25*12-119 ?
answered Jul 13 in DS asqwer 633 points 15 views
0 votes
1 answer 10 views
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.
answered Jul 11 in DS asqwer 633 points 10 views
0 votes
1 answer 22 views
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
answered Jul 10 in DS asqwer 633 points 22 views
0 votes
1 answer 92 views
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
answered Jul 3 in DS asqwer 633 points 92 views
4 votes
1 answer 1.3K views
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$
answered Jun 24 in DS amitkhurana512 173 points 1.3K views
1 vote
1 answer 39 views
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.
answered May 24 in DS Deepakk Poonia (Dee) 1.7k points 39 views
0 votes
0 answers 24 views
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.
asked May 23 in DS prateek_hazard 5 points 24 views
0 votes
1 answer 176 views
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)
answered May 18 in DS aryavart 73 points 176 views
0 votes
0 answers 33 views
asked Apr 7 in DS Relon 5 points 33 views
1 vote
3 answers 1K views
​​​​​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)$
asked Feb 18 in DS Arjun 1.5k points 1K views
2 votes
2 answers 900 views
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 _____________
asked Feb 18 in DS Arjun 1.5k points 900 views
4 votes
3 answers 1.1K views
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)$
asked Feb 18 in DS Arjun 1.5k points 1.1K views
0 votes
2 answers 695 views
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 ___________.
asked Feb 18 in DS Arjun 1.5k points 695 views
4 votes
2 answers 2.4K views
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$.
asked Feb 18 in DS Arjun 1.5k points 2.4K views
0 votes
0 answers 37 views
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
asked Feb 4 in DS hadarsh 5 points 37 views
0 votes
1 answer 92 views
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
answered Jan 16 in DS Abhisheksmile94 347 points 92 views
0 votes
1 answer 44 views
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
answered Jan 14 in DS zxy123 3.6k points 44 views
0 votes
0 answers 32 views
https://gateoverflow.in/311536/made-easy-test-series-binary-tree how tree will look like ...please see
asked Jan 12 in DS eyeamgj 29 points 32 views
0 votes
0 answers 29 views
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
asked Jan 12 in DS eyeamgj 29 points 29 views
0 votes
0 answers 13 views
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...
asked Jan 8 in DS eyeamgj 29 points 13 views
0 votes
1 answer 29 views
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
answered Jan 3 in DS Abhisheksmile94 347 points 29 views
0 votes
1 answer 44 views
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_________
answered Jan 1 in DS wander 301 points 44 views
0 votes
2 answers 54 views
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
answered Dec 22, 2020 in DS toxicdesire 555 points 54 views
0 votes
0 answers 13 views
Maximum number of node at level I is 2^I. Prove
asked Dec 19, 2020 in DS ApolloXYZ 1 point 13 views
0 votes
0 answers 13 views
What are the total number of nodes in a binary tree of height K ?
asked Dec 19, 2020 in DS ApolloXYZ 1 point 13 views
0 votes
2 answers 48 views
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.
answered Dec 17, 2020 in DS Sahil91 683 points 48 views
0 votes
1 answer 16 views
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
answered Dec 17, 2020 in DS gajendercse 41 points 16 views
0 votes
0 answers 17 views
Prove that Maximum no. of node at level I is 2^I
asked Dec 16, 2020 in DS ApolloXYZ 1 point 17 views
0 votes
0 answers 10 views
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
asked Dec 16, 2020 in DS ApolloXYZ 1 point 10 views
0 votes
1 answer 85 views
The average successful search time taken by binary search on a sorted array of 10 items is ___________
answered Dec 3, 2020 in DS ijnuhb 747 points 85 views
0 votes
1 answer 36 views
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?
answered Nov 26, 2020 in DS zxy123 3.6k points 36 views
0 votes
0 answers 82 views
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?
asked Nov 18, 2020 in DS rish-18 9 points 82 views
1 vote
1 answer 60 views
The post order traversal of a heap is ACEDBHIGF. The possible pre-order traversal is: 1. ABCDEFGHI FBEACDGHI FBEADCGHI ABDCEFGIH
answered Nov 10, 2020 in DS zxy123 3.6k points 60 views
0 votes
1 answer 49 views
When inorder traversal of a tree is given by OBAXVRZPW, the preorder traversal will yield: 1. XABOVZRWP 2. XABOVZRPW 3. XOBAZRPWV 4. XOBAVRZPW
answered Oct 18, 2020 in DS kalin 155 points 49 views
0 votes
0 answers 15 views
Resultant tree on deleting A,V,P in the below tree of order 3? DL B H PT A C E JK M R V
asked Oct 6, 2020 in DS TechLover 5 points 15 views
0 votes
0 answers 53 views
https://gateoverflow.in/2716/gate1996-1-12 In this question it is said that linked list is more efficient that array for basic operations. If I consider the operations Insert, Delete (pointer given), Find the time complexities are as follows – Insert – LL → O(1), Array → O(n) Delete – LL → O(n), Array → O(1) Find – LL → O(n), Array → O(n). How is linked list more efficient.
asked Sep 24, 2020 in DS Mellophi 363 points 53 views
0 votes
1 answer 107 views
A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L=41, and I=10, what is the value of n: (a) 3 (b) 4 (c ) 5 (d) 6
answered Sep 21, 2020 in DS Musa 5 points 107 views
0 votes
0 answers 43 views
Nine nodes labeled 1,2,3…...9 are used to construct different binary trees. How many such binary trees can be constructed whose pre-order traversal 1,2,3….9.
asked Sep 20, 2020 in DS Vishal_kumar98 37 points 43 views
To see more, click for all the questions in this category.
...