You have an array of n elements. Suppose you implement quick sort by always choosing the
central element of the array as the pivot. Then the tightest upper bound for the worst case
performance is

**A. ** O(n^{2})

**B. ** O(n log n)
**C. ** θ(n log n)

**D. ** θ(n2)

**Answer : ****Option A**

**Explaination / Solution: **

The Worst case time complexity of quick sort is O(n2). This will happen when the elements of the input array are already in order (ascending or descending), irrespective of position of pivot element in array.

The Worst case time complexity of quick sort is O(n2). This will happen when the elements of the input array are already in order (ascending or descending), irrespective of position of pivot element in array.

Workspace

Report

Consider the C function given below. Assume that the array listA contains n (> 0) elements,
sored in ascending order. **A. ** It will run into an infinite loop when x is not in listA.

**B. ** It is an implementation of binary search

**C. ** It will always find the maximum element in listA.

**D. ** It will return – 1 even when x is present in listA.

**Answer : ****Option B**

**Explaination / Solution: **

By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D. A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is also wrong. Correct answer is B. It is a correct implementation of Binary Search.

int ProcessArray (int * listA, int x, int n)

{

Int 1, j, k;

i = 0;

j = n – 1;

do {

k = (i + j) /2;

if (x < = listA [k])

j = k – 1;

If (listA [k] < = x)

i = k+1;

}while (1 < = j);

If (listA [k] = = x)

return (k) ;

else

return -1;

}

Which one of the following statements about the function ProcessArray is CORRECT?

By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D. A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is also wrong. Correct answer is B. It is a correct implementation of Binary Search.

Workspace

Report

A subsequence of a given sequence is just the given sequence with some elements (possibly none or
all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of
X and Y starting from 0.
The values of l(i, j) could be obtained by dynamic programming based on the correct recursive
definition of l(i, j) of the form given above, using an array L[M, N], where M = m + 1 and N = n + 1,
such that L[i, j] = l(i, j).
Which of the following statements would be TRUE regarding the dynamic programming solution for
the recursive definition of l(i, j)?

**A. ** All elements of L should be initialized to 0 for the values of l(i, j) to be properly computed

**B. ** The values of l(i, j) may be computed in a row major order or column major order of L[M, N]

**C. ** The values of l(i, j) cannot be computed in either row major order or column major order of L[M, N]

**D. ** L[p, q] needs to be computed before L [r, s] if either p < r or q < s

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

K4 and Q3 are graphs with the following structures

**A. ** K4 is planar while Q3 is not

**B. ** Both K4 and Q3 are planar

**C. ** Q3 is planar while K4 is not

**D. ** Neither K4 not Q3 is planar

**Answer : ****Option B**

**Explaination / Solution: **

Which one of the following statements is TRUE in relation to these graphs?

Both K4 and Q3 are planar

Workspace

Report

Consider the intermediate code given below.

**A. ** 5 and 7

**B. ** 6 and 7

**C. ** 5 and 5

**D. ** 7 and 8

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

The number of nodes and edges in the control-flow-graph constructed for the above code,
respectively, are

No Explaination.

Workspace

Report

If f(x) = 2x^{7} + 3x - 5 which of the following is a factor of f(x)?

**A. ** (x^{3}+8)
**B. ** (x-1)

**C. ** (2x-5)

**D. ** (x+1)

**Answer : ****Option B**

**Explaination / Solution: **

from the option (b0 substitute x=1 in

from the option (b0 substitute x=1 in

2x7 + 3x - 5 = 0

2(1)7 + 3(1) - 5 = 0

5-5 = 0

So (x - 1) is a factor of f (x)

Workspace

Report

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

**A. ** Θ(n log n), Θ(n log n), and Θ(n^{2})

**B. ** Θ(n^{2}), Θ(n^{2}), and Θ(n log n)

**C. ** Θ(n^{2}), Θ(n log n), and Θ(n log n)

**D. ** Θ(n^{2}), Θ(n log n), and Θ(n^{2})

**Answer : ****Option D**

**Explaination / Solution: **

Merge sort θ(n log n) in all the cases

Merge sort θ(n log n) in all the cases

Quick sort θ(n log n) best case and θ(n2) worst cases

Insertion sort θ(n)best case R θ(n2) worst case

Workspace

Report

The following function computes the maximum value contained in an integer array p[ ] of size
n (n >= 1).

**A. ** a != n

**B. ** b != 0

**C. ** b > (a + 1)

**D. ** b != a

**Answer : ****Option D**

**Explaination / Solution: **

When a=b then P[a] will have the maximum value of the array

int max(int *p, int n) {

int a=0, b=n-1;

while ( _________ ) {

if (p[a] <= p[b]) { a = a+1; }

else { b = b-1; }

}

return p[a];

}

The missing loop condition is

When a=b then P[a] will have the maximum value of the array

Workspace

Report

G = (V, E ) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE? **A. ** I only

**B. ** II only

**C. ** both I and II

**D. ** neither I nor II

**Answer : ****Option B**

**Explaination / Solution: **

No Explaination.

I. If e is the lightest edge of some cycle in G, then every MST of G includes e

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

No Explaination.

Workspace

Report

Consider the C code fragment given below.

**A. ** append list m to the end of list n for all inputs.

**B. ** either cause a null pointer dereference or append list m to the end of list n.

**C. ** cause a null pointer dereference for all inputs.

**D. ** append list n to the end of list m for all inputs.

**Answer : ****Option B**

**Explaination / Solution: **

While loop in Join Procedure moves the pointer ‘p’ to the last node of the list “n”. And at the last statement, we are initializing the next of the last node of list n to start of list “m”. But in some cases it may dereference to null pointer.

typedef struct node {

int data;

node* next ;

} node;

void join (node* m, node* n) {

node* p=n ;

while (p->next ! =NULL){

p = p –> next ;

}

p–> next = m;

}

Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will

While loop in Join Procedure moves the pointer ‘p’ to the last node of the list “n”. And at the last statement, we are initializing the next of the last node of list n to start of list “m”. But in some cases it may dereference to null pointer.

Workspace

Report

**Preparation Study Material**- Digital Electronics (Study/Preparation)
- Digital Logic Circuits (Study/Preparation)
- Computer Architecture (Study/Preparation)
- Programming and Data Structures I (Study/Preparation)
- Programming and Data Structure II (Study/Preparation)
- Database Management Systems (Study/Preparation)
- Computer Networks (Study/Preparation)
- Operating Systems (Study/Preparation)
- Software Engineering (Study/Preparation)
- Theory of Computation (Study/Preparation)
- Design and Analysis of Algorithms (Study/Preparation)
- Compiler Design (Study/Preparation)

- Engineering Mathematics (Practise Test)
- Digital Logic (Practise Test)
- Computer Organization and Architecture (Practise Test)
- Programming and Data Structures (Practise Test)
- Algorithms (Practise Test)
- Theory of Computation (Practise Test)
- Compiler Design (Practise Test)
- Operating System (Practise Test)
- Databases (Practise Test)
- Computer Networks (Practise Test)