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

Saturday, 02 February 2013 01:55Web

End-Term exam

Second Semester [MCA] – MAY 2003

Paper Code: MCA-102 Subject: Data Structure

**Time:**three Hours

**Maximum Marks**: 60

**Q.**one

**(**discuss why there might be ‘tradeoffs’ ranging from saving computer (Execution)

**a)**time and saving programming tim

**e.**3

**(**discuss the difference ranging from sequential array based representation and

**b)**linked representation of a list with examples. 4

**(**discuss the difference ranging from internal and external sorting with exampl

**c)****e.**3

**(**describe Big-O notation. 2

**d)****Q.**two

**(**Write a procedure in C/C++ to add 2 single variable polynomial using

**a)**linked list. 7

**(**Write an algorithm that implement insertion and deletion operation on

**b)**circular queu

**e.**5

**Q.**three

**(**Formulate an algorithm to implement insertion sort. 6

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

**b)**6

**Q.**four

**(**describe B-Tre

**a)****e.**What is the difference B-Tree and B+ -Tre

**e.**5

**(**Construct an AVL tree in which element are inserted in subsequent order :

**b)**72, 44, 100, 200, 30, 57, 10 5

**(**What is difference ranging from tree, binary tree and a graph? 2

**c)****Q.**five Write a non-recursive algorithm for preorder traversal of a tre

**e.**provide example

also. 12

**Q.**six

**(**Write an algorithm to implement breadth 1st search for a graph. 6

**a)****(**Taking an example of graph, show how depth 1st search operates on the

**b)**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

**(**Polyphase mergesort.

**a)****(**Search Tree

**b)****(**Inverted Tree

**c)****(**Hashing

**d)**Earning: Approval pending. |