RGPV Computer Science (Semester 3)
Data Structures
December 2015
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

Solve any one question from Q.1(d) & Q.1(e)
1(a) Define sparse matrices.
2 M
1(b) What is garbage collection
2 M
1(c) Discuss tower of Hanoi problem
2 M
Solve any one question from Q.1(d) & Q.1(e)
1(d) Let X[11][8] be stored in column major order and X[2][2] be stored at 1024 and X[3][3] at 1084. Find the address of X[5][3] and X[1][1].
7 M
1(e) Write a program in C to search and display the position of an element in one dimensional array.
7 M

2(a) Define multi-queue
2 M
2(b) Discuss the dynamic representation of linked list.
2 M
2(c) Discuss the comparison between stacks and queues
2 M
Solve any one question from Q.2(d) & Q.2(e)
2(d) Discuss an algorithm for evaluation of postfix expression with example
7 M
2(e) Discuss the algorithm for insertion at a specified position in the linked list.
7 M

3(a) What is Huffman coding algorithm?
2 M
3(b) What are application of trees?
2 M
3(c) Define extended binary trees.
2 M
Solve any one question from Q.3(d) & Q.3(e)
3(d) Construct the AVL tree for the following set of elements 13,5,1,7,8,98,67,26,33,12,6,7,8
7 M
3(e) Construct B-tree of order 5 for the list of elements given as follows 1,7,6,2,11,4,8,13,12,5,19,9,18,24,5,12,14,20,21.
7 M

4(a) Define symbol table.
2 M
4(b) Discuss internal and external sorting
2 M
4(c) What are the collision resolution strategies?
2 M
Solve any one question from Q.4(d) & Q.4(e)
4(d) Discuss the algorithm of quick sort with example.
7 M
4(e) Search the element 39 in the following list using binary search 16,18,24,35,37,39,43,63,80,88 and also write the algorithm of binary search.
7 M

5(a) Define spanning tree
2 M
5(b) Define weakly connected graph
2 M
5(c) Discuss the representation of graph in computer.
3 M
Solve any one question from Q.5(d) & Q.5(e)
5(d) Discuss breadth first search algorithm with example.

7 M
5(e) Find the minimum spanning tree for the following graph using Prim's algorithm.

7 M

More question papers from Data Structures