Data Structure & Algorithms (December 2011)

Data Structure & Algorithms (December 2011)

(3 Hours)

[Total Mark 100]

N.B.: (1) Question No. 1 is compulsory.
(2) Attempt any four questions from remaining six questions.

1. (a) Explain the Asymptotic notations to measure the time complexity of algorithm.—5 Marks
(b) What are linear and non – linear data structures? ---- 5 Marks
(c) Explain vectors with at least five methods.—5 Marks
(d) Discuss circular and priority Queue.—5 Marks

2. (a) Write a program to create ‘QUEUE’ ADT using Linked list implementation . ADT should support                 following operations:--10 Marks

1. Create queue
2. Enqueue
3. Dqueue
4. Display

(b) Explain Huffman Coding Algorithm with example.—10 Marks

3. (a) Write a program to implement Quick Sort and comment on its complexity. –10 Marks
    (b) Implement the function to delete a node from Binary search tree. (Consider all possible cases).
         10 Marks
4. (a) Write a program to create Binary tree and inorder, preorder and postorder traversal of the tree.—
          10 Marks
(b) Write any pattern matching algorithm and explain it with suitable example.—10 Marks

5. (a) Using Prism’s and Kruskal’s algorithm, find minimum spanning tree for the following graph. –
          10 Marks

(b) What is Hashing ? What is meant by Collision? Hash the following in table of size 10. Use any two                 collision resolution techniques:--10 Marks

99

33

23

44

56

43

19

6. (a) Given a ‘INFIX’ expression, write a program to convert it to its ‘POSTFIXX’ form. – 10 Marks
    (b) Write an algorithm to traverse a graph using.—10 Marks

1. Breath First Search
2. Depth First Search

7. Write short notes on any four of the following :--20 Marks

1. Red Black Trees
2. Searching Algorithms
3. Recursion
4. Doubly Linked List
5. Expression Trees
6. Comparison of Sorting Algorithms

Also see Data structure & algorithms question papers for December 2013