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?


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?


What is the
time complexity of the algorithm ‘a’ in question 2?


What is the
best choice for the time complexity of the algorithm C in question 2?


What is the
Postfix form of the following in fix expression?
(2+3)*(4+(5*6)/(7*8/9*1))


The direct
or random access of element is not possible in


If for a
given ‘Queue’ initially f=0 and r=1, then f = r refers to


Any string
of bits of length ‘n’ represents a unique nonnegative integer between


Pick the
statement(s) which is(are) not true


Using
arrays the most efficient implementation of the QUEUE is as

Answers
181.

Answer : (a)
Reason : The
smart bubble sort assumes that the computation stops as soon as no more swaps
in pass one.

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.


Answer : (e)
Reason : Each
ordered insertion costs O(n2). There is a total of n1 insertions.
Therefore, the answer is O(n1*n2).


Answer : (c)
Reason : If
the size of each list is n1 and n2, then in merge sort the final list
contains n1+n2 elements.


Answer : (a)
Reason : According
to precedence of operators.


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.


Answer : (d)
Reason : If
front pointer ‘f’ and rear pointer ‘r’ points to same location then there is
only one element in the queue.


Answer : (e)
Reason : As
all the bits are used to hold the data bits, and there is no sign bit in the
array.


Answer : (c)
Reason : Though
ADT is independent of any programming language, but still every ADT can’t be
implemented using any programming language.


Answer : (b)
Reason : Because
in Circular queue the memory can be used efficiently.

No comments :
Post a Comment