search
Log In

Webpage

Arrays, Stacks, Queues, Linked lists, Trees, Binary search trees, Binary heaps, Graphs.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}&\textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count}&4&2&2&0&2&3&1&1&1&0&1.7&4
\\\hline\textbf{2 Marks Count}&1&0&1&2&0&0&1&3&3&0&1.2&3
\\\hline\textbf{Total Marks}&6&2&4&4&2&3&3&7&7&\bf{2}&\bf{4.2}&\bf{7}\\\hline
\end{array}}}$$

Recent questions in DS

1 vote
3 answers
1
​​​​​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 860 views
2 votes
2 answers
2
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 718 views
3 votes
4 answers
3
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$
asked Feb 18 in DS Arjun 1.1k views
2 votes
2 answers
4
Consider the following statements. $S_1:\quad$ The sequence of procedure calls corresponds to a preorder traversal of the activation tree. $S_2:\quad$ The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct? $S_1$ is ... $S_2$ is true $S_1$ is true and $S_2$ is true $S_1$ is false and $S_2$ is false
asked Feb 18 in DS Arjun 496 views
3 votes
3 answers
5
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 897 views
0 votes
2 answers
6
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 602 views
4 votes
2 answers
7
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 2.3k views
0 votes
2 answers
8
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$? $3$ $4$ $5$ $6$
asked Nov 20, 2020 in DS jothee 300 views
2 votes
2 answers
9
In a binary max heap containing $n$ numbers, the smallest element can be found in ______ $O(n)$ $O(\log _2 n)$ $O(1)$ $O(\log_2 \log_2 n)$
asked Nov 20, 2020 in DS jothee 207 views
0 votes
1 answer
10
Which of the following statements are true? Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in next level. The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined The alpha-beta search algorithms computes the same ... and $(c)$ only $(a)$ and $(d)$ only $(b)$ and $(c)$ only $(c)$ and $(d)$ only
asked Nov 20, 2020 in DS jothee 238 views
0 votes
1 answer
11
Match $\text{List I}$ with $\text{List II}$ Let $R_1=\{(1,1), (2,2), (3,3)\}$ and $R_2=\{(1,1), (1,2), (1,3), (1,4)\}$ ... answer from the options given below: $A-I, B-II, C-IV, D-III$ $A-I, B-IV, C-III, D-II$ $A-I, B-III, C-II, D-IV$ $A-I, B-IV, C-II, D-III$
asked Nov 20, 2020 in DS jothee 165 views
0 votes
2 answers
12
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is $6$ $5$ $4$ $3$
asked Apr 2, 2020 in DS Lakshman Patel RJIT 308 views
0 votes
0 answers
13
0 votes
1 answer
14
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. Total time required for this is $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$
asked Apr 2, 2020 in DS Lakshman Patel RJIT 190 views
0 votes
1 answer
15
You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1,2,\dots,n.$ You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this? $\Theta(\log n)$ $\Theta(n)$ $\Theta(n \log n)$ None of the above, as the tree cannot be uniquely determined.
asked Apr 2, 2020 in DS Lakshman Patel RJIT 202 views
0 votes
1 answer
16
Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is $\Theta(\log _{2}n)$ $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$
asked Apr 2, 2020 in DS Lakshman Patel RJIT 742 views
0 votes
0 answers
17
In a circularly linked list organization, insertion of a record involves the modification of no pointer $1$ pointer $2$ pointers $3$ pointers
asked Apr 2, 2020 in DS Lakshman Patel RJIT 253 views
2 votes
0 answers
18
To sort many large objects or structures, it would be most efficient to place them in an array and sort the array pointers to them in an array and sort the array them in a linked list and sort the linked list references to them in an array and sort the array
asked Apr 2, 2020 in DS Lakshman Patel RJIT 412 views
2 votes
0 answers
19
The average search time of hashing, with linear probing will be less if the load factor is far less than one equals one is far greater than one none of these
asked Apr 2, 2020 in DS Lakshman Patel RJIT 211 views
0 votes
1 answer
20
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number number of nodes in a binary tree of height $h$ is $2^{h}$ $2^{h-1} – 1$ $2^{h+1} – 1$ $2^{h+1}$
asked Apr 1, 2020 in DS Lakshman Patel RJIT 406 views
...