subject – RBR

Data-Structures

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

A	5.54
B	1.34
C	4.25
D	3.82

Data-Structures GATE 2019

Question 1 Explanation:

There can be 8 paths between any 2 uniformly & independently chosen leaf nodes.
A node can be chosen twice and the path from that node to itself will be zero.
∴ Path 1 = 0
Similarly,
Path 2 = 2
Path 3 = 4
Path 4 = 4
Path 5 = 6
Path 6 = 6
Path 7 = 6
Path 8 = 6
∴ Expected value = Σ Path length × Probability of selecting path
= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8
= 1/4 + 1/1 + 3/1 + 0
= 4 + 1/4
= 17/4
= 4.25

Question 2

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?

A	20, 19, 18, 16, 15, 12, 11, 10
B	11, 12, 10, 16, 19, 18, 20, 15
C	10, 11, 12, 15, 16, 18, 19, 20
D	19, 16, 18, 20, 11, 12, 10, 15

Data-Structures Binary-Trees GATE 2020

Question 2 Explanation:

Question 3

Consider a double hashing scheme in which the primary hash function is h₁(k)=k mod 23, and the secondary hash function is h₂(k)=1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is _______.

Data-Structures Hashing GATE 2020

Question 3 Explanation:

• Probe sequence is the list of locations which a method for open addressing produces as alternatives in case of a collision.
• K=90
• h₁(k)= k mod 23 = 90 mod 23 =21
• In case of collision , we need to use secondary hash function
• h₂(k)=1+(k mod19)=1+90mod19=1+14 =15
• Now (21+15) mod 23 =36 mod 23 =13
• So the address is 13

Question 4

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

A
B
C
D
E	option A and option B

Data-Structures Linked-List GATE 2020

Question 4 Explanation:

Method-1:
When we are inserting an element in to empty linked list and to perform sorted order list of every element will take O(n^2)
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case.
After inserting elements into an empty linked list we have to perform sorting operation.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only.
Let head be the first node of the linked list to be sorted and head Reference be the pointer to head. The head in MergeSort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^2) and heap sort will not be suitable to apply.
Method-2:
When we are inserting an element into an empty linked list and to perform a sorted list after inserting all elements will take O(nlogn) time.
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case. After inserting elements into an empty linked list we have to perform sorting operations.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only. Let head be the first node of the linked list to be sorted and head Reference be the pointer to head. The head in Merge Sort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^2) and heap sort will not be suitable to apply.
Note: They are given “needs to be maintained in sorted order” but not given clear conditions to sort an elements.

Question 5

Consider the following C program.
#include
int main () {
int a [4] [5] = {{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}};
printf (“%d\n”, *(* (a+**a+2) +3));
return (0);
}
The output of the program is _______.

Data-Structures Arrays GATE 2020

Question 5 Explanation:

Check out the step by step program and its output in the comment:
#include
int main()
{
int a[4][5] = { {1,2,3,4,5},
             {6,7,8,9,10},
             {11,12,13,14,15},
             {16,17,18,19,20}
           };
printf("%d\n",a); //880 (consider base address = 880)
printf("%d\n",*a); //880
printf("%d\n",**a); //1
printf("%d\n",**a+2); //3
printf("%d\n",a+**a+2); //940
printf("%d\n",*(a+**a+2));//940
printf("%d\n",*(a+**a+2)+3);//952
printf("%d\n",*(*(a+**a+2)+3));//19
return 0;
}

Question 6

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?

A
B
C
D

Data-Structures Binary-Trees GATE 2020

Question 6 Explanation:

AVL Tree all operations(insert, delete and search) will take O(logn) time.
In question they asked about n² elements.
So, In worst case it will take o(n² logn) time.

Question 7

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.

A
B
C
D

Data-Structures Binary-Trees GATE 2020

Question 7 Explanation:

The idea is to traverse the given binary search tree starting from root. For every node being visited, check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If the current node is smaller than the low value of range, then recur for right child, else recur for left child.
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is logn, hence O(logn+k)

Question 8

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

511

Data-Structures Heap-Tree GATE 2020

Question 8 Explanation:

The binary heap contains 1023 elements.
When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2. So, we have to subtract from the total elements
=512-1
=511

Question 9

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.

A	1
B	2
C	3
D	4

Data-Structures Trees Gate 2018

Question 9 Explanation:

Post – 8 9 6 7 4 5 2 3 1
In – 8 6 9 4 7 2 5 1 3
Post: 8 9 6 7 4 5 2 3 1→(root)
In: 8 6 9 4 7 2 5→(left subtree) 13→(right subtree)

Question 10

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?

A	θ(1), θ(1)
B	θ(1), θ(n)
C	θ(n), θ(1)
D	θ(n), θ(n)

Data-Structures Queues-and-Linked-Lists Gate 2018

Question 10 Explanation:

For insertion of node at the beginning of linked list only need manipulation of pointers so θ(1) time.
But if we have pointer to the tail of the list in order to delete it, we need the address of the 2^nd last node which can be obtained by traversing the list which takes O(n) time.

Question 11

Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements.

Which of the statements above must necessarily be true?

A	I only
B	II only
C	Both I and II
D	Neither I nor II

Data-Structures Graphs Gate 2018

Question 11 Explanation:

I. Undirected graph do not have cross edges in DFS. But can have cross edges in directed graph. Hence True.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.
There is an edge between B and C too. So here |i - j| = |1 - 1| = 0. Hence, False.

Question 12

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.

A	80
B	81
C	82
D	83

Data-Structures Heap-Tree Gate 2018

Question 12 Explanation:

--> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
--> After sorting, pick the minimum element and make it the root of the min heap.
--> So, there is only 1 way to make the root of the min heap.
--> Now we are left with 6 elements.
--> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80

Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .

Question 13

Consider the C code fragment given below.

typedef struct node   {
    int data;
    node* next;
}   node;

void join(node* m, node* n)   {
    node*  p = n;
    while(p→next  !=NULL)    {
       p = p→next; 
    }
    p→next=m;
}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

A	append list m to the end of list n for all inputs.
B	either cause a null pointer dereference or append list m to the end of list n.
C	cause a null pointer dereference for all inputs.
D	append list n to the end of list m for all inputs.

Data-Structures Linked-List Gate 2017 set-01

Question 13 Explanation:

As specified in the question m & n are valid lists, but there is no specific condition/ statement tells that lists are empty or not.
So have to consider both the cases.
⇾ 1. Lists are not null, invocation of JOIN will append list m to the end of list n.
m = 1, 2, 3
n = 4, 5, 6
After join, it becomes 4, 5, 6, 1, 2, 3, NULL.
⇾ 2. If lists are null, if the list n is empty, and itself NULL, then joining & referencing would obviously create a null pointer issue.
Hence, it may either cause a NULL pointer dereference or appends the list m to the end of list n.

Question 14

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.

A	18
B	19
C	20
D	21

Data-Structures Trees Gate 2017 set-01

Question 14 Explanation:

Sum of degrees of all vertices is double the number of edges.
A tree, with 10 vertices, consists n - 1, i.e. 10 - 1 = 9 edges.
Sum of degrees of all vertices = 2(#edges)
= 2(9)
= 18

Question 15

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?

A	I only
B	II only
C	Both I and II
D	Neither I nor II

Data-Structures Circular-Queue-and-Linked-List GATE 2017(set-02)

Question 15 Explanation:

1. Next pointer of front node points to the rear node.
2. Next pointer of rear points to the front node.

So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.

Question 16

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

A	MNOPQR
B	NQMPOR
C	QMNROP
D	POQNMR

Data-Structures BFS GATE 2017(set-02)

Question 16 Explanation:

The possible order of visiting the nodes in Breadth First Search Algorithm, implementing using Queue Data Structure is

(Do it by option Elimination)
(a) MNOPQR – MNO is not the proper order R must come in between.
(b) NQMPOR – QMP is not the order O is the child of N.
(C) QMNROP – M is not the child of Q, so QMN is false.
(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).

Question 17

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

A	2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
B	2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
C	7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
D	7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

Data-Structures Binary-Trees GATE 2017(set-02)

Question 17 Explanation:

From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree.

From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.
From <17, 19, 20>, 19 as root.

Hence, 2,7,6,10,9,8 |,15,17,20,19,16 |12 is the post-order traversal.

Question 18

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efﬁciently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

A	Both operations can be performed in O(1) time
B	At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
C	The worst case time complexity for both operations will be Ω(n)
D	Worst case time complexity for both operations will be Ω(logn)

Data-Structures Queues 2016 set-01

Question 18 Explanation:

Since it is mentioned in the question that both of the operations are performed efficiently.
Hence even the worst case time complexity will be O(1) by the use of the Circular queue there won't be any need of shifting in the array.

Question 19

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is __________.

A	7
B	9
C	8
D	6

Data-Structures Topological ordering 2016 set-01

Question 19 Explanation:

Different topological orderings of the vertices of the graph are:

It is observed that (a) is the starting vertex & (f) is the final one.
Also observed that c must come after b & e must come after d.
So,

Hence, there are 6 different topological orderings can be derived.

Question 20

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

A	P only
B	Q only
C	Neither P nor Q
D	Both P and Q

Data-Structures Graphs 2016 set-01

Question 20 Explanation:

Given undirected weighted graph with distinct positive edges.
Every edge weight is increased by the same value say,

P: Minimum Spanning Tree will not change ABC in both the cases.
Q: Shortest path will change because in 1st figure the path from A to C calculated as ABC but in fig.2, it is AC (Direct path).

Question 21

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-ﬁx the heap efﬁciently after the removal of the element?

A	O(1)
B	O(d) but not O(1)
C	O(2^d) but not O(d)
D	O(d 2^d) but not O(2^d)

Data-Structures Binary-Heap 2016 set-01

Question 21 Explanation:

→ If heap has n elements generally it takes O(n) to delete any arbitrary element.
→ Because we first need to find that element, O(n) time
Delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].
**but here, we don't need to find that element, because in delete(i), i is index of that element.
Note: Delete time = O(height) = O(d)

