Data Structures - Dec 2014

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) What is recursion? Write a 'C' program to calculate sum of 'n' natural numbers using recursion.(5 marks) 1 (b) What is a Multiway Search Tree. Explain with an example.(5 marks) 1 (c) Give ADT for the queue data structure. Discuss in brief any two applications of the queue data structure.(5 marks) 1 (d) Compare and contrast Quicksort and Radix sot on basis of their advantages and disadvantages.(5 marks) 2 (a) Write a 'C' program to implement a priority queue.(8 marks) 2 (c) Explain with examples different techniques to represent the graph data structure on a computer. Give 'C' language representations for the same.(5 marks) 3 (a) Consider the following list of numbers:
67, 12, 89, 26, 38, 45, 22, 79, 53, 9, 61.
Sort these numbers using Heap Sort.(10 marks) 3 (b) Write a 'C' program to implement a singly Linked List which supports the following operations:
i) Insert a node in the beginning
ii) Insert a node in the end
iii) Insert a node after a specific node
iv) Deleting a specific node
v) Displaying the list.(10 marks) 4 (a) Write a 'C' program to convert a polish notation to reverse polish notation.(10 marks) 4 (b) Consider the following list of numbers:
18, 25, 16, 36, 08, 29, 45, 12, 32, 9.
Create a binary search tree using these numbers and display them in a non decreasing order. Write a 'C' program for the same.(10 marks) 5 (a) Discuss how memory allocation for a sparse matrix can be optimized using a linked list. Write a C-program for the same.(15 marks) 5 (b) Write a function for DFS traversal of graph. Explain its working with an example.(5 marks) 6 (a) Insert the following elements in AVL tree: 44, 17, 32, 78, 50, 88, 48, 62, 54.
Explain the different rotations that will be used.(10 marks) 6 (b) Write a 'C' program to search a list using Indexed Sequential Search. What are the advantages of using Indexed Sequential Search over Sequential Search?(10 marks)