Algorithms - Programming Language (MCQ) questions

1)   Algorithms: What will be the Huffman code for the letters a,b,c,d,e?
- Published on 24 Jun 15

a. 0,10,110,1110,1111
b. 10,011,11,001,010
c. 10,01,0001,100,1010
d. 100,110,001,000,010
Answer  Explanation 

ANSWER: 0,10,110,1110,1111

Explanation:
The probability are ½,1/4, 1/8,1/16,,1/32
So, the Huffman code according to the tree is unique.


2)   Algorithms: Consider a B-tree of order 4 and is built from scratch by 10 successive insertions. What would be the maximum number of node splitting operations that take place?
- Published on 24 Jun 15

a. 6
b. 3
c. 4
d. 2
Answer  Explanation 

ANSWER: 4

Explanation:
A B-tree of order m contains n records and each contains b records on average then the tree will have about n/b leaves. If we split k nodes along the path from leaves then
k<=1+logm/2 [n/b]
here n=10,b=3,m=4 so
k<=1+log4/2 [n/b]
k<=1+log2 4
k<= 1+2
k<=3


3)   Algorithms: From the following algorithm design techniques which one is used to find all the pairs of shortest distances in a graph?
- Published on 24 Jun 15

a. Backtracking
b. Greedy
c. Dynamic programming
d. Divide
Answer  Explanation 

ANSWER: Dynamic programming

Explanation:
The Bellman-Ford algorithm is used to find all the pairs of shortest distances in a graph.


4)   By using which method sorting is not possible?

- Published on 16 Jun 15

a. Insertion
b. Selection
c. Deletion
d. Exchange
Answer  Explanation 

ANSWER: Deletion

Explanation:
Deletion means removing so we cannot sort anything by using deletion.


5)   Out of 4 distinct keys how many distinct primary keys can be created?
- Published on 16 Jun 15

a. 5
b. 20
c. 45
d. 14
Answer  Explanation 

ANSWER: 14

Explanation:
the no of keys given are 4
apply the formula Bn=1/(n+1)*(2n!/n!n!)
where B is the binary tree and n is the number of keys.
Bn=1/(4+1)*(8!/4!4!)
Bn=1/5*(8*7*6*5*4!)/4!4!
Bn=8*7*9*6/(4*3*2)
Bn=56/4
Bn=14
Hence, the total no of binary trees with n=4 is 14.


6)   From the following sorting algorithms which algorithm needs the minimum number of swaps
- Published on 16 Jun 15

a. Bubble sort
b. Quick sort
c. Merge sort
d. Selection sort
Answer  Explanation 

ANSWER: Selection sort

Explanation:
First find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position and continue in this way until the entire array is sorted. Hence, we say that selection sort takes the minimum number of swaps.


7)   From the following sorting algorithms which has the lowest worst case complexity?
- Published on 16 Jun 15

a. Bubble sort
b. Quick sort
c. Merge sort
d. Selection sort
Answer  Explanation 

ANSWER: Merge sort

Explanation:
Let the input be n. The merge sort uses the weak complexity their complexity is shown as O(n log n).


1