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

Saturday, 02 February 2013 02:00Web

End-Term exam

Second Semester [MCA] – MAY 2004

Paper Code: MCA-102 Subject: Data Structure

**Time:**three Hours

**Maximum Marks**: 60

**Q.**one

**(**What is difference ranging from Big-O and Small-O notation. describe them. 4

**a)****(**provide an example of algorithm that has subsequent complexity (in terms of

**b)**Big-O). 4

**(**O

**i)****(**

**1)****(**O(N)

**i****i)****(**O (N

**i****i****i)****2)**

**(**O (n log n)

**i****v)****(**Algorithm one does a particular task in time N3 where N is no. of elements

**c)**processe

**d.**Algorithm two does identical task in time 3N + 1000. 4

**(**elaborate Big-O requirement of every algorithm.

**i)****(**Under what conditions, if any, would the ‘less efficient’ algorithm

**i****i)**executes more quickly than ‘more efficient’ algorithm?

**Q.**two

**(**Write a procedure to print elements of a singly linked list in reverse order

**a)**while traversing it only onc

**e.**6

**(**Let a queue be implemented as a circular linked structure with an external

**b)**pointer accessing the ‘rear’ element: 6

**(**Draw a sketch of such a queue with 1 node.

**i)****(**Write a algorithm for insertion and deletion.

**i****i)****Q.**three

**(**Write an algorithm to implement selection sort. 7

**a)****(**Sort the subsequent numbers (Showing every iteration) using 5

**b)**Quick Sort :- 57, 73, 43, 77, 83, 63, 87.

**Q.**four Write a algorithm to convert infix expression to postfix expression using stack.

Also, write an algorithm to evaluate postfix expression. 12

**Q.**five describe sparse matr

**i**Implement sparse matrix as an array. provide an algorithm to

**x.**transpose a sparse matrix for this implementation. 12

**Q.**six

**(**What do you mean by file organization? Differentiate ranging from sequential,

**a)**hashed and random file organization. 6

**(**What is aim of hashing? elaborate various hashing techniques? elaborate the

**b)**issues encountered in them and how to overcome them. 6

**Q.**seven

**(**Write a algorithm for topological sort of a graph. 7

**a)****(**Taking an example of a graph. Show how breadth 1st search operates on this

**b)**graph. 5

**Q.**eight Write short notes on any 3 of the subsequent :- three x 4

**(**Balanced Merge sort

**a)****(**Critical path

**b)****(**B+ tree

**c)****(**B-tree

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