2023 2024 MBA - GATE questions on data structures

For GATE exam preparation in computer science, a data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently.

Data structures can implement one or more particular abstract data types (ADT), which specify the operations that can be performed on a data structure and the computational complexity of those operations.

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

Some GATE questions on data structures:

Que 1. For 8 keys and 6 slots in a hashing table with uniform hashing and chaining, what is the expected number of items that hash to a particular location.
(A) 2.33
(B) 0.75
(C) 1.33
(D) 2

Que 2. For m keys and n slots in a hashing table, which of the following is the expected number of empty location.
(A) n((m-1)/m)^n
(B) m((m-1)/m)^n
(C) n((n-1)/m)^n
(D) n((n-1)/n)^m

Que 3. What is the number of binary search trees with 20 nodes with elements 1, 2, 3 20 such that the root of tree is 12 and the root of left subtree is 7?
(A) 2634240
(B) 1243561
(C) 350016
(D) 2642640

Que 4. For a graph with E edges and V vertices what is the time complexity of Dijkstra algorithm using array as data structure for storing non-finalized vertices. Graph is undirected and represented as adjacency list?
(A) O(VE)
(B) O(ElogV)
(C) O(V^2 )
(D) O(E^2log V)

Que 5. What is the output of the following program?

int a = 5;
main()

extern int a;
extern int a;
printf(a);

(A) Compile time error.
(B) Run time error.
(C) 0
(D) 5

Que 1. The function shiftNode() which takes as input two linked lists- destination and source. It deletes front node from source and places it onto the front of destination. Choose the set of statements which replace X, Y, Z in given function.

void shiftNode(struct node** destRoot,
struct node** srcRoot)

// the front of source node
struct node* newNode = *srcRoot;
assert(newNode != NULL);
X;
Y;
Z;

(A)

X: *srcRoot = newNode->next
Y: newNode->next = *destRoot->next
Z: *destRoot->next = newNode
(B)

X: *srcRoot->next = newNode->next
Y: newNode->next = *destRoot
Z: *destRoot = newNode->next
(C)

X: *srcRoot = newNode->next
Y: newNode->next = *destRoot
Z: *destRoot = srcRoot->next
(D)

X: *srcRoot = newNode->next
Y: newNode->next = *destRoot
Z: *destRoot = newNode

Que 2. A vertex v is said to be over when the recursion DFS(v) finishes. What is the order of the vertices being over for the given graph? Consider the DFS to begin at vertex a and in case of multiple possible paths, travel in an alphabetical manner.
1
(A) e f i h g c d b a
(B) a b d c e g f h i
(C) a b c d e g i f h
(D) e f i h d g c b a

Que 3. You are given two singly linked lists with heads head_ref1 and head_ref2 respectively. What does the following function do?

int myFunc(Node* head_ref1, Node* head_ref2)
Node *pointer1 = head_ref1, *pointer2 = head_ref2;
while (pointer1 != pointer2)
pointer1 = pointer1?pointer1->next:head_ref2;
pointer2 = pointer2?pointer2->next:head_ref1;

return pointer1?pointer1->data:-1;

(A) Merging the two linked lists
(B) Finding the merging point of the two linked lists
(C) Swapping nodes of the two linked lists
(D) The program runs in an infinite loop

Que 4. The function copyBSTNodes() creates a copy of each node of a Binary Search Tree and inserts the copied node as the left child of the original node. The resultant tree remains a BST. Choose the set of statements which replace X and Y in given function.

void copyBSTNodes (struct node* root)
struct node* prevLeft;
if (root==NULL) return;

copyBSTNodes (root->left);
copyBSTNodes (root->right);

X;
root->left = newNode(root->data);
Y;

(A)

X: prevLeft->left = root->left
Y: root->left->left = prevLeft->left
(B)

X: prevLeft = root->left
Y: root->left->left = prevLeft
(C)

X: prevLeft = root
Y: root->left = prevLeft
(d)

X: prevLeft = root->left
Y: root->left->left = prevLeft->left

Que 5. The function eraseDup() takes as input a linked list sorted in ascending order. It removes duplicate nodes from the list by traversing it just once. Choose the set of statements which replace X, Y, Z in given function.

void eraseDup(struct node* root)
struct node* current = root;
if (X)
return;

while (current->next!=NULL)
if (Y)
struct node* nextOfNext = current->next->next;
free(current->next);
current->next = nextOfNext;

else
Z
}
}
}
(A)

X: current == NULL
Y: current = current->next
Z: current->data = current->next->data;
(B)

X: current == NULL
Y: current->data == current->next->data
Z: current = current->next;
(C)

X: current->next == NULL
Y: current->next->data == current->next->next->data
Z: current = current->next;
(D)

X: current->next == NULL
Y: current->data = current->next->data
Z: current = current->next;