GATE Core Subject Knowledge & Technical Concepts 2 — Questions and Answers
Question 1: In a binary search tree, the worst-case time complexity for searching an element is:
- O(log n)
- O(n) (Correct answer)
- O(n log n)
- O(1)
Correct answer: O(n)
In the worst case (a skewed BST), every node must be visited, giving O(n) time complexity.
Question 2: Which of the following sorting algorithms has the best average-case time complexity?
- Bubble Sort
- Insertion Sort
- Merge Sort (Correct answer)
- Selection Sort
Correct answer: Merge Sort
Merge Sort has O(n log n) average-case complexity, which is optimal for comparison-based sorting.
Question 3: The output of a JK flip-flop when J=1 and K=1 is:
- Set (Q=1)
- Reset (Q=0)
- No change
- Toggle (Correct answer)
Correct answer: Toggle
When both J and K are 1, the JK flip-flop toggles its output on the clock edge.
Question 4: In a full adder, the carry-out expression is:
- A XOR B XOR Cin
- A AND B OR Cin
- AB + BCin + ACin (Correct answer)
- A XNOR B AND Cin
Correct answer: AB + BCin + ACin
The carry-out of a full adder is Cout = AB + BCin + ACin (carry generated or propagated).
Question 5: Which scheduling algorithm can lead to starvation?
- Round Robin
- FCFS
- Priority Scheduling (Correct answer)
- Shortest Job First (non-preemptive)
Correct answer: Priority Scheduling
Priority Scheduling can starve low-priority processes if high-priority processes continuously arrive.
Question 6: The minimum number of NOR gates required to implement the Boolean function F = A + B is:
- 1
- 2
- 3 (Correct answer)
- 4
Correct answer: 3
F = A + B = (A NOR B) NOR (A NOR B), requiring 3 NOR gates (two for inputs, one for OR).
Question 7: In Dijkstra's shortest path algorithm, which data structure gives the most efficient implementation?
- Stack
- Queue
- Priority Queue (Min-Heap) (Correct answer)
- Hash Table
Correct answer: Priority Queue (Min-Heap)
A priority queue (min-heap) allows efficient extraction of the minimum distance vertex in O(log V) time.
GATE Core Subject Knowledge & Technical Concepts 2
In a binary search tree, the worst-case time complexity for searching an element is: