Computer Science and Engineering B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2013 Question Paper.

Question Paper Code: 31297 

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

Third Semester 

Computer Science and Engineering 

CS 2201/CS 33/10144 CS 302/08030007 — DATA STRUCTURES (Regulation 2008/2010) . 

Time : Three hours Maximum: 100 marks 

Answer ALL questions. 

PARTA—(10x2=20marks) . 

1. Define a linear and non linear data structure. Give an example for each.


2. What is an abstract data type? Give an example.


3. Convert the expression ((A + B) * C-. (D-E) ^(F + G)) into its equivalent Postfix notation.


4. Define a full binary tree. Give an example.


5. What is a heap?


6. List any two applications of binary heap.


7. What is rehashing?


8. List any two applications of set.


9. What are Euler circuits?


10. What is a spanning tree?

PART B — (5 x 16. 80 marks) 

11. (a) Develop an algorithm to implement a Stack ADT. Give relevant example and diagrammatic illustrations. (16)


Or


(b) Develop an algorithm to implement a Doubly Linked List. Give relevant example and diagrammatic illustrations. (16)


12. (a) List the different types of Tree Traversal. Develop an algorithm for traversing a Binary Tree. Validate the algorithm with a suitable example. (16)


Or


(b) Develop an algorithm to implement a Threaded Binary Tree. Validate the


algorithm with a suitable example. (16)


13. (a) Develop an algorithm to implement an Splay Tree. Validate the algorithm with a Suitable example. . (16)


Or


(b) Develop an algorithm to implement a Binary Heap. Validate the


algorithm with a suitable example. (16)


14. (a) State the dynamic equivalence problem. With a procedure and an example discuss the dynamic


equivalence problem. (16)


Or


(b) With a procedure and a relevant example discuss separate chaining in hashing. . (16)


15. (a) Develop an algorithm to compute the shortest path using Dijkstra’s algorithm. Validate the algorithm with a suitable example. (16)


Or


(b) Develop an algorithm to find the minimal spanning tree using Prim’s algorithm. Validate the algorithm with a suitable example. (16)