# Data Structure

 Question 1
Consider the following ANSI C program:
#include < stdio.h >

#include < stdlib.h >

struct Node{
int value;
struct Node *next;};
int main( ) {
struct Node *boxE, *head, *boxN; int index=0;
boxE=head= (struct Node *) malloc(sizeof(struct Node));
for (index =1; index < = 3; index++){
boxN = (struct Node *) malloc (sizeof(struct Node));
boxE -> next = boxN;
boxN -> value = index;
boxE = boxN; }
for (index=0; index < = 3; index++) {
printf("Value at index %d is %d\n", index, head -> value);
printf("Value at index %d is %d\n", index+1, head -> value); } } 
Which one of the following statements below is correct about the program?
 A Upon execution, the program creates a linked-list of five nodes B Upon execution, the program goes into an infinite loop C It has a missing returnreturn which will be reported as an error by the compiler D It dereferences an uninitialized pointer that may result in a run-time error
GATE CSE 2021 SET-2      Link List
Question 1 Explanation:
 Question 2
Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.

The value of |A-B| is _____________
 A 3 B 4 C 1 D 2
GATE CSE 2021 SET-2      Binary Tree
Question 2 Explanation:
 Question 3
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
 A $\Theta (\sqrt{n})$ B $\Theta ( \log _2 (n))$ C $\Theta ( n^2)$ D $\Theta ( n)$
GATE CSE 2021 SET-2      Array
Question 3 Explanation:
 Question 4
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?
 A $\Theta (1)$ B $\Theta (\log n)$ C $\Theta ( n)$ D $\Theta (n \log n)$
GATE CSE 2021 SET-2      Heap Tree
Question 4 Explanation:
 Question 5
Consider a dynamic hashing approach for 4-bit integer keys:

1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table. entry is organized as a binary tree that grows on demand.
5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees based on the 4th least significant bit.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
 A 5,9,4,13,10,7 B 9,5,10,6,7,1 C 10,9,6,7,5,13 D 9,5,13,6,10,14
GATE CSE 2021 SET-1      Hashing
Question 5 Explanation:
 Question 6
Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s=pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q=dequeue();

The value of s+q is ___________.
 A 94 B 83 C 79 D 86
GATE CSE 2021 SET-1      Stack
Question 6 Explanation:
 Question 7
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?
 A $\Theta(n\log n)$ B $\Theta(n)$ C $\Theta(\log n)$ D $\Theta(1)$
GATE CSE 2021 SET-1      Binary Search Tree
Question 7 Explanation:
 Question 8
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?
 A $t \gt 2n-2$ B $t \gt 3\lceil \frac{n}{2}\rceil \text{ and } t\leq 2n-2$ C $t \gt n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$ D $t \gt \lceil \log_2(n)\rceil \text{ and } t\leq n$
GATE CSE 2021 SET-1      Array
Question 8 Explanation:
 Question 9
A stack is implemented with an array of ${ }^{\prime} A[0 \ldots N-1]^{\prime}$ and a variable $\text { 'pos'. }$ The push and pop operations are defined by the following code.
 push (x)
A[pos] <- x
pos <- pos -1
end push
pop()
pos <- pos+1
return A[pos]
end pop

Which of the following will initialize an empty stack with capacity N for the above implementation?
 A $\text { pos } \leftarrow-1$ B $\text { pos } \leftarrow 0$ C $\text { pos } \leftarrow 1$ D $\text { pos } \leftarrow N-1$
ISRO CSE 2020      Stack
Question 9 Explanation:
 Question 10
Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complete K-ary tree of depth N ?
 A 1/N B N-1/N C 1/K D K-1/K
ISRO CSE 2020      n-ary Tree
Question 10 Explanation:

There are 10 questions to complete.