** **

**MODEL QUESTION PAPER**

**B.E / B.Tech. Degree Examinations**

**III Semester**

** **

**IF 246 DATA STRUCTURES AND ALGORITHMS**

** **

Time: 3 Hours Max Marks: 100

Answer all questions

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

hashing, (b) dynamic hashing.

# PART – B

(5 x 16 = 80 Marks)

11. i) Implement typical stack operation when stacks are represented using (1) arrays

and (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 N

times. (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 circular

queue 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 word

form. 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 each

queue 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 priority

queue. (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 represented

using 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 record

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

——

-spac�:e�` �P ii) Compare program controlled I/O with interrupt based processing of I/O. In which cases are the two schemes more suitable? (6 Marks)

**(OR)**

14b. i) A 1024 x 1024 array of 32-bit numbers is to be normalized as follows. For each column, the largest element is found, and all elements of that column are divided by that maximum value. Assume that each page in the virtual memory consists of 4K bytes, and that 1M bytes of main memory are allocated for storing data during this computation. Assume it takes 40 ms to load page from the disk into tha main memory when a page fault occurs. How many page faults would occur if the elements were stored in row order? How many would occur if they were stored in column order? Estimate the total time needed to perform the normalization in both cases. (10 Marks)

ii) How is arbitration for the bus handled during DMA? (6 Marks)

15a. i) Discuss the various techniques used to handled control hazards in a pipelined processor. (10 Marks)

ii) Discuss the various fault-tolerance techniques used. (6 Marks)

**(OR)**

15b. i) Consider the following sequence of instructions.

Add #20, R0, R1

Mul #3, R2, R3

AND #$3A, R2, R4

Add R0, R2, R5

In all instructions the destination is given last. Initially registers R0 and R2 contain 2000, and 50 respectively. These instruction are executed on a 4-stage pipeline. Show the sequence of operations using a pipe-line timing diagram. Explain each step. Give the contents of the interstage buffers B1, B2, and B3 during clock cycles 2 to 5. (10 Marks)

ii) Differentiate between RISC and CISC processors. (6 Marks)

—–