[solved] data structures gate previous year questions
data structures gate previous year questions with solutions
Q1➡| GATE 2021 Set-1 Consider the following statements. S1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2:The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct?
Q2➡| GATE 2021 Set-1 A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
Q3➡| GATE 2021 Set-1 Consider a dynamic hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the main hash table. 3. Initially, the main hash table entries are empty. 4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand. 5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees. 6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit. 7. A split is done only if it is needed, i.e., only when there is a collison.
Consider the following state of the hash table. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
Q4➡| GATE 2021 Set-1 Consider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s=pop(); Consider the following sequence of operations on an empty queue. enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue(); The value of s + q is __
Q7➡| GATE 2021 Set-2 Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?
Q8➡| GATE 2021 Set-2 Consider a complete binary tree with 7 nodes, Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of |A – B| is _______.
Q10➡| GATE 2021 Set-2 Assume that the variable y points to a struct (allocated on the head) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and de-reference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:
Q14➡| GATE 2020 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?
Q15➡| GATE 2020 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?
Q16➡| GATE 2020 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 _______.
Q18➡|GATE 2020 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.
Q19➡|GATE 2020 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, _________”.
i ➥ if and only if ∀u ∈ V, f(u) is negative
ii ➥ for every f: V→R
iii ➥ if and only if ∀u ∈ V, f(u) is positive
iv ➥ 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
Q20➡|GATE 2020 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 _______.
Q25➡| GATE 2019 Consider the following C function: Which one of the following will happen when the function convert is called with any positive integer n as argument?
i ➥ It will print the binary representation of n and terminate.
ii ➥ It will print the binary representation of n in the reverse order and terminate.
iii ➥ It will print the binary representation of n but will not terminate.
iv ➥ It will not print anything and will not terminate.
Q26➡| GATE 2019 Consider the following statements: I. The smallest element in a max-heap is always at a leaf node. II. The second largest element in a max-heap is always a child of the root node. III. A max-heap can be constructed from a binary search tree in Θ(n) time. IV. A binary search tree can be constructed from a max-heap in Θ(n) time.
Q27➡|GATE 2019 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) __________.
Q29➡|GATE 2019 Consider the following C program: The number of times the variable sum will be printed, when the above program is executed, is ________.
Q30➡| GATE 2018 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?
Q32➡| GATE 2018 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_____.
Q34➡|GATE 2018 Consider the following C code. Assume that unsigned long int type length is 64 bits. The value returned when we call fun with the input 240 is
Q38➡| GATE 2017 Set-1 Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: Note: The height of a tree with a single node is 0.
Q39➡| GATE 2017 Set-1 Consider the C code fragment given below. Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will
i ➥ either cause a null pointer dereference or append list m to the end of list n.
ii ➥ cause a null pointer dereference for all inputs.
iii ➥append list n to the end of list m for all inputs.
iv ➥append list m to the end of list n for all inputs.
Q44➡|GATE 2017 Set-1 Consider the following C program: Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int. The output of the program is _________.
Q47➡| GATE 2017 Set-2 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?
Q49➡| GATE 2017 Set-2 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? I: Next pointer of front node points to the rear node. II: Next pointer of rear node points to the front node.
Q50➡| GATE 2017 Set-2 Consider the C program fragment below which is meant to divide x and y using repeated subtractions. The variables x, y, q and r are all unsigned int. Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y*q + r)?
Q51➡| GATE 2017 Set-2 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:
Q52➡|GATE 2017 Set-2 Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y. The output of the program is _______.
Q55➡|GATE 2016 Set-1 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)?
i ➥ Both operations can be performed in O(1) time
ii ➥ At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
iii ➥ The worst case time complexity for both operations will be Ω(n)
iv ➥ Worst case time complexity for both operations will be Ω(logn)
Q56➡| GATE 2016 Set-1 Consider the following directed graph: The number of different topological orderings of the vertices of the graph is ___________.
Q57➡| GATE 2016 Set-1 Consider the following C program: Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
Q58➡| GATE 2016 Set-1 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? • P: Minimum spanning tree of G does not change • Q: Shortest path between any pair of vertices does not change
Q60➡| GATE 2016 Set-1 The following function computes the maximum value contained in an integer array p[] of size n (n >= 1). The missing loop condition is
Q63➡| GATE 2016 Set-1 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?
Q64➡|GATE 2016 Set-1 Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry Wij 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 ________.
Q65➡|GATE 2016 Set-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. The maximum possible number of iterations of the while loop in the algorithm is ___________.
Q66➡| GATE 2016 Set-1 Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y’ reduces to W, and Z reduces to X’ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
i ➥ W can be recursively enumerable and Z is recursive.
ii ➥ W can be recursive and Z is recursively enumerable.
iii ➥ W is not recursively enumerable and Z is recursive.
iv ➥ W is not recursively enumerable and Z is not recursive.
Q67➡| GATE 2016 Set-2 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 _________.
Q69➡| GATE 2016 Set-2 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) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together?
Q70➡| GATE 2016 Set-2 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 ________.
Q71➡| GATE 2016 Set-2 The following function computes XY for positive integers X and Y. Which one of the following conditions is TRUE before every iteration of the loop?
Q72➡| GATE 2016 Set-2 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:
Q74➡| GATE 2016 Set-2 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.
Q75➡|GATE 2016 Set-2 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?
Q76➡| GATE 2015 Set-1 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
Q80➡|GATE 2015 Set-1 Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
Q81➡| GATE 2015 Set-1 What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory. int main() { unsigned int x[4][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; printf(“%u, %u, %u”, x+3, *(x+3), *(x+2)+3); }
Q84➡| GATE 2015 Set-2 An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
Q86➡| GATE 2015 Set-2 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
Q89➡|GATE 2015 Set-2 A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries. When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is __________.
Q90➡| GATE 2015 Set-2 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?
Q95➡| GATE 2015 Set-3 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
