CS301 Final Term Quiz 3

FINALTERM EXAMINATION Fall 2009 CS301Data Structures

Q1. The data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve this problem we should (1 marks)

1. Use better data structures
2. Increase the hard disk space
3. Use the better algorithm
4. Use as much data as we can store on the hard disk

Q2. In an array list the current element is (1 marks)

1. The first element
2. The middle element
3. The last element
4. The element where the current pointer points to

Q3. Which one of the following is a valid postfix expression? (1 marks)

1. ab+c*d-
2. abc*+d-
3. abc+*d-
4. (abc*)+d-

Q4. In sequential access data structure, accessing any element in the data structure takes different amount of time. Tell which one of the following is sequential access data structure, Linked list (1 marks)

1. Arrays
2. Lists
3. Both of these
4. None of these

Q5. I have implemented the queue with a circular array. If data is a circular array of (1 marks)

CAPACITY elements, and last is an index into that array, what is the formula for the index after last?

1. (last % 1) + CAPACITY
2. last % (1 + CAPACITY)
3. (last + 1) % CAPACITY
4. last + (1 % CAPACITY)

Q6. Which one of the following is TRUE about recursion? (1 marks)

1. Recursion extensively uses stack memory.
2. Threaded Binary Trees use the concept of recursion.
3. Recursive function calls consume a lot of memory.
4. Iteration is more efficient than iteration.

Q7. Compiler uses which one of the following to evaluate a mathematical equation, (1 marks)

1. Binary Tree
2. Binary Search Tree
3. Parse Tree
4. AVL Tree

Q8. Which one of the following is TRUE about iteration? (1 marks)

1. Iteration extensively uses stack memory.
2. Threaded Binary Trees use the concept of iteration.
3. Iterative function calls consumes a lot of memory.
4. Recursion is more efficient than iteration.

Q9. If a max heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value? Data[0] (1 marks)

data[1] data[n-1] data[n] data[2*n+1]

Q10. If there are 56 internal nodes in a binary tree then how many external nodes this binary tree will have? (1 marks)

1. 54
2. 55
3. 56
4. 57

Q11. Which of the following heap method increase the value of key at position ‘p’ by the amount ‘delta’? (1 marks)

1. increaseKey(p,delta)
2. decreaseKey(p,delta)
3. preculateDown(p,delta)
4. remove(p,delta)

Q12. If we have 1000 sets each containing a single different person. Which of the following relation will be true on each set: (1 marks)

1. Reflexive
2. Symmetric
3. Transitive
4. Associative

Q13. Which one of the following is not an example of equivalence relation: (1 marks)

Electrical connectivity Set of people <= relation Set of pixels

Q14. A binary tree of N nodes has _______. (1 marks)

1. Log10 N levels
2. Log2 N levels
3. N / 2 levels