Q.P. Code : 24783

[Time: 3 Hours] [ Marks: 80]

Please check whether you have got the right question paper.

N.B: 1. Question No.1 is compulsory.

1. Attempt any three questions of the remaining five questions.

2. Figures to the right indicate full marks.

3. Make suitable assumptions wherever necessary with proper justifications.

Q.1. a. Explain ADT. List the linear and Non-linear data structures with example. (5marks)

b. Explain B Tree and B+ Tree. (5marks)

c. Write a program to implement Binary search on sorted set of integers (10marks)

Q. 2. a. Write a program to convert Infix expression into Post-fix expression. (10marks)

b. Explain Huffman Encoding with an example. (10marks)

Q.3. a. Write a program to implement Doubly Linked List. Perform the following operations: (10marks)

1] Insert a node in the beginning.

2] Insert a node in the end.

3] Delete a node from the end.

4] Display the list.

b. Explain Topological sorting with example. (10marks)

Q.4. a. Write a program to implement Quick sort. Show the steps to sort the given numbers: (10marks)

25, 13, 7, 34, 56, 23, 13, 96, 14, 2

b. Write a program to implement linear queue using array. (10marks)

Q.5. a. Write a program to implement STACK using Linked List. What are the advantages of linked list over array. (10marks)

b. Write a program to implement Binary Search Tree [BST], Show BST for the following input: 10, 5, 4 12, 15, 11, 3 (10marks)

Q.6. Write Short notes on [any two] (20marks)

a] AVL Tree.

b] Graph Traversal Techniques.

c] Expression Trees.

d] Application of Linked list - Polynomial Addition.