Question Paper: Data Structures Question Paper - May 17 - Computer Engineering (Semester 3) - Mumbai University (MU)

0

## Data Structures - May 17

### Computer Engineering (Semester 3)

Total marks: 80

Total time: 3 Hours
INSTRUCTIONS

(1) Question No. 1 is compulsory

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

(3) Draw neat diagrams wherever necessary

**1(a)**Explain different types of Data Structures with example.

**1(b)**What are the various techniques to represent Graphs in memory?

**1(c)**What is recursion? Write a recursive function in 'C' to find sum of digits of a number.

**1(d)**Convert the following expression to postfix.

$$ (f-g)* ((a+b)* (c-d)) / e $$

**2(a)**What is Huffman coding? Construct the Huffman Tree and determine the code for each symbol in the sentence "ENGINEERING".

**2(b)**Write a 'C' program to implement singly linked list which supports the following operations.

- (i) Insert a node in the beginning
- (ii) Insert a node in the end
- (iii) Insert a node after a specific node
- (iv) Deleting element from the beginning
- (v) Displaying the list
- (vi) Exit

**3(a)**Using Linear probing and Quadratic Probing insert the following values in a hash table of size 10. Show how many collisions occur in each interation:

28, 55, 71, 67, 11, 10, 90, 44

**3(b)**Write a program in 'C' for Quick sort

**4(a)**Write a Progam in 'C' to implement Doubly linked list with methods insert, delete and search.

**4(b)**compare Quick Sort and Radix sort based on their advantages and disadvantages.

**4(c)**Discuss some practical applications of trees

**5(a)**Explain AVL trees. Insert the following elements in a AVL search tree:

63, 52, 49, 83, 92, 29, 23, 54, 13, 99

**5(b)**Write a 'C' program to search a list using Indexed Sequential search. What are the advantages of using Indexed Sequential Search over Sequential Search.

**6(a)**What is Heap? Sort the following numbers using Heap Sort.

67, 12, 89, 26, 38, 45, 22, 79, 53

**6(b)**Give ADT for the queue data structure. Discuss any two applications of queue data structure.

**6(c)**Explain Threaded Binary Tree.