B.E / B.Tech DEGREE EXAMINATION NOVEMBER / December 2011
Common to B.E.(EEE/EIE/ICE)
Third Semester
DATA STRUCTURES AND ALGORITHMS
(Regulation 2010)
Time: Three hours
Maximum: 100 marks
Answer ALL questions
PART A - (10*2=2O marks)
2. Mention the advantages of representing stacks using linked lists than arrays.
3 State the properties of a binary tree.
4. Draw a directed tree representation of the formula (a + b * c)+ ((d * e ÷ f) * g).
5. In an AVL tree, at what condition the balancing is to be done?
6. What is collision hashing?
7. What do you mean by depth-first traversal?
8. What is mean by topological sorting?
9 Write lown the best,average and worst case complexity of Quick and Merge sort.
IO.State the various asymptotic relations used for denoting Time complexity.
PART B (5x16 = 80 marks)
Or
(b) Write an algorithm for covert infix expression to postfix expresion with an example of
(A + (B * C - (D/E^F)* G)*H).
12. (a) (i) Illustrate the construction of tree of a binary tree given its in order and postorder traversal.
in-order: H D I J E K B A L F M C N G O
Post-order: H I D J K E B L M F N O G C A
in-order: H D I J E K B A L F M C N G O
Post-order: H I D J K E B L M F N O G C A
(ii) To find inorder, preorder and postorder for a given tree (6)
Or
(b) Narrate the operation of Binary search tree on searching a node, Insertion node and deletion of a node from binary tree with example.
13. (a) Discuss about AVL Trees
Or
(b) (i) Briefly explain the hash function in detail (6)
(ii) Narrate B-Tree operations. (10)
14. (a)Explain the followiag with algorithm
(i)DFS (4
(ii)BFS (4)
(iii)Kruskal algorithm with example. (8)
Or
(b) Explain Single source path algorithm with an example. Does the algorithm work for paths of negative values? Explain.
(i) Finduig Maximum and Minimum. (8)
(ii) Binary Search. (8)
Or
(b) Explain how the traveling salesman problem can be solved using greedy algorithm.
No comments:
Post a Comment