Algorithms - Online Test
Q1.
What will be the output of the following C program segment?
Char inChar = ‘A’ ;
switch (inChar ) {
case ‘A’ : printf (“Choice A\ n”);
case ‘B’ :
case ‘C’ : print f(“Choice B”);
case ‘D’ :
case ‘E’ :
default : printf (“No Choice”) ; }
Answer : Option C
Explaination / Solution:
Since there is no ‘break’ statement , the program executes all the subsequent case statements
after printing “choice A”
Q2. Consider the following C code segment:
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1; /* Line 1 */
prtFun( );
a + = 1;
prtFun( )
printf(“\n %d %d “, a, b);
}
void prtFun(void)
{ static int a=2; /* Line 2 */
int b=1;
a+=++b;
printf(“\n %d %d “, a, b);
}
What output will be generated by the given code segment if:
Line 1 is replaced by auto int a = 1;
Line 2 is replaced by register int a = 2;
Answer : Option D
Explaination / Solution:
Static local variables: Scope is limited to function/block but life time is entire program. 
Automatic local variables:
Storage allocated on function entry and automatically deleted or freed when the function is
exited.
Register variables: Same as automatic variables except that the register variables will not
have addresses Hence may not take the address of a register variable.
Q3. Consider the following C code segment:
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1; /* Line 1 */
prtFun( );
a + = 1;
prtFun( )
printf(“\n %d %d “, a, b);
}
void prtFun(void)
{ static int a=2; /* Line 2 */
int b=1;
a+=++b;
printf(“\n %d %d “, a, b);
}
What output will be generated by the given code segment?
Answer : Option C
Explaination / Solution:
Q4. What is the time complexity of Bellman-Ford single-source shortest path algorithm on a
complete graph of n vertices?
Answer : Option C
Explaination / Solution:
Bellman-ford time complexity: Θ(|V| × |E|)
For complete graph: |E| = n(n - 1)/2
|V| = n
Θ(n × (n(n - 1)/2) = Θ(n3)
Q5. A scheduling algorithm assigns priority proportional to the waiting time of a process. Every
process starts with priority zero(the lowest priority). The scheduler re-evaluates the process
priorities every T time units and decides the next process to schedule. Which one of the
following is TRUE if the processes have no I/O operations and all arrive at time zero?
Answer : Option B
Explaination / Solution:
The given scheduling definition takes two parameters, one is dynamically assigned process
priority and the other is ‘T’ time unit to re-evaluate the process priorities.
This dynamically assigned priority will be deciding processes order in ready queue of round
robin algorithm whose time quantum is same as ‘T’ time units. As all the processes are
arriving at the same time, they will be given same priority but soon after first ‘T’ time burst
remaining processes will get higher priorities
Q6. An unordered list contain n distinct elements. The number of comparisons to find an element
in this list that is neither maximum nor minimum is
Answer : Option D
Explaination / Solution:
Consider first three element of the list, atleast one of them will be neither minimum nor
maximum
ϴ(1)
Q7. Consider the following function written the C programming language.
void foo (char *a) {
if (*a && *a ! = ' ') {
putchar (*a) ;
}
}
The output of the above function on input “ABCD EFGH” is
Answer : Option D
Explaination / Solution:
if condition fails
& returns controls
DCBA will be pointed
Q8. Given below are some algorithms, and some algorithm design paradigms
Match the above algorithms on the left to the corresponding design paradigm they follow.
Answer : Option C
Explaination / Solution:
Dijkstra shortest path algorithm find next node by choosing minimum distance hence greedy
approach.
Floyd warshall always apply dynamic programming, once it saves a cost and in the next
iteration it will change if this is minimum hence dynamic.
Binary search always divide on two parts .Hence divide and conquer.
Backtracking uses by DFS, one it will reach to dead end it will take back track.
Q9. Suppose you are provided with the following function declaration in the C programming
language
int partition (int a [ ], int n);
The function treats the first element of a [ ] as a pivot, and rearranges the array so that all
elements less than or equal to the pivot is in the left part of the array , and all elements greater
than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last
elements of the left part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the Kth smallest element in an array a [ ] of size n using the partition function We assume
k ≤ n.
int kth _smallest (int a [ ], int n, int k)
{
int left _ end = partition (a,n);
if (left _ end + 1 == k) {
return a [left _ end];
}
if (left _ end + 1 > k) {
return kth _ smallest (__________________);
}else {
return kth_smallest (_______________________);
}
}
The missing argument lists are respectively
Answer : Option A
Explaination / Solution:
No Explaination.
Q10. The secant method is used to find the root of an equation f(x) = 0. It is started from
two distinct estimates xa and xb for the root. It is an iterative procedure involving
linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is
the solution. The procedure is given below. Observe that there is an expression
which is missing and is marked by? Which is the suitable expression that is to be
put in place of? So that it follows all steps of the secant method?
Initialize: xa, xb, ε, N // ε = convergence indicator
fb = f(xb)
i = 0
while (i < N and | fb | > ε) do
i = i + 1 // update counter
xt = ? // missing expression for
// intermediate value
xa= xb // reset xa
xb = xt // reset xb
fb = f(xb) // function value at new xb
end while
if |fb| > ε then // loop is terminated with i = N
write “Non-convergence”
else
write “return xb”
end if
Answer : Option D
Explaination / Solution:
Secant method direct formula
