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 (a) What is difference ranging from Big-O and Small-O notation. describe them. 4
(b) provide an example of algorithm that has subsequent complexity (in terms of
Big-O). 4
(i) O (1) (ii) O(N)
(iii) O (N2) (iv) O (n log n)
(c) Algorithm one does a particular task in time N3 where N is no. of elements
processed. Algorithm two does identical task in time 3N + 1000. 4
(i) elaborate Big-O requirement of every algorithm.
(ii) Under what conditions, if any, would the ‘less efficient’ algorithm
executes more quickly than ‘more efficient’ algorithm?
Q. two (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 1 node.
(ii) Write a algorithm for insertion and deletion.
Q. three (a) Write an algorithm to implement selection sort. 7
(b) Sort the subsequent numbers (Showing every iteration) using 5
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 matrix. Implement sparse matrix as an array. provide an algorithm to
transpose a sparse matrix for this implementation. 12
Q. six (a) What do you mean by file organization? Differentiate ranging from sequential,
hashed and random file organization. 6
(b) What is aim of hashing? elaborate various hashing techniques? elaborate the
issues encountered in them and how to overcome them. 6
Q. seven (a) Write a algorithm for topological sort of a graph. 7
(b) Taking an example of a graph. Show how breadth 1st search operates on this
graph. 5
Q. eight Write short notes on any 3 of the subsequent :- three x 4
(a) Balanced Merge sort
(b) Critical path
(c) B+ tree
(d) B-tree
| Earning: Approval pending. |
