CS2201 DATA STRUCTURES NOVEMBER/DECEMBER 2009 ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS

CS2201 DATA STRUCTURES NOVEMBER/DECEMBER 2009 ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS

CS2201 DATA STRUCTURES NOVEMBER/DECEMBER 2009 ANNA UNIVERSITY QUESTION PAPER QUESTION BANK IMPORTANT QUESTIONS 2 MARKS AND 16 MARKS

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2009

Third Semester

Computer Science and Engineering

CS 2201 — DATA STRUCTURES

(Regulation 2008)

Time : Three hours Maximum : 100 Marks

Answer ALL Questions

PART A — (10 × 2 = 20 Marks)

1. What is abstract data type?
2. Give any four applications of stack.
3. What is meant by binary search tree?
4. Write the advantages of threaded binary tree.
5. Define B-Tree.
6. What is sentinel?
7. What is primary clustering?
8. What is meant by rehashing?
9. What are articulation points?
10. What is activity-node graph?
PART B — (5 × 16 = 80 Marks)
11. (a) (i) Explain the process of postfix expression evaluation with an
example. (8)
(ii) Write a program to print the elements of a singly linked list. (8)
Or


(b) (i) Explain with an example the creation of a linked list, insertion and
deletion of nodes, and swapping of any two nodes. (10)
(ii) Explain the process of conversion from infix expression to postfix
expression using stack. (6)
12. (a) (i) Explain the operations of insertion of nodes into and deletion of
nodes from, a binary search tree with code. (10)
(ii) Construct an expression tree for the expression (a + b * c) +
((d * e + 1) * g). Give the outputs when you apply preorder, inorder
and postorder traversals. (6)
Or
(b) Give the analysis of insertion and deletion operations of nodes in binary
search tree. (16)
13. (a) Explain the operations which are done in B-Tree with examples. (16)
Or
(b) What is heap order property? Explain the operations which can be done
in heap with examples. (16)
14. (a) Briefly explain the three common collision resolution strategies in open
addressing hashing. (16)
Or
(b) Give an account on the following :
(i) Dynamic equivalence problem. (8)
(ii) Smart union algorithms. (8)
15. (a) Define network flow problem. Explain the maximum flow algorithm for
the graph given below. (16)
Or
(b) (i) Explain the Kruskal’s algorithm with an example. (10)
(ii) Give a short note on Euler circuits. (6)