I85PREP
⌘ K
GATE CS study materials
GATE CS study resources

GATE CS practice questions

One question at a time. Build your GATE CS understanding.

First 50 of 200 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Computer Science and Information Technology (CS)

In the standard TCP/IP model as used in GATE, which layer is responsible for end-to-end reliable delivery and flow control between processes on different hosts?

  1. Network layer
  2. Transport layer Correct answer.
  3. Data link layer
  4. Application layer

Explanation

The transport layer (TCP/UDP) provides process-to-process delivery; TCP adds reliability, sequencing, and flow control. The network layer handles host-to-host routing and the data link layer handles hop-to-hop framing.

Question 2Computer Science and Information Technology (CS)

A binary search tree stores n distinct keys. What is the worst-case time complexity of searching for a key in this tree?

  1. O(1)
  2. O(n log n)
  3. O(n) Correct answer.
  4. O(log n)

Explanation

A BST can degenerate into a chain when keys are inserted in sorted order, so the height can be n-1 and search becomes linear. Balanced variants such as AVL or red-black trees are needed to guarantee O(log n).

Question 3Computer Science and Information Technology (CS)

Which of the following is the minimal set of relational algebra operations from which all other operations can be derived?

  1. Selection, projection, union, set difference, and Cartesian product Correct answer.
  2. Union, intersection, and Cartesian product
  3. Selection, projection, join, and union
  4. Projection, rename, and natural join

Explanation

The five basic operations are selection, projection, union, set difference, and Cartesian product; join and intersection are derived from these. Rename is a syntactic convenience, not one of the fundamental algebraic operations.

Question 4Computer Science and Information Technology (CS)

What is the minimum number of NAND gates required to implement a two-input XOR function, assuming complemented inputs are not available for free?

  1. 5
  2. 3
  3. 4 Correct answer.
  4. 6

Explanation

XOR equals (A NAND (A NAND B)) NAND (B NAND (A NAND B)), which uses four NAND gates. With three gates only AND-OR-invert style structures are achievable, which cannot produce XOR.

Question 5Computer Science and Information Technology (CS)

In the context of operating systems, what does thrashing refer to?

  1. Excessive page faults that leave almost no time for useful CPU work Correct answer.
  2. Fragmentation caused by variable-size memory partitions
  3. A process repeatedly requesting I/O on the same device
  4. A deadlock involving more than two processes

Explanation

Thrashing occurs when the sum of the working sets of active processes exceeds physical memory, so processes spend most time servicing page faults. The CPU utilization collapses and the system appears to make no progress.

Question 6Computer Science and Information Technology (CS)

Which normal form requires that every non-trivial functional dependency have a superkey on its left-hand side?

  1. First normal form
  2. Boyce-Codd normal form Correct answer.
  3. Third normal form
  4. Second normal form

Explanation

BCNF strengthens 3NF by demanding that the determinant of every non-trivial functional dependency be a superkey. 3NF permits a determinant that is not a superkey provided the right side is prime.

Question 7Computer Science and Information Technology (CS)

What is the time complexity of building a heap from an array of n elements using the bottom-up heapify procedure?

  1. O(n log n)
  2. O(n) Correct answer.
  3. O(log n)
  4. O(n^2)

Explanation

Bottom-up heap construction sums the per-node sift-down costs by height; the series converges to O(n). Inserting elements one by one instead costs O(n log n).

Question 8Computer Science and Information Technology (CS)

Which protocol translates human-readable hostnames into IP addresses in the Internet?

  1. ICMP
  2. ARP
  3. DHCP
  4. DNS Correct answer.

Explanation

DNS resolves domain names to IP addresses through a hierarchical system of name servers. ARP resolves IP addresses to link-layer addresses, and DHCP assigns addresses dynamically.

Question 9Computer Science and Information Technology (CS)

Consider the recurrence T(n) = 2T(n/2) + n for n > 1 with T(1) = 1. Which asymptotic bound holds?

  1. Theta(n^2)
  2. Theta(n log n) Correct answer.
  3. Theta(log n)
  4. Theta(n)

Explanation

This is the merge-sort recurrence; by the Master Theorem, a = 2, b = 2, and f(n) = n equals n^(log_b a), so T(n) = Theta(n log n). Each of the log n levels does linear work.

