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.
(5 marks) 1077

1(b) What are the various techniques to represent Graphs in memory?
(5 marks) 2198

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

1(d) Convert the following expression to postfix.

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

(5 marks) 2181

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

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
(10 marks) 1948

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

(10 marks) 2209

3(b) Write a program in 'C' for Quick sort
(10 marks) 2204

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

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

4(c)Discuss some practical applications of trees
(5 marks) 2284

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

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

(10 marks) 2193

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.
(10 marks) 2207

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

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

(10 marks) 2206

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

6(c) Explain Threaded Binary Tree.
(5 marks) 2188