FOLLOWING QUESTIONS ASKED IN GATE
1) Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?
(A) t1 = 5
(B) t1 < t2
(C) t1 > t2
(D) t1 = t2
Answer: (C)
Explanation: When first element or last element is chosen as pivot, Quick Sort‘s worst case occurs for the sorted arrays.
In every step of quick sort, numbers are divided as per the following recurrence.
T(n) = T(n-1) + O(n)
2) Consider the following C function in which size is the number of elements in the array E:
The value returned by the function MyX is the
int MyX(int *E, unsigned int size){ int Y = 0; int Z; int i, j, k; for (i = 0; i < size; i++) Y = Y + E[i]; for (i = 0; i < size; i++) for (j = i; j < size; j++) { Z = 0; for (k = i; k <= j; k++) Z = Z + E[k]; if (Z > Y) Y = Z; } return Y;} |
(A) maximum possible sum of elements in any sub-array of array E.
(B) maximum element in any sub-array of array E.
(C) sum of the maximum elements in all possible sub-arrays of array E
(D) the sum of all the elements in the array E.
Answer: (A)
Explanation: The function does following
Y is used to store maximum sum seen so far and Z is used to store current sum
1) Initialize Y as sum of all elements
2) For every element, calculate sum of all subarrays starting with arr[i]. Store the current sum in Z. If Z is greater than Y, then update Y.
3) What is the return value of f(p, p) if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f(int &x, int c) {
c = c - 1;
if (c == 0) return 1;
x = x + 1;
return f(x, c) * x;
}
(A) 3024
(B) 6561
(C) 55440
(D) 161051
Answer (B)
Since c is passed by value and x is passed by reference, all functions will have same copy of x, but different copies of c.
f(5, 5) = f(x, 4)*x = f(x, 3)*x*x = f(x, 2)*x*x*x = f(x, 1)*x*x*x*x = 1*x*x*x*x = x^4
Since x is incremented in every function call, it becomes 9 after f(x, 2) call. So the value of expression x^4 becomes 9^4 which is 6561.
#include <stdio.h>int f(int &x, int c){ c = c - 1; if (c == 0) return 1; x = x + 1; return f(x, c) * x;}int main(){ int p = 5; printf("%d", f(p, p));} |
4) The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
(A) 10, 20, 15, 23, 25, 35, 42, 39, 30
(B) 15, 10, 25, 23, 20, 42, 35, 39, 30
(C) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30
Ans (D)
The following is the constructed tree
30
/ \
20 39
/ \ / \
10 25 35 42
\ /
15 23
5) Consider the following function
int unknown(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}
What is the returned value of the above function?
(A) Θ(n^2)
(B) Θ(n^2Logn)
(C) Θ(n^3)
(D) Θ(n^3Logn)
Answer (B)
The outer loop runs n/2 or Θ(n) times. The inner loop runs Θ(Logn) times (Note that j is divide by 2 in every iteration). So the statement “k = k + n/2;” runs Θ(nLogn) times. The statement increases value of k by n/2. So the value of k becomes n/2*Θ(nLogn) which is Θ(n^2Logn)
6) The number of elements that can be sorted in Θ(logn) time using heap sort is
(A) Θ(1)
(B) Θ(sqrt(logn))
(C) Θ(Log n/(Log Log n))
(d) Θ(Log n)
Answer (C)
Time complexity of Heap Sort is Θ(mLogm) for m input elements. For m = Θ(Log n/(Log Log n)), the value of Θ(m * Logm) will be Θ( [Log n/(Log Log n)] * [Log (Log n/(Log Log n))] ) which will be Θ( [Log n/(Log Log n)] * [ Log Log n – Log Log Log n] ) which is Θ(Log n)
7) The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed
void find_and_replace(char *A, char *oldc, char *newc) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}
The procedure is tested with the following four test cases
(1) oldc = “abc”, newc = “dab”
(2) oldc = “cde”, newc = “bcd”
(3) oldc = “bca”, newc = “cda”
(4) oldc = “abc”, newc = “bac”
The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?
(A) Only one
(B) Only two
(C) Only three
(D) All four
Answer (B)
The test cases 3 and 4 are the only cases that capture the flaw. The code doesn’t work properly when an old character is replaced by a new character and the new character is again replaced by another new character. This doesn’t happen in test cases (1) and (2), it happens only in cases (3) and (4).
8) If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?
(A) None
(B) 2 only
(C) 3 and 4 only
(D) 4 only
Answer (C)
#include <stdio.h>#include <string.h>void find_and_replace(char *A, char *oldc, char *newc) { for (int i = 0; i < 5; i++) for (int j = 0; j < 3; j++) if (A[i] == oldc[j]) A[i] = newc[j];}int main(){ char *oldc1 = "abc", *newc1 = "dab"; char *oldc2 = "cde", *newc2 = "bcd"; char *oldc3 = "bca", *newc3 = "cda"; char *oldc4 = "abc", *newc4 = "bac"; char test[] = "abcde"; printf("Test 2\n"); printf("%s\n", test); find_and_replace(test, oldc2, newc2); printf ("%s\n", test); printf("\nTest 3\n"); strcpy(test, "abcde"); printf("%s\n", test); find_and_replace(test, oldc3, newc3); printf ("%s\n", test); printf("\nTest 4\n"); strcpy(test, "abcde"); printf("%s\n", test); find_and_replace(test, oldc4, newc4); printf ("%s\n", test);} |
Output:
Test 2
abcde
abbcd
Test 3
abcde
addde
Test 4
abcde
aacde
9) Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
A) P Only
B) Q Only
C) Both P and Q
D) Neither P nor Q
Answer (C)
Q is true: Since the graph is undirected, every edge increases the sum of degrees by 2.
P is true: If we consider sum of degrees and subtract all even degrees, we get an even number (because Q is true). So total number of odd degree vertices must be even.
10) Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
(A) 1/8
(B) 1
(C) 7
(D) 8
Answer (C)
A cycle of length 3 can be formed with 3 vertices. There can be total 8C3 ways to pick 3 vertices from 8. The probability that there is an edge between two vertices is 1/2. So expected number of unordered cycles of length 3 = (8C3)*(1/2)^3 = 7
11) What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(A) Θ(n2)
(B) Θ(n2 Logn)
(C) Θ(n3)
(D) Θ(n3 Logn)
Answer (C).
Time complexity of Bellman-Ford algorithm is Θ(VE) where V is number of vertices and E is number edges (Seethis). If the graph is complete, the value of E becomes Θ(V2). So overall time complexity becomes Θ(V3)
12) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
(A) 1,2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only
Answer (A)
1 is true because cycle detection can be done in polynomial time using DFS (See this).
2 is true because P is a subset of NP.
3 is true because NP complete is also a subset of NP and NP means Non-deterministic Polynomial time solution existS.
13) Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Answer (C)
The worst case occurs for a skewed tree. In a skewed tree, when a new node is inserted as a child of bottommost node, the time for insertion requires traversal of all node. For example, consider the following tree and the case when something smaller than 70 is inserted.
100
/
90
/
80
/
70
14) Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)
Answer (B)
Selection sort requires only O(n) swaps.
15) Consider the following operation along with Enqueue and Dequeue operations on
queues, where k is a global parameter
MultiDequeue(Q){
m = k
while (Q is not empty and m > 0) {
Dequeue(Q)
m = m - 1
}
}
What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?
(A) Θ(n)
(B) Θ(n + k)
(C) Θ(nk)
(D) Θ(n2)
Answer (A)
Since the queue is empty initially, the condition of while loop never becomes true. So the time complexity is Θ(n)
16) Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
A) P Only
B) Q Only
C) Both P and Q
D) Neither P nor Q
Answer (C)
Since the graph is undirected, every edge increases the sum of degrees by 2.
P is true: If we consider sum of degrees and subtract all even degrees, we get an even number (because Q is true). So total number of odd degree vertices must be even.
17) Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?
(A) 1/8
(B) 1
(C) 7
(D) 8
Answer (C)
A cycle of length 3 can be formed with 3 vertices. There can be total 8C3 ways to pick 3 vertices from 8. The probability that there is an edge between two vertices is 1/2. So expected number of unordered cycles of length 3 = (8C3)*(1/2)^3 = 7
18) What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(A) Θ(n2)
(B) Θ(n2 Logn)
(C) Θ(n3)
(D) Θ(n3 Logn)
Answer (C).
Time complexity of Bellman-Ford algorithm is Θ(VE) where V is number of vertices and E is number edges . If the graph is complete, the value of E becomes Θ(V2). So overall time complexity becomes Θ(V3)
19) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
(A) 1,2 and 3
(B) 1 and 2 only
(C) 2 and 3 only
(D) 1 and 3 only
Answer (A)
1 is true because cycle detection can be done in polynomial time using DFS
2 is true because P is a subset of NP.
3 is true because NP complete is also a subset of NP and NP means Non-deterministic Polynomial time solution exists.
20) Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)
Answer (C)
The worst case occurs for a skewed tree. In a skewed tree, when a new node is inserted as a child of bottom most node, the time for insertion requires traversal of all node. For example, consider the following tree and the case when something smaller than 70 is inserted.
100
/
90
/
80
/
70