Data Structures and Algorithm Analysis Set 19

Data Structures and Algorithm Analysis

Questions 181 to 190




181.
For the smart bubble sort algorithm, what is the time complexity of the best and worst case?
(a)
best case: O(n)                   worst case: O(n2)
(b)
best case: O(n)                   worst case: O(n*log n)
(c)
best case: O(n*log n)         worst case: O(n*log n)
(d)
best case: O(n*log n)         worst case: O(n2)
(e)
best case: O(1 )            worst case: O(n).
182.
There are two sorted lists L1 and L2. Their lengths are n1 and n2 respectively. You are asked to design an algorithm to generate a sorted list L3 from L1 and L2. That is, for example, if L1=[1,5,30] and L2=[3,6,12,24,43] then L3=[1,3,5,6,12,24,30,43]. Which of the following methods is the most efficient?
(a)
Taking elements from L1 one by one, and inserting them into L2 such that the order of L2 remains unchanged
(b)
Appending two lists (i.e. join one list's beginning to the other one's end), then applying quick sort to the appended list.
(c)
Using a merge method that compares two elements at the head of both lists. The smaller one is then taken out and inserted at the end of L3 while the larger one is kept its location unchanged. Repeat this until either L1 or L2 is empty.
(d)
Append two lists and apply Shell sort.
(e)
Append two lists and apply Selection sort.
183.
What is the time complexity of the algorithm ‘a’ in question 2?
(a)
O(log(n1)*n2)
(b)
O(n1*log(n2))
(c)
O(n1+n2)
(d)
O(max(n1,n2))
(e)
O(n1*n2).
184.
What is the best choice for the time complexity of the algorithm C in question 2?
(a)
O(n1*n2)
(b)
O(n1*log(n2))
(c)
O(n1+n2)
(d)
O(max(n1,n2))
(e)
O(log(n1)*n2).
185.
What is the Postfix form of the following in fix expression? 
(2+3)*(4+(5*6)/(7*8/9*1))
(a)
23+456*78*9/1*/+*
(b)
23+456*78*91/*/+*
(c)
23+456*78*91*//+*
(d)
23+456*78*91*//*+
(e)
23+456*+78*91*//*.
186.
The direct or random access of element is not possible in
(a)
Array
(b)
String
(c)
Linked List
(d)
Both (a) and (b) above
(e)
Both (b) and (c) above.
187.
If for a given ‘Queue’ initially f=0 and r=-1, then f = r refers to
(a)
Queue is empty
(b)
Queue is full
(c)
Queue has two elements
(d)
Exactly one element is there
(e)
Not possible at all.
188.
Any string of bits of length ‘n’ represents a unique non-negative integer between
(a)
0 and 2n-1-1
(b)
0 and 2n –1
(c)
2n-1
(d)
0 and 2n
(e)
0 and 2n-1.
189.
Pick the statement(s) which is(are) not true
(a)
ADT is useful tool for specifying the logical properties of data type
(b)
While defining the ADT as a mathematical concept, the space efficiency isn’t a major concern
(c)
Every ADT can be implemented using any programming language
(d)
ADT helps us to hide the organization of the data
(e)
A & B.
190.
Using arrays the most efficient implementation of the QUEUE is as
(a)
Linear queue
(b)
Circular queue
(c)
Linked queue
(d)
Can’t be implemented
(e)
Priority queue.


Answers


181.
Answer : (a)
Reason  :       The smart bubble sort assumes that the computation stops as soon as no more swaps in pass one.
182.
Answer : (c)
Reason  :       As the time complexity of merge sort is small when compared with all the remaining algorithms. Also the lists L1 and L2 already sorted.
183.
Answer : (e)
Reason  :       Each ordered insertion costs O(n2). There is a total of n1 insertions. Therefore, the answer is O(n1*n2).
184.
Answer : (c)
Reason  :       If the size of each list is n1 and n2, then in merge sort the final list contains n1+n2 elements.
185.
Answer : (a)
Reason  :       According to precedence of operators.
186.
Answer : (c)
Reason  :       Because, in linked list the elements are always not stored at contiguous memory locations, but are stored at discrete locations. And hence random access is not possible.
187.
Answer : (d)
Reason  :       If front pointer ‘f’ and rear pointer ‘r’ points to same location then there is only one element in the queue.
188.
Answer : (e)
Reason  :       As all the bits are used to hold the data bits, and there is no sign bit in the array.
189.
Answer : (c)
Reason  :       Though ADT is independent of any programming language, but still every ADT can’t be implemented using any programming language.
190.
Answer : (b)
Reason  :       Because in Circular queue the memory can be used efficiently.



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

No comments :

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

Post a Comment

Subscribe to: Post Comments ( Atom )