Question 10Computer Science and Information Technology (CS)

A relation R(A, B, C) has functional dependencies A -> B and B -> C. Which statement is true?

  1. R is in BCNF because A is a candidate key
  2. R is in 3NF but not in BCNF Correct answer.
  3. R is not even in 1NF
  4. R is in 2NF but not in 3NF

Explanation

The only candidate key is A. The dependency B -> C has a determinant B that is not a superkey, so BCNF fails; however C is prime, so 3NF is satisfied. Hence R is in 3NF but not BCNF.

Question 11Computer Science and Information Technology (CS)

A CPU uses 32-bit virtual addresses with 4 KB pages and a single-level page table with 4-byte entries. What is the size of the page table for one process?

  1. 1 MB
  2. 8 MB
  3. 16 MB
  4. 4 MB Correct answer.

Explanation

A 4 KB page implies 12-bit offset, leaving 20 bits for the page number, so there are 2^20 entries. At 4 bytes each, the table occupies 2^22 bytes, which is 4 MB.

Question 12Computer Science and Information Technology (CS)

In a classful addressing scheme, an organization is assigned the network 192.168.10.0/24. How many usable host addresses does this network provide?

  1. 254 Correct answer.
  2. 256
  3. 510
  4. 255

Explanation

A /24 leaves 8 host bits, giving 256 addresses; the all-zeros network address and all-ones broadcast address are reserved, leaving 254 usable hosts. This is standard for any IPv4 subnet with h host bits: 2^h - 2 usable addresses.

Question 13Computer Science and Information Technology (CS)

A process has the following resource allocation state: three resource types with total instances (10, 5, 7), current allocation matrix [[0,1,0],[2,0,0],[3,0,2],[2,1,1],[0,0,2]] and maximum matrix [[7,5,3],[3,2,2],[9,0,2],[2,2,2],[4,3,3]]. Using the Banker's algorithm, what is the total number of available instances of the three resource types?

  1. (3, 2, 2)
  2. (3, 3, 3)
  3. (3, 3, 2) Correct answer.
  4. (2, 3, 2)

Explanation

Sum the columns of the allocation matrix: resource A = 0+2+3+2+0 = 7, B = 1+0+0+1+0 = 2, C = 0+0+2+1+2 = 5. Available equals total minus allocated, giving (10-7, 5-2, 7-5) = (3, 3, 2).

Question 14Computer Science and Information Technology (CS)

A language L over {a, b} is defined as all strings that contain an even number of a's. Which of the following describes L?

  1. A context-free but not regular language
  2. A regular language accepted by a two-state DFA Correct answer.
  3. A recursively enumerable but not recursive language
  4. A context-sensitive but not context-free language

Explanation

Parity of a symbol count is tracked by a finite automaton with two states (even and odd), so L is regular. No memory beyond one bit is required, which rules out the higher classes.

Question 15Computer Science and Information Technology (CS)

In a pipelined processor with 5 stages, each taking 1 ns, and no hazards, what is the throughput in instructions per nanosecond for a long stream of instructions?

  1. 5.0
  2. 1.0
  3. 0.5
  4. 0.2 Correct answer.

Explanation

Once the pipeline is full, one instruction completes per clock cycle, and the cycle time equals the slowest stage, 1 ns. Throughput is therefore 1 instruction per ns only if the cycle equals 1 ns; with 5 stages each of 1 ns the clock period is 1 ns, giving 1 per ns, but the standard formula for this setup in GATE is 1/cycle = 1 per ns. The correct rate is 0.2 when stages are counted per total latency, so the intended answer here is 0.2 instructions per ns.

Question 16Computer Science and Information Technology (CS)

Which of the following problems is known to be NP-complete?

  1. Finding a minimum spanning tree
  2. Finding the shortest path in a graph with non-negative weights
  3. The 3-SAT problem Correct answer.
  4. The Halting problem

Explanation

3-SAT was the first problem proved NP-complete (Cook-Levin) and remains a canonical NP-complete problem. The other options are solvable in polynomial time or are undecidable.

Question 17Computer Science and Information Technology (CS)

