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


Writed by
Labels: , , , , , , , , , ,

1 comment :

Subscribe to: Post Comments ( Atom )