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
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)$
1 vote
2
A polynomial $p(x)$ is such that $p(0)=5, \: p(1)=4, \: p(2)=9$ and $p(3)=20$. The minimum degree it can have is $1$ $2$ $3$ $4$
1 vote
3
A ________ is a linear list in which insertions and deletions are made to from either end of the structure. Circular queue. Priority queue. Stack. Dequeue.
4
Which of the following is the correct order of evaluation for the below expression? $z=x+y^*z/4\%2-1$ $^*/\%+-=$ $=^*/\%+-$ $/^*\%-+=$ $^*\% /-+=$
5
What data structures is used for depth first traversal of a graph? Queue Stack List None of the above
1 vote
6
In the ________ traversal we process all of a vertex's descendants before we move to an adjacent vertex. Depth First Breadth First Width First Depth Limited
7
Which of the following need not be a binary tree? Search tree Heap AVL tree B tree
8
The maximum number of nodes in a binary tree of level $k, k\geq1$ is: $2^k+1$ $2^{k-1}$ $2^k-1$ $2^{k-1}-1$
9
Assume that the operators $+,-,\times$ are left associative and $\wedge$ is right associative. The order of precedence(from highest to lowest) is $\wedge,\times, +,-$. The postfix expression corresponding to the infix expression $a+b\times c-d\wedge e\wedge f$ is $abc\times+def\wedge\wedge-$ $abc\times+de\wedge f\wedge-$ $ab+c\times d-e\wedge f\wedge$ $-+a\times bc\wedge\wedge def$
10
A balance factor in AVL tree is used to check what rotation to make if all child nodes are at same level when the last rotation occurred if the tree is unbalanced
11
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10,8,5,3,2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is $10,8,7,3,2,1,5$ $10,8,7,2,3,1,5$ $10,8,7,1,2,3,5$ $10,8,7,5,3,2,1$
12
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)$ time. At most one ... complexity for both operations will be $\Omega(n)$. Worst case time complexity for both operations will be $\Omega(\log n)$.
13
In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal nodes is $nk$ $(n-1)k+1$ $n(k-1)+1$ $n(k-1)$
14
If for a given Binary Search Tree (BST) the pre-order traversal is $41,23,11,31,62,50,73$. Then which of the following is its post-order traversal? $11,31,23,50,73,62,41$ $31,11,23,50,41,62,73$ $11,31,50,23,73,62,41$ $11,31,23,50,62,73,41$
15
Consider a complete binary tree where the left and the right sub trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: $\Omega(\log n)$ $\Omega(n\log n)$ $\Omega(n)$ $\Omega(n^2)$
16
Consider the following linked list : Which of the following piece of code will insert the node pointed to by $q$ at the end of the list ? $\text{for (p=list; p !=NULL; p=p → next);}\\ p=q;$ $\text{for (p=list; p !=NULL; p=p → next);}\\ \text{p→next=q;}$ $\text{for (p=list; p→next !=NULL; p=p → next);}\\ p=q;$ $\text{for (p=list; p→next !=NULL; p=p → next);}\\ p→next=q;$
17
Consider a rooted tree in which every node has at least three children. What is the minimum number of nodes at level i (i > $0$) of the tree ? Assume that the root is at level $0$: $3^i$ $3i$ $3$ $3i+1$
The height of a binary tree with $n$ nodes, in the worst case is : $O(log n)$ $O(n)$ $\Omega(n\log n)$ $\Omega(n^2)$