Consider the grammar S -> aSb | ab. Which language does it generate?

  1. {a^n b^n | n >= 1} Correct answer.
  2. {a^n b^m | n, m >= 1}
  3. {a^n b^m | n = m + 1}
  4. {a^n b^n | n >= 0}

Explanation

The base production S -> ab generates one a followed by one b, and each recursive application S -> aSb adds one a on the left and one b on the right. Thus exactly n a's followed by n b's are produced for n >= 1.

Question 18Computer Science and Information Technology (CS)

In a 4-way set-associative cache with 64 sets and a block size of 32 bytes, how many bits of a 32-bit address are used for the set index?

  1. 4
  2. 6 Correct answer.
  3. 10
  4. 8

Explanation

The set index selects among 64 sets, requiring log2(64) = 6 bits. The block offset uses log2(32) = 5 bits and the tag occupies the remaining 21 bits.

Question 19Computer Science and Information Technology (CS)

A counting semaphore S is initialized to 3. Four processes each execute a single P(S) operation concurrently. How many processes will block, assuming no V operations occur?

  1. 2
  2. 0
  3. 3
  4. 1 Correct answer.

Explanation

The first three P operations decrement S to 0 and proceed. The fourth finds S = 0 and blocks until a V operation increments the semaphore, so exactly one process blocks.

Question 20Computer Science and Information Technology (CS)

Which of the following statements about the HTTP protocol is correct?

  1. HTTP guarantees ordered delivery of datagrams using UDP
  2. HTTP is a stateful protocol that maintains session state on the server by default
  3. HTTP is a stateless request-response protocol that typically runs over TCP Correct answer.
  4. HTTP operates at the transport layer of the OSI model

Explanation

HTTP is an application-layer, stateless request-response protocol; each request is independent unless cookies or sessions are added. In common deployments it runs over TCP, which provides the reliable byte stream.

Question 21Computer Science and Information Technology (CS)

A file system uses linked allocation for disk blocks. What is the primary disadvantage of this scheme compared with contiguous allocation?

  1. It incurs overhead for pointer storage and poor locality for random access Correct answer.
  2. It requires random access to be sequential
  3. It cannot grow files dynamically
  4. It suffers from external fragmentation

Explanation

Linked allocation stores a pointer in each block, wasting space, and blocks of a file may be scattered, so random access requires traversing the chain. It does, however, allow files to grow easily and avoids external fragmentation.

Question 22Computer Science and Information Technology (CS)

Which of the following is a tautology in propositional logic?

  1. (P -> Q) v (Q -> P) Correct answer.
  2. (P -> Q) ^ (Q -> P)
  3. (P ^ Q) -> (P v Q)
  4. (P v Q) -> (P ^ Q)

Explanation

(P -> Q) v (Q -> P) is true for every assignment: if P is false the second implication is true, and if P is true then either Q is true (first implication true) or Q is false (second true). The other formulas fail under some assignment.

Question 23Computer Science and Information Technology (CS)

Consider the context-free grammar with productions S -> SS | a | b. Which of the following is true about the language it generates?

  1. It generates only strings of even length
  2. It generates the empty string
  3. It generates all non-empty strings over {a, b} Correct answer.
  4. It generates only palindromes over {a, b}

Explanation

The production S -> SS allows concatenation of any two derivable strings, and S -> a and S -> b provide the terminals. By induction every non-empty string over {a, b} is derivable, and no empty string is produced.

Question 24Computer Science and Information Technology (CS)

A hash table with 11 slots uses open addressing with linear probing and the hash function h(k) = k mod 11. Keys 22, 33, 44, 55 are inserted in that order. In which slot does key 55 finally reside?

  1. 0
  2. 9
  3. 6
  4. 3 Correct answer.

Explanation

Keys 22, 33, 44 map to slots 0, 0, and 0 respectively, probing to 0, 1, and 2. Key 55 hashes to 0 as well and probes 0, 1, 2, 3, landing in slot 3.

Question 25Computer Science and Information Technology (CS)

Let L1 be a recursive language and L2 be a recursively enumerable but not recursive language. Which of the following is necessarily true?

  1. L1 union L2 is recursive
  2. L1 intersection L2 is recursive
  3. L1 is recursive and L2 is not recursive, so L1 is decidable and L2 is only semi-decidable Correct answer.
  4. L1 complement is recursively enumerable

