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

** University Question Papers **

**
**2004 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 2004

Paper Code: MCA-102 Subject: Data Structure

Time: 3 Hours Maximum Marks: 60

Q. 1 (a) What is difference between Big-O and Small-O notation. Define them. 4

(b) Give an example of algorithm that has following complexity (in terms of

Big-O). 4

(i) O (1) (ii) O(N)

(iii) O (N2) (iv) O (n log n)

(c) Algorithm 1 does a particular task in time N3 where N is no. of elements

processed. Algorithm 2 does same task in time 3N + 1000. 4

(i) What are Big-O requirement of each algorithm.

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

executes more quickly than ‘more efficient’ algorithm?

Q. 2 (a) Write a procedure to print elements of a singly linked list in reverse order

while traversing it only once. 6

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

pointer accessing the ‘rear’ element: 6

(i) Draw a sketch of such a queue with one node.

(ii) Write a algorithm for insertion and deletion.

Q. 3 (a) Write an algorithm to implement selection sort. 7

(b) Sort the following numbers (Showing each iteration) using 5

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

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

Also, write an algorithm to evaluate postfix expression. 12

Q. 5 Define sparse matrix. Implement sparse matrix as an array. Give an algorithm to

transpose a sparse matrix for this implementation. 12

Q. 6 (a) What do you mean by file organization? Differentiate between sequential,

hashed and random file organization. 6

(b) What is aim of hashing? What are different hashing techniques? What are the

problems encountered in them and how to overcome them. 6

Q. 7 (a) Write a algorithm for topological sort of a graph. 7

(b) Taking an example of a graph. Show how breadth first search operates on this

graph. 5

Q. 8 Write short notes on any three of the following :- 3 x 4

(a) Balanced Merge sort

(b) Critical path

(c) B+ tree

(d) B-tree