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

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. List-I A. Prim’s algorithm for minimum spanning tree B. Floyd-Warshall algorithm for all-pairs shortest paths C. Mergesort D. Hamiltonian circuit List-II 1. Backtracking 2. Greed method 3. Dynamic programming 4. Divide and conquer Codes: A B C D (a) 3 2 4 1 (b) 1 2 4 3 (c) 2 3 4 1 (d) 2 1 3 4 2. Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting n ( ≥ 2) numbers? In the recurrence equations given in the options below, c is a constant. T(n)=2T(n/2)+cn T(n)=T(n−1)+T(1)+cn T(n)=2T(n−1)+cn T(n)=T(n/2)+cn 3. 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 4. Which of the following is/are correct in order 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 I and IV only II and III only II and IV only II only 5. 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 6. 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 (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 7. The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________. 8. Consider the following C function. int fun1 (int n) { int i, j, k, p, q = 0; for (i = 1; i less then n; ++i) { p = 0; for (j = n; j greater then 1; j = j/2) ++p; for (k = 1; k less p; k = k*2) ++q; } return q; } Which one of the following most closely approximates the return value of the function fun1? (A) n3 (B) n(logn)2 (C) nlogn (D) nlog(logn) 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 #computerscience #nargishgupta #gatecse