# Data Structures and Algorithm Analysis Set 20

## Data Structures and Algorithm Analysis

### Questions 191 to 200

191.
One has implemented the queue with a circular array, keeping track of first, last, and count (the number of items in the array). Suppose first is zero, and last is SIZE-1. What can you tell me about count?
 (a) count must be zero (b) count must be SIZE (c) count could be zero or SIZE, but no other values could occur (d) count must be SIZE+1 (e) count must be SIZE-2.
192.
When we say the order of a tree is M, we mean
 (a) every non-leaf node must have M subtrees (b) every non-leaf node must have M keys (c) every non-leaf node can have at most M keys (d) every non-leaf node can have at most M subtrees (e) the Height of the tree is M.
193.
Find the odd one out from the following categories of algorithms
 (a) Bin-packing (b) OBST (c) N-Queens (d) 15-Puzzle (e) TVSP.
194.
This algorithm scans the list by swapping the entries whenever pair of adjacent keys are out of desired order.
 (a) Insertion sort. (b) Bubble sort. (c) Shell sort. (d) Quick sort. (e) Radix sort.
195.
The mathematical definition for Omega can be defined as, provided f,g:NàR+ and c is a positive constant and n > n0,
 (a) f(n) =   g(n)  n (b) f(n) = c. g(n)  n (c) f(n) ≥ c + g(n)  n (d) f(n) = c + g(n)  n (e) f(n) ≥ c. g(n)  n.
196.
Let f, t: N→ R+, then t (n) Î Ω (f (n)), iff  f(n) Î O (t (n)) is known as what?
 (a) Limit rule (b) Rule of inference (c) Duality rule (d) Rule of consequences (e) Rule of symmetricity.
197.
The q notation is
 (a) Symmetric (b) Reflexive (c) Transitive (d) B & C only (e) A, B, & C.
198.
How many children do an external node of a binary tree of order N contains.
 (a) N exactly (b) N-1 exactly (c) One exactly (d) 0 exactly (e) N/2 exactly.
199.
From the following chose the one which belongs to the algorithm paradigm other than to which others from the following belongs to.
 (a) Minimum & Maximum problem. (b) Knapsack problem. (c) Selection problem. (d) Merge sort. (e) Quick sort.
200.
To calculate c(i, j )’s, w( i, j)’s and r(i, j)’s; the OBST algorithm in worst case takes the following time.
 (a) O(log n) (b) O (n4) (c) O (n3) (d) O (n log n) (e) O (n2).