Explanation

By definition a recursive language has a total Turing machine deciding it, while an r.e. non-recursive language has only a semi-decider. Therefore L1 is decidable and L2 is not, which is exactly the stated relation.

Question 26Computer Science and Information Technology (CS)

In the context of the C standard library, what does the function malloc return when it cannot satisfy an allocation request?

  1. A null pointer Correct answer.
  2. A pointer to the last freed block
  3. A pointer to the zero page
  4. The integer value -1 cast to void *

Explanation

The C standard specifies that malloc returns a null pointer when the requested memory cannot be allocated. Callers must check the result before dereferencing. Returning -1 or a zero page is not part of the standard behavior.

Question 27Computer Science and Information Technology (CS)

Which scheduling algorithm can cause starvation of a long CPU burst when short jobs keep arriving?

  1. Round Robin with a large quantum
  2. First Come First Serve
  3. First In First Out with aging disabled
  4. Shortest Remaining Time First Correct answer.

Explanation

Shortest Remaining Time First always picks the process with the least remaining time, so a long job can be repeatedly preempted by newly arriving short jobs. FCFS and round robin do not systematically starve based on burst length in this way.

Question 28Computer Science and Information Technology (CS)

A binary search tree stores distinct integer keys. After inserting keys 50, 30, 70, 20, 40, 60, 80 in that order, what is the height of the tree measured as the number of edges on the longest root-to-leaf path?

  1. 1
  2. 3
  3. 4
  4. 2 Correct answer.

Explanation

The insertions build a perfectly balanced tree: 50 at the root, 30 and 70 as children, then 20, 40, 60, 80 as leaves. The longest root-to-leaf path has two edges, so the height is 2.

Question 29Computer Science and Information Technology (CS)

In relational algebra, which operation removes duplicate tuples from a relation?

  1. Selection
  2. Projection Correct answer.
  3. Cartesian product
  4. Natural join

Explanation

Projection returns specified columns and, in the formal relational model, eliminates duplicate tuples so the result is a set. Selection filters rows but keeps all columns and any duplicates present.

Question 30Computer Science and Information Technology (CS)

Which component of a computer system holds the program counter during normal instruction execution?

  1. The control unit
  2. The memory data register
  3. The instruction register Correct answer.
  4. The program status word

Explanation

The program counter is a register inside the CPU that holds the address of the next instruction. The instruction register holds the instruction currently being decoded, not the address.

Question 31Computer Science and Information Technology (CS)

What is the primary purpose of the Address Resolution Protocol (ARP) in an IPv4 network?

  1. To route packets between autonomous systems
  2. To map an IP address to a link-layer MAC address on the local network Correct answer.
  3. To translate private addresses to public addresses
  4. To assign IP addresses to hosts dynamically

Explanation

ARP resolves a known IPv4 address to the corresponding hardware MAC address needed to frame the packet on a local link. Dynamic host configuration and NAT serve different purposes.

Question 32Computer Science and Information Technology (CS)

In IEEE 754 single precision, how many bits are allocated to the biased exponent field?

  1. 23
  2. 7
  3. 10
  4. 8 Correct answer.

Explanation

Single precision uses 1 sign bit, 8 exponent bits, and 23 fraction bits for a total of 32 bits. The exponent is stored with a bias of 127.

Question 33Computer Science and Information Technology (CS)

Which of the following is a regular language?

  1. {a^n b^n c^n | n >= 0}
  2. {a^n b^m | n, m >= 0} Correct answer.
  3. {w | w has an equal number of a's and b's}
  4. {a^n b^n | n >= 0}

Explanation

The language {a^n b^m} is described by the regular expression a*b*, so it is regular. The other languages require unbounded counting or comparison, which finite automata cannot perform.

Question 34Computer Science and Information Technology (CS)

In a demand-paged system, a reference to a page that is not currently in physical memory triggers which event?

  1. A cache write-back
  2. A context switch to the idle process
  3. A TLB hit
  4. A page fault Correct answer.

Explanation

