Wednesday, October 14, 2009
| IF 246 DATA STRUCTURES AND ALGORITHMS |
| PART – A(10 x 2 = 20 Marks) |
| 1. Take a linear search algorithms and discuss best-case time analysis. |
| 2. Explain the basic of the Markov algorithm and discuss two ways in which such an |
| algorithm terminates. |
| 3. What is the purpose of a stack in implementing a recursive procedure? Explain. |
| 4. What is the need for using circular array to implement queues? |
| 5. Give the tree T, find the inorder and postorder traversals. |
| 6. Discuss the basis of the Buddy system of allocation. What type of fragmentation still |
| exists? |
| 7. Discuss the timing analysis of the heap-sort algorithm. |
| 8. What are the two broad classes of collision resolution techniques? Explain. |
| 9. With an example explain the Huffman encoding scheme. |
| 10. Explain how the size of a hashing table could be decreased when using (a) |
| linearhashing, (b) dynamic hashing. |
| PART – B(5 x 16 = 80 Marks) |
| 11. i) Implement typical stack operation when stacks are represented using (1) arraysand |
| (ii) using singly linked lists. (8 Marks) |
| ii) Define a binary tree. (2 Marks) |
| iii) Give the iterative algorithm for the inorder traversal of a binary tree. (6 Marks) |
| 12a. i) Design a string manipulation algorithm for duplicating a given character string |
| Ntimes. (6 Marks) |
| ii) Design an algorithm which trims off all the trailing blanks of a character string.(5 |
| Marks) |
| iii) Give a procedure that uses a stack in order to reverse the elements of a circularqueue |
| which is stored in an array. (5 Marks) |
| (OR) |
| 12b. i) Given as input a word form assigned to the variable WORD, derive function ORD- |
| SEARCH which searches the ordered array of words looking for the wordform. If the word |
| form is present, its index location is returned, else zero is returned. Any search |
| procedure can be used. (6 Marks) |
| ii) Assume we have a priority queue split into several queues.To access these queues we |
| have vectors of pointers to the front and rear of eachqueue and one to indicate the |
| length of each.Thus to access the front of the queue representing priority 2, one merely |
| starts at PRIORITY_F[2]. This representation allows each queue to be of different |
| length.Given this representation, devise algorithms to insert and delete from a |
| priorityqueue. (10 Marks) |
| 13a. i) Give an algorithm to reverse the elements of a single linked lists without using a |
| temporary list. (6 Marks) |
| ii) Write algorithms to insert into and delete elements from a doubly linked list.(6 Marks) |
| iii) Write an algorithms to count the number of nodes in a given singly linked list.(4 Marks) |
| (OR) |
| 13b. i) Write algorithms to allocate and free nodes in a body system of memory |
| allocation. (10 Marks) |
| ii) Write an algorithm to add two polynomials when the polynomials are representedusing |
| singly linked lists. (6 Marks) |
| 14a. i) Give the best case and worst case analysis of the binary search. (8 Marks) |
| ii) Write any one external sorting algorithm in detail. (8 Marks) |
| (OR) |
| 14b. i) Write an algorithm to delete a node from a binary search tree. (8 Marks) |
| ii) Give the radix sort algorithm in detail. (8 Marks) |
| 15a. i) Give in detail the structure of a typical Indexed Sequential file. (8 Marks) |
| ii) Describe the direct file organization and give the procedure to retrieve a recordfrom a |
| direct file given the key. (8 Marks) |
| (OR) |
| 15b. Write notes on:-i. Garbage compaction (6 Marks) |
| ii. VASM Files (5 Marks)iii. Virtual Hashing (5 Marks) |