Webpage

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\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}&0&2&3&1&1&1&0&1.3&3 \\\hline\textbf{2 Marks Count}&2&0&0&1&3&3&0&1.5&3 \\\hline\textbf{Total Marks}&4&2&3&3&7&7&\bf{2}&\bf{4.3}&\bf{7}\\\hline \end{array}}}$$

# Recent questions in DS

1
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$
2
A full binary tree with $n$ non-leaf nodes contains $\log_ 2 n$ nodes $n+1$ nodes $2n$ nodes $2n+1$ nodes
3
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})$
4
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.
5
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)$
6
In a circularly linked list organization, insertion of a record involves the modification of no pointer $1$ pointer $2$ pointers $3$ pointers
1 vote
7
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
1 vote
8
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
9
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}$
10
Which of the following is useful in traversing a given graph by breadth first search? Stack Set List Queue
11
If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations? $O(n),O(n)$ $O(n),O(1)$ $O(1),O(n)$ $O(1),O(1)$
12
The number of possible binary trees with $4$ nodes is $12$ $13$ $14$ $15$
13
A binary search tree contains the values-$1,2,3,4,5,6,7$ and $8.$ The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output? $5\;\;3\;\;1\;\;2\;\;4\;\;7\;\;8\;\;6\;\;$ $5\;\;3\;\;1\;\;2\;\;6\;\;4\;\;9\;\;7$ $5\;\;3\;\;2\;\;4\;\;1\;\;6\;\;7\;\;8$ $5\;\;3\;\;1\;\;2\;\;4\;\;7\;\;6\;\;8$
14
In binary search tree which traversal is used for getting ascending order values ? Inorder Preorder Postorder None of the options
15
In a full binary tree number of nodes is $63$ then the height of the tree is : $2$ $4$ $3$ $6$
1 vote
16
The address field of linked list : Contain address of next node May contain null character Contain address of next pointer Both $\left (A \right)$ and $\left ( B \right)$
1 vote
17
The expression $5-2-3^{*} – 2$ will evaluate to $18$, if : $‘ – ‘$ is left associative and $‘*‘$ has precedence over $‘ – ‘$ $‘ – ‘$ is right associative and $‘*‘$ has precedence over $‘ – ‘$ $‘ – ‘$ is right associative and $‘ – ‘$ has precedence over $‘*‘$ $‘ – ‘$ is left associative and $‘ – ‘$ has precedence over $‘*‘$
The number of unused pointers in a complete binary tree of depth $5$ is: $4$ $8$ $16$ $32$