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) |