Netaji Subhas Open University (NSOU) 2009 M.C.A Data Structure & Algorithm - Question Paper

MCA 2.5

MCA (2nd Semester)

Term End exam – December, 2009

Data Structure & Algorithm

Paper – 2.5

Time : three Hours Full Marks : 75

ans ques. one and any 4 from the rest.

1. a) What is Data Structure ? [Marks 2]
b) Convert the subsequent to Postfix –
((A+B)*C)-(D-E) $ (F+G) [Marks 3]
c) State the various kinds of Sparse Matrix with examples. [Marks 3]
d) What is a Deque ? [Marks 2]
e) Write the concept of ADT with an example ? [Marks 3]
f) What is Ancester with example ? [Marks 2]

2. a) Write an algorithm to merge 2 arrays and finally sort them in ascending order. [Marks 7]
b) provide the algorithm of insertion of a node into a single linked list. [Marks 8]

3. a) discuss the Binary search algorithm [Marks 5]
b) elaborate the drawbacks of a Linear Queue ? [Marks 2]
c) What is Heap ? Develop the algorithm of Heap sort. Use suitable example
to discuss the algorithm and its complexity. [Marks 8]

4. a) Write the functions (using C. prog. Language) to implement the Push and
POP operation of a stack. [Marks 8]
b) Write the algorithm to convert an infix expression to postfix notation. [Marks 7]

5. a) Construct a Binary Tree with the subsequent data : [Marks 7]
Preorder Sequence : ACEGIFNKM
Inorder Sequence : ECIGANFKM
b) Write the algorithm of deletion of a node from an AVL Tree. [Marks 8]

6. a) discuss Prime's Algorithm [Marks 5]
b) What is Spanning Tree ? [Marks 3]
c) What is the difference ranging from the DFS and BFS ? [Marks 5]
d) discuss – A weighted Graph or a Network. [Marks 2]

7. Write short notes on (any three) [Marks 5*3=15]
a) Circular Linked List.
b) Priority Queue.
c) Hash Table.
d) Threaded Binary Tree.
e) Quick Sort.
f) Kruth-Morris-Pratt Algorithm.

Earning:   Approval pending.