MCQs

Total Questions : 36 | Page 1 of 4 pages
Question 1.
Which of the following sorting algorithms are stable?
(I).Bubble Sort,
(II).Selection Sort,
(III).Insertion Sort,
(IV).Shell Sort,
(V).Binary tree sort,
(VI).Merge Sort,
(VII).In-place merge sort,
(VIII).Heap Sort,
(IX).Quick Sort,
(X).Bucket Sort,
(XI).Counting Sort,

1.    I,III,V,VI,IX,XII,XIII
2.    I,III,IV,VI,XII,XIII
3.    III,V,VI,IX,XII,XIII
4.    I,III,V,VI,X,XI,XII

Question 2.
To copy a binary tree we have to copy the tree in :

1.    pre order
2.    post order
3.    in order
4.    any order
Answer: Option C. -> in order

Question 3.
Maximum worst case complexity of heap construction:

1.    O(n^2)
2.    O(n)
3.    O(n log n)
4.    O(log n)
Answer: Option C. -> O(n log n)

Question 4.
Algorithm used to sort the subarrays of a merge sort:

1.    Selection
2.    Bubble
3.    Insertion
4.    Quick

Question 5.

The following code reverses an N-bit quantity in parallel. How many operations does it take?
unsigned int v; // 32 bit word to reverse bit order

v = ((v& >> 1)& 0x55555555) | ((v & 0x55555555)<<1); // swap odd and even
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333)<<2); // swapconsecutivepair
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F)<<4); // swap nibbles
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF)<<8); // swap bytes
v = ( v >> 16 ) | ( v <<16); // swap 2-byte long pairs

1.    5*lg(N)
2.    lg(N)
3.    N
4.    5*N

Question 6.
Number of distinct binary trees with 7 nodes:

1.    49
2.    2^7
3.    7!
4.    429

Question 7.
Maximum worst case complexity of cycle deletion in a directed graph:

1.    O(eXn)
2.    O(e+n)
3.    O(e(e+n))
4.    O(n^2)

Question 8.
Which of the following sorting methods has least worst case complexity

1.    Bubble Sort
2.    Insertion sort
3.    Merge Sort
4.    Quick Sort
Answer: Option C. -> Merge Sort

Question 9.
Find the ordering in running times of following programs
(i)main(){
int i,j,l;
char str[]="Hello";
l=strlen(str);
for(i=0;i<l;i++) printf("%c",str[i]);}
(ii)main(){
int i,j,l;
char str[]="Hello";
for(i=0;i<strlen(str);i++) printf("%c",str[i]);}
(iii)main(){
int i,j,l;
char str[]="Hello";
l=strlen(str);
for(i=l-1;i>0;i--) printf("%c",str[l-i-1]);}

1.    T(i)=T(iii)
2.    T(i)
3.    T(i)=T(ii)=T(iii)
4.    T(iii)

Question 10.
In the linked representation of binary tree, complexity of post order traversal is :

1.    O(n)
2.    O(log n)
3.    O(nlog n)
4.    O(n^2)