Data Structure GATE CS and IT previous year questions with Answer
Ques 21 Gate 2019
Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?
Ques 22 Gate 2019
Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to
Ques 23 Gate 2017 Set-2
G is undirected graph with n vertices and 25 edges such that each vertex has degree at least 3. Then the maximum possible value of n is ________
a is the correct answer.
Ques 24 Gate 2017 Set-2
A Circular queue has been implemented using singly linked list where each node consists of a value and a pointer to next node. We maintain exactly two pointers FRONT and REAR pointing to the front node and rear node of queue. Which of the following statements is/are correct for circular queue so that insertion and deletion operations can be performed in O(1) i.e. constant time.
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
Ques 25 Gate 2017 Set-2
Match the following:
| (P)static char var; | (i)Sequence of memory locations to store addresses |
| (Q)m=malloc(10); m=NULL; |
(ii)A variable in data section of memory |
| (R)char *ptr[10]; | (iii)Request to allocate a CPU register to store data |
| (S)register int var1; | (iv)A lost memory which cannot be freed |
Ques 26 Gate 2017 Set-2
Match the algorithms with their time complexities:
| Algorithm | Time Complexity |
|---|---|
| (P)Tower of Hanoi with n disks | (i)θ(n2) |
| (Q)Binary Search given n sorted numbers | (ii)θ(nlogn) |
| (R)Heap sort of n numbers at the worst case | (iii)θ(2n) |
| (S)Addition of two n*n matrices | (iv)θ(logn) |
Ques 27 Gate 2017 Set-1
Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________.
a is the correct answer.
Ques 28 Gate 2017 Set-1
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.
18 is the correct answer.
Ques 29 Gate 2017 Set-1
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:
II. Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
Ques 30 Gate 2017 Set-1
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.