Centre for Development of Advanced Computing(C-DAC) 2003 M.C.A Code: -102 Subject: Data Structure - Question Paper

End-Term exam
Second Semester [MCA] – MAY 2003

Paper Code: MCA-102 Subject: Data Structure
Time: three Hours Maximum Marks: 60

Q. one (a) discuss why there might be ‘tradeoffs’ ranging from saving computer (Execution)
time and saving programming time. 3
(b) discuss the difference ranging from sequential array based representation and
linked representation of a list with examples. 4
(c) discuss the difference ranging from internal and external sorting with example. 3
(d) describe Big-O notation. 2

Q. two (a) Write a procedure in C/C++ to add 2 single variable polynomial using
linked list. 7
(b) Write an algorithm that implement insertion and deletion operation on
circular queue. 5

Q. three (a) Formulate an algorithm to implement insertion sort. 6
(b) Derive time complexities for insertion sort, quick sort, and selection sort.
6

Q. four (a) describe B-Tree. What is the difference B-Tree and B+ -Tree. 5
(b) Construct an AVL tree in which element are inserted in subsequent order :
72, 44, 100, 200, 30, 57, 10 5
(c) What is difference ranging from tree, binary tree and a graph? 2

Q. five Write a non-recursive algorithm for preorder traversal of a tree. provide example
also. 12

Q. six (a) Write an algorithm to implement breadth 1st search for a graph. 6
(b) Taking an example of graph, show how depth 1st search operates on the
graph. 12

Q. seven What is sparse matrix? Implement sparse matrix as an array. provide an algorithm to
add and subtract 2 sparse matrices for this implementation. 6

Q. eight Write short notes on any 3 of the subsequent :- 12
(a) Polyphase mergesort.
(b) Search Tree
(c) Inverted Tree
(d) Hashing

Earning:   Approval pending.