MU Computer Engineering (Semester 3)
Data Structures
December 2016
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) Explain linear and non-linear data structure with example
5 M
1(b) Write ADT for stack. Give application of stack.
5 M
1(c) Explain practical applications of trees.
5 M
1(d) What is file? Explain various file handling operations in C.
5 M

2(a) Write a program in C to perfrom Quick sort. Show steps with example.
10 M
2(b) Explain Circular queue and Double ended queue with example.
10 M

3(a) Write a program to convert and expression fro infix to postfix using stack.
10 M
3(b) Write a function for BFS traversal of graph.
10 M

4(a) Write a program in C to create a singly linked list and perform the following operations:
i) Insert into list
ii) Search for data
iii) Delete from list
iv) Display data.
10 M
4(b) Insert the following elements in a AVJ search tree:
40,
23,
32,
84,
55,
88,
46,
71,
57 Explain different rotations used in AVL trees
10 M

5(a) Write a program to constract binary tree for the following pre-order and in-order traversal sequences. Pre-Orde: A B D G C E H I F
In-Order: D G B A H E IC F
10 M
5(b) What is hashing ? What is mean by collision? Using modulo division method insert the following values in a hash table of size 10. Show how many collisions occurred. 99,
33,
23,
44,
56,
43,
19
10 M
5(b) Let A ={1,
2,
3,
4} and let R={(1,
2)
(2,
3)
(3,
4)
(2,
1)} Find transitive closure of R by using Warshall's algorithm.
6 M
5(c) Prove that the set A={0,
1,
2,
3,
4,
5} is a finite Abelian group unde addition modulo6.
8 M

Write short notes on any four of the following Q6.(1,2,3,4,5)
6(1) Huffman coding
5 M
6(2) Iteration VS Recursion
5 M
6(3) Various techniques of Graph representation
5 M
6(4) Threaded binary tree
5 M
6(5) Heap Sort
5 M
6(a) Find the oridinary generating functions for the given sequences:
i) {1,
2,
3,
4,
5....}
{2,
2,
2,
2....}
iii) {1,
1,
1,
1....}
6 M
6(b) Define group, monoid, semigroup.
6 M
6(c) Solve the following recurrence relation:$$a_n-7a_{a-1}+10a_{a-2}=0$$/ with initial condition a0=1,
a2=6
8 M

More question papers from Data Structures