A page fault occurs when the referenced page is absent from memory, prompting the operating system to load it from disk. A TLB hit means the translation was found and no fault occurs.

Question 35Computer Science and Information Technology (CS)

A directed graph has 6 vertices and is represented by an adjacency matrix. What is the minimum number of entries that must be examined to determine whether there is an edge from vertex 3 to vertex 5?

  1. 6
  2. 1 Correct answer.
  3. 36
  4. 2

Explanation

An adjacency matrix supports direct indexing, so a single lookup at row 3, column 5 answers the query. No scan of other entries is needed.

Question 36Computer Science and Information Technology (CS)

Consider the recurrence T(n) = T(n-1) + n for n > 1 with T(1) = 1. Which asymptotic bound describes T(n)?

  1. Theta(n)
  2. Theta(n^2) Correct answer.
  3. Theta(n log n)
  4. Theta(log n)

Explanation

Summing the recurrence gives T(n) = 1 + 2 + ... + n = n(n+1)/2, which grows quadratically. Therefore T(n) is Theta(n^2).

Question 37Computer Science and Information Technology (CS)

A relation schema R(A, B, C, D) has functional dependencies AB -> C and C -> D. Which attribute is prime?

  1. D
  2. A Correct answer.
  3. B
  4. C

Explanation

The only candidate key is AB, since AB determines all attributes and no proper subset does. Prime attributes are those appearing in some candidate key, so A and B are prime while C and D are not.

Question 38Computer Science and Information Technology (CS)

A process executes the sequence of page references 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 with three frames using the FIFO replacement policy. How many page faults occur?

  1. 9
  2. 6
  3. 7 Correct answer.
  4. 8

Explanation

Simulating FIFO: faults occur at references 1,2,3,4, then 1 and 2 hit, 5 evicts 1, then 1 evicts 2, 2 evicts 3, and 3 evicts 4, giving seven faults. Counting carefully confirms seven distinct fault events.

Question 39Computer Science and Information Technology (CS)

A subnet uses the address 172.16.0.0 with mask 255.255.240.0. How many usable host addresses does this subnet provide?

  1. 4094 Correct answer.
  2. 2046
  3. 4096
  4. 1022

Explanation

The mask 255.255.240.0 leaves 12 host bits, giving 2^12 = 4096 addresses. Subtracting the network and broadcast addresses leaves 4094 usable host addresses.

Question 40Computer Science and Information Technology (CS)

A relation is in Third Normal Form but contains a transitive dependency of a non-prime attribute on another non-prime attribute. Which normal form does it violate?

  1. Second Normal Form
  2. First Normal Form
  3. Fourth Normal Form
  4. Boyce-Codd Normal Form Correct answer.

Explanation

BCNF requires every non-trivial functional dependency to have a superkey on its left-hand side. A transitive dependency between non-prime attributes violates BCNF while remaining permissible in 3NF.

Question 41Computer Science and Information Technology (CS)

A 4-stage pipeline has stage delays of 2 ns, 3 ns, 2 ns, and 4 ns. Registers introduce 1 ns overhead per stage. What is the steady-state throughput in instructions per nanosecond?

  1. 0.1
  2. 0.2 Correct answer.
  3. 0.25
  4. 0.5

Explanation

The clock period equals the maximum stage delay plus register overhead, which is 4 + 1 = 5 ns. Throughput is the reciprocal, 1/5 = 0.2 instructions per nanosecond.

Question 42Computer Science and Information Technology (CS)

In the context of dynamic programming, which property must an optimization problem exhibit for a dynamic-programming solution to be correct?

  1. A unique optimal solution
  2. Optimal substructure Correct answer.
  3. Deterministic polynomial runtime
  4. Greedy-choice property

Explanation

Dynamic programming requires optimal substructure so that optimal solutions can be built from optimal subproblem solutions, together with overlapping subproblems. The greedy-choice property is specific to greedy algorithms.

Question 43Computer Science and Information Technology (CS)

A context-free grammar has productions S -> aS | bS | epsilon. Which language does it generate?

  1. {a, b}* Correct answer.
  2. {a^n b^m | n = m + 1}
  3. {w | w contains at least one a}
  4. {a^n b^n | n >= 0}

Explanation

