## APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

PART A

1.Let f(n) = 2000n+5. Express f(n) in terms of big oh, omega, theta by specifying the constants to be satisfied. (3)

2. How can we analyze an algorithm (3)

3. Write an algorithm to print a single linked list in reverse order (3)

4. Explain linear data structure (3)

PART B

1.Consider the following recursive algorithm

ALGORITHM Q(n) // n is a positive integer

If n == 1

Return 1

Else

Return Q(n-1) + 2 * n-1

a) Setup a recurrence relation for this function value and determine what this algorithm compute. (2)

b) Solve the given recurrence relation (4)

c) Distinguish recursive and iterative algorithm (3)

2. Consider a collection of elements. 12, 24, 35, 55, 60, 70.

a) Insert an item 45 into the above collection. Identify the data structure which efficiently handle the situation. Explain its feature (2)

b) Write an algorithm to insert the item 45 into the collection without violating the order of collection (4)

c) Justify your proposed algorithm (3)

3. Consider the expression

3x^2+ 4x + 1 op 2x + 1 = 6x^3 + 9x^2+ 6x + 2

a) Identify the data structure in order to implement above (1)

b) Explain stepwise refinement technique to implement above operation (8)

Part C

1. Convert infix expression to postfix

A + ( B * C – ( C / E ^ F) * G ) * H                   (3)

2. Consider Queue, where QUEUE is a circular array which is allocated 6 memory cells

FRONT = 2 REAR = 4 QUEUE : - , A ,C , D ,-, -

a) F is added to the QUEUE

b) Two letter are deleted

c) K,L and M are added                  (3)

3. Consider the following tree. And find

a) Sibling ( B)

b) Level of node F

c) Height of the tree                        (3)

## DATA STRUCTURES QUESTION PAPERS

### PART D

1. Consider the expression 5 * ( 6 + 2 ) – ( 12 / 4 )

a) Convert infix expression to post fix and prefix (4)

b) Evaluate resulting postfix expression using stack (3)

c) Explain about Multiple queues (2)

2. a) Construct a binary tree from following traversal

preorder: 20 , 10, 5, 15, 30, 25, 35

postorder: 5, 15, 10, 25, 35, 30, 20 (2)

b) Write an algorithm to rearrange the elements of resulting tree in ascending order (2)

c) Write the procedure for deleting ‘30’ from resultant tree and construct the tree after the removal of ‘30’ (5)

3. a) Write an algorithm to implement memory allocation and deallocation using linked list (4)

b) Explain different allocation scheme (3)

### PART E

1. a) What do you mean by the term sorting? List different types of sorting techniques. (2)

b) Explain detail of simple sorting methods. (5)

c) Give a chart to show time and space complexity of various simple sorting methods (3)

2. a) What is heap. (2)

b) Construct a max heap from following data 20, 14, 17, 8, 6, 9, 4, 1 (3)

c).Write a procedure to sort the above heap and justify your answer. (5)

3. a) Compare the performance of different searching algorithm with example. (4)

b) Explain Hashing (6)

4. a) Find the hash value for the key “ramesh” using hash function as division where size of hash table is 97. (3)

b) Explain hash function in detail. (3)

c) Consider insertion of keys 10, 22, 31, 4, 15, 28, 17, 88 and 59 into hash table of length 11 using chaining (4)

5. Consider the insertion of keys 76, 26, 37, 59, 21, and 65 into hash table of size 11.

a) Illustrate the operation using linear probing. (3)

b) Identify the drawback of linear probing and resolve it. (4)

c) Consider an open address hash table with uniform hashing.

Give upper bound on expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when load factor is 3/4 and when it is 7/8.(3)