# 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).

#### Answers

 191 Answer : (c) Reason  :       This is the case where either the list is full or the list the made empty after it was full. 192 Answer : (d) Reason  :       Here in the answer ‘can’ is most important. That is “every non-leaf node ‘can’ have at most M subtrees. 193 Answer : (a) Reason  :       This one belongs to NP-Class category. 194 Answer : (b) Reason  :       Bubble sort only is the algorithm from the given options which compares the adjacent keys 195 Answer : (e) Reason  :       According to the mathematical definition of the Asymptotic notations. 196 Answer : (c) Reason  :       According to the asymptotic notation rules. And this rule is used to apply the limit rule for the omega notated values 197 Answer : (e) Reason  :       Because q notation is equivalence relationship in nature. 198 Answer : (d) Reason  :       Because, the leaf nodes can’t have the children. 199 Answer : (b) Reason  :       Remaining all belongs to divide and conquer paradigm. 200 Answer : (c) Reason  :       Because, we have to calculate all c(i, j )’s, w( i, j)’s and r(i, j)’s for the tree of ‘n’ identifiers
<< PrevNext >>

#### No comments :

What you think about these Questions and Answers ? Let me know in comments.