Data Structures - Dec 2013
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) Explain linear and non-linear data structures with examples.(5 marks) 1 (b) Explain various techniques of graph representation.(5 marks) 1 (c) Write a 'C' program to convert decimal to binary using any approprite data structure you have studdied.(7 marks) 1 (d) Define ADT with example.(3 marks) 2 (a) What is Huffman Coding. Construct the Huffman Tree and determine the code for the following characters whose frequencies are as gien :-
(i) Creating the queue.
(ii) Deleting from the queue.
(iii) Inserting in the queue.
(iv) Displaying all the elements of the queue.(12 marks) 3 (b) Sort the following elements using Radix Sort :-
121, 70, 965, 432, 12, 577, 683.
What is the limitations of Radix Sort ?(8 marks) 4 (a) Write a 'C' program to create a "Single Linked List" ADT. The ADT shpuld support the following functions :-
(i) Creating a Linked List
(ii) Inserting a node after a specific node.
(iii) Deleting a node.
(iv) Displaying the list.(12 marks) 4 (b) Explain various graph traversal techniques with examples.(8 marks) 5 (a) Discuss AVL trees. Insert the following elements in a AVL search tree :-
27, 25, 23, 29, 35, 33, 34.(10 marks) 5 (b) Using linear probing and quadratic probing insert the following values in a hash table of size 10. show how many collision occur in each techniques :-
99, 33, 23, 44, 56, 43, 19.(10 marks) 6 (a) Explain indexed sequential search with suitable example. What are the advantages and disadvantages of indexed sequential search ?(10 marks) 6 (b) Write a program in 'C' for deletion of a node from a Binary Search Tree. The program should consider all the cases.(10 marks)