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