Data Structures and Algorithms - Unit Wise Questions

2. What is Data Structure? Show the status of stack converting following infix expression to prost fix P + Q – (R*S/T+U)-V*W [1+4]

1.

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

1.

ii) Which of the following is the result of evaluation of 5 7 4 - * 8 4 / +?

a) 5    b) 8    c) 10    d) 17

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

1.

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

4. What are deterministic and non-deterministic algorithms? Explain greedy algorithm. [3+2]

5. Draw a BST from the string DATASTRUCTURE and traverse the tree in post order and preorder. [3+2]

1.

iv) What is the number of disk movement in TOH with 4 disks?

a) 9    b) 14    c) 17    d) 15

6. Define circular queue? How does circular queue overcome the limitation of linear queue? Explain. [2+3]

1.

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

1.

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

7. What is singly linked list? Write an algorithm to add a node at the beginning and end of singly linked list. [1+4]

1.

vii) A variation of linked list in which none of the node contains NULL pointer is ……

a) Singly    b) Multiple    c) Circular    d) Doubly

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

1.

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

1.

ix) Which of the following is true for B-Tree of order M?

a) Leaf nodes should be at different level

b) All the key values within a node must be in descending order

c) Every node has at least M children

d) All non-leaf nodes with M-1 keys must have M number of children

1.

x) Which of the following is not a hash function?

a) Division remainder    b) Folding    c) Chaining    d) Mid square

9. What is stack? List the applications of stack. Write an algorithm or procedure to perform PUSH and POP operation in stack. [1+2+7]

10. 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. [2+2+6]

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