ANNA UNIVERSITY QUESTION PAPER IT 2201 DATA STRUCTURES AND ALGORITHMS

 IT2201 DATA STRUCTURES AND ALGORITHMS ANNA UNIVERSITY QUESTION PAPER

DATA STRUCTURES AND ALGORITHMS ANNA UNIVERSITY QUESTION PAPER

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2009
Third Semester
Information Technology
IT 2201 — DATA STRUCTURES AND ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 Marks
Answer ALL Questions

PART A — (10 × 2 = 20 Marks)

1. What is meant by abstract data type (ADT)?
2. What are the postfix and prefix forms of the expression
A + B* (C – D) / (P – R)
3. What is a Binary tree?
4. Define expression tree.
5. What are the applications of hash table?
6. What is an equivalence relation?
7. Define indegree and out degree of a graph.
8. What is a minimum spanning tree?
9. Compare backtracking and branch-and-bound.
10. List the various decision problems which are NP-Complete.

PART B — (5 × 16 = 80 Marks)

11. (a) (i) Write the insertion and deletion procedures for cursor based linked
lists. (8)
(ii) Write the algorithm for the deletion and reverse operations on
doubly linked list. (8)
Or
(b) (i) Write an algorithm for Push and Pop operations on Stack using
Linked List. (8)
(ii) Explain the addition and deletion operations performed on a
circular queue with necessary algorithms. (8)
12. (a) (i) Write the algorithm for pre-order and post-order traversals of a
binary tree. (8)
(ii) Explain the algorithm to convert a postfix expression into an
expression tree with an example. (8)
Or
(b) (i) Write an algorithm to insert an item into a binary search tree and
trace the algorithm with the items 6, 2, 8, 1, 4, 3, 5. (8)
(ii) Describe the algorithms used to perform single and double rotation
on AVL tree. (8)
13. (a) Discuss the common collision resolution strategies used in closed hashing
system. (16)
Or
(b) (i) What is union-by-height? Write the algorithm to implement it. (8)
(ii) Explain the path compression with an example. (8)
14. (a) (i) What is topological sort? Write an algorithm to perform topological
sort. (8)
(ii) Write the Dijkstra’s algorithm to find the shortest path. (8)
Or
(b) Write the Kruskal’s algorithm and construct a minimum spanning tree
for the following weighted graph. (16)

15. (a) (i) Formulate an algorithm to multiply n-digit integers using divide
and conquer approach. (8)
(ii) Briefly discuss the applications of greedy algorithm. (8)
Or
(b) Find the optimal tour in the following traveling salesperson problem
using dynamic programming : (16)