Quick Links

University Papers | University Syllabus | Entrance Exam |

PSU Papers | Bank Papers | Placement Papers |

VTU | Anna Univerity Syllabus | Anna Univerity Papers |

**B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.**

**B.Tech. - Information Technology**

**Third Semester**

**IT2201/142301 - DATA STRUCTURES AND ALGORITHMS**

**(Regulation 2010)**

**University Papers | Syllabus | Entrance Exam | Govt & PSU Papers | Bank Papers**

**Programming Questions | Travel Tips | Mobile Review | Placement Papers**

**ANNA UNIVERSITY SYLLABUS: CLICK HERE**

**ANNA UNIVERSITY**PAPERS:**CLICK HERE**

**For more question paper of IT**- CLICK HERE

**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)

## 0 Comments