Wednesday, October 14, 2009
| IF246 — DATA STRUCTURES AND ALGORITHMS |
| PART A — (10 * 2 = 20 marks) |
| 1. What is time and space complexity of an algorithm? |
| 2. Define grammar. |
| 3. Explain the primitive string manipulation functions. |
| 4. How do you store two dimensional array in a memory? |
| 5. What is linked stack? |
| 6. Explain dequeue. |
| 7. Explain the adjacency list representation of graph. |
| 8. Explain the selection sort algorithm with an example. |
| 9. What is 2–3 tree? |
| 10. What is multiple key access? Explain. |
| PART B — (5 ? 16 = 80 marks) |
| 11. (i) Write insertion and deletion algorithm for a linked queue. (8) |
| (ii) Write recursive and non recursive algorithms for inorder traversal. (8) |
| 12. (a) (i) Write insertion and deletion algorithm for doubly linked list. (4 + 4) |
| (ii) Explain the representations of priority queue. (2 ? 4) |
| Or |
| (b) Write insertion and deletion algorithm for output restricted and input restricted |
| dequeue. (16) |
| 13. (a) A polynomial in three variables is represented by a linked linear list. Design an |
| algorithm to subtract two polynomials in three variables. (16) |
| Or(b) (i) For the three dimensional array x, whose subscript limits are . Give addressing |
| function for the element where the storage representation is in row major order. (8) |
| (ii) Write an algorithm for converting infix to postfix expression. Explain the evaluation |
| of postfix expression. (8) |
| 14. (a) (i) Explain the representations of binary tree. Discuss about one application of |
| stack. (8) |
| (ii) Write an algorithm to delete an element from binary tree. (8) |
| Or |
| (b) The node of the linked list consists of an info and link, write the algorithms for the |
| following : |
| (i) Count the number of nodes in the list. |
| (ii) Change the info field of the kth node to the value given by Y. |
| (iii) Perform an insertion to the immediate left of the kth node in the list. |
| (iv) Appends a linear list to another linear list. (4 ? 4) |
| 15. (a) (i) Write an algorithm to calculate the shortest distance from a start node using a |
| breadth first search strategy. (8) |
| (ii) Write the first fit storage allocation algorithm. (8) |
| Or |
| (b) (i) Design an algorithm which perform deletion in a 2-3 tree. (8) |
| (ii) Explain the processing of indexed sequential files. (8) |
http://www.ziddu.com/download/7201357/DSA.pdf.html