# Data Structure and Algorithms 3rd ND11 IT2201-142301

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
B.Tech. - Information Technology
Third Semester
IT2201/142301 - DATA STRUCTURES AND ALGORITHMS
(Regulation 2010)

Programming Questions  |  Travel Tips | Mobile Review | Placement Papers

For more question paper of IT

PART A — (10 ´ 2 = 20 marks)

1. Differentiate between stack and queue and give its applications.
2. Convert A * (B + D)/E- F* (G +H/K) into Postfix expression.
3. Draw the expression tree for (a + b * c) + ((d * e + f) * g) .
4. What is an AVL tree?
5. What is a Hash table?
6. Give two examples of disjoint sets.
7. Differentiate between graph and tree.
8. Trace the Euler’s path and Euler’s circuit in the graph.
9. Define dynamic programming and backtracking.
10. Define NP hard and NP complete.

PART B — (5 ´ 16 = 80 marks)

11. (a) (i) Write ADT operations for array implementation of polynomial addition. (8)
(ii) Formulate an algorithm to insert an element in a doubly linked list. (8)
Or
(b) (i) Write down the algorithm to convert infix to reverse polish form.
Using it convert ((A + B) *D) ­ (E- F). (8)
(ii) Write an algorithm to find whether a particular element is present or not in a circular queue. (8)

12. (a) (i) Explain the various tree traversal & predict a binary tree with Preorder : ABCDEFGHI & Inorder : BCAEDGHFI. (8)
(ii) Formulate an algorithm to insert an element in a binary tree. (8)
Or
(b) (i) Formulate an algorithm to search an element in a binary tree. (8)
(ii) Explain binary search tree and give its time complexity. (8)

13. (a) (i) What is open addressing hashing? Describe any one technique. (8)
(ii) Explain the operations on bit vector representation of sets. (8)
Or
(b) (i) Explain the smart union algorithm. (8)
(ii) Discuss the use of sets in tree representation of sets in client-server environment. (8)

14. (a) (i) Write Dijkstra’s algorithm for shortest path. (8)
(ii) Explain topological sorting with an example. (8)
Or
(b) (i) Explain Euler’s and Hamiltonian circuits. (8)
(ii) Write down the Prim’s algorithm and find the minimum spanning tree for the following graph. (8)

15. (a) (i) Explain divide and conquer technique with an example. (8)
(ii) Explain Asymptotic complexity classes. (8)
Or
(b) (i) Define big Oh notation. (6)
(ii) Write short notes on :
• Branch and bound techniques and (5)
• NP complete problems. (5)