UNIV4VINU | ENGINEERING ACHIEVERS

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)

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