KONGU ENGINEERING COLLEGE, PERUNDURAI 638 060
EVEN SEMESTER 2024 - 2025 WEEKLY TEST
(Regulations 2022)
Programme : B.E Date : .02.2025
Branch : CSE Time : 3.45 PM to 4.30 PM
Semester : III
Course Code : 22GEP61 Duration : 45 Minutes
Course Name : Comprehensive Test & Viva Max. Marks : 30
Title of the topic : Pattern of the Question : MCQ Type (GATE
Pattern)
1. What is the time complexity of the following function?
void processArray(int a[], int n) {
for (int i = 0; i < n / 2; i++) {
int temp = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = temp;
}
}
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
2. O( n2 ) is the worst case time complexity, so among the given options it can represent
A) O(n)
B) O(1)
C) O (n log n)
D) All of the above
3. Consider the following C function:
int f(int n)
{
static int i = 1;
if (n >= 5)
return n;
n = n+i;
i++;
return f(n);
}
The value returned by f(1) is
A) 5
B) 6
C) 7
D) 8
4. Which of the following requires n-1 swaps?
A)Selection
B)Bubble
C)Insertion
D)All of the above
5. Which of the following statements about the Convex Hull is TRUE?
A) The convex hull of a set of points is always a triangle.
B) The convex hull is the smallest convex polygon that encloses all the given points.
C) Convex Hull algorithms only work in 2D space.
D) The number of points in a convex hull is always equal to the number of input points.
6. Which of the following is not a subsequence of the string "GATEEXAM"? (GATE2015)
A) "GAM"
B) "GEX"
C) "GXT"
D) "EXA"
7. Let 2ⁿ, n!, n³, n log n, 3ⁿ.
Which of the following is the correct order of growth from lowest to Highest?
(A) n log n, n³, 2ⁿ, 3ⁿ, n!
(B) n³, n log n, 2ⁿ, n!, 3ⁿ
(C) n log n, n³, 3ⁿ, 2ⁿ, n!
(D) n log n, n³, 2ⁿ, n!, 3ⁿ
8. Which of the following sorting algorithms has the best worst-case time complexity?
(A) Bubble Sort
(B) Selection Sort
(C) Merge Sort
(D) Insertion Sort
9. A thief wants to steal items from a shop. He has a knapsack of capacity 5 kg and the following
items:
Item Weight(kg) Value(₹)
A 2 10
B 3 15
C 2 5
What is the maximum profit the thief can obtain using the 0/1 Knapsack approach? (GATE2018)
A) ₹15
B) ₹20
C) ₹25
D) ₹30
10. Given the following points:
P(5, 10), Q(8, 14), R(3, 9), S(6, 13)
Find the two closest points using the Euclidean distance formula. (GATE2019)
(A) P and Q
(B) R and P
(C) Q and S
(D) P and S
1.c,2.d,3.c,4.a,5.b,6.c,7.a,8.c,9.c,10.c
11. Apply Prim’s algorithm to the following graph. Identify the cost of the minimum spanning
tree. (GATE2020)
A) 10
B) 13
C) 11
D) 14
E) 12
12. If 8*8 chess board is indexed as shown in given figure, identify the solution for the 8 queens
problem. (GATE2021)
1 2 3 4 5 6 7 8
1 x
2 x
3 x
4 x
5 x
6 x
7 x
8 x
A) (1,3) (2,6) (3,8) (4,2) (5,3) (6,7) (7,5) (8,2)
B) (1,3) (2,2) (3,8) (4,1) (5,2) (6,7) (7,5) (8,2)
C) (1,5) (2,6) (3,8) (4,1) (5,4) (6,7) (7,5) (8,4)
D) (1,3) (2,6) (3,8) (4,1) (5,4) (6,7) (7,5) (8,2)
E) (1,3) (2,6) (3,8) (4,1) (5,4) (6,6) (7,5) (8,2)
13. Let there be N tasks and N workers. The NXN cost matrix is as follows
1 2 3
A 18 3 15
B 4 7 14
C 13 12 7
If task 1 to A, task 2 to B, task 3 to C are assigned. Find the lower bound.
A) 49
B) 50
C) 51
D) 52
14. Consider the following array.
Which algorithm out of the following options uses the least number of comparisons (among
the array elements) to sort the above array in ascending order? (GATE2023)
A) Selection sort
B) Mergesort
C) Insertion sort
D) Quicksort using the last element as pivot
15. Identify the statement which is true about backtracking.
a) A node in a state-space tree is considered promising if it leads directly to a solution without
exploring other branches.
b) Backtracking always guarantees finding an optimal solution in the shortest possible time.
c) The algorithm explores all possible solutions but prunes paths that cannot lead to a valid
result.
d) In backtracking, once a solution is found, the algorithm stops immediately without
exploring other possibilities.
e) A state-space tree for a backtracking algorithm follows a fixed depth level for all solutions.
16. Calculate the initial lower bound for the given traveling salesman problem
A) 7
B) 8
C) 9
D) 10
E) 12
17. The number of distinct minimum-weight spanning trees of the following graph is _______
[GATE 2022]
A) 7
B) 8
C) 9
D)10
18. Which of the following sequences of array elements represents a valid max-heap?
A) 50, 30, 40, 10, 20, 35, 15
B) 50, 25, 40, 10, 30, 35, 15
C) 50, 30, 40, 20, 10, 35, 15
D) 50, 20, 40, 30, 10, 35, 15
E) 50, 40, 30, 20, 10, 35, 15
19. A message is made up entirely of characters from the set X = {P,Q,R,S,T} . The table of
probabilities of each character is shown below:
Character Probability
P 0.22
Q 0.34
R 0.17
S 0.19
T 0.08
Total 1.00
A message of 100 characters over X is encoded using Huffman coding. Then the excepted
length of the encoded message in bits is _____
A) 225
B) 226
C) 227
D) 228
20. Solve the recurrence relation:
z(n)=2z(n−1)+1,for n>1,z(1)=3
A) 2ⁿ + 1
B) 2ⁿ - 1
C) 3 · 2ⁿ - 1
D) 3 · 2ⁿ + 1
E) 2ⁿ + 3
11.d,12.d,13.c,14.c,15.c,16.a,17.c,18.c,19.a,20.c
