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