Data Structures and Algorithm Analysis Set 12

Data Structures and Algorithm Analysis

Questions 111 to 120



111.
Which of the following belongs to the algorithm paradigm?
(a)
Minimum & Maximum problem
(b)
Knapsack problem
(c)
Selection problem
(d)
Merge sort
(e)
Quick sort.
112.
If  f, t: N→ R+, then t (n) Î Ω (f (n)), iff  f(n) Î O (t (n)) is known as
(a)
Limit rule
(b)
Rule of inference
(c)
Duality rule
(d)
Rule of consequences
(e)
Rule of symmetricity.
113.
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.
114.
To calculate c(i, j )’s, w( i, j)’s and r(i, j)’s; Howmuch time does the OBST algorithm in worst case takes?
(a)
O(log n)
(b)
O (n4)
(c)
O (n3)
(d)
O (n log n)
(e)
O (n2).
115.
Which of the following in breadth first search uses data structures as an auxiliary structure to hold nodes for future processing?
(a)
Queue
(b)
Linked list
(c)
Graph
(d)
B-Tree
(e)
Stack.
116.
The number of loop(s) of a node in a simple graph of ‘N’ nodes is
(a)
One
(b)
N
(c)
Zero
(d)
Exactly two
(e)
N-1.
117.
The time taken by NP-class sorting algorithm is
(a)
O(1)
(b)
O(log n)
(c)
O(n2)
(d)
O(n log n)
(e)
O(n).
118.
Pick the correct one from the following by reading carefully the below statements
I.     Floyd’s algorithm takes n3 among of time.
II.     Warshall’s algorithm takes n3 among of time.
(a)
I is true but II is false
(b)
I is false but II is true
(c)
Both are false
(d)
Both are true
(e)
I is true and II takes n4 amount of time.
119.
What defines the average case for the functions f, g : N –> R  for all n,  
lt n –> f(n)/g(n) = 
(a)
f(n) ( g(n)), and f(n)  ( g(n))
(b)
f(n) ( g(n)), but f(n) Ï ( g(n))
(c)
f(n) Ï( g(n)), but f(n)  ( g(n))
(d)
f(n) ( g(n)), but g(n) Ï  ( f(n))
(e)
f(n) ( g(n)), but f(n) Ï ( g(n)).
120.
For the functions f, g : N –> R  for all n,   f(n) = n and g(n) = n log n then
(a)
f(n) Ï( g(n)), but g(n) ( f(n))
(b)
f(n) ( g(n)), but g(n) Ï( f(n))
(c)
g(n) ( f(n)), but f(n) Ï( g(n))
(d)
f(n) ( g(n)), and g(n) ( f(n))
(e)
f(n) ( g(n)), but f(n) Ï( g(n)).


Answers


111.
Answer : (b)
Reason:  Remaining all belongs to divide and conquer paradigm.
112.
Answer : (c)
Reason:  According to the asymptotic notation rules. And this rule is used to apply the limit rule for the omega notated values.
113.
Answer : (d)
Reason:  Because, the leaf nodes can’t have the children.
114.
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.
115.
Answer : (a)
Reason:  As in BFS, all the adjacent nodes are traversed first, before traversing the descendent nodes. And hence a queue is used.
116.
Answer : (c)
Reason:  Because, the simple graph should not contain any loop in the entire graph.
117.
Answer : (e)
Reason:  Here only one loop from one to n is there. And hence it runs for ‘n’ times only.
118.
Answer : (d)
Reason:  As there are three nested loops running from 1 to n in both of the algorithms. And hence it is O(n3)
119.
Answer : (b)
Reason:  According to the limit rules for big Oh notation.
120.
Answer : (a)
Reason:  According to the limit rules for big Oh notation.



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

1 comment :

Subscribe to: Post Comments ( Atom )