DATA STRUCTURES (DS), B.E. Computer Science (CS), Semester 3, December 2013.

DATA STRUCTURES (DS), B.E. Computer Science (CS),

Semester 3, December 2013.

Con.8613-13

GX-12113

(3 Hours)

[Total Mark: 80]

N. B.: (1) Question no 1 is compulsory.

(2) Attempt any three questions out of the remaining five questions.

(3) Make suitable assumptions wherever necessary bust justify your assumptions.

(4) Figure to the right indicates full marks.

1. (a) Explain linear and non-linear data structure with examples. --- (5 Marks)

(b) Explain various techniques of graph representations. --- (5 Marks)

(c) Write a “C” program to convert decimal to binary using any appropriate data structure you have studied. --- (7 Marks)

(d) Define ADT with an 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 given: --- (10 Marks)

Characters	A	B	C	D	E
Frequency	20	10	10	30	30

(b) Write a program in “C” to evaluate a postfix expression. --- (10 Marks)

3. (a) Write a program in “C” to implement a circular queue. The following operations should be performed by the program: --- (12 Marks)

I. Creating the queue.

II. Deleting from the queue.

III. Inserting in the queue.

IV. Displaying all the elements of the queue.

(b)Sort the following elements using radix Sort: --- (8 Marks)

121,

70,

965,

432,

12,

577,

683

4. (a) What a “C” program to create a “Single Linked List” ADT. The ADT should support the following functions: --- (12 Marks)

I. Creating a Linked List.

II. Inserting a node after a specific node.

III. Deleting a node

IV. Displaying the list.

(b) Explain various graph traversal techniques with examples. --- (8 Marks)

5. (a) Discuss AVL trees. Insert the following elements in a AVL search tree: --- (10 marks)

27,

25,

23,

29,

35,

33,

34

(b) Using linear probing and quadratic probing insert the following values in a Hash table of size 10. Show how many collisions occur in each technique: --- (10 Marks)

99,

33,

23,

44,

56,

43,

19

6. (a) Explain indexed sequential search with a suitable example. What are the advantages and disadvantages of indexed sequential search? --- (10 Marks)

(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)