1 . Differentiate between stack and queue. What are the general applications of a stack?

2 . What is a linked list? How doubly linked list is different from circular linked list? Explain with example.

3 . What is recursion and recursive function? Write a recursive function to compute Fibonacci number.

4 . How does collision occur during hashing? Explain any two hashing functions.

5 . What is an AVL tree? Create an AVL tree from the following data: 18, 12, 14, 8, 5, 25, 31, 24, 27

6 . What are deterministic and non-deterministic algorithms? Explain the use of Big Oh notation to measure the complexity of an algorithm with an example.

7 . Implement the quick sort to sort the following data items: 12, 1, 14, 7, 2, 10, 4, 7, 22, 6, 15

8 . What are the differences between linear queue and circular queue? Write an algorithm to enqueue and dequeue data elements in a circular queue.

9 . What is B-tree? How insertions and deletions of elements can be done in a B-tree.

10 . Explain the different ways to represent a graph. For the following graph use Prim’s algorithm to find a minimum spanning tree stating from the node ‘A’.

11 . 1. Circle (O) the correct answer. i) What is the measurement for time complexity of an algorithm? a) Counting microseconds b) Counting kilobytes of algorithms c) Counting number of key operations d) Counting number of statements ii) Which of the following is the result of evaluation of 5 7 4 - * 8 4 / +? a) 5 b) 8 c) 10 d) 17 iii) What is the recursive formula for post order traversal of binary tree? a) Left-Root-Right b) Root-Left-Right c) Left-Right-Root d) Right-Left-Root iv) What is the number of disk movement in TOH with 4 disks? a) 9 b) 14 c) 17 d) 15 v) What is the Big-Oh of best case complexity of insertion sort? a) O (n) b) O (nlogn) c) O (1) d) O (n²) vi) How does the rear index incremented in circular queue? a) front=(rear+1)%SIZE b) rear=(rear+1)%SIZE c) rear=rear+1 d) rear=(rear-1)%SIZE vii) A variation of linked list in which none of the node contains NULL pointer is ...... a) Singly b) Multiple c) Circular d) Doubly viii) Which of the following data structure is used in depth first search of graph? a) Stack b) Queue c) Linked List d) None of the above

12 . What is Data Structure? Show the status of stack converting following infix expression to postfix P + Q – (R*S/T+U)-V*W

13 . Write binary search. Consider a hash table of size 10; insert the keys 62, 37, 36, 44, 67, 91 and 107 using linear probing.

14 . What are deterministic and non-deterministic algorithms? Explain greedy algorithm.

15 . Draw a BST from the string DATASTRUCTURE and traverse the tree in post order and preorder.

16 . Define circular queue? How does circular queue overcome the limitation of linear queue? Explain.

17 . What is singly linked list? Write an algorithm to add a node at the beginning and end of singly linked list.

18 . Define AVL tree. Construct AVL tree from given data set: 4, 6, 12, 9, 5, 2, 13, 8, 3, 7, 11.

19 . What is stack? List the applications of stack. Write an algorithm or procedure to perform PUSH and POP operation in stack.

20 . What is heap? Explain quick sort algorithm with Big-oh notation in best case, average case and worst case and trace it to sort the data: 8, 10, 5, 12, 14, 5, 7, 13.

21 . Define graph and tree data structure. Explain breadth first traversal and depth first traversal with example.