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

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 2017. The questions are as follows: 1. The Breadth-First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is (A) MNOPQR (B) NQMPOR (C) QMNPRO (D) QMNPOR 2. Consider the following recurrence relation: T(n)=2T(n^1/2)+1 (A) θ(loglogn) (B) θ(logn) (C) θ(sqrt(n)) (D) θ(n) 3.Consider the following C function. int fun(int n) { int i, j; for (i = 1; i = n ; i++) { for (j = 1; j =n; j += i) { printf("%d %d", i, j); } } } Time complexity of fun in terms of θ notation is: (A) θ(n√n) (B) θ(n2) (C) θ(nlogn) (D) θ(n 2 log n) 4. Match the algorithms with their time complexities: P. Tower of Hanoi (i) O(n^2) Q. Binary search given n sorted numbers (ii) O(nlogn) R. Heap sort given n numbers at the worst case (iii) O(2^n) S.Addition matrix of n*n matrices. (iv) O(logn) (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) 5. 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)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. A. (I) only. B. (II) only. C. Both (I) and (II). D. Neither (I) nor (II). 6.A message is made up entirely of characters from the set X = {P,Q,R,S,T} . The table of probabilities of each character is shown below : A message of 100 characters over X is encoded using Huffman coding. Then the excepted length of the encoded message in bits is _____ (A) 225 (B) 226 (C) 227 (D) 228 7. 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: (A) 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20 (B) 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12 (C) 7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12 (D) 7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 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 #gate2017 #gate #computerscience #nargishgupta My Website URL: https://www.nargishgupta.com