ANNA UNIVERSITY DSA QUESTION PAPER

DATA STRUCTURES QUESTION PAPER- ANNA UNIVERSITY DECEMBER 2012 

TWO MARKS:-

1. Write any four applications of stack?
2. What is abstract data type? five any two examples?
3. Define binary tree and give the binary tree node structure?
4. Draw an expression tree for the expression: a8(b+c)+((d+e*f)*g)?
5. How does the AVL tree differ from binary search tree?
6. What are the applications of priority queue?
7. What is meant by primary clustering?
8. Define open addressing hashing?
9. What is residual graph?
10. Define event-node graph?

PART-B

11. (a) (i) Write an algorithm to merge two sorted linked lists into a single sorted list?

           (ii) Explain the operation of inserting an element at the front, middle and the rear in a doubly linked list?

(b) (i) Write and explain an algorithm to display the contents of a stack with an example?

     (II) Briefly explain the operations of queue with examples?

12.(a) (i) Explain the process of finding the minimum and maximum elements of binary search tree?

          (ii) Explain the process of displaying the nodes of a binary tree at a particular level?

     (b) (i) Write a function to insert a node into a binary search tree and explain with an example?

          (ii) Explain the operations of threaded binary tree?

13. (a) (i) Explain the insert and delete operations of heap with examples?

            (ii) Explain how does double rotation fix the problem found in the single rotation of AVL tree with an example

      (b) (i) Describe the operation of B-tree using 2-3 tree

            (ii) Explain the operation which are performed in splay tree?

14.(a) (i) Briefly describe linear probing and quadratic probing collision resolution srategies?

          (ii) Discuss about the two permissible operations in the dynamic equivalence problem?

     (b) (i) Explain the algorithm which are associated with path compression?

          (ii) List the advantages and disadvantages of various collision resolution strategies?

15.(a) (i) Explain the Kruskal's algorith to find out minimum cost spanning tree with an example?

          (ii) Explain the Dijkstra's algorithm for shortest path problem with an example?

     (b) (i) Explain the topological sort with an example?

          (ii) Give an account of Euler circuits in the applications of graph?

Posted in: anna university questions