M.Tech – I Year – I Sem(Computer Science & Engg.) (R15D5801) ADVANCED DATA STRUCTURES AND ALGORITHMS

: Question paper Consists of 5 SECTIONS (One SECTION for each UNIT) and answer FIVE Questions, Choosing ONE Question from each SECTION. Each Question carries 15 marks. * * * * * * SECTION - I 1. a. write a program to merge two linked list one at the end of the other 8M b. write a program to transpose the matrix 7M (Or) 2. a. Explain asymptotic notations 7M b. write a program to multiply two matrices 8M SECTION – II 3. Convert the given infix expression into postfix expression x = (b + (b ^ 2 – 4*a*c)^1/2)/(2*a) and evaluate the postfix expression for the following values( a=1, b=4, c=3) 15M (Or) 4. a. write a pseudo code to implement a queue using two stacks 8M b. construct a max heap for the sequence of the input 24, 12, 2, 13, 32, 42, 7, 9, 41, 65, 1, 18 and 15. 7M SECTION – III 5. write a program to sort the elements using Quick sort 15M (Or) 6. a. Given two arrays of unordered numbers, check both arrays have same set of numbers using hash tables 8M b. Implement binary search tree 7M M.Tech (Computer Science and Engineering) R-15 Malla Reddy College of Engineering & Technology Page 11 SECTION – IV 7. a. Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences. inorder: a f b c d g e, postorder: a f c g e d b 8M b. Find the minimum cost spanning tree using kruskal’s algorithm for the given graph 7M (Or) 8. Consider the following directed graph. There are a multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Write the sequence of vertices and cost of the shortest path from S to T. Assume that, in any iteration the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered. 15M SECTION – V 9. Suppose eight characters have a distribution A(1), B(1), C(1), D(2), E(3), F(5), G(5), H(10). Draw a Huffman tree and calculate average number of bits nee