GATE Computer Science questions with answers and solutions
Browse crawlable GATE CS question pages by subject. Each page includes question text, options, answer, theory, and solution.
Digital Electronics
Which Boolean identity correctly represents the absorption law?Number Systems & Boolean Algebra / Boolean Algebra Basics / 2022Which logic gate produces a HIGH output only when both inputs are HIGH?Number Systems & Boolean Algebra / Logic Gates / 2022When J = K = 1 in a JK flip-flop, the output behaviour is?Sequential Circuits / Flip-Flops / 2022In a half adder, the Sum and Carry outputs are given by?Number Systems & Boolean Algebra / Half Adder & Full Adder / 2023How many flip-flops are required to design a MOD-16 binary counter?Sequential Circuits / Binary Counters / 2023Which of the following can be implemented using an 8:1 multiplexer (3 select lines)?Combinational Circuits / Multiplexer / 2024Convert the binary number (10110)₂ to decimal.Number Systems & Boolean Algebra / Number Conversion / 2023
Data Structures
What is the time complexity of accessing an element in an array by index?Arrays & Strings / Introduction to Arrays / 2022Which data structure is used to evaluate postfix expressions?Stacks & Queues / Stack / 2022What is the worst-case time complexity to insert an element at the end of a singly linked list (without tail pointer)?Linked Lists / Singly Linked List / 2022The worst-case time complexity of search in a BST is?Trees / Binary Search Tree / 2023A complete binary tree has 31 nodes. What is its height? (Root at height 0)Trees / Binary Tree Traversal / 2024Which of the following are valid collision resolution techniques?Hashing / Collision Handling / 2023
Algorithms
The average-case time complexity of Quick Sort is?Sorting / Quick Sort / 2022Merge Sort's worst-case space complexity is?Sorting / Merge Sort / 2023Dijkstra's algorithm fails when the graph has?Graph Algorithms / Dijkstra's Algorithm / 2023Time complexity of 0/1 Knapsack via DP with n items and capacity W?Dynamic Programming / 0/1 Knapsack / 2024Given activities with start/end times, the greedy strategy that maximizes the number of activities selects activities sorted by which attribute? (1 = start time, 2 = end time)Greedy / Activity Selection / 2022
Operating System
Which is NOT a typical process state?Process Management / Process States / 2023Which scheduling algorithm provably gives minimum average waiting time?Process Management / CPU Scheduling / 2023Paging eliminates which type of fragmentation?Memory Management / Paging / 2024For reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames using FIFO, how many page faults occur?Memory Management / Page Replacement / 2023Which problems are classic synchronization problems?Synchronization / Semaphores / 2022
DBMS
A relation is in BCNF if for every non-trivial FD X → Y, X is a?Normalization / Normal Forms / 2022An INNER JOIN returns?SQL / Joins / 2023Which are the ACID properties?Transactions / ACID Properties / 2023A B+ tree of order 4 has at most how many children per internal node?Indexing / B+ Trees / 2024
Computer Networks
How many usable host addresses are available in a /27 IPv4 subnet?Network Layer / IP Addressing / 2023TCP slow start initializes the congestion window (cwnd) to?Transport Layer / TCP / 2022DNS primarily uses which transport-layer protocol?Application Layer / DNS / 2024CRC is used for?Data Link Layer / Error Detection / 2023
Theory of Computation
Computer Organization
A 5-stage pipeline executes 100 instructions with 10 stall cycles. Total clock cycles required?Pipelining / Hazards / 2023In direct-mapped cache, each block in main memory maps to?Cache / Cache Mapping / 2022What is the 8-bit two's complement representation of −5? Give the answer as a decimal value of the binary pattern.Number Representation / Two's Complement / 2024Consider a 16-bit hypothetical processor that supports 1-word-long instructions. The processor has 30 registers and 4 KB memory. If there are 11 two-address register-reference instructions and 10 one-address memory-reference instructions, how many zero-address instructions can be formulated?Instruction Set Architecture / Instruction Formats / 2024Consider a computer with a 4-way set-associative cache with these characteristics: Main memory size = 1 MB Word size = 1 byte Block size = 128 words Cache size = 8 KB For memory address 0C795H, find the TAG field value. Find the number of bits in TAG, SET, and WORD fields. Enter the TAG value in hexadecimal (without trailing H).Cache / Set-Associative Mapping / 2024