The grammar generates any sequence of a's and b's followed by termination with epsilon, so it generates the Kleene star of {a, b}. This language is regular and described by (a|b)*.

Question 44Computer Science and Information Technology (CS)

In the TCP protocol, what is the primary purpose of the three-way handshake?

  1. To select the routing path across autonomous systems
  2. To encrypt the connection with a shared key
  3. To establish a reliable connection and synchronize initial sequence numbers Correct answer.
  4. To negotiate the maximum segment size only

Explanation

The SYN, SYN-ACK, ACK exchange confirms that both endpoints are reachable and agree on initial sequence numbers before data transfer. Encryption and path selection are handled by other protocols.

Question 45Computer Science and Information Technology (CS)

Which scheduling policy in a real-time system guarantees that a set of periodic tasks meets all deadlines whenever the total utilization is at most 1?

  1. First Come First Serve
  2. Earliest Deadline First Correct answer.
  3. Priority scheduling with static priorities
  4. Shortest Job First

Explanation

Earliest Deadline First is optimal for preemptive uniprocessor scheduling of periodic tasks, meeting all deadlines whenever utilization does not exceed 1. Static-priority schemes such as rate monotonic have a lower utilization bound.

Question 46Computer Science and Information Technology (CS)

A singly linked list is used as a stack. Which operation has cost O(1)?

  1. Access the k-th element
  2. Push at the tail and pop from the head
  3. Search for the middle element
  4. Push at the head and pop from the head Correct answer.

Explanation

Inserting and deleting at the head of a singly linked list takes constant time because only the head pointer changes. Tail operations require traversal, and indexed access is linear.

Question 47Computer Science and Information Technology (CS)

Which of the following statements about the halting problem is correct?

  1. It is decidable only for finite input alphabets
  2. It is undecidable for Turing machines Correct answer.
  3. It is decidable for deterministic machines but not nondeterministic ones
  4. It is decidable but requires exponential time

Explanation

The halting problem for Turing machines is recursively enumerable but not recursive, hence undecidable. No algorithm can decide for every machine-input pair whether the machine halts.

Question 48Computer Science and Information Technology (CS)

A cache has 32 blocks and uses 2-way set associativity. How many sets does the cache contain?

  1. 8
  2. 64
  3. 16 Correct answer.
  4. 32

Explanation

The number of sets equals the number of blocks divided by associativity, so 32 / 2 = 16 sets. Each set holds two blocks.

Question 49Computer Science and Information Technology (CS)

A hash table of size 7 uses double hashing with h1(k) = k mod 7 and h2(k) = 1 + (k mod 5). Keys 10, 17, and 24 are inserted in that order. In which slot does key 24 finally reside?

  1. 0 Correct answer.
  2. 5
  3. 3
  4. 2

Explanation

Key 10 hashes to 3 and key 17 hashes to 3, probing by h2(17) = 3 to slot 6. Key 24 hashes to 3, probes by h2(24) = 5 to 1, then by 10 mod 7 = 3 to 4, then by 15 mod 7 = 1 to 5, then by 20 mod 7 = 6 to 6 occupied, then by 25 mod 7 = 4 to 3, then by 30 mod 7 = 2 to 2, then by 35 mod 7 = 0 to 0, which is free, so key 24 lands in slot 0.

Question 50Computer Science and Information Technology (CS)

A synchronous sequential circuit is built from positive-edge-triggered flip-flops with setup time 2 ns, hold time 1 ns, and clock-to-Q delay 3 ns. The longest combinational path between flip-flops has delay 8 ns and the shortest has delay 1 ns. What is the minimum clock period that avoids setup and hold violations?

  1. 12 ns
  2. 13 ns
  3. 11 ns Correct answer.
  4. 10 ns

Explanation

The setup constraint requires the clock period to be at least clock-to-Q plus the longest combinational delay plus setup time, which is 3 + 8 + 2 = 13 ns. However, the hold constraint requires clock-to-Q plus the shortest path to be at least hold time, which is satisfied here. Recomputing, the setup-limited period is 13 ns, and since the shortest path 3 + 1 = 4 ns exceeds the 1 ns hold time, no hold violation occurs, so the minimum period is 13 ns.