# 2003 Centre for Development of Advanced Computing C DAC M C A Paper Code MCA 102 Subject Data Structure University Question paper

** University Question Papers **

**
**2003 Centre for Development of Advanced Computing C DAC M C A Paper Code MCA 102 Subject Data Structure University Question paper

End-Term Examination

Second Semester [MCA] – MAY 2003

Paper Code: MCA-102 Subject: Data Structure

Time: 3 Hours Maximum Marks: 60

Q. 1 (a) Explain why there might be ‘tradeoffs’ between saving computer (Execution)

time and saving programming time. 3

(b) Explain the difference between sequential array based representation and

linked representation of a list with examples. 4

(c) Explain the difference between internal and external sorting with example. 3

(d) Define Big-O notation. 2

Q. 2 (a) Write a procedure in C/C++ to add two single variable polynomial using

linked list. 7

(b) Write an algorithm that implement insertion and deletion operation on

circular queue. 5

Q. 3 (a) Formulate an algorithm to implement insertion sort. 6

(b) Derive time complexities for insertion sort, quick sort, and selection sort.

6

Q. 4 (a) Define B-Tree. What is the difference B-Tree and B+ -Tree. 5

(b) Construct an AVL tree in which element are inserted in following order :

72, 44, 100, 200, 30, 57, 10 5

(c) What is difference between tree, binary tree and a graph? 2

Q. 5 Write a non-recursive algorithm for preorder traversal of a tree. Give example

also. 12

Q. 6 (a) Write an algorithm to implement breadth first search for a graph. 6

(b) Taking an example of graph, show how depth first search operates on the

graph. 12

Q. 7 What is sparse matrix? Implement sparse matrix as an array. Give an algorithm to

add and subtract two sparse matrices for this implementation. 6

Q. 8 Write short notes on any three of the following :- 12

(a) Polyphase mergesort.

(b) Search Tree

(c) Inverted Tree

(d) Hashing