MU Computer Engineering (Semester 3)
Data Structures
December 2014
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) What is recursion? Write a 'C' program to calculate sum of 'n' natural numbers using recursion.
5 M
1 (b) What is a Multiway Search Tree. Explain with an example.
5 M
1 (c) Give ADT for the queue data structure. Discuss in brief any two applications of the queue data structure.
5 M
5 M

2 (a) Write a 'C' program to implement a priority queue.
8 M
2 (c) Explain with examples different techniques to represent the graph data structure on a computer. Give 'C' language representations for the same.
5 M

3 (a) Consider the following list of numbers:
67, 12, 89, 26, 38, 45, 22, 79, 53, 9, 61.
Sort these numbers using Heap Sort.
10 M
3 (b) Write a 'C' program to implement a 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 a specific node
v) Displaying the list.
10 M

4 (a) Write a 'C' program to convert a polish notation to reverse polish notation.
10 M
4 (b) Consider the following list of numbers:
18, 25, 16, 36, 08, 29, 45, 12, 32, 9.
Create a binary search tree using these numbers and display them in a non decreasing order. Write a 'C' program for the same.
10 M

5 (a) Discuss how memory allocation for a sparse matrix can be optimized using a linked list. Write a C-program for the same.
15 M
5 (b) Write a function for DFS traversal of graph. Explain its working with an example.
5 M

6 (a) Insert the following elements in AVL tree: 44, 17, 32, 78, 50, 88, 48, 62, 54.
Explain the different rotations that will be used.
10 M
6 (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 M

More question papers from Data Structures