Data Structure Gate Previous Year Questions

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

a) The best algorithm for the problem takes θ(n) time in the worst case.
b) The best algorithm for the problem takes θ( nlog n) time in the worst case.
c) The best algorithm for the problem takes θ(n²) time in the worst case.
d) It is not possible to reverse a singly linked list in O(1) space.

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

a) The diagonal entries of A² are the degrees of the vertices of the graph.
b) If the graph is connected, then none of the entries of A^n-1+I_n can be zero.
c) If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic.
d) If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

a) A³
b) A³ divided by 2
c) A³ divided by 3
d) A³ divided by 6

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_______

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) Θ(log n)
b) Θ(log(n)+k)
c) Θ(k log n)
d) Θ(n log k)

Let G = (V, G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u, v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

a) Θ(∣E∣ + ∣V∣)
b) Θ(∣E∣.∣V∣)
c) Θ(E∣ log ∣V∣)
d) Θ(∣V∣)

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) 10, 11, 12, 15, 16, 18, 19, 20
b) 11, 12, 10, 16, 19, 18, 20, 15
c) 20, 19, 18, 16, 15, 12, 11, 10
d) 19, 16, 18, 20, 11, 12, 10, 15

Let G=(V,E) be a directed, weighted graph with weight function w:E→R.
For some function f:V→R, for each edge (u,v)∈E, define w′(u,v) as w(u,v)+f(u)−f(v).
Which one of the options completes the following sentence so that it is TRUE ? “The shortest paths in G under w are shortest paths under w′ too, _________”.

a) for every f:V→R
b) if and only if ∀u∈V, f(u) is positive
c) if and only if ∀u∈V, f(u) is negative
d) if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is ___________ .

Graph G is obtained by adding vertex s to K_3,4 and making s adjacent to every vertex of K_3,4 . The minimum number of colours required to edge-colour G is _________ .

Consider a graph G=(V, E), where V = { v₁,v₂,…,v₁₀₀ }, E={ (v_i, v_j) ∣ 1<=i<j<=100 is ∣ i–j ∣ . The weight of minimum spanning tree of G is ________ .

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 _________

Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(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 ________

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) ___________ .

Consider the following statements:

a) I, II and III
b) I, III and IV
c) I, II and IV
d) II, III and IV

Let G be any connection, weighted, undirected graph:

a) I only
b) II only
c) Both I and II
d) Neither I nor II

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

a) B+ Tree is a height-balanced tree.
b) Non-leaf nodes have pointers to data records.
c) Key values in each node are kept in sorted order.
d) Key values in each node are kept in sorted order.

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

a) n!
b) (n-1)!
c) 1
d) ^(n-1)!/₂

G is undirected graph with n vertices and 25 edges such that each vertex has degree at least 3. Then the maximum possible value of n is ________

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

I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

a) I only
b) II only
c) Both I and II
d) Neither I nor II

Match the following:

a) P->(ii), Q->(iv), R->(i), S->(iii)
b) P->(ii), Q->(i), R->(iv), S->(iii)
c) P->(ii), Q->(iv), R->(iii), S->(i)
d) P->(iii), Q->(iv), R->(i), S->(ii)

Match the algorithms with their time complexities:

a) P-> (iii), Q -> (iv), R -> (i), S -> (ii)
b) P-> (iv), Q -> (iii), R -> (i), S -> (ii)
c) P-> (iii), Q -> (iv), R -> (ii), S -> (i)
d) P-> (iv), Q -> (iii), R -> (ii), S -> (i)

Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________.

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

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:

a) I only
b) II only
c) both I and II
d) neither I and II

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.

a) 4 and 15 respectively
b) 3 and 14 respectively
c) 4 and 14 respectively
d) 3 and 15 respectively

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 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 _____________

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 efficient algorithm to set the twin pointer in each entry in each adjacency list?

a) Θ(n²)
b) Θ(m+n)
c) Θ(m²)
d) Θ(n⁴)

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 * - ˆ -

B+ Trees are considered BALANCED because

a) the lengths of the paths from the root to all leaf nodes are all equal.
b) the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
c) the number of children of any two non-leaf sibling nodes differ by at most 1.
d) the number of records in any two leaf nodes differ by at most 1.

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.

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is_____

G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE

I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

a) I only
b) II only
c) both I and II
d) neither I nor II

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-fix the heap efficiently 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(d2^d) but not O(2^d)

What will be the output of the following C program?

a) 3 1 2 2 1 3 4 4 4
b) 3 1 2 1 1 1 2 2 2
c) 3 1 2 2 1 3 4
d) 3 1 2 1 1 1 2

What will be the output of the following C program?

a) 3 1 2 2 1 3 4 4 4
b) 3 1 2 1 1 1 2 2 2
c) 3 1 2 2 1 3 4
d) 3 1 2 1 1 1 2

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) Both P and Q
d) Neither P nor Q

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

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)

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

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

a) 256
b) 512
c) 1024
d) 2048

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) 3
d) 2

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

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

a) 284
b) 213
c) 142
d) 71

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

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) Ω(nlogn)
d) Ω(n²)

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

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

a) Θ(logn) for both insertion and deletion
b) Θ(n) for both insertion and deletion
c) Θ(n) for insertion and Θ(logn) for deletion
d) Θ(logn) for insertion and Θ(n) for deletion

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9, 18, 20, 25

a) I and IV only
b) II and III only
c) II and IV only
d) II only

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

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

a) θ (n)
b) θ (n+m)
c) θ(n²)
d) θ(m²)

Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

a) G₁ = (V,E₁) where E₁={(u,v)∣(u,v)∉E}
b) G₂ = (V,E₂) where E₂={(u,v)∣(v,u)∈E}
c) G₃ = (V,E₃) where E₃={(u,v)∣ there is a path of length ≤2 from u to v in E}
d) G₄= (V₄,E) where V₄ is the set of vertices in G which are not isolated