Question 22

Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry W_ij in the matrix W.

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is _________.

A	12
B	13
C	14
D	15

Data-Structures Graphs 2016 set-01

Question 22 Explanation:

Let vertices be A, B, C and D.
x directly connects C to D.
The shortest path (excluding x) from C to D is of weight 12 (C-B-A-D).

Question 23

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

The maximum possible number of iterations of the while loop in the algorithm is _________.

A	256
B	257
C	258
D	259

Data-Structures Queues-and-Stacks 2016 set-01

Question 23 Explanation:

The maximum possible number of iterations of the while loop in this algorithm is:
Try to solve it for 3 numbers [1. 2, 3].
Step 1: Initially Queue contains 3 elements so after 5 while loop iterations queue contains 3, 2 and stack contains 1.
Step 2: Now after 3 more while loop iterations, Queue contains 3 and stack contains 1, 2 (TOS = 2).
Step 3: After 1 more while loop iteration, push 3 onto the stack so queue is empty and stack contains 1, 2, 3 {top = 3}.
So, total number of iterations will be 5 + 3 + 1 = 9
i.e., for 3 it is 9 iterations (3*3)
for 4 it is 16 iterations (4*4)
Given: 16 numbers, so 16 * 16 = 256

Question 24

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.

A	31
B	32
C	33
D	34

Data-Structures BFS GATE 2016 set-2

Question 24 Explanation:

Given is a vertex t at a distance of 4 from the root.

For distance 1, max possible value is (3).
Similarly, for distance 2, max value is (7).
So, maximum number of nodes = 2^(h+1) - 1
For distance 4, 2⁽⁴⁺¹⁾ - 1 ⇒ 2⁵ - 1 ⇒ 32 - 1 = 31
31 is the last node.

So for distance 4, the maximum possible node will be 31 & minimum will be 16.

Question 25

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(N) delete,O(logN) insert, O(logN) ﬁnd, and Θ(N) decrease-key. What is the time complexity of all these operations put together?

A	O(log² N)
B	O(N)
C	O(N²)
D	Θ(N² logN)

Data-Structures Linked-List GATE 2016 set-2

Question 25 Explanation:

In Doubly linked list (sorted)
→ Delete needs O(1) time
→ Insert takes O(N) time
→ Find takes O(N) time
→ Decrease by takes O(N) time
Now number of each operation performed is given, so finally total complexity,
→ Delete = O(1) × O(N) = O(N)
→ Find = O(N) × O(log N) = O(N log N)
→ Insert = O(N) × O(log N) = O(N log N)
→ Decrease key = O(N) × O(N) = O(N²)
So, overall time complexity is, O(N²).

Question 26

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

A	8
B	9
C	10
D	11

Data-Structures Heap-Tree GATE 2016 set-2

Question 26 Explanation:

This is not possible because it violates a property of complete binary tree.
We have total [0, 1023] elements. It means that

∴ 2⁰ + 2¹ + 2² + ⋯ + 2^k = 1024
Add if 1(2^(k+1)-1)/(2-1) [using formula for sum of k terms k+1 in G.P]
= 2^(k+1) - 1 = 1024 - 1 = 1023
∴ The level ‘9’ at the depth of 8.
Actually we have 1023 elements, we can achieve a complete binary min heap of depth 9, which would cover all 1023 elements, but the max depth of node 9 can be only be 8.

Question 27

Consider the following New-order strategy for traversing a binary tree:

Visit the root;
Visit the right subtree using New-order;
Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

A	+ - 1 6 7 * 2 ˆ 5 - 3 4 *
B	- + 1 * 6 7 ˆ 2 - 5 * 3 4
C	- + 1 * 7 6 ˆ 2 - 5 * 4 3
D	1 7 6 * + 2 5 4 3 * - ˆ -

Data-Structures Binary-Trees GATE 2016 set-2

Question 27 Explanation:

New Order strategy: Root, Right, Left.
Given Reverse Polish Notation as:
3 4 * 5 - 2 ^ 6 7 * 1 + -
We know Reverse Polish Notation takes Left, Right, Root.

So the expression tree looks like

From the tree, we can write the New Order traversal as: Root, Right, Left.
- + 1 * 7 6 ^ 2 - 5 * 4 3

Question 28

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _________.

Note: The height of a tree with a single node is 0.

A	64
B	65
C	66
D	67

Data-Structures Trees GATE 2016 set-2

Question 28 Explanation:

To get the tree of height 6, every level should contain only 1 node.
So to get such tree at each level we should have either maximum or minimum element from remaining numbers till that level. So no. of binary search tree possible is,
1^st level - 2 (maximum or minimum)
⇓
2^nd level - 2
⇓
3^rd level - 2
⇓
4^th level - 2
⇓
5^th level - 2
⇓
6^th level - 2
⇓
7^th level - 2
= 2 × 2 × 2 × 2 × 2 × 2 × 1
= 2⁶
= 64

Question 29

In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efﬁcient algorithm to set the twin pointer in each entry in each adjacency list?

A	Θ(n²)
B	Θ(n+m)
C	Θ(m²)
D	Θ(n⁴)

Data-Structures Graphs GATE 2016 set-2

Question 29 Explanation:

Applying BFS on Undirected graph give you twin pointer.
Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.

Question 30

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

A	63 and 6, respectively
B	64 and 5, respectively
C	32 and 6, respectively
D	31 and 5, respectively

Data-Structures Trees GATE 2015 (Set-01)

Question 30 Explanation:

Maximum number of nodes in a binary tree of height h is,
2^h+1 - 1 = 2⁵⁺¹ - 1 = 63
Minimum number of nodes in a binary tree of height h is
h + 1 = 5 + 1 = 6

Question 31

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. N

now consider that a value 35 is inserted into this heap. After insertion, the new heap is

A	40, 30, 20, 10, 15, 16, 17, 8, 4, 35
B	40, 35, 20, 10, 30, 16, 17, 8, 4, 15
C	40, 30, 20, 10, 35, 16, 17, 8, 4, 15
D	40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Data-Structures Heap GATE 2015 (Set-01)

Question 31 Explanation:

Given max. heap is

Heapification:

Array representation of above max-heap is (BFS)
40,35,20,10,30,16,17,8,4,15

Question 32

A binary tree T has 20 leaves. The number of nodes in T having two children is _________.

A	19
B	20
C	21
D	22

Data-Structures Binary-Trees GATE 2015 -(Set-2)

Question 32 Explanation:

Let the number of vertices of a binary tree with „p‟ leaves be n then the tree has
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n- p-1' (i.e., interval) vertices of degree 3
(iv) n- 1 edges
∴ By Handshaking theorem,
p×1+1×2+(n-p-1)×3=2(n-1)
⇒n=2p-1
=39 as p=20
∴ n-p=19 vertices have exactly two children

Question 33

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

A	Ω(logn)
B	Ω(n)
C	Ω(nlog n)
D	Ω(n²)

Data-Structures Heap-Tree GATE 2015 -(Set-2)

Question 33 Explanation:

Since left and right subtree is already a heap. So we can apply Heapify (node) which take log n time.

Question 34

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

A	h(i) = i² mod 10
B	h(i) = i³ mod 10
C	h(i) = (11 *i²) mod 10
D	h(i) = (12 * i) mod 10

Data-Structures Hashing GATE 2015 -(Set-2)

Question 34 Explanation:

If we take first 10 elements, number of collisions taken by the hash function given by option (B) is less when compared to others.

Question 35

Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let α be the value of RTT in milliseconds. (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size the window scale option. Then the values of α and β are

A	63 milliseconds, 65535×2¹⁴
B	63 milliseconds, 65535×2¹⁶
C	500 milliseconds, 65535×2¹⁴
D	500 milliseconds, 65535×2¹⁶

Data-Structures TCP GATE 2015 -(Set-2)

Question 35 Explanation:

TCP header sequence number field consist 16 bits. The maximum number of sequence numbers possible = 2^16 = 65,535.
The wrap around time for given link = 1048560 * α. The TCP window scale option is an option to increase the receive window size. TCP allows scaling of windows when wrap around time > 65,535.
==> 1048560 * α. > 65,535*8 bits
==> α = 0.5 sec = 500 mss
Scaling is done by specifying a one byte shift count in the header options field. The true receiver window size is left shifted by the value in shift count. A maximum value of 14 may be used for the shift count value. Therefore maximum window size with scaling option is 65535 × 2^14
.

Question 36

A younf tableau is a 2D array of integers iniceasing from left to right and from top to bottom. Any unfilled entries are marked with

A	4
B	5
C	6
D	7

Data-Structures Arrays GATE 2015 -(Set-2)

Question 36 Explanation:

Question 37

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.

A	80
B	70
C	60
D	50

Data-Structures Hashing GATE 2015(Set-03)

Question 37 Explanation:

Load factor(α) = no. of elements/no. of slots = 2000/25 = 80

Question 38

Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is

A	4
B	5
C	2
D	3

Data-Structures Heap-Tree GATE 2015(Set-03)

Question 38 Explanation:

Let's first draw heap from the given array,

→ Swap 100 & 15

→ Swap 100 & 50

→ Swap 89 & 100

∴ Total 3 interchanges are needed.

Question 39

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

A	65
B	67
C	69
D	83

Data-Structures Binary-Search-Tree GATE 2015(Set-03)

Question 39 Explanation:

Question 40

The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is

A	284
B	213
C	142
D	71

Data-Structures Postfix-Expression GATE 2015(Set-03)

Question 40 Explanation:

→ '10' is pushed in the stack

→ '5' is pushed in the stack

→ '+' comes so addition will be done by popping the top two elements in the stackand the result is pushed back into the stack, i.e., 10+5 = 15

→ 60 pushed in the stack

→ 6 pushed in the stack

→ '/' comes. So, 60/6 = 10

→ '*' comes. So, 15 * 10 = 150

→ '8' comes, push in the stack

→ '-' comes. So, 150-8 = 142

So the final result is 142.

Question 41

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____ .

A	199
B	198
C	197
D	196

Data-Structures Binary-Trees GATE 2015(Set-03)

Question 41 Explanation:

A binary tree T with n leaf nodes have exactly (n - 1) nodes that have exactly two children.

Question 42

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

A	θ(n)
B	θ(n+m)
C	θ(n² )
D	θ(m² )

Data-Structures Graphs GATE 2014(Set-01)

Question 42 Explanation:

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V²).

Question 43

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n^alog^bn). Then the value of a+10b is ________.

A	1
B	2
C	3
D	4

Data-Structures Time-Complexity GATE 2014(Set-01)

Question 43 Explanation:

Binary tree traversal takes O(n) time for reaching 4th level from the leaf node. Every node has to check their subtree having exactly 4 nodes. Checking time can be done in maximum constant time for each node. Nodes in the level is always less than n and it's complexity is O(n). Finally a value becomes 1 and b value becomes 0.
Substitute into a and b values in equation.
⇒ a+10b
⇒ a*1 + 10*0
⇒ 1+0
⇒ 1

Question 44

Consider the directed graph given below.

Which one of the following is TRUE?

A	The graph does not have any topological ordering.
B	Both PQRS and SRQP are topological.
C	Both PSRQ and SPRQ are topological orderings.
D	PSRQ is the only topological ordering.

Data-Structures Graphs GATE 2014(Set-01)

Question 44 Explanation:

There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.

Question 45

Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t₁ and t₂ be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

A	t₁=5
B	t₁2
C	t₁>t₂
D	t₁=t₂

Data-Structures Quick-Sort GATE 2014(Set-01)

Question 45 Explanation:

[1, 2, 3, 4, 5] [4, 1, 5, 3, 2]
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2^nd array through not in sorted manner.
Hence t₁> t₂.

Question 46

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

A	3, 0, and 1
B	3, 3, and 3
C	4, 0, and 1
D	3, 0, and 2

Data-Structures Hashing GATE 2014(Set-01)

Question 46 Explanation:

Hash table has 9 slots.
h(k) = k mod 9
Collisions are resolved using chaining.
Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5
28%9 – 1
19%9 – 1
15%9 – 6
20%9 – 2
33%9 – 6
12%9 – 3
17%9 – 8
10%9 – 1
Maximum chain length is 3
Minimum chain length is 0
Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1

Question 47

Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the

int MyX(int *E, unsigned int size)
{
    int Y = 0;
    int Z;
    int i, j, k;
    for(i = 0; i < size; i++)
        Y = Y + E[i];
    for(i = 0; i < size; i++)
        for(j = i; j < size; j++)
        {
            Z = 0;
            for(k = i; k <= j; k++)
                Z = Z + E[k];
            if (Z > Y)
                Y = Z;
        }
    return Y;
}

A	maximum possible sum of elements in any sub-array of array E.
B	maximum element in any sub-array of array E.
C	sum of the maximum elements in all possible sub-arrays of array E.
D	the sum of all the elements in the array E.

Data-Structures General GATE 2014(Set-01)

Question 47 Explanation:

Y=0
for (i=0; i Y=Y+E[i] // E is an array, this statement calculates the sum of elements of the array E and stores it in Y.
for (i=0; i for(j=i; j {
Z=0;
for(k=i; k<=j; k++)
Z=Z+E[k];
// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].
Store the current sum in Z.
If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.

Question 48

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

A	Half of the product of the 3 consecutive integers.
B	One-third of the product of the 3 consecutive integers.
C	One-sixth of the product of the 3 consecutive integers.
D	None of the above.

Data-Structures Time-Complexity GATE 2014(Set-01)

Question 48 Explanation:

D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3;

Also you can try for smaller ‘n’.

Question 49

Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______________________.

A	4
B	5
C	6
D	7

Data-Structures Pipelining GATE 2014(Set-01)

Question 49 Explanation:

For 6 stages, non- pipelining takes 6 cycles.
There were 2 stall cycles for pipelining for 25% of the instructions.
So pipeline time =(1+(25/100)*2)=3/2=1.5
Speed up =Non-pipeline time / Pipeline time=6/1.5=4

Question 50

An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?

A	n⁄N
B	1⁄N
C	1⁄A
D	k⁄n

Data-Structures Cache GATE 2014(Set-01)

Question 50 Explanation:

Consider the scenario, you have k-way set associative cache, let us say a block b0 comes to set-0 and then there are k-1 unique blocks to the same set. Now the set-0 is full then one more block came to set-0 and the block b0 is replaced using LRU, if b0 comes again then it will cause a miss. But it is given that the set associativity A>=k, means the no. of blocks in a set is k or more so assume we have (k+1)-way set associativity, applying the above logic b0 comes first and then k-1 other unique accesses come to the same set-0 then there is still place for one more block in set-0 and if b0 comes again now then it will not cause a miss. As the associativity increases further there will not be any more misses other than the unique blocks we have a best case scenario. So out of N accesses only the unique blocks n can be missed and the miss ratio is n/N.
As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.

Question 51

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:

A	10, 8, 7, 3, 2, 1, 5
B	10, 8, 7, 2, 3, 1, 5
C	10, 8, 7, 1, 2, 3, 5
D	10, 8, 7, 5, 3, 2, 1

Data-Structures Heap Gate 2014 Set -02

Question 51 Explanation:

Max-Heap has 5 elements:

The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.

Question 52

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

A	the shortest path between every pair of vertices.
B	the shortest path from W to every vertex in the graph.
C	the shortest paths from W to only those nodes that are leaves of T.
D	the longest path in the graph.

Data-Structures Graphs Gate 2014 Set -02

Question 52 Explanation:

One of the application of BFS algorithm is to find the shortest path between nodes u and v.
But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.

Question 53

The worst case running time to search for an element in a balanced binary search tree with n2ⁿ elements is

A	Θ (n log n)
B	Θ (n2ⁿ)
C	Θ (n)
D	Θ (log n)

Data-Structures Binary-Search-Tree Gate 2012

Question 53 Explanation:

→ Worst case running time to search for an element in a balanced binary search tree of ‘n’ elements is (log n).
→ No of elements = n.2ⁿ then search time = (log n.2ⁿ)
= (log n + log 2ⁿ)
= (log n + n log 2)
= O(n)

Question 54

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

A	T(n) = 2T(n - 2) + 2
B	T(n) = 2T(n - 1) + n
C	T(n) = 2T(n/2) + 1
D	T(n) = 2T(n - 1) + 1

Data-Structures Recursion Gate 2012

Question 54 Explanation:

The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2² T(n – 2) + 3
⋮
= 2^k T( n – k) + (2^k – 1)
n – k = 1
= 2^n-1 T(1) + (2^n-1 – 1)
= 2^n-1 + 2^n-1 – 1
= 2ⁿ – 1
≌ O(2ⁿ)

Question 55

Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

A	full: (REAR+1)mod n == FRONT empty: REAR == FRONT
B	full: (REAR+1)mod n == FRONT empty: (FRONT+1) mod n == REAR
C	full: REAR == FRONT empty: (REAR+1) mod n == FRONT
D	full: (FRONT+1)mod n == REAR empty: REAR == FRONT

Data-Structures Queues Gate 2012

Question 55 Explanation:

To circulate within the queue we have to write mod n for (Rear + 1).
We insert elements using Rear & delete through Front.

Question 56

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are

A	B1: (1+height(n→right)) B2: (1+max(h1,h2))
B	B1: (height(n→right)) B2: (1+max(h1,h2))
C	B1: height(n→right) B2: max(h1,h2)
D	B1: (1+ height(n→right)) B2: max(h1,h2)

Data-Structures Binary-Trees Gate 2012

Question 56 Explanation:

Now, we analyze the code,
The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.
In such case, height of n will be the height of the right subtree +1.
The box B2 gets executed when both left & right subtrees of n are not NULL.
In such case, height of n will be max of heights of left & right subtrees of n+1.

Question 57

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

A
B
C
D

Data-Structures Binary-Heap Gate 2011

Question 57 Explanation:

Heap is a complete binary tree
Option A: It violates the property of complete binary tree.
Option C: 8 is greater than 5. The root value is always greater than his children. So, the above tree is violating the property of max heap
Option D: 10 is greater than 8. The root value is always greater than his children. So, the above tree is violating the property of max heap

Question 58

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

A	0
B	1
C	n!
D

Data-Structures Binary-Trees Gate 2011

Question 58 Explanation:

Corresponding to each set only 1 binary search tree can be formed because in-order is fixed. only 1 tree possible. If Binary trees would be asked n! possible corresponding to each distinct tree set. Here tree structure is fixed and have only 1 possibility for BST as elements are distinct.

Question 59

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

A	0
B	1
C	(n-1)/2
D	n-1

Data-Structures Binary-Trees 2010

Question 59 Explanation:

Given a Binary Tree with n nodes.
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant.

― This is even number of descendants (2), because A is also considered as a descendant.

― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.

Question 60

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node 
{
  int value;
  struct node *next;
}Node;
 
Node *move_to_front(Node *head) 
{
  Node *p, *q;
  if ((head == NULL: || (head->next == NULL)) 
    return head;
  q = NULL; p = head;
  while (p-> next !=NULL) 
  {
    q = p;
    p = p->next;
  }
  _______________________________
  return head;
}

A	q = NULL; p→next = head; head = p;
B	q→next = NULL; head = p; p→next = head;
C	head = p; p→next = q; q→next = NULL;
D	q→next = NULL; p→next = head; head = p;

Data-Structures Linked-List 2010

Question 60 Explanation:

C function takes a simple linked list as input argument.
The function modifies the list by moving the last element to the front of the list.
Let the list be 1 → 2 → 3 → 4 & the modified list must be 4 → 1 → 2 → 3.
Algorithm:
Traverse the list till last node. Use two pointers. One to store the address of last node & other for the address of second last node.
After completion of loop. Do these.
(i) Make second last as last
(ii) Set next of last as head
(iii) Make last as head

while (p → !=NULL)
{
q = p;
p = p → next;
}
― p is travelling till the end of list and assigning q to whatever p had visited & p takes next new node, so travels through the entire list.
Now the list looks like

According to the Algorithm new lines must be
q → next = NULL; p → next = head; head = p

Question 61

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

A	7
B	8
C	9
D	10

Data-Structures Graphs 2010

Question 61 Explanation:

The MST will be 1---3---4---0 => cost = 4+2+4 = 10

Question 62

A	46, 42, 34, 52, 23, 33
B	34, 42, 23, 52, 33, 46
C	46, 34, 42, 23, 52, 33
D	42, 46, 33, 23, 34, 52

Data-Structures Hashing 2010

Question 62 Explanation:

Hash Table consists of 10 slots, uses Open Addressing with hash function and linear probing.
After inserting 6 values, the table looks like

The possible order in which the keys are inserted are:
34, 42, 23, 46 are at their respective slots 4, 2, 3, 6.
52, 33 are at different positions.
― 52 has come after 42, 23, 34 because, it has the collision with 42, because of linear probing, it should have occupy the next empty slot. So 52 is after 42, 23, 34.
― 33 is after 46, because it has the clash with 23. So it got placed in next empty slot 7, which means 2, 3, 4, 5, 6 are filled.
42, 23, 34 may occur in any order but before 52 & 46 may come anywhere but before 33.

So option (C)

Question 63

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

A	10
B	20
C	30
D	40

Data-Structures Hashing 2010

Question 63 Explanation:

Total 6 insertions
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉can be sequenced in 3! ways.
Hence, 5×3! = 30 ways

Question 64

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

A
B
C
D

Data-Structures Hashing 2009

Question 64 Explanation:

Given keys: 12, 18, 13, 2, 3, 23, 5 & 15
They are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k)=k mod 10 & linear probing is used.

12 % 10 = 2
18 % 10 = 8
13 % 10 = 3
2 % 10 = 2 (Index 4 is empty)
3 % 10 = 3 (Index 5 is empty)
23 % 10 = 3 (Index 6 is empty)
5 % 10 = 5 (Index 7 is empty)
15 % 10 = 5 (Index 9 is empty)
Hence Option C is correct.
A & B doesn’t include all the keys & option D is similar to chaining. So, will go with C.

Question 65

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

A	2
B	3
C	4
D	5

Data-Structures AVL-Trees 2009

Question 65 Explanation:

The maximum height of any AVL tree with 7 nodes is, [where root is considered as height 0]
2^h-1=7
∴ h=3

Question 66

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

A	{25,12,16,13,10,8,14}
B	{25,14,13,16,10,8,12}
C	{25,14,16,13,10,8,12}
D	{25,14,12,13,10,8,16}

Data-Structures Heap-Tree 2009

Question 66 Explanation:

Option-A:

Violating a max heap property.
Option-B:

Violating a max heap property.
Option-C:

Question 67

Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on the correct answer to the previous question?

A	{14,13,12,10,8}
B	{14,12,13,8,10}
C	{14,13,8,12,10}
D	{14,13,12,8,10}

Data-Structures Heap-Tree 2009

Question 67 Explanation:

Actual Graph:

Step 1: Delete 25

Step 2:

Step 3: Delete 16

Step 4:

Step 5:

∴ Finary array elements: 14, 13, 12, 8, 10.

Question 68

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

A	θ(n)
B	θ(m)
C	θ(m+n)
D	θ(mn)

Data-Structures Graphs Gate-2008

Question 68 Explanation:

To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n²).

Question 69

Given f₁, f₃ and f in canonical sum of products form (in decimal) for the circuit

A	Σm(4,6)
B	Σm(4,8)
C	Σm(6,8)
D	Σm(4,6,8)

Data-Structures Canonical-Normal-Form Gate-2008

Question 69 Explanation:

f= f₁* f₂ + f₃
f₁*f₂ is intersection of minterms of f₁ and f₂
f= (f₁*f₂) + f₃ is union of minterms of (f₁*f₂) and f₃
Σm(1,6,8,15)= Σm(4,5,6,7,8) * f₂ + Σm(1,6,15)
Options A, B and D have minterm m₄ which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f₂= Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
=Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f= LHS

Question 70

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

A	MNOPQR
B	NQMPOR
C	QMNPRO
D	QMNPOR

Data-Structures Graphs Gate-2008

Question 70 Explanation:

Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).

Question 71

G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

A	For every subset of k vertices, the induced subgraph has at most 2k–2 edges
B	The minimum cut in G has at least two edges
C	There are two edge-disjoint paths between every pair to vertices
D	There are two vertex-disjoint paths between every pair of vertices

Data-Structures Graphs Gate-2008

Question 71 Explanation:

→ In Spanning tree n nodes require n-1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n-1 + n-1 =2n-2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).

Question 72

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., 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?

A	θ(log n)
B	θ(n)
C	θ(nlog n)
D	None of the above, as the tree cannot be uniquely determined

Data-Structures Binary-Search-Tree Gate-2008

Question 72 Explanation:

Last element in post order is the root of tree- find this element in inorder-log n time. Now as in quick sort consider this as pivot and split the post order array into 2. All elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have k elements smaller than pivot, these elements will be same in both in-order as well as post order. Now, we already got the root, now left child is the left split and right child is the right split.
T(n) = T(k) + T(n-k-1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the in-order traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element- if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(n-k-1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)

Question 73

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

A	θ(log n)
B	θ(n)
C	θ(nlog n)
D	θ(n²)

Data-Structures Heap-Tree Gate-2008

Question 73 Explanation:

Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements and inserting one by one n elements, so it takes 2n time. So, O(n).
Note: We can also insert all the elements once, there will be no difference on time complexity.

Question 74

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node { int value; struct node * next; }; Void rearrange (struct node * list){ struct node * p, * q; int temp; if (!list !list - > next)return; p = list; q = list - > next; while (q){ temp = p- > value;p- > value = q- > value; q- > value = temp;p = q- > next; q = p ? p- > next : 0; } }

A	1,2,3,4,5,6,7
B	2,1,4,3,6,5,7
C	1,3,2,5,4,7,6
D	2,3,4,5,6,7,1

Data-Structures Linked-List Gate-2008

Question 74 Explanation:

The given list is 1,2,3,4,5,6,7.
After 1st Iteration: 2,1,3,4,5,6,7
2nd Iteration: 2,1,4,3,5,6,7
3rd Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;

Hence 2,1,4,3,6,5,7.

Question 75

Which of the following is TRUE?

A	The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)
B	The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)
C	The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)
D	The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)

Data-Structures AVL-Trees Gate 2008-IT

Question 75 Explanation:

Complexity of AVL tree is O(logn) because it is a balanced tree, in Worst case binary search tree complexity is O(n).

Question 76

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. MBCAFHPYK KAMCBYPFH MABCKYFPH Pick the true statement from the following.

A	I and II are preorder and inorder sequences, respectively
B	I and III are preorder and postorder sequences, respectively
C	II is the inorder sequence, but nothing more can be said about the other two sequences
D	II and III are the preorder and inorder sequences, respectively

Data-Structures Binary-Trees Gate 2008-IT

Question 76 Explanation:

In preorder, root comes at the beginning of the traversal sequence and in post order, root comes at last of the traversal sequence.
So, out of the given sequence only I & II are having such kind of order, i.e., K at the beginning and at the last.
Therefore, II is the preorder and I is postorder and the sequence III will definitely be inorder.

Question 77

Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

A	I and III only
B	II and III only
C	II, III and IV only
D	I, II and III only

Data-Structures Graphs Gate 2008-IT

Question 77 Explanation:

I) After visiting 'f', 'c' or 'g' should be visited next. So, the traversal is incorrect.
IV) After visiting 'c', 'e' or 'f' should be visited next. So, the traversal is incorrect.

Question 78

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?

A	2
B	4
C	6
D	7

Data-Structures Hashing Gate 2008-IT

Question 78 Explanation:

Hence, correct option is (D).

Question 79

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

I.  81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

A	II and III only
B	I and III only
C	III and IV only
D	III only

Data-Structures Binary-Trees Gate 2008-IT

Question 79 Explanation:

Question 80

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270 Which of the following statements is TRUE?

A	I, II and IV are inorder sequences of three different BSTs
B	I is a preorder sequence of some BST with 439 as the root
C	II is an inorder sequence of some BST where 121 is the root and 52 is a leaf
D	IV is a postorder sequence of some BST with 149 as the root

Data-Structures Binary-Trees Gate 2008-IT

Question 80 Explanation:

A) Incorrect because I & IV are not in ascending order. (Inorder sequence of BST is in increasing order).
B) False because if 439 is root then it should be first element in preorder.
C) This is correct.
D) False because if 149 is root, then it should be last element in postorder.

Question 81

A	4
B	5
C	6
D	9

Data-Structures Binary-Trees Gate 2008-IT

Question 81 Explanation:

Formula:

Question 82

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n₃ can be expressed as

A
B
C
D

Data-Structures Binary-Trees Gate 2008-IT

Question 82 Explanation:

n₁ = 3
n₂ = 1
n₃ = 1
So, option (B) satisfies.

Question 83

A binary tree with n > 1 nodes has n₁, n₂ and n₃ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process?

A	2 * n₁ – 3
B	n₂ + 2 * n₁ – 2
C	n₃ – n₂
D	n₂ + n₁ – 2

Data-Structures Binary-Trees Gate 2008-IT

Question 83 Explanation:

n₁ = 3
n₃ = 1
So, option (A) satisfies.

Question 84

Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

A	1 2 3 4 5 6
B	1 3 2 4 5 6
C	1 3 2 4 6 5
D	3 2 4 1 6 5

Data-Structures Graphs Gate-2007

Question 84 Explanation:

The process to find topological order is,
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.

Question 85

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

A	2^h−1
B	2^h−1 – 1
C	2^h+1– 1
D	2^h+1

Data-Structures Binary-Trees Gate-2007

Question 85 Explanation:

img src = "https://pyq.ravindrababuravula.com/wp-content/uploads/2018/09/5-1.png">
1,3,7,15,31,...=2^h+1 - 1

Question 86

The maximum number of binary trees that can be formed with three unlabeled nodes is:

A	1
B	5
C	4
D	3

Data-Structures Binary-Trees Gate-2007

Question 86 Explanation:

Total number of binary trees possible for n nodes is C(n)=(2n)!/(n+1)!n! C(n)=(2(3))!/(3+1)!3!=6×5×4×3×2×1/4×3×2×1×3×2=5
Total no. of possible trees is 5.

Total = 5

Question 87

The following postfix expression with single digit operands is evaluated using a stack:

8 2 3 ^ / 2 3 * + 5 1 * -

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

A	6, 1
B	5, 7
C	3, 2
D	1, 5

Data-Structures Stacks Gate-2007

Question 87 Explanation:

8 2 3 ^ / 2 3 * + 5 1 * -

After the * is evaluated at the time elements in the stack is 1, 6.

Question 88

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

A	d e b f g c a
B	e d b g f c a
C	e d b f g c a
D	d e f g b c a

Data-Structures Binary-Trees Gate-2007

Question 88 Explanation:

Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g

Pre order: a b d e c f g
Post order: d e b f g c a

Question 89

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

A	8, _, _, _, _, _, 10
B	1, 8, 10, _, _, _, 3
C	1, _, _, _, _, _,3
D	1, 10, 8, _, _, _, 3

Data-Structures Hashing Gate-2007

Question 89 Explanation:

Consider a hash table of size 7
Starting index is zero i.e.,

⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).

Question 90

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

A	3
B	4
C	5
D	6

Data-Structures N-array-Tree Gate-2007

Question 90 Explanation:

L = (n-1) * I + 1
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n-1) * 10 + 1
40 = (n-1) * 10
n = 5

Question 91

Consider the following C program segment where CellNode represents a node in a binary tree:

struct CellNode 
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};
int GetValue(struct CellNode *ptr) 
{
  int value = 0;
  if (ptr != NULL) 
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}



The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

A	the number of nodes in the tree
B	the number of internal nodes in the tree
C	the number of leaf nodes in the tree
D	the height of the tree

Data-Structures Binary-Trees Gate-2007

Question 91 Explanation:

Let take example,

So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.

Question 92

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:

A	θ(log₂n)
B	θ(log₂log₂n)
C	θ(n)
D	θ(nlog₂n)

Data-Structures Heap-Tree Gate-2007

Question 92 Explanation:

Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+---- this series is equal to "logn". All the elements are sorted, the binary search which will result in O(loglogn) number of comparisons.

Question 93

A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ?

A	d[u] < d[v]
B	d[u] < f[v]
C	f[u] < f[v]
D	f[u] > f[v]

Data-Structures Graphs Gate 2007-IT

Question 93 Explanation:

Option A:
d[u] Option B:
d[u] Option C:
f[u] So, option D is True.

Question 94

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?

A	35
B	64
C	128
D	5040

Data-Structures Binary-Trees Gate 2007-IT

Question 94 Explanation:

To find 60 in BST then there are two possible set i.e., greater than 60 and smaller than 60.
Smaller values 90, 80 and 70 are visited in order
i.e., 7!/(4!3!) = 35

Question 95

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty (Q) — returns true if the queue is empty, false otherwise. ii. delete (Q) — deletes the element at the front of the queue and returns its value. iii. insert (Q, i) — inserts the integer i at the rear of the queue. Consider the following function:

 void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
   i = delete(Q);
   f(Q);
   insert(Q, i);
  }
}

What operation is performed by the above function f ?

A	Leaves the queue Q unchanged
B	Reverses the order of the elements in the queue Q
C	Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order
D	Empties the queue Q

Data-Structures Queues Gate 2007-IT

Question 95 Explanation:

As a recursive call, and removing from front while inserting from end, that means that element will be deleted at last and will be inserted 1^st in the new queue. And like that it will continue till first call execute insert (Q, i) function. So the queue is in reverse order.

Question 96

Consider the following C program:

   #include 
           #define EOF -1
           void push (int); /* push the argument on the stack */
           int pop  (void); /* pop the top of the stack */
           void flagError ();
           int main ()
          {         int c, m, n, r;
                     while ((c = getchar ()) != EOF)
                    { if  (isdigit (c) )
                               push (c);
                     else if ((c == '+') || (c == '*'))
                    {          m = pop ();
                                n = pop ();
                                r = (c == '+') ? n + m : n*m;
                                push (r);
                      }
                      else if (c != ' ')
                               flagError ();
             }
              printf("% c", pop ());
}

What is the output of the program for the following input ? 5 2 * 3 3 2 + * +

A	15
B	25
C	30
D	150

Data-Structures Stacks Gate 2007-IT

Question 96 Explanation:

push 5
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.

Question 97

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

A	log₂n
B	n
C	2n+1
D	2ⁿ-1

Data-Structures Binary-Trees Gate-2006

Question 97 Explanation:

The binary right skewed tree follows 2ⁿ -1 because level 2 value is 7 and level 3 value 15.
Note: Assume level numbers are start with 0.

Question 98

In a binary max heap containing n numbers, the smallest element can be found in time

A	O(n)
B	O(log n)
C	O(log log n)
D	O(1)

Data-Structures Heap-Tree Gate-2006

Question 98 Explanation:

We have to search all the elements in max heap. So, the worst case time complexity for Max Heap is O(n).

Question 99

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?

A	10, 7, 9, 8, 3, 1, 5, 2, 6, 4
B	10, 9, 8, 7, 6, 5, 4, 3, 2, 1
C	10, 9, 4, 5, 7, 6, 8, 2, 1, 3
D	10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Data-Structures Heap-Tree Gate-2006

Question 99 Explanation:

Question 100

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property. Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

A	1, 3, 5, 6, 8, 9
B	9, 6, 3, 1, 8, 5
C	9, 3, 6, 8, 5, 1
D	9, 5, 6, 8, 3, 1

Data-Structures Heap-Tree Gate-2006

Question 100 Explanation:

Question 101

Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

A	There must exist a vertex w adjacent to both u and v in G
B	There must exist a vertex w whose removal disconnects u and v in G
C	There must exist a cycle in G containing u and v
D	There must exist a cycle in G containing u and all its neighbours in G

Data-Structures Graphs Gate-2006

Question 101 Explanation:

Very difficult assume a graphs here. So, As per the GATE key they given Option D is correct answer.

Question 102

An implementation of a queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x) {
   push (S1, x);
}
 
void delete(Q){
   if(stack-empty(S2)) then 
      if(stack-empty(S1)) then {
          print(“Q is empty”);
          return;
      }
      else while (!(stack-empty(S1))){
          x=pop(S1);
          push(S2,x);
      }
   x=pop(S2);
}



Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

A	n+m ≤ x < 2n and 2m ≤ y ≤ n+m
B	n+m ≤ x< 2n and 2m ≤y ≤ 2n
C	2m ≤ x< 2n and 2m ≤ y ≤ n+m
D	2m ≤ x < 2n and 2m ≤ y ≤ 2n

Data-Structures Stack-and-Queue Gate-2006

Question 102 Explanation:

Let's first consider for push, i.e., x.
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (n-m) elements to S1.
So total push operation
= m + m + (n-m)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (n-m) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.

Question 103

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

A	10
B	11
C	12
D	15

Data-Structures Binary-Trees Gate 2006-IT

Question 103 Explanation:

A node in a binary tree has degree 0, 1, 2.
No. of 1 degree nodes = 5
No. of 2 degree nodes = 10
Total no. of edges = (1*5) + (2*10) = 5 + 20 = 25
So, Total no. of edges = 25 + 1 = 26 (No. of nodes in a tree is 1 more than no. of edges)
Total no. of leaf nodes (node with 0 degree) = 26 - 5 - 10 = 11

Question 104

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

A	Hamiltonian cycle
B	grid
C	hypercube
D	tree

Data-Structures Tree Gate 2006-IT

Question 104 Explanation:

MST:
If all edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is minimum spanning tree.

Question 105

Which of the following sequences of array elements forms a heap?

A	{23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
B	{23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
C	{23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
D	{23, 17, 14, 7, 13, 10, 1, 12, 5, 7}

Data-Structures Heap-Tree Gate 2006-IT

Question 105 Explanation:

In this every children and parent satisfies Max heap properties.

Question 106

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

A	{10, 75, 64, 43, 60, 57, 55}
B	{90, 12, 68, 34, 62, 45, 55}
C	{9, 85, 47, 68, 43, 57, 55}
D	{79, 14, 72, 56, 16, 53, 55}

Data-Structures Binary-Trees Gate 2006-IT

Question 106 Explanation:

In the binary search tree on right side of parent number, the number should be greater than it. But in option C, after 47, 43 appears. So, this is False.

Question 107

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

A	{P, Q, R, S}, {T}, {U}, {V}
B	{P, Q, R, S, T, V}, {U}
C	{P, Q, S, T, V}, {R}, {U}
D	{P, Q, R, S, T, U, V}

Data-Structures Graphs Gate 2006-IT

Question 107 Explanation:

In a strongly connected component every two vertices must be reachable from one to other and itis maximal component.
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.

Question 108

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that d(P) = 5 units f(P) = 12 units d(Q) = 6 units f(Q) = 10 units d(R) = 14 unit f(R) = 18 units which one of the following statements is TRUE about the graph

A	There is only one connected component
B	There are two connected components, and P and R are connected
C	There are two connected components, and Q and R are connected
D	There are two connected components, and P and Q are connected

Data-Structures Graphs Gate 2006-IT

Question 108 Explanation:

Since, d(q) = d(p) + 1 and f(q) < f(p) which means p and q are connected and r is separate, so (D) is the answer.

Question 109

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?

A	⌊i/2⌋
B	⌈(i-1)/2⌉
C	⌈i/2⌉
D	⌈i/2⌉ - 1

Data-Structures Binary-Trees Gate 2006-IT

Question 109 Explanation:

If index of array start with 1 then directly divide the i^th value by 2 and take floor. If index start with '0' then ⌈i/2⌉ - 1.

Question 110

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity of

A	O(n)
B	O(log n)
C	O(n log n)
D	O(n log log n)

Data-Structures Binary-Trees Gate 2006-IT

Question 110 Explanation:

It takes O(log n) to heapify an element of heap.

Question 111

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X[i], i ≠ 0, is

A	⌊log₂ i⌋
B	⌈log₂ (i + 1)⌉
C	⌊log₂ (i + 1)⌋
D	⌈log₂ i⌉

Data-Structures Binary-Trees Gate 2006-IT

Question 111 Explanation:

If the root node is at level 0 then the level of element X[i] is ⌊log₂ (i + 1)⌋.

Question 112

An Abstract Data Type (ADT) is:

A	Same as an abstract class
B	A data type that cannot be instantiated
C	A data type type for which only the operations defined on it can be used, but none else
D	All of the above

Data-Structures Abstract-Data-Type Gate-2005

Question 112 Explanation:

An Abstract datatype is a type for objects whose behaviour is defined by set of values and set of operations.

Question 113

A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

A	An array of 50 numbers
B	An array of 100 numbers
C	An array of 500 numbers
D	A dynamically allocated array of 550 numbers

Data-Structures Arrays Gate-2005

Question 113 Explanation:

→ Here we are storing values above 50 and we are ignoring the scores which is less than 50.
→ Then using array of 50 numbers is the best way to store the frequencies.

Question 114

An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are l's. Which one of the following is TRUE?

A	Graph G has no minimum spanning tree (MST)
B	Graph G has a unique MST of cost n-1
C	Graph G has multiple distinct MSTs, each of cost n-1
D	Graph G has multiple spanning trees of different costs

Data-Structures Graphs Gate-2005

Question 114 Explanation:

From given data, we can say that the given graph is complete graph with all edge weights 1. Hence weight of MST is n-1.
Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n-1).

Question 115

A	the minimum weighted spanning tree of G
B	the weighted shortest path from s to t
C	each path from s to t
D	the weighted longest path from s to t

Data-Structures Graphs Gate-2005

Question 115 Explanation:

Since every edge has distinct edge weights. So, the edge with minimum weight will definitely be present in MST.

Question 116

Let s and t be two vertices in a undirected graph G + (V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

A	a path from s to t in the minimum weighted spanning tree
B	a weighted shortest path from s to t
C	an Euler walk from s to t
D	a Hamiltonian path from s to t

Data-Structures Graphs Gate-2005

Question 116 Explanation:

Let us first understand what is minimum congestion actually.
Minimum congestion is the edge with maximum weight among all other edges included in the path.
Now suppose shortest path from A→B is 6, but in MST, we have A→C→B(A→C=4, C→B=3), then along the path in MST, we have minimum congestion i.e., 4.

Question 117

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:

A	nk
B	(n - 1) k + 1
C	n (k - 1) + 1
D	n (k - 1)

Data-Structures K array Tree Gate-2005

Question 117 Explanation:

Total nodes = nk+1 (1 for root)
Leaves = total nodes - internal nodes
= nk+1-n
= n(k-1)+1

Question 118

How many distinct binary search trees can be created out of 4 distinct keys?

A	5
B	14
C	24
D	42

Data-Structures Binary-Search-Tree Gate-2005

Question 118 Explanation:

There are ²ⁿC_n / (n+1) unlabelled trees are possible.
(or)

t(0)=1
t(1)=1
t(4) = t(0)t(3) + t(1)t(2) + t(2)t(1) + t(3)t(0)
= 5+2+2+5
= 14
(or)
⁸C₄ / 5 = 14

Question 119

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

A	10, 8, 7, 5, 3, 2, 1
B	10, 8, 7, 2, 3, 1, 5
C	10, 8, 7, 1, 2, 3, 5
D	10, 8, 7, 3, 2, 1, 5

Data-Structures Queues-And-Heap Gate-2005

Question 119 Explanation:

Initial heap sequence: 10, 8, 5, 3, 2

Insert → 1 into heap structure

Insert → 7 into heap structure

Here, violating Max-heap property. So perform heapify operation.

The final sequence is 10, 8, 7, 3, 2, 1, 5.

Question 120

Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?

A	9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
B	9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
C	29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
D	95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Data-Structures Binary-Search-Tree Gate-2005

Question 120 Explanation:

Inorder traversal of any binary search tree is the sorted sequence of element in ascending order.

Question 121

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

A	(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
B	top1 + top2 = MAXSIZE
C	(top1 = MAXSIZE/2) or (top2 = MAXSIZE)
D	top1 = top2 – 1

Data-Structures Stacks Gate-2004

Question 121 Explanation:

Since the stacks are growing from opposite ends, so initially top1=1 and top2=Max_size. Now to make the efficient use of space we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So any of the stack can grow towards each other until there is space available in the array. Hence, the condition must be top1=top2 - 1.

Question 122

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

A	2
B	3
C	4
D	6

Data-Structures Binary-Search-Tree Gate-2004

Question 122 Explanation:

Height of the binary search tree = 3

Question 123

The best data structure to check whether an arithmetic expression has balanced parentheses is a

A	queue
B	stack
C	tree
D	list

Data-Structures Stacks Gate-2004

Question 123 Explanation:

Stack is the best data structure to validate the arithmetic expression.
While evaluating when left parentheses occur then it push in to the stack, when right parentheses occur pop from the stack.
While at the end there is empty in the stack.

Question 124

Level order traversal of a rooted tree can be done by starting from the root and performing

A	preorder traversal
B	in-order traversal
C	depth first search
D	breadth first search

Data-Structures Graphs Gate-2004

Question 124 Explanation:

Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

Question 125

A	i only
B	ii only
C	i and ii only
D	iii or iv

Data-Structures Hashing Gate-2004

Question 125 Explanation:

Given Input = (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199)
Hash function = x mod 10
Hash values = (2, 4, 1, 9, 9, 1, 3, 9)
9679, 1989, 4199 have same hash values
&
1471, 6171 have same hash values.

Question 126

A	(i) only
B	(ii), (iii)
C	(iii) only
D	(iv) only

Data-Structures Binary-Trees Gate-2004

Question 126 Explanation:

→We have some combinations such that which can be able to identity a tree
(i) Inorder and Preorder
(ii) Inorder and Postorder
(iii) Inorder and Levelorder
→And following are do not
(i) Post order and Preorder
(ii) Pre order and Level order
(iii) Post order and Level order

Question 127

A	rear node
B	front node
C	not possible with a single pointer
D	node next to front

Data-Structures Linked-List Gate-2004

Question 127 Explanation:

We can perform enqueue and dequeue from rear within O(1) time. But from the front node we cannot rear from front in O(1) time.

Question 128

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a MaxHeap. The resultant MaxHeap is

A
B
C
D

Data-Structures Heap-Tree Gate-2004

Question 128 Explanation:

32, 15, 20, 30, 12, 25, 16

Question 129

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b×c-d^e^f is

A	abc×+def^^-
B	abc×+de^f^-
C	ab+c×d-e^f^
D	-+a×bc^^def

Data-Structures Stacks Gate-2004

Question 129 Explanation:

a+b×c-d^e^f

Note: When low precedence operator enters into stack then pop.

Question 130

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

A	union only
B	intersection, membership
C	membership, cardinality
D	union, intersection

Data-Structures Linked-List Gate-2004

Question 130 Explanation:

Let no. of elements in list 1 be n₁.
Let no. of elements in list 2 be n₂.
Union:
To union two lists, for each element in one list we will search in other list, to avoid duplicates. So, time complexity will be O(n₁×n₂).
Intersection:
To take intersection of two lists, for each element in one list we will search in other list if it is present or not. So time complexity will be O(n₁ × n₂).
Membership:
In this we search if particular element is present in the list or not. So time complexity will be O(n₁ + n₂).
Cardinality:
In this we find the size of set or list. So to find size of list we have to traverse each list once. So time complexity will be O(n₁+n₂).
Hence, Union and Intersection will be slowest.

Question 131

A	The number of leaf nodes in the tree
B	The number of nodes in the tree
C	The number of internal nodes in the tree
D	The height of the tree

Data-Structures Binary-Trees Gate-2004

Question 131 Explanation:

→ Dosomething ( ) returns the max (height of left child + 1, height right child + 1).
→ So given that pointer to root of tree is passed to DoSomething ( ), it will return height of the tree. It is done when the height of single node is '0'.

Question 132

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

A	O(n)
B	O(log² n)
C	O(logn)
D	O(1)

Data-Structures Linked-List Gate 2004-IT

Question 132 Explanation:

Worst case complexity for deleting a node from singly linked list is O(1).

Question 133

Assume the following C variable declaration Of the following expressions I A[2] II A[2][3] III B[1] IV B[2][3] which will not give compile-time errors if used as left hand sides of assignment statements in a C program?

int *A [10], B[10][10];

A	I, II, and IV only
B	II, III, and IV only
C	II and IV only
D	IV only

Data-Structures Arrays Gate-2003

Question 133 Explanation:

i) A[2] can be consider as a pointer and this will not give any compile-time error.
ii) A[2][3] This results an integer, no error will come.
iii) B[1] is a base address of an array. This will not be changed it will result a compile time error.
iv) B[2][3] This also results an integer. No error will come.

Question 134

Let T(n) be the number of different binary search trees on n distinct elements. Then

A	n – k + 1
B	n – k
C	n – k – 1
D	n – k – 2

Data-Structures Binary-Search-Tree Gate-2003

Question 134 Explanation:

A binary search tree consists of n distinct elements. Let consider on left subtree, it consists of (k-1) elements. Then right subtree consists of (n-k) elements. From this we c an write recursive function as T(k-1)*(n-k) i.e.,

Question 135

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

A	7 5 1 0 3 2 4 6 8 9
B	0 2 4 3 1 6 5 9 8 7
C	0 1 2 3 4 5 6 7 8 9
D	9 8 6 4 2 3 0 1 5 7

Data-Structures Binary-Search-Tree Gate-2003

Question 135 Explanation:

Inorder: 0 1 2 3 4 5 6 7 8 9

Question 136

Consider the following graph,

Among the following sequences:

(I) a b e g h f 
(II) a b f e h g
(III) a b f h g e 
(IV) a f g h b e

Which are depth first traversals of the above graph?

A	I, II and IV only
B	I and IV only
C	II, III and IV only
D	I, III and IV only

Data-Structures Graphs Gate-2003

Question 136 Explanation:

I) a → b → e → g → h → f (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)

Question 137

In a heap with n elements with the smallest element at the root, the 7^th smallest element can be found in time

A	Θ(n log n)
B	Θ(n)
C	Θ(log n)
D	Θ(1)

Data-Structures Heap-Tree Gate-2003

Question 137 Explanation:

The 7^th smallest elements can be present in any of 7 levels. Then total possible elements can be present is seven levels is
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^th smallest element in Θ(1) time.

Question 138

A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

   o	Delection of the smallest element 
   o	Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

A	A heap can be used but not a balanced binary search tree
B	A balanced binary search tree can be used but not a heap
C	Both balanced binary search tree and heap can be used
D	Neither balanced binary search tree nor heap can be used

Data-Structures Tree Gate-2003

Question 138 Explanation:

→ In heap deletion takes O(log n).
Insertion of an element takes O(n).
→ In balanced primary tree deletion takes O(log n).
Insertion also takes O(log n).

Question 139

Let S be a stack of size n ≥1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

A	n(X + Y)
B	3Y + 2X
C	n(X + Y) - X
D	Y + 2X

Data-Structures Stacks Gate-2003

Question 139 Explanation:

Life time of last element present in the stack = Y
(After push into stack then immediately popped)
Life time of (n-1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n-2) element = (n-1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n-1)X + (2n-1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n-1)+Y(1+3+5+...+(2n-1))
⇒ 2X(n(n-1) /2) +Y((n/2)(1+2n-1))
⇒ n(n(X+Y)-X))
Avg. of n numbers = n(n(X+Y)-X)/n = n(X+Y)-X

Question 140

Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting G in the above tree ?

A
B
C
D	None of the above

Data-Structures Trees Gate-2003

Question 140 Explanation:

Given Tree is

Insert G at root level:

Question 141

Consider the function f defined below.

struct item
{
    int data;
    struct item * next;
};
int f(struct item *p)
{
    return ((p == NULL) || (p->next == NULL) ||
            ((P->data <= p->next->data) &&
            f(p->next)));
}



For a given linked list p, the function f returns 1 if and only if

A	the list is empty or has exactly one element
B	the elements in the list are sorted in non-decreasing order of data value
C	the elements in the list are sorted in non-increasing order of data value
D	not all elements in the list have the same data value

Data-Structures Linked-List Gate-2003

Question 141 Explanation:

It return a value '1' when the elements in the list are presented in sorted order and non-decreasing order of data value.

Question 142

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

A	log n
B	n/2
C	(log₂)ⁿ - 1
D	n

Data-Structures Linked-List Gate-2002

Question 142 Explanation:

Worst case time complexity of singly linked list is O(n). So we need n number of comparisons needed to search a singly linked list of length n.

Question 143

The results returned by function under value-result and reference parameter passing conventions

A	Do not differ
B	Differ in the presence of loops
C	Differ in all cases
D	May differ in the presence of exception

Data-Structures Parameter-Passing Gate-2002

Question 143 Explanation:

The result return by the function under value-result and reference parameter passing conventions may differ in presence of exception because in value-result the updated value can be returned to the original variable. But in case of reface parameter the value can change immediately.

Question 144

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

A
B
C
D

Data-Structures Tree Gate-2002

Question 144 Explanation:

Question 145

A	4040
B	4050
C	5040
D	5050

Data-Structures Arrays Gate-2002

Question 145 Explanation:

Address for a[40][50] = BaseAddress + [40 * 100 * element size] + [50 * element size]
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050

Question 146

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

A
B
C
D

Data-Structures Tree Gate-2002

Question 146 Explanation:

Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log_3/2 n

Question 147

To evaluate an expression without any embedded function calls

A	One stack is enough
B	Two stacks are needed
C	As many stacks as the height of the expression tree are needed
D	A Turning machine is needed in the general case

Data-Structures Stacks Gate-2002

Question 147 Explanation:

To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.

Question 148

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

A	Theory Explanation is given below.

Data-Structures Binary-Trees Gate-2002

Question 148 Explanation:

Total 5 binary trees are possible with the preorder C, B, A.

Question 149

A	Theory Explanation is given below.

Data-Structures Recursion Gate-2002

Question 149 Explanation:

move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 2²T(n - 2) + 3
⁞
2^k T(n - k) + (2^k - 1)
= 2^n-1T(1) + (2^n-1 - 1)
= 2^n-1 + 2^n-1 - 1
= 2ⁿ - 1
≅ O(2ⁿ)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}

Question 150

A	X – 1 Y – 2 Z – 3
B	X – 3 Y – 1 Z – 2
C	X – 3 Y – 2 Z – 1
D	X – 2 Y – 3 Z – 1

Data-Structures Match-the-Following Gate-2000

Question 150 Explanation:

Stack is used in depth first search.
Queus is used in Queue.
Heap is used in heap.

Question 151

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

A	(1 2 (4 5 6 7))
B	(1 (2 3 4) 5 6) 7)
C	(1 (2 3 4) (5 6 7))
D	(1 (2 3 NULL) (4 5))

Data-Structures Binary-Trees Gate-2000

Question 151 Explanation:

Option C:

(Proper Representation)

Question 152

A	Rotates s left by k positions
B	Leaves s unchanged
C	Reverses all elements of s
D	None of the above

Data-Structures Arrays Gate-2000

Question 152 Explanation:

If we perform the three given open operations it will result left rotation by K positions. If we perform n time it will result the initial array.

Question 153

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

A	LASTIN = LASTPOST
B	LASTIN = LASTPRE
C	LASTPRE = LASTPOST
D	None of the above

Data-Structures Binary-Trees Gate-2000

Question 153 Explanation:

In full Binary tree LASTIN = LASTPRE.
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.

Question 154

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

A	{u, v} must be an edge in G, and u is a descendant of v in T
B	{u, v} must be an edge in G, and v is a descendant of u in T
C	If {u, v} is not an edge in G then u is a leaf in T
D	If {u, v} is not an edge in G then u and v must have the same parent in T

Data-Structures Graphs Gate-2000

Question 154 Explanation:

In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.

Question 155

A	Theory Explanation is given below.

Data-Structures Descriptive Gate-2000

Question 155 Explanation:

(a) Enqueue → push
Dequeue → reverse, pop, reverse
(b) (i) After evaluating 5 2 * 3 4 +
Sol:
7(3+4) 10(5*2)
(ii) After evaluating 5 2 * 3 4 + 5 2
Sol:
25(5*5) 7(3+4) 10(5*2)
(iii) At the end of evaluation
Sol: 80

Question 156

A	0
B	1
C	2
D	3

Data-Structures Graphs Gate-1999

Question 156 Explanation:

Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3

Question 157

Which of the following statements is false?

A	A tree with a n nodes has (n – 1) edges
B	A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results
C	A complete binary tree with n internal nodes has (n + 1) leaves
D	Both B and C

Data-Structures Binary-Trees Gate-1998

Question 157 Explanation:

A: Tree with n nodes must have (n-1) edges.
D: The maximum no. of nodes in a binary tree of height h is 2^h+1 - 1.
h=2 ⇒ 2³ - 1 ⇒ 7

Question 158

A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

A	x(n-1) + 1
B	xn - 1
C	xn + 1
D	x(n+1)

Data-Structures N-array-Tree Gate-1998

Question 158 Explanation:

No. of internal node = x
Let no. of leaf nodes = L
Let n_t be total no. of nodes.
So, L+x = n_t -----(I)
Also for n-ary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = n_t -----(II)
So, equating (I) & (II),
L+x = nx+1
L = x(n-1) + 1

Question 159

A	15i + j + 84
B	15j + i + 84
C	10i + j + 89
D	10j + i + 89

Data-Structures Arrays Gate-1998

Question 159 Explanation:

The address of element A[i][j] will be,
100 + 15 * (i-1) + (j-1)
= 100 + 15i - 15 + j - 1
= 15i + j + 84

Question 160

Faster access to non-local variables is achieved using an array of pointers to activation records called a

A	stack
B	heap
C	display
D	activation tree

Data-Structures Pointers Gate-1998

Question 160 Explanation:

Properties of displays:
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for non-local variables but may be complicated to maintain.

Question 161

The concatenation of two lists is to be performed on O(1) time. Which of the following implementations of a list should be used?

A	Singly linked list
B	Doubly linked list
C	Circular doubly linked list
D	Array implementation of list

Data-Structures Linked-List Gate-1997

Question 161 Explanation:

In circular doubly linked list concatenation of two lists is to be performed on O(1) time.

Question 162

Which of the following is essential for converting an infix expression to the postfix form efficiently?

A	An operator stack
B	An operand stack
C	An operand stack and an operator stack
D	A parse tree

Data-Structures Stacks Gate-1997

Question 162 Explanation:

An operator stack ⇒ Infix to (Postfix or Prefix)
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use

Question 163

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A	5 3 1 2 4 7 8 6
B	5 3 1 2 6 4 8 7
C	5 3 2 4 1 6 7 8
D	5 3 1 2 4 7 6 8

Data-Structures Binary-Trees Gate-1997

Question 163 Explanation:

Preorder traversal means (Root, left, right)
Option D:
Let draw binary search tree for the given sequence,

After traversing through this tree we will get same sequence.

Question 164

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

A	non-increasing order
B	non-decreasing order
C	strictly increasing order
D	strictly decreasing order

Data-Structures Stack-and-Queue Gate-1997

Question 164 Explanation:

In stack last element pushed should be popped first. And in priority queue Q, minimum element is given the highest priority. So whenever we will call DELETEMIN(Q), it will pop the elementwith min value. So we can conclude that the minimum element should be inserted last or the insertion should be in decreasing order. And also it should be in strictly decreasing order, because for two elements with equal value the priority queue will pick any of one randomly which should not be the case in the stack.

Question 165

A	(ii) and (iii) are true
B	(i) and (ii) are true
C	(iii) and (iv) are true
D	(ii) and (iv) are true

Data-Structures Stack-and-Queue Gate-1996

Question 165 Explanation:

(i) FIFO computation efficiently supported by queues.
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
Answer:- A

Question 166

An advantage of chained hash table (external hashing) over the open addressing scheme is

A	Worst case complexity of search operations is less?
B	Space used is less
C	Deletion is easier
D	None of the above

Data-Structures Hashing Gate-1996

Question 166 Explanation:

In chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing can be postponed for longer time.

Question 167

A	1
B	3
C	7
D	8

Data-Structures Binary-Trees Gate-1996

Question 167 Explanation:

a, b, c are going to unbalance.

Question 168

Which of the following sequences denotes the post order traversal sequence of the tree of question 14?

A	f e g c d b a
B	g c b d a f e
C	g c d b f e a
D	f e d g c b a

Data-Structures Binary-Trees Gate-1996

Question 168 Explanation:

Postorder:-
Left → Right → Root
g c d b f e a

Question 169

A	0
B	1
C	2
D	3

Data-Structures Heap-Tree Gate-1996

Question 169 Explanation:

Lets draw first heap from given sequence,

Question 170

A	(4, 7)
B	(7, 4)
C	(8, 3)
D	(3, 8)

Data-Structures Binary-Trees Gate-1996

Question 170 Explanation:

50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).

Question 171

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:

A	log₂ n
B	n - 1
C	n
D	2ⁿ

Data-Structures Trees Gate-1995

Question 171 Explanation:

A binary tree is a tree data structure in which each node has atmost two child nodes.
The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
The number of nodes of degree 2 in T is "n - 1".

Question 172

An unrestricted use of the “goto” statement is harmful because

A	it makes it more difficult to verify programs
B	it increases the running time of the programs
C	it increases the memory required for the programs
D	it results in the compiler generating longer machine code

Data-Structures Programming Gate-1994

Question 172 Explanation:

If we use "goto" statements then it leads to structural decomposition of code then it is difficult to verify the programs.

Question 173

Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?

A	3, 4, 5, 1, 2
B	3, 4, 5, 2, 1
C	1, 5, 2, 3, 4
D	5, 4, 3, 1, 2

Data-Structures Stacks Gate-1994

Question 173 Explanation:

Push 1 Push 2 Push 3 Pop 3 Push 4 Pop 4 Push 5 Pop 5 Pop 2 Pop 1.
→ Remaining options are not possible.

Question 174

Linked lists are not suitable data structures of which one of the following problems?

A	Insertion sort
B	Binary search
C	Radix sort
D	Polynomial manipulation

Data-Structures Linked-List Gate-1994

Question 174 Explanation:

In linked list finding an element take O(n) which is not suitable for the binary search. And time complexity of binary search is O(log n).

Question 175

A	4
B	5
C	6
D	7
E	Both A and D

Data-Structures Trees Gate-1992

Question 175 Explanation:

Case 1:

Where L is leaf node.
So, no. of internal node is 4.
Case 2:

Where L is leaf node.
So, no. of internal node is 7.

Question 176

How many edges are there in a forest with p components having n vertices in all?

n-p

Data-Structures Graphs Gate-1992

Question 176 Explanation:

Forest is a graph with no cycle.
Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).
So, total of n-p edges for p components.

Question 177

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

A
B
C
D

Data-Structures Heap-Tree Gate-2001

Question 177 Explanation:

Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1

Question 178

A	Only P3
B	Only P1 and P3
C	Only P1 and P2
D	P1, P2 and P3

Data-Structures Pointers Gate-2001

Question 178 Explanation:

[P1] → May cause error because the function is returning the address of locally declared variable.
[P2] → It will cause problem because px is in int pointer that is not assigned with any address and we are doing dereferencing.
[P3] → It will work because memory will be stored in px that can be use further. Once function execution completes this will exist in Heap.

Question 179

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

A	d(r,u)
B	d(r,u)>d(r,v)
C	d(r,u)≤d(r,v)
D	None of the above

Data-Structures Graphs Gate-2001

Question 179 Explanation:

d(r,u) and d(r, v) will be equal when u and v are at same level, otherwise d(r,u) will be less than d(r,v).

Question 180

What is the minimum number of stacks of size n required to implement a queue of size n?

A	One
B	Two
C	Three
D	Four

Data-Structures Stack-and-Queue Gate-2001

Question 180 Explanation:

Minimum number of stacks of size n required to implement a queue of size n is two. With the help of two stacks we can able to implement a queue.

Question 181

A	Theory Explanation is given below.

Data-Structures Binary-Search-Tree Gate-2001

Question 182

A	(a) - (q), (b) - (r), (c) - (s), (d) - (p)

Data-Structures Match-the-Following Gate-1990

Question 182 Explanation:

Heap construction - O(n)
Constructing Hash table with linear probing - O(n²
AVL tree construction - O(n log₁₀ n)
Digital trie construction - Ω(n log₁₀ n)

Question 183

A	Equal to the number of ways of multiplying (n+1) matrices.
B	Equal to the number of ways of arranging n out of 2n distinct elements.
C
D	Equal to n!.
E	Both (A) and (C).

Data-Structures Binary-Trees Gate-1990

Question 183 Explanation:

No. of rooted binary trees (unlabeled) with n nodes is given by n^th catalan number which equals (²ⁿC_n)/(n+1)
Here, both options A and C are true as option A corresponds to n multiply operations of (n+1) matrices, the no. of ways for this is again given by the n^th catalan number.

Question 184

A	≤ n² always.
B	≥ nlog₂ n always.
C	Equal to n² always.
D	O(n) for some special trees.

Data-Structures Binary-Trees Gate-1990

Question 184 Explanation:

Here the question asked for binary tree.
It can be of 2 types:
1) Skewed tree.
2) Balanced binary tree or AVL tree.
We have to find external path length, i.e., leaf node.
We also know cost of external path = leaf node value + length of path
Now for balanced tree external path length = n × logn
But for skewed tree it will be O(n) only.
So, answer will be (D).

Question 185

A	4
B	5
C	6
D	3

Data-Structures Hashing Gate-1989

Question 185 Explanation:

In this, maximum size of cluster = 4 (S6, S3, S7, S1)
→ Worst case of finding a number is equal to maximum size of cluster + 1(after searching all the cluster it enters into empty cluster)
→ Maximum no. of comparisions = 4 + 1 = 5

Question 186

A	(A)-(r), (B)-(s), (C)-(p), (D)-(q)

Data-Structures Match-the-Following Gate-1989

Question 186 Explanation:

O(log n) - Binary search
O(n) - Selection of the k^th smallest element in a set of n elements
O(n log n) - Heapsort
O(n²) - Depth-first search

Question 187

Which one of the following statements (s) is/are FALSE?

A	Overlaying is used to run a program, which is longer than the address space of the computer.
B	Optimal binary search tree construction can be performed efficiently by using dynamic programming.
C	Depth first search cannot be used to find connected components of a graph.
D	Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.
E	A, C and D.

Data-Structures True or False Gate-1989

Question 187 Explanation:

Option A - False
As per the definition of address space memory used by the overlay comes under the address space of computer.
Option B: True
By using dynamic programming we can construct optimal binary search tree efficiently.
Option C: False
DFS can be used to find connected components of a graph.
Option D: False
Infix + C postfix or prefix is required to construct the binary tree uniquely.

Question 188

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?

A	True
B	False

Data-Structures Binary-Trees GATE-1987

Question 188 Explanation:

To construct binary tree uniquely we need either inorder and postorder or inorder and preorder.

Question 189

There is a linear-time algorithm for testing the planarity of finite graphs.

A	True
B	False

Data-Structures Graphs GATE-1987

Question 189 Explanation:

Yes, Linear time algorithm is there for testing the planarity of finite graphs.

Question 190

If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.

A	True
B	False

Data-Structures Binary-Trees GATE-1987

Question 190 Explanation:

In the above binary tree, no. of leaves is 3, which is not the power of 2. Hence the given statement is false.

Question 191

In a circular linked list oraganisation, insertion of a record involves modification of

A	One pointer.
B	Two pointers.
C	Multiple pointers.
D	No pointer.

Data-Structures Linked-List GATE-1987

Question 191 Explanation:

Suppose we have to insert node p after node q then
p → next = q → next
q → next = p
So, two pointers modifications.

There are 191 questions to complete.