Data Structures - May 2016

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) Define ADT with an example(3 marks) 1(b) What are the advantages of using linked lists over arrays?(5 marks) 1(c) Describe Expression Tree with an example.(5 marks) 1(d) Write a program in C to implement Insertion Sort(7 marks) 2(a) Discuss file I/O in C language with different library functions.(10 marks) 2(b) Explain recursion as an application of stack with examples.(10 marks) 3(a) Write a menu driven program in C to implement QU/EUE ADT. The program should perform the following operations:
(i) Inserting an Element in the Queue
(ii) Deleting Element from the Queue
(iii) Displaying the Queue
(iv) Exiting the program(12 marks) 3(b) Write a function to implement indexed Sequential Search, Explain with an Example(8 marks) 4(a) Write a C program to implement a Doubly Linked List which performs the following operations:
(i) Inserting element in the beginning
(ii) inserting element in the end
(iii) Inserting element after an element
(iv) Deleting a particular element
(v) Displaying the list(12 marks) 4(b) Apply Huffman Coding for the word 'MALAYALAM'. Give the Huffman code for each symbol.(8 marks) 5(a) Explain any one application of linked with an example.(8 marks) 5(b) Write a program in C to delete a node from a Binary Search Tree. The program should consider all the possible cases.(12 marks) 6(a) Write a program in C to implement the BFS traversal of a graph. Explain the code with an example.(10 marks) 6(b) Hash the following in a table of size 11. Use any two collision resolution techniques:
23, 55, 10, 71, 67, 32, 100, 18, 10, 90, 44.(10 marks)