These essential MCQ questions are selected from the most important topics in GATE Computer Science & Information Technology 2026 as per the official GATE CS syllabus. Sections include Data Structures, Design & Analysis of Algorithms, Operating Systems, Database Management Systems, Computer Networks, and Digital Logic & Computer Organisation. For truly unlimited daily MCQ practice, visit Vooo AI Education.
💻 GATE Computer Science
1What is the time complexity of binary search on a sorted array of n elements?
Answer: B — O(log n)
Binary search repeatedly halves the search space. At each step the problem size reduces by half: n → n/2 → n/4 → ... → 1. Number of steps = log₂n. Therefore time complexity = O(log n). Prerequisite: array must be sorted. Space complexity = O(1) iterative, O(log n) recursive. Linear search = O(n). Merge sort = O(n log n). Bubble sort = O(n²). Binary search is optimal for searching in a sorted array — no algorithm can do better than O(log n) for comparison-based search.
Binary search repeatedly halves the search space. At each step the problem size reduces by half: n → n/2 → n/4 → ... → 1. Number of steps = log₂n. Therefore time complexity = O(log n). Prerequisite: array must be sorted. Space complexity = O(1) iterative, O(log n) recursive. Linear search = O(n). Merge sort = O(n log n). Bubble sort = O(n²). Binary search is optimal for searching in a sorted array — no algorithm can do better than O(log n) for comparison-based search.
2In a stack, the operations follow which principle?
Answer: B — LIFO — Last In First Out
A stack follows LIFO: the last element pushed is the first to be popped. Operations: push (insert at top), pop (remove from top), peek (view top without removing). A queue follows FIFO (first in, first out). Stack applications: function call stack, expression evaluation (infix to postfix), undo operations, backtracking (DFS). Stack can be implemented using arrays or linked lists. In GATE, stack-based questions on recursion, tree traversal and expression parsing are very common.
A stack follows LIFO: the last element pushed is the first to be popped. Operations: push (insert at top), pop (remove from top), peek (view top without removing). A queue follows FIFO (first in, first out). Stack applications: function call stack, expression evaluation (infix to postfix), undo operations, backtracking (DFS). Stack can be implemented using arrays or linked lists. In GATE, stack-based questions on recursion, tree traversal and expression parsing are very common.
3Which page replacement algorithm suffers from Belady's anomaly?
Answer: A — FIFO
Belady's anomaly: increasing the number of page frames sometimes increases the number of page faults with FIFO replacement. This is counterintuitive — more memory leading to worse performance. LRU and Optimal algorithms do NOT suffer from Belady's anomaly (they are stack algorithms). Optimal page replacement (Belady's algorithm) replaces the page that will not be used for the longest time — it gives the minimum page faults but requires future knowledge, making it impractical. LRU is a practical approximation of Optimal.
Belady's anomaly: increasing the number of page frames sometimes increases the number of page faults with FIFO replacement. This is counterintuitive — more memory leading to worse performance. LRU and Optimal algorithms do NOT suffer from Belady's anomaly (they are stack algorithms). Optimal page replacement (Belady's algorithm) replaces the page that will not be used for the longest time — it gives the minimum page faults but requires future knowledge, making it impractical. LRU is a practical approximation of Optimal.
4In SQL, which command is used to remove all rows from a table without deleting the table structure?
Answer: B — TRUNCATE
TRUNCATE removes all rows from a table but keeps the table structure — it is a DDL command, faster than DELETE, and cannot be rolled back. DELETE is a DML command that removes rows (with or without WHERE clause) and can be rolled back. DROP removes the entire table structure and data — cannot be rolled back. Key difference: DELETE fires triggers and logs each row deletion (slow for large tables); TRUNCATE does not fire row-level triggers and deallocates data pages directly (fast).
TRUNCATE removes all rows from a table but keeps the table structure — it is a DDL command, faster than DELETE, and cannot be rolled back. DELETE is a DML command that removes rows (with or without WHERE clause) and can be rolled back. DROP removes the entire table structure and data — cannot be rolled back. Key difference: DELETE fires triggers and logs each row deletion (slow for large tables); TRUNCATE does not fire row-level triggers and deallocates data pages directly (fast).
5The OSI model layer responsible for end-to-end communication and error recovery is the:
Answer: B — Transport layer
The Transport layer (Layer 4) provides end-to-end communication, error recovery, flow control, and segmentation. Protocols: TCP (reliable, connection-oriented) and UDP (unreliable, connectionless). Network layer (Layer 3) handles routing between networks — IP protocol. Data Link layer (Layer 2) handles node-to-node delivery on the same network — MAC addresses, error detection (not correction). Remember OSI layers: Physical, Data Link, Network, Transport, Session, Presentation, Application — "Please Do Not Throw Sausage Pizza Away."
The Transport layer (Layer 4) provides end-to-end communication, error recovery, flow control, and segmentation. Protocols: TCP (reliable, connection-oriented) and UDP (unreliable, connectionless). Network layer (Layer 3) handles routing between networks — IP protocol. Data Link layer (Layer 2) handles node-to-node delivery on the same network — MAC addresses, error detection (not correction). Remember OSI layers: Physical, Data Link, Network, Transport, Session, Presentation, Application — "Please Do Not Throw Sausage Pizza Away."
6What is the minimum number of 2-input NAND gates required to implement a NOT gate?
Answer: A — 1
A NOT gate can be made from a single NAND gate by connecting both inputs together: if A is input to both inputs of a NAND gate, output = NAND(A,A) = NOT(A·A) = NOT(A). NAND and NOR are universal gates — any logic circuit can be built using only NAND gates or only NOR gates. An AND gate needs 2 NAND gates. An OR gate needs 3 NAND gates. An XOR gate needs 4 NAND gates. NAND universality is very important in digital design as NAND gates are cheaper to fabricate in CMOS technology.
A NOT gate can be made from a single NAND gate by connecting both inputs together: if A is input to both inputs of a NAND gate, output = NAND(A,A) = NOT(A·A) = NOT(A). NAND and NOR are universal gates — any logic circuit can be built using only NAND gates or only NOR gates. An AND gate needs 2 NAND gates. An OR gate needs 3 NAND gates. An XOR gate needs 4 NAND gates. NAND universality is very important in digital design as NAND gates are cheaper to fabricate in CMOS technology.
7Which of the following sorting algorithms is stable and has O(n log n) worst-case time complexity?
Answer: C — Merge Sort
Merge Sort is stable (preserves relative order of equal elements) and has O(n log n) in all cases (best, average, worst). Quick Sort: average O(n log n) but worst case O(n²) — not stable. Heap Sort: O(n log n) worst case but NOT stable. Selection Sort: O(n²) — not stable. Merge Sort's disadvantage: requires O(n) extra space. In GATE, stability matters when sorting records with multiple keys. A stable sort ensures that records with equal keys maintain their original relative order.
Merge Sort is stable (preserves relative order of equal elements) and has O(n log n) in all cases (best, average, worst). Quick Sort: average O(n log n) but worst case O(n²) — not stable. Heap Sort: O(n log n) worst case but NOT stable. Selection Sort: O(n²) — not stable. Merge Sort's disadvantage: requires O(n) extra space. In GATE, stability matters when sorting records with multiple keys. A stable sort ensures that records with equal keys maintain their original relative order.
8Deadlock in an operating system can occur only if all four conditions hold simultaneously. Which is NOT one of them?
Answer: C — Preemption allowed
The four necessary conditions for deadlock (Coffman conditions, 1971): (1) Mutual exclusion — resource held by one process at a time; (2) Hold and wait — a process holds a resource and waits for another; (3) No preemption — resources cannot be forcibly taken; (4) Circular wait — a circular chain of processes each waiting for a resource held by the next. "Preemption allowed" is the OPPOSITE of condition 3 — if preemption is allowed, deadlock cannot occur. Deadlock prevention works by eliminating at least one of these four conditions.
The four necessary conditions for deadlock (Coffman conditions, 1971): (1) Mutual exclusion — resource held by one process at a time; (2) Hold and wait — a process holds a resource and waits for another; (3) No preemption — resources cannot be forcibly taken; (4) Circular wait — a circular chain of processes each waiting for a resource held by the next. "Preemption allowed" is the OPPOSITE of condition 3 — if preemption is allowed, deadlock cannot occur. Deadlock prevention works by eliminating at least one of these four conditions.
9In a relational database, a foreign key is used to:
Answer: B — Establish a link between two tables
A foreign key in one table references the primary key of another table, enforcing referential integrity — it establishes a relationship between two tables. A primary key uniquely identifies each row in a table (cannot be NULL or duplicate). A candidate key is any column set that could be a primary key. A super key is any set of columns that uniquely identifies a row. Foreign keys prevent orphan records — you cannot insert a foreign key value that does not exist in the referenced primary key column.
A foreign key in one table references the primary key of another table, enforcing referential integrity — it establishes a relationship between two tables. A primary key uniquely identifies each row in a table (cannot be NULL or duplicate). A candidate key is any column set that could be a primary key. A super key is any set of columns that uniquely identifies a row. Foreign keys prevent orphan records — you cannot insert a foreign key value that does not exist in the referenced primary key column.
10The time complexity of the Floyd-Warshall algorithm for finding all-pairs shortest paths in a graph with V vertices is:
Answer: C — O(V³)
Floyd-Warshall uses dynamic programming with three nested loops over all vertices: O(V³) time and O(V²) space. It finds shortest paths between all pairs of vertices and works with negative edge weights (but not negative cycles). Dijkstra's algorithm finds shortest path from a single source: O(V² ) with adjacency matrix, O((V+E) log V) with priority queue. Bellman-Ford handles negative weights from single source: O(VE). Floyd-Warshall is preferred for dense graphs where all-pairs paths are needed.
Floyd-Warshall uses dynamic programming with three nested loops over all vertices: O(V³) time and O(V²) space. It finds shortest paths between all pairs of vertices and works with negative edge weights (but not negative cycles). Dijkstra's algorithm finds shortest path from a single source: O(V² ) with adjacency matrix, O((V+E) log V) with priority queue. Bellman-Ford handles negative weights from single source: O(VE). Floyd-Warshall is preferred for dense graphs where all-pairs paths are needed.
Ready to crack GATE CS 2026?
Get free daily GATE Computer Science MCQs. Unlimited practice starts from just ₹120/month.
See Plans — Starts at ₹120