# Programming and Data Structures (Test 5)

## Gate Exam : Cs Computer Science And Information Technology

| Home | | Gate Exam | | Cs Computer Science And Information Technology | | Programming and Data Structures | Programming and Data Structures
| Programming and Data Structures |
Q.1
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(n2)
B. O(n log n)
C. θ(n log n)
D. θ(n2)
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.

Workspace
Report
Q.2
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order.
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?
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.
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.

Workspace
Report
Q.3
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
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
K4 and Q3 are graphs with the following structures Which one of the following statements is TRUE in relation to these graphs?
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
Explaination / Solution: Both K4 and Q3 are planar

Workspace
Report
Q.5
Consider the intermediate code given below. The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are
A. 5 and 7
B. 6 and 7
C. 5 and 5
D. 7 and 8
Explaination / Solution:
No Explaination.

Workspace
Report
Q.6
If f(x) = 2x7 + 3x - 5 which of the following is a factor of f(x)?
A. (x3+8)
B. (x-1)
C. (2x-5)
D. (x+1)
Explaination / Solution:

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
Q.7
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
A. Θ(n log n), Θ(n log n), and Θ(n2)
B. Θ(n2), Θ(n2), and Θ(n log n)
C. Θ(n2), Θ(n log n), and Θ(n log n)
D. Θ(n2), Θ(n log n), and Θ(n2)
Explaination / Solution:

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
Q.8
The following function computes the maximum value contained in an integer array p[ ] of size n (n >= 1).
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

A. a != n
B. b != 0
C. b > (a + 1)
D. b != a
Explaination / Solution:

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

Workspace
Report
Q.9
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?
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
A. I only
B. II only
C. both I and II
D. neither I nor II
Explaination / Solution:
No Explaination.

Workspace
Report
Q.10
Consider the C code fragment given below.
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
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.