Data Structure and Algorithm Analysis Set 22

Data Structure and Algorithm Analysis

Questions 211 to 220



211.
Find the correct sequence for the Big Oh values for all n > 2
(a)
O(1) < O( n) < O( log n) < O(n log n) < O(n2) < O(n3) < O(2n)
(b)
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n3)
(c)
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
(d)
O(1) < O(n) < O(log n) < O(n log n) < O(n2) < O(2n) < O(n3)
(e)
O(1) < O(log n) < O(n) < O(n2) < O(n log n) < O(n3) < O(2n).
212.
The q notation is
I.     Reflexive.
II.    Symmetric.
III.   Transitive.
(a)
Only (I) above
(b)
Only (III) above
(c)
Both (I) and (II) above
(d)
Both (II) and (III) above
(e)
All (I), (II) and (III) above.
213.
Data structure
(a)
May be helpful to develop efficient algorithms in different phases of data processing
(b)
Need not give relationship between data items
(c)
Is programming language dependent
(d)
Is procedural language dependent
(e)
Need to describe the relationship among data items.
214.
Modular programming uses
(a)
Only top-down method
(b)
Only bottom-up method
(c)
Both (a) and (b) above
(d)
Procedural approach
(e)
Object oriented approach.
215.
In Knapsack problem, the best strategy to get the optimal solution, where Pi, Wi is the Profit, Weight associated with each of the Xith object respectively is to
(a)
Arrange the values Pi/Wi in ascending order
(b)
Arrange the values Pi/Xi in ascending order
(c)
Arrange the values Pi/Wi in descending order
(d)
Arrange the values Pi/Xi in descending order
(e)
Arrange the values Wi/ Xi in decreasing order.
216.
In the following weighted graph, the length of the minimum spanning tree is
(a)
39
(b)
41
(c)
43
(d)
52
(e)
depends on the starting vertex.
217.
The time complexities of Max Min recursive and non-recursive algorithms are
(a)
 – 1,  – 2    
(b)
,  – 2
(c)
 – 2,  – 1
(d)
,
(e)
3n – 2, 3n – 1.
218.
Greedy job scheduling with deadlines algorithms’ complexity is defined as 
(a)
O(N)
(b)
Ω( n log n)
(c)
O (n2 log n)
(d)
O ( n log n)
(e)
Ω (N2).
219.
The divide and conquer merge sort algorithm’s time complexity can be defined as
(a)
q (long n)
(b)
q (n)
(c)
Ω (n log n)
(d)
q (n log n)
(e)
q (n2 log n).
220.
In analysis of algorithm, approximate relationship between the size of the job and the amount of work required to do it is expressed by using
(a)
Order of magnitude or Big - O
(b)
Central tendency
(c)
Differential equation
(d)
Polynomial equation
(e)
Space complexity.

Answers


211.
Answer : (c)
Reason  :       O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
212.
Answer : (e)
Reason  :       (I), (II), & (III).
213.
Answer : (a)
Reason  :       may be helpful to develop efficient algorithms in different phases of data processing
214.
Answer : (c)
Reason  :       both a & b
215.
Answer : (d)
Reason  :       Arrange the values Pi/Xi in descending order
216.
Answer : (e)
Reason  :       depends on the starting vertex
217.
Answer : (a)
Reason  :       – 1,  – 2
218.
Answer : (a)
Reason  :       O(N)
219.
Answer : (d)
Reason  :       q (n log n)
220.
Answer : (a)
Reason  :       order of magnitude or Big - O




No comments :

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

Post a Comment