Data Structures - Dec 2015

Computer Engineering (Semester 3)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks. 1 (a) Write a function to implement an HUFFMAN coding given a symbol and its frequency occurance.(10 marks) 1 (b) Write a function to count the leaf nodes in Binary tree and Branch modes in Binary tree.(10 marks) 2 (a) Explain Linked list as an ADT. Write a function for deletion of a node from Doubly linked list?(10 marks) 2 (b) What do you mean by Sparse matrix? How one can implement sparse matrix using Linked list? Support your answer with an example.(10 marks) 3 (a) Explain STACK and ADT? Write a function in C to convert prefix expression to postfix expression.(10 marks) 3 (b) Write a function in C to maintain 2 stack in a single array.(10 marks) 4 (a) Explain Queue as ADT? Write a function in C to insert, delete and display elements in Circular Queue.(10 marks) 4 (b) Explain the concept of threaded binary search tree? Show the declaration of a node in threaded binary search tree? Write a function for inorder traversal of threaded binary search tree.(10 marks) 5 (a) What are different methods for traversing the graph? Explain DFS in detail with an example. Write a function for DFS.(10 marks) 5 (b) Write a function for creating a tree if IN-ORDER traversal and POST-ORDER traversal of a tree is given.(10 marks) 6 (a) Write an algorithm for Shell sort. Sort the following numbers in ascending order 23, 12, 45, 54, 76, 67, 88, 97, 54 using shell sort. Show output after each pass.(10 marks) 6 (b) Explain Index sequential Search with an example.(10 marks)