GATE Computer Science | Complete Paper Solution | Data Structures and Algorithm | GATE 2015- SET-2

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 2015. The questions are as follows: 1. 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) Ω(n2) 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 (A) Θ(nlogn) (B) Θ(n) (C) Θ(logn) (D) Θ(1) 3. A binary tree T has 20 leaves. The number of nodes in T having two children is ____. 4. Given below are some algorithms, and some algorithm design paradigms. A. Dijkstra’s Shortest Path B. Floyd-Warshall algorithm to compute all pairs shortest path C. Binary search on a sorted array D. Backtracking search on a graph 1. Divide and Conquer 2. Dynamic Programming 3. Greedy design 4. Depth-first search 5. Breadth-first search Match the above algorithms on the left to the corresponding design paradigm they follow Codes: A B C D (a) 1 3 1 5 (b) 3 3 1 5 (c) 3 2 1 4 (d) 3 2 1 5 5. 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) =i2 mod 10 (B) h(i) =i3 mod 10 (C) h(i) = (11 ∗ i2) mod 10 (D) h(i) = (12 ∗ i) mod 10 7. Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of a[] as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[] of size n using the partition function. We assume k≤n. int kth_smallest (int a[], int n, int k) { int left_end = partition (a, n); if (left_end+1==k) { return a[left_end]; } if (left_end+1 greater k) { return kth_smallest (___________); } else { return kth_smallest (___________); } } The missing arguments lists are respectively A. (a, left_end,k) and (a+left_end+1,n−left_end−1,k−left_end−1) B. (a, left_end,k) and (a,n−left_end−1,k−left_end−1) C. (a+ left_end+1,n−left_end−1,k−left_end−1) and (a, left_end,k) D. (a,n−left_end−1,k−left_end−1) and (a,left_end,k) I have created this free of cost YouTube channel for computer science and information technology students. Through this channel, I have tried to explain some important topics in a simple way. This channel is very helpful for computer science engineering students may be from GATE, NET, M.TECH, B.Tech, BCA, BSC, MCA, MSC etc. In this channel, I am trying to cover previous years solved GATE questions, Data Structures, Algorithm Design, Operating System, Data Base Management System(DBMS), Theory of computation (TOC), compiler design, C programming etc. My Channel URL: http://www.youtube.com/c/NargishGupta My Website URL: https://www.nargishgupta.com #gate2015 #gate #gatecse #computerscience #nargishgupta