 # Algorithm Multiple Choice Questions

This Test will cover basic concepts of data Structure and related algorithm.

Q. What is the maximum height of stack required to process the given directed graph using DFS (Depth first search) ? A. 5 B. 3 C. 4 D. 6
Q. Which of the following BFS (Breadth First Search) sequence is valid for the given graph A. ACFDEB B. AFBCDE C. DCBEF D. DBFEC
Q. What is the maximum height of queue (To keep track of un-explored nodes) required to process a connected Graph G1 which contains 'N' node using BFS algorithm?
 A. (N/2)-1 B. (N-1)/2 C. N-1 D. N

Q. What will be the probability that the upcoming element will be hashed to 0th cell using linear probing:
Hash function : h(k) = k mod 10
Where K denotes the key to be inserted. A. 4/5 B. 1/5 C. 2/5 D. 3/5
Q. Which of the following permutations can be obtained in the output (In the same order) using a stack .Assuming the Input is the sequence A,B,C,D,E in that order.
 A. CDEAB B. CDEBA C. AEBCD D. EDCAB
Q. Consider a single linked list with start node pointed by 'head' pointer. Suppose there is a middle node 'X' which is pointed by a pointer 'ptr'. What is the time complexity of the best known algorithm to delete the node X .
 A. O(n) B. O(1) C. O(n^2) D. None of the above
Q. Suppose a new data type 'X' is created to hold integers. The maximum number of bits allocated to the this X is 5. Consider the number to be represented in 2's compliment form then what will be the range of the values which can be assigned to X.
 A. -16 to +15 B. -16 to +16 C. -15 to +15 D. -15 to +16
Q. Consider a hash table with 50 slots .Collision is resolved using chaining. What is the probability that there will be No collision in any of the 50 slots
 A. 50! / (5050) B. (50 X 49 X 48)/ (50 50) C. 1/2 D. (1/50 50)

Q. Which of the following statements are true :
(I) When an integer array is initialized to number of elements less that the declared size then the uninitialized elements become 0.
(II) If a macro value is not defined then the pre-processor assigns 0 to it by default.
(III) In a queue when Front pointer = Rear +1 , this condition may denote Over flow.
(IV) 2 stacks are sufficient to implement queue.
 A. I & II B. II & IV C. II ,III,IV D. I,II,III,IV
Q. Which of the following statements are essentially true for NP problems.
(I) There doesn't exist any algorithm for NP problems which can solve it in O(polynomial) time.
(II) There always exist a polynomial time verification algorithm.
(III) Every P is NP but every NP is not P.
 A. I,II,III B. I & II C. II & III D. I & III
Q. Suppose there is problem X which satisfy the following properties:

1. X is NP.

2. X is NP hard.

3. X is P also.

Now which of the following conclusions can be drawn from the above properties.
 A. Every NP problem is P now B. Problem X may not be NP-Complete C. There does not exist any polynomial time verification algorithm for X D. Given properties are contradicting with each other hence No such X can exist
Q. What is the time complexity of the below 'C 'code snippet.
``````
for (int j=0;j<n;j++)
{
for (int I =0 ;i<n;i=i*2)
printf("study tonight");
}
```
```
 A. O (n2) B. O(n log n) C. O (logn) D. O (n2 log n)

Q. What will be the recursive equation for the below code snippet.
``````
Studytonight(n)
{
if(n>=1)
{
Studytonight(n/2);
int temp,a,b;
scanf("%d",&a);
scanf("%d",&b);
}
}
```
```
 A. T(n ) =T(n) +1 B. T(n)= T(n/2)+ 2 C. T(n)=T(n/2)+n D. T(n)=T(n)+n
Q. What is the time complexity of the below recursive equation? T(n) = 5 T(n/3) + n2
 A. Theta(n2) B. Theta(n log n) C. Theta (n) D. O(1)
Q. What is the maximum number of movements required in order to get the correct location of an element in insertion sort?
 A. N B. N-1 C. N-2 D. N-3