GATE Computer Science | Complete Paper Solution | Data Structures and Algorithm | GATE 2016

In this video, I have discussed the GATE computer science and engineering paper solution based on data structures and algorithm. In this video, I have explained all questions of gate 2016. The questions are as follows: 1. The worst-case running times of Insertion sort, Merge sort and Quicksort, respectively, are: (A) Θ(n log n), Θ(n log n) and Θ(n2) (B) Θ(n2), Θ(n2) and Θ(n Log n) (C) Θ(n2), Θ(n log n) and Θ(n log n) (D) Θ(n2), Θ(n log n) and Θ(n2) 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? P: Minimum spanning tree of G does not change. Q: Shortest path between any pair of vertices does not change. A. P only B. Q only C. Neither P nor Q D. Both P and Q 3. The attributes of three arithmetic operators in some programming language are given below. Operator Precedence Associativity Arity + High Left Binary - Medium Right Binary * Low Left Binary The value of the expression 2 – 5 + 1 – 7 * 3 in this language is __________ ? 4. 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. 5. 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(2d) but not O(d) (D) O(d2d) but not O(2d) 6. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? I. Quicksort runs in Θ(n2) time II. Bubblesort runs in Θ(n2) time III. Mergesort runs in Θ(n) time IV. Insertion sort runs in Θ(n) time A. I and II only B. I and III only C. II and IV only D. I and IV only 7. The Floyd-Warshall algorithm for all-pair shortest paths computation is based on: (A) Greedy paradigm. (B) Divide-and-Conquer paradigm. (C) Dynamic Programming paradigm. (D) Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm. 8. 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 _____________ 9. 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 * – ˆ – 10. 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) The worst-case time complexity for both operations will be Ω(log n) 11. The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(nα), then the least possible value (accurate up to two decimal positions) of α is ________. Flow chart for Recursive Function A(n). My Website URL: https://www.nargishgupta.com #gate2016 #gate #computerscience #nargishgupta #gatecse