Anna University Coimbatore 2010 B.E Information Technology 080250005-data structures and algorithms - Question Paper

ANNA UNIVERSITY COIMBATORE
B.E./B.TECH. DEGREE EXAMINATIONS:DECEMBER-2009
REGULATIONS:2008
4th SEMESTER:INFORMATION TECHNOLOGY
080250005-DATA STRUCTURES AND ALGORITHMS
TIME:3 Hours Max.Marks:100
PART-A
(20*2=40 Marks)
ans ALL ques.
1. What is time complexity and space complexity?
2. What is a linked list?
3. provide any 2 applications of stack.
4. What is a circularly linked list?
5. provide any 2 typical examples of non-linear data structure?
6. What is an expressions tree?
7. How do you describe a complete binary tree?
8. What is the height of AVL tree with n elements?
9. What is the advantage of open addressing hashing?
10. What is a quadratic probing?
11. elaborate the 3 properties of equivalence relations in a set?
12. What is a union by size?
13. describe the following:
(i)Graph (ii) weakly connected graph.
14. What do you mean by depth 1st search? What is the precaution to be made?
15. What is a topological sort? provide an example for it.
16. describe spanning tree?
17. What is the principle of Dynamic programming?
18. List out 2 examples of backtracking algorithms with examples.
19. What is skip test? elaborate its advantages?
20. What do you mean by NP problems? provide any 1 example for it.
PART-B
(5*12=60 Marks)
ans ANY 5 ques.
21. discuss the different operations performed on a stack. Also discuss the different forms of expressions.
22. discuss the add and deletion operation in a doubly linked list.
23. Write and discuss the different tree traversal algorithms with examples.
24. What is hash function? elaborate the 2 kinds of it. Write on separate chaining method.
25. What is the prim's algorithm? discuss it with diagram.
26. discuss the concept of Dijkstra's algorithm and show how the data modifications during the unweighted shortest-path algorithm.
27. Write short notes on subsequent (i) Euler circuit (ii) Biconnectivity
28. Write short notes on subsequent (i) Randomized algorithms (ii) path compression
*****END*****

Earning:   Approval pending.