Data Structures - May 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) State difference between Singly Linked List and Doubly Linked List data structures along with their applications.(5 marks) 1 (b) What is a graph? Explain methods to represent a graph.(5 marks) 1 (c) What is binary search tree? Explain with an example.(5 marks) 1 (d) What is data structure? List out the areas in which data structures are applied extensively?(5 marks) 2 (a) Write a program in C to implement the quick sort algorithm.(8 marks) 2 (b) Define traversal to binary tree. Explain different types of traversals of Binary tree with examples.(6 marks) 2 (c) Explain infix, postfix and prefix expressions with examples.(6 marks) 3 (a) What is a circular queue? Write a program in C implement circular queue.(10 marks) 3 (b) Explain linear and non-linear data structures with examples.(5 marks) 3 (c) Explain the term recursion with an example.(5 marks) 4 (a) Write a C program to convert infix expression into postfix expression.(10 marks) 4 (b) What is an AVL tree? Construct AVL tree for the following data. Mention the type of rotation for each case. 50, 25, 10, 5, 7, 3, 30, 20, 8, 15(10 marks) 5 (a) Write a C program to implement doubly linked list.
Provide following operations.
i) Insert at beginning
ii) Insert at location
iii) Remove from beginning
iv) Remove from Location(10 marks) 5 (b) What is Indexed Sequential Search? Write program in C to implement it.(10 marks) 6 (a) What is heap? Consider the following list of numbers:
15, 19, 10, 7, 17, 16
Sort these numbers using heap sort.(10 marks) 6 (b) Explain Huffman Algorithm with an example.(5 marks) 6 (c) What is a file? Explain various file handling operations in C.(5 marks)