Back to Sections

Type:ALLMCQNATMSQ

Digital Logic(17)Computer Organization and Architecture(29)Programming and Data Structures(30)Algorithms(30)Theory of Computation(23)Compiler Design(20)Operating System(26)Databases(21)Computer Networks(27)

Digital Logic

17 Questions

GATE→2026→CS Core→Digital Logic

Q1

MSQ[1 Mark]

Consider the following Boolean expression of a function F: F(P,Q) = (not P + Q) (+) (not P * Q). Which of the following expressions is/are equivalent to F?

(A)

P (+) 0

(B)

P (+) Q

(C)

not P (+) Q

(D)

not P (+) not Q

Explanation

GATE→2026→CS Core→Digital Logic

Q2

MSQ[1 Mark]

Consider the 8-bit signed integers X, Y and Z represented using the sign-magnitude form. X: 10110100, Y: 01001100. Which of the following operations result(s) in an arithmetic overflow?

(A)

Z = X + Y

(B)

Z = X - Y

(C)

Z = -X + Y

(D)

Z = -X - Y

Explanation

GATE→2026→CS Core→Digital Logic

Q3

MCQ[2 Marks]

Consider a 2-bit saturating up/down counter... Which one of the following options corresponds to the expressions for the inputs of the D flip-flops, D1 and D0?

(A)

(B)

(C)

(D)

Explanation

GATE→2026→CS Core→Digital Logic

Q4

MSQ[2 Marks]

Consider Boolean function F(P,Q,R,S) = sum m(1,2,3,4,5,7,10,12,13,14). Which of the following are minimal sum-of-products expressions?

(A)

not(P)not(S) + Q not(R) + not(P)not(Q)R + not(Q)R not(S)

(B)

not(P)not(S) + Q not(R) + not(P)not(Q)R + P R not(S)

(C)

not(P)not(S) + Q not(R) + P Q not(S) + P R not(S)

(D)

not(P)not(S) + Q not(R) + P Q not(S) + not(Q)R not(S)

Explanation

GATE→2025→CS Core→Digital Logic

Q5

MSQ[1 Mark]

Let X be 3-variable majority function. Which statements are CORRECT?

(A)

X(a,b,X(c,d,e))=X(X(a,b,c),d,e)

(B)

X(a,b,X(a,b,c))=X(a,b,c)

(C)

X(a,b,X(a,c,d))=(X(a,b,a) AND X(c,d,c))

(D)

X(a,b,X(a,b,c))=X(a,b,c)

Explanation

GATE→2025→CS Core→Digital Logic

Q6

MSQ[1 Mark]

-6 in 4-bit 2's comp is 1010. Correct 2's complement representations?

(A)

1000 1010 in 8-bits

(B)

1111 1010 in 8-bits

(C)

1000 0000 0000 1010 in 16-bits

(D)

1111 1111 1111 1010 in 16-bits

Explanation

GATE→2025→CS Core→Digital Logic

Q7

MCQ[2 Marks]

Boolean function F(b3, b2, b1, b0) = sum m(0, 2, 4, 8, 10, 11, 12). Minimized SOP expression?

(A)

$\overline{b}_{1}\overline{b}_{0}+\overline{b}_{2}\overline{b}_{0}+b_{1}\overline{b}_{2}b_{3}$

(B)

$\overline{b}_{1}\overline{b}_{0}+\overline{b}_{2}\overline{b}_{0}$

(C)

$\overline{b}_{2}\overline{b}_{0}+b_{1}b_{2}b_{3}$

(D)

$\overline{b}_{0}\overline{b}_{2}+\overline{b}_{3}$

Explanation

GATE→2025→CS Core→Digital Logic

Q8

NAT[2 Marks]

Minimum number of states required to realize FSM given by state transition table.

Explanation

GATE→2025→CS Core→Digital Logic

Q9

NAT[2 Marks]

Sequential circuit with D flip-flops. Number of distinct states before returning to initial state.

Explanation

GATE→2024→CS Core→Digital Logic

Q10

MCQ[1 Mark]

Consider a system that uses 5 bits for representing signed integers in 2's complement format. A = 01010 and B = 11010. Which operation results in an arithmetic overflow or underflow?

(A)

A + B

(B)

A - B

(C)

B - A

(D)

2 * B

Explanation

GATE→2024→CS Core→Digital Logic

Q11

MSQ[1 Mark]

Consider the circuit shown below where the gates may have propagation delays. Which of the following statements about the circuit is/are CORRECT?

(A)

With no propagation delays, the output Y is always logic Zero

(B)

With no propagation delays, the output Y is always logic One

(C)

With propagation delays, the output Y can have a transient logic One after X transitions from logic Zero to logic One

(D)

With propagation delays, the output Y can have a transient logic Zero after X transitions from logic One to logic Zero

Explanation

GATE→2024→CS Core→Digital Logic

Q12

MSQ[2 Marks]

Consider F(X,Y,Z) = sum m(3,5,6,7). Which of the following is/are CORRECT?

(A)

(B)

$F(X,Y,Z)=XY+YZ+XZ$

(C)

$F(X,Y,Z)$ is independent of input Y

(D)

$F(X,Y,Z)$ is independent of input X

Explanation

GATE→2024→CS Core→Digital Logic

Q13

NAT[2 Marks]

Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2, and M3... For inputs X1=1, X2=1, X3=0, X4=0, the number of combinations of A, B, C that give output Y=1 is

Explanation

GATE→2023→CS Core→Digital Logic

Q14

MCQ[1 Mark]

The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure. Match the functional equivalence of this circuit to one of the following options.

(A)

D Flip-flop

(B)

D Latch

(C)

Half-adder

(D)

Demultiplexer

Explanation

GATE→2023→CS Core→Digital Logic

Q15

NAT[1 Mark]

A particular number is written as 132 in radix-4 representation. The same number in radix-5 representation is

Explanation

GATE→2023→CS Core→Digital Logic

Q16

MCQ[2 Marks]

Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown in the figure... Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?

(A)

(0, 0, 1)

(B)

(1, 0, 0)

(C)

(1, 0, 1)

(D)

(1, 1, 1)

Explanation

GATE→2023→CS Core→Digital Logic

Q17

MCQ[2 Marks]

A Boolean digital circuit is composed using two 4-input multiplexers (M1 and M2) and one 2-input multiplexer (M3)... Which one of the following set of values of (X0, X1, X2, X3, X4, X5, X6, X7) will realise the Boolean function \overline{A} + \overline{A}\overline{C} + A\overline{B}C?

(A)

(1, 1, 0, 0, 1, 1, 1, 0)

(B)

(1, 1, 0, 0, 1, 1, 0, 1)

(C)

(1, 1, 0, 1, 1, 1, 0, 0)

(D)

(0, 0, 1, 1, 0, 1, 1, 1)

Explanation

Computer Organization and Architecture

29 Questions

GATE→2026→CS Core→Computer Organization and Architecture

Q18

MCQ[1 Mark]

Match each addressing mode in List I with a data element or an element of a data structure in List II: P. Immediate Q. Indirect R. Base with index S. Base with offset/displacement List II: 1. Element of an array 2. Pointer 3. Element of a record 4. Constant

(A)

P-4, Q-3, R-1, S-2

(B)

P-4, Q-2, R-1, S-3

(C)

P-1, Q-4, R-3, S-2

(D)

P-2, Q-3, R-1, S-4

Explanation

GATE→2026→CS Core→Computer Organization and Architecture

Q19

MCQ[1 Mark]

Consider a processor P whose instruction set architecture is the load-store architecture... Which one of the following sequences of instructions corresponds to the high-level language statement Z = X + Y?

(A)

ADD Z, X, Y

(B)

LOAD R0, X; ADD Z, R0, Y

(C)

ADD R0, X, Y; STORE Z, R0

(D)

LOAD R0, X; LOAD R1, Y; ADD R2, R0, R1; STORE Z, R2

Explanation

GATE→2026→CS Core→Computer Organization and Architecture

Q20

MCQ[1 Mark]

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

(A)

Read-after-read

(B)

Read-after-write

(C)

Write-after-read

(D)

Write-after-write

Explanation

GATE→2026→CS Core→Computer Organization and Architecture

Q21

MCQ[2 Marks]

Consider IEEE 754 single-precision floating-point variables X (35C00000) and Y (34A00000). Let Z = X + Y. The hexadecimal representation of Z is

(A)

35C80000

(B)

35CC0000

(C)

35E80000

(D)

35EC0000

Explanation

GATE→2026→CS Core→Computer Organization and Architecture

Q22

MCQ[2 Marks]

Physical address space size 2^32 bytes, cache capacity 2^23 bytes, block size 128 bytes. Tag length M for direct mapped and N for K-way set-associative (K = 2^L). Which option is true?

(A)

N = M + L

(B)

N = M - L

(C)

N = M + K

(D)

N = M - K

Explanation

GATE→2025→CS Core→Computer Organization and Architecture

Q23

MCQ[1 Mark]

Suppose a program is running on a non-pipelined single processor computer system. Steps: (i) saves program counter, (ii) loads PC with ISR start address, (iii) finishes present instruction. Correct sequence?

(A)

(iii), (i), (ii)

(B)

(i), (iii), (ii)

(C)

(i), (ii), (iii)

(D)

(iii), (ii), (i)

Explanation

GATE→2025→CS Core→Computer Organization and Architecture

Q24

MSQ[1 Mark]

Partial data path of processor. Which are CORRECT related to arithmetic operations?

(A)

The data path can implement arithmetic operations involving two registers.

(B)

The data path can implement arithmetic operations involving one register and one immediate value.

(C)

The data path can implement arithmetic operations involving two immediate values.

(D)

The data path can only implement arithmetic operations involving one register and one immediate value.

Explanation

GATE→2025→CS Core→Computer Organization and Architecture

Q25

MCQ[2 Marks]

Memory system 1MB main memory, 16KB cache, 20-bit address, 16-byte block size. Direct mapped cache. Bits required to store all tag values?

(A)

$6\times2^{10}$

(B)

$8\times2^{10}$

(C)

$2^{12}$

(D)

$2^{14}$

Explanation

GATE→2025→CS Core→Computer Organization and Architecture

Q26

MCQ[2 Marks]

Processor has 64 general-purpose registers and 50 distinct instruction types. 32-bit instruction format. Maximum bits for immediate operand?

(A)

16

(B)

20

(C)

22

(D)

24

Explanation

GATE→2025→CS Core→Computer Organization and Architecture

Q27

NAT[2 Marks]

Memory hierarchy L1 cache (hit rate 95%, access time 10ns), L2 cache (hit rate 85%, access time 20ns), Main memory (200ns). Average memory access time in ns?

Explanation

GATE→2024→CS Core→Computer Organization and Architecture

Q28

MCQ[1 Mark]

Which one of the following statements is FALSE?

(A)

In the cycle stealing mode of DMA, one word of data is transferred between an I/O device and main memory in a stolen cycle

(B)

For bulk data transfer, the burst mode of DMA has a higher throughput than the cycle stealing mode

(C)

Programmed I/O mechanism has a better CPU utilization than the interrupt driven I/O mechanism

(D)

The CPU can start executing an interrupt service routine faster with vectored interrupts than with non-vectored interrupts

Explanation

GATE→2024→CS Core→Computer Organization and Architecture

Q29

MSQ[1 Mark]

Consider a 5-stage pipelined processor. Which of the following statements about forwarding is/are CORRECT?

(A)

In a pipelined execution, forwarding means the result from a source stage of an earlier instruction is passed on to the destination stage of a later instruction

(B)

In forwarding, data from the output of the MEM stage can be passed on to the EX stage

(C)

Forwarding helps in reducing data hazard stalls

(D)

Forwarding does not require any extra hardware...

Explanation

GATE→2024→CS Core→Computer Organization and Architecture

Q30

MSQ[2 Marks]

Consider two set-associative cache memory architectures: WBC (write back) and WTC (write through). Which of the following statements is/are TRUE?

(A)

A read miss in WBC never evicts a dirty block

(B)

A read miss in WTC never triggers a write back operation of a cache block to main memory

(C)

A write hit in WBC can modify the value of the dirty bit of a cache block

(D)

A write miss in WTC always writes the victim cache block to main memory before loading the missed block...

Explanation

GATE→2024→CS Core→Computer Organization and Architecture

Q31

NAT[2 Marks]

Consider a 512 GB hard disk with 32 storage surfaces. There are 4096 sectors per track and each sector holds 1024 bytes of data. The number of cylinders in the hard disk is

Explanation

GATE→2024→CS Core→Computer Organization and Architecture

Q32

NAT[2 Marks]

The baseline execution time of a program on a 2 GHz single core machine is 100 ns. 90% parallelizable. Overhead 10 ns per core. Number of cores that minimize execution time?

Explanation

GATE→2024→CS Core→Computer Organization and Architecture

Q33

NAT[2 Marks]

A given program has 25% load/store instructions. Ideal CPI = 2. 2% instruction miss rate, 8% data miss rate. Miss penalty = 100 cycles. Speedup (rounded off to two decimal places) achieved with a perfect cache is

Explanation

GATE→2023→CS Core→Computer Organization and Architecture

Q34

NAT[1 Mark]

Consider a 3-stage pipelined processor having a delay of 10 ns, 20 ns, and 14 ns. Total execution time for executing 100 instructions on this processor is ___ ns.

Explanation

GATE→2023→CS Core→Computer Organization and Architecture

Q35

MCQ[2 Marks]

Consider the given C-code and its corresponding assembly code, with a few operands U1-U4 being unknown... Which one of the following options is a CORRECT replacement for operands in the position (U1, U2, U3, U4)?

(A)

(8, 4, 1, L02)

(B)

(3, 4, 4, L01)

(C)

(8, 1, 1, L02)

(D)

(3, 1, 1, L01)

Explanation

GATE→2023→CS Core→Computer Organization and Architecture

Q36

MCQ[2 Marks]

A 4 kilobyte (KB) byte-addressable memory is realized using four 1 KB memory blocks... The input memory addresses (IA11-IA0), in decimal, for the starting locations (Addr=0) of each block (indicated as X1, X2, X3, X4) are among the options given below. Which one is CORRECT?

(A)

(0, 1, 2, 3)

(B)

(0, 1024, 2048, 3072)

(C)

(0, 8, 16, 24)

(D)

(0, 0, 0, 0)

Explanation

GATE→2023→CS Core→Computer Organization and Architecture

Q37

MCQ[2 Marks]

Consider the IEEE-754 single precision floating point numbers P = 0xC1800000 and Q = 0x3F5C2EF4. Which one of the following corresponds to the product of these numbers?

(A)

0x404C2EF4

(B)

0x405C2EF4

(C)

0xC15C2EF4

(D)

0xC14C2EF4

Explanation

GATE→2023→CS Core→Computer Organization and Architecture

Q38

NAT[2 Marks]

An 8-way set associative cache of size 64 KB is used in a system with 32-bit address... The number of bits in the TAG is

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q39

MCQ[1 Mark]

Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

(A)

DMA based I/O transfer

(B)

Interrupt driven I/O transfer

(C)

Polling based I/O transfer

(D)

Programmed I/O transfer

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q40

MCQ[1 Mark]

Let R1 and R2 be two 4-bit registers that store numbers in 2's complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

(A)

R1=1011 and R2=1110

(B)

R1=1100 and R2=1010

(C)

R1=0011 and R2=0100

(D)

R1=1001 and R2=1111

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q41

MSQ[1 Mark]

WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

(A)

Each cache block in WB and WT has a dirty bit.

(B)

Every write hit in WB leads to a data transfer from cache to main memory.

(C)

Eviction of a block from WT will not lead to data transfer from cache to main memory.

(D)

A read miss in WB will never lead to eviction of a dirty block from WB.

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q42

NAT[1 Mark]

The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q43

MCQ[2 Marks]

Which one of the following represents the functionality of P, Q, and T?

(A)

Q is 5:1 multiplexer; T is 2:1 multiplexer; P is 10:1 multiplexer

(B)

P is 10:2^10 decoder; Q is 5:2^5 decoder; T is 2:1 encoder

(C)

P is 10:2^10 decoder; Q is 5:2^5 decoder; T is 2:1 multiplexer

(D)

P is 1:10 de-multiplexer; Q is 1:5 de-multiplexer; T is 2:1 multiplexer

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q44

MCQ[2 Marks]

Which one of the following is FALSE?

(A)

A + C = 0

(B)

C = A + B

(C)

B = 3C

(D)

(B - C) > 0

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q45

MSQ[2 Marks]

Consider a system with 2 KB direct mapped data cache... Which of the following statements is/are TRUE with respect to the data cache?

(A)

Every access to S is a hit.

(B)

Once P is brought to the cache it is never evicted.

(C)

At the end of the execution only R and S reside in the cache.

(D)

Every access to R evicts Q from the cache.

Explanation

GATE→2022→CS Core→Computer Organization and Architecture

Q46

NAT[2 Marks]

The speed up (rounded off to two decimal places) obtained by X2 over X1 in executing P is

Explanation

Programming and Data Structures

30 Questions

GATE→2026→CS Core→Programming and Data Structures

Q47

MSQ[1 Mark]

Consider a hash table P[0, 1, ..., 10] initially empty, using linear probing with h(x) = (x + 7) mod 11. Insertions: 1, 13, 22, 15, 11, 24. Which of the following positions is/are empty after these insertions?

(A)

0

(B)

10

(C)

2

(D)

1

Explanation

GATE→2026→CS Core→Programming and Data Structures

Q48

NAT[1 Mark]

The height of a binary tree is the number of edges in the longest path from root to leaf. The maximum possible height of a full binary tree with 23 nodes is

Explanation

GATE→2026→CS Core→Programming and Data Structures

Q49

NAT[1 Mark]

Consider the following program in C... The output of the program is

Explanation

GATE→2026→CS Core→Programming and Data Structures

Q50

MCQ[2 Marks]

Consider C code computing node count in a linked list... Which option gives correct replacements for E1 and E2?

(A)

E1: head == NULL; E2: 1 + getListSize(head)

(B)

E1: head->next == NULL; E2: 1 + getListSize(head->next)

(C)

E1: head == NULL; E2: 1 + getListSize(head->next)

(D)

E1: head->next == NULL; E2: 1 + getListSize(head)

Explanation

GATE→2026→CS Core→Programming and Data Structures

Q51

MCQ[2 Marks]

Let P be integers 1 to 15. Insertion into BST creating a complete binary tree. Which element can NEVER be the third element inserted?

(A)

4

(B)

2

(C)

10

(D)

5

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q52

MSQ[1 Mark]

Which statements are TRUE for any BST with n distinct integers?

(A)

The maximum length of a path from the root node to any other node is (n-1)

(B)

An inorder traversal will always produce a sorted sequence of elements.

(C)

Finding an element takes O(log2 n) time in the worst case.

(D)

Every BST is also a Min-Heap.

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q53

NAT[1 Mark]

Array of 30 distinct integers in descending order. Number of swaps performed by bubble sort function fun().

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q54

NAT[1 Mark]

Output of C program with foo(int *p, int x) { *p = x; } and main.

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q55

NAT[2 Marks]

Value printed by given C program with foo on array A = {0, 1, 2, 2, 2, 0, 0, 1, 1}.

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q56

NAT[2 Marks]

Linked lists L1 (9 nodes) and L2 (7 nodes). C program modifies L1. Number of nodes in L1 after execution?

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q57

NAT[2 Marks]

Value printed by given C program gate(14362).

Explanation

GATE→2025→CS Core→Programming and Data Structures

Q58

NAT[2 Marks]

Double hashing scheme, h1(k) = k mod 11, h2(k) = 1 + (k mod 7), m = 11. Keys inserted in order: 63, 50, 25, 79, 67, 24. Slot at which key 24 gets stored?

Explanation

GATE→2024→CS Core→Programming and Data Structures

Q59

MCQ[1 Mark]

Consider the following C program... Output of printf('%d', a)?

(A)

(B)

(C)

1

(D)

Explanation

GATE→2024→CS Core→Programming and Data Structures

Q60

MCQ[1 Mark]

Consider the following recursive C program with getchar() and putchar(). Input: 1234 followed by newline.

(A)

(B)

(C)

4321 as output

(D)

Explanation

GATE→2024→CS Core→Programming and Data Structures

Q61

NAT[1 Mark]

Evaluate expression 3 + 1 + 5 * 2 / 7 + 2 - 4 - 7 - 6 / 2 as per given operator precedence and associativity rules.

Explanation

GATE→2024→CS Core→Programming and Data Structures

Q62

MCQ[2 Marks]

An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?

(A)

(B)

(C)

131, 11, 93

(D)

131, 111, 90

Explanation

GATE→2024→CS Core→Programming and Data Structures

Q63

MCQ[2 Marks]

Consider a binary min-heap containing 10^5 distinct elements. Let k be the index (in the underlying array) of the maximum element stored in the heap. The number of ancestors of max element...

(A)

(B)

52

(C)

27

(D)

1

Explanation

GATE→2024→CS Core→Programming and Data Structures

Q64

MSQ[2 Marks]

Consider the following C function definition. Which of the following statements is/are TRUE about the above function?

(A)

If the inputs are x=20, y=10, then the return value is greater than 220

(B)

If the inputs are x=20, y=20, then the return value is greater than 2^20

(C)

If the inputs are x=20, y=10, then the return value is greater than 2^10

(D)

If the inputs are x=10, y=20, then the return value is greater than 2^20

Explanation

GATE→2023→CS Core→Programming and Data Structures

Q65

MCQ[1 Mark]

Which one of the following sequences when stored in an array at locations A[1],...,A[10] forms a max-heap?

(A)

23, 17, 10, 6, 13, 14, 1, 5, 7, 12

(B)

23, 17, 14, 7, 13, 10, 1, 5, 6, 12

(C)

23, 17, 14, 6, 13, 10, 1, 5, 7, 15

(D)

23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Explanation

GATE→2023→CS Core→Programming and Data Structures

Q66

MCQ[1 Mark]

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list. Worst-case time complexity?

(A)

SLLdel is O(1) and DLLdel is O(n)

(B)

Both SLLdel and DLLdel are O(log(n))

(C)

Both SLLdel and DLLdel are O(1)

(D)

SLLdel is O(n) and DLLdel is O(1)

Explanation

GATE→2023→CS Core→Programming and Data Structures

Q67

NAT[1 Mark]

The integer value printed by the ANSI-C program given below is

Explanation

GATE→2023→CS Core→Programming and Data Structures

Q68

MCQ[2 Marks]

Let A be a priority queue implemented using a max-heap data structure... When A contains n elements, which one of the following statements about worst case running time of these two operations is TRUE?

(A)

Both run in O(1).

(B)

Both run in O(log(n)).

(C)

EXTRACT-MAX runs in O(1) and INSERT runs in O(n).

(D)

EXTRACT-MAX runs in O(1) and INSERT runs in O(log(n)).

Explanation

GATE→2023→CS Core→Programming and Data Structures

Q69

MCQ[2 Marks]

Consider the C function foo and the binary tree shown... When foo is called with a pointer to the root node of the given binary tree, what will it print?

(A)

3 8 5 13 11 10

(B)

3 5 8 10 11 13

(C)

3 8 16 13 24 50

(D)

3 16 8 50 24 13

Explanation

GATE→2023→CS Core→Programming and Data Structures

Q70

NAT[2 Marks]

Consider a sequence a of elements a0=1, a1=5, a2=7, a3=8, a4=9 and a5=2... The top element of S after executing the above operations is

Explanation

GATE→2022→CS Core→Programming and Data Structures

Q71

MCQ[1 Mark]

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

(A)

The best algorithm for the problem takes \theta(n) time in the worst case.

(B)

The best algorithm for the problem takes \theta(n \log n) time in the worst case.

(C)

The best algorithm for the problem takes \theta(n^2) time in the worst case.

(D)

It is not possible to reverse a singly linked list in O(1) space.

Explanation

GATE→2022→CS Core→Programming and Data Structures

Q72

MCQ[1 Mark]

What is printed by the following ANSI C program?

(A)

1, 10, 11

(B)

1, 10, 14

(C)

10, 14, 11

(D)

10, 10, 14

Explanation

GATE→2022→CS Core→Programming and Data Structures

Q73

NAT[1 Mark]

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using array representation starting with 0. The 3rd largest element is stored at index

Explanation

GATE→2022→CS Core→Programming and Data Structures

Q74

MCQ[2 Marks]

What is printed by the following ANSI C program?

(A)

(B)

(C)

(D)

Explanation

GATE→2022→CS Core→Programming and Data Structures

Q75

MCQ[2 Marks]

What is printed by the following ANSI C program?

(A)

ZKS

(B)

75 122 83

(C)

* - +

(D)

P x +

Explanation

GATE→2022→CS Core→Programming and Data Structures

Q76

NAT[2 Marks]

The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse order without using any additional storage is

Explanation

Algorithms

30 Questions

GATE→2026→CS Core→Algorithms

Q77

MCQ[1 Mark]

Consider the following recurrence relations: T1(n) = 4 T1(n/2) + T2(n), T2(n) = 5 T2(n/4) + Theta(log2 n)... Which one of the following options is correct?

(A)

T1(n) = Theta(n^2)

(B)

T1(n) = Theta(n^2 log2 n)

(C)

T1(n) = Theta(n^(log_4 5))

(D)

T1(n) = Theta(n^(log_4 5) log2 n)

Explanation

GATE→2026→CS Core→Algorithms

Q78

MSQ[1 Mark]

Let n be an odd number greater than 100. Consider a binary minheap with n elements stored in an array P whose index starts from 1. Which of the following indices of P do/does NOT correspond to any leaf node of the minheap?

(A)

(n + 1) / 2

(B)

(n - 1) / 2

(C)

(n - 3) / 2

(D)

n

Explanation

GATE→2026→CS Core→Algorithms

Q79

MCQ[2 Marks]

Let G(V,E) be an undirected edge-weighted graph... Consider statements S1 and S2 regarding shortest paths. Which option is correct?

(A)

Only S1 is true

(B)

Only S2 is true

(C)

Both S1 and S2 are true

(D)

Neither S1 nor S2 is true

Explanation

GATE→2026→CS Core→Algorithms

Q80

MSQ[2 Marks]

Let G(V,E) be a simple undirected graph, smallest vertex cover size k. For vertex v in V, which constraints ensure v in S?

(A)

Degree of v is at least k + 1

(B)

Vertex v is on a path of length k + 1

(C)

Vertex v is on a cycle of length k + 1

(D)

Vertex v is part of a clique of size k

Explanation

GATE→2026→CS Core→Algorithms

Q81

MSQ[2 Marks]

Let G(V,E) be a simple undirected graph with unique edge weights. Which statements about Minimum Spanning Trees (MST) are true?

(A)

In every cycle C of G, the edge with the largest weight in C is not in any MST

(B)

In every cycle C of G, the edge with the smallest weight in C is in every MST

(C)

For every vertex v, the largest weight edge incident on v is not in any MST

(D)

For every vertex v, the smallest weight edge incident on v is in every MST

Explanation

GATE→2026→CS Core→Algorithms

Q82

MSQ[2 Marks]

Consider DFS pseudocode on a DAG G(V,E). For an edge (u,v) in E, which option will NEVER be correct?

(A)

d[u] < d[v] < f[v] < f[u]

(B)

d[v] < d[u] < f[u] < f[v]

(C)

d[v] < f[v] < d[u] < f[u]

(D)

d[u] < d[v] < f[u] < f[v]

Explanation

GATE→2026→CS Core→Algorithms

Q83

MSQ[2 Marks]

An undirected unweighted graph G(V,E) is 2-colorable if there exists c: V -> {0,1} with c(u) != c(v) for all (u,v) in E. Which statements about 2-colorable graphs are true?

(A)

If G is 2-colorable, G may contain cycles of odd length

(B)

If G is 2-colorable, G may contain cycles of even length

(C)

Optimal algorithm for testing 2-colorability runs in Theta(|V|+|E|) with adjacency list

(D)

Optimal algorithm for testing 2-colorability runs in Theta(|E| log |V|) with adjacency list

Explanation

GATE→2025→CS Core→Algorithms

Q84

MCQ[1 Mark]

Let G be undirected graph with positive weights, T be MST. d1(u,v) and d2(u,v) are shortest distances in G and T respectively. Which is CORRECT?

(A)

d1(u,v) = d2(u,v)

(B)

d1(u,v) <= d2(u,v)

(C)

d1(u,v) >= d2(u,v)

(D)

d1(u,v) != d2(u,v)

Explanation

GATE→2025→CS Core→Algorithms

Q85

MCQ[1 Mark]

Recurrence relation: T(n) = 2 T(n-1) + n 2^n for n > 0, T(0) = 1. Solution?

(A)

T(n) = Theta(n^2 2^n)

(B)

T(n) = Theta(n 2^n)

(C)

T(n) = Theta((log n)^2 2^n)

(D)

T(n) = Theta(4^n)

Explanation

GATE→2025→CS Core→Algorithms

Q86

NAT[1 Mark]

Min-Heap stores 32 keys. Height of T (max edges from root to leaf)?

Explanation

GATE→2025→CS Core→Algorithms

Q87

MCQ[2 Marks]

Undirected unweighted graph with 100 vertices, max shortest path distance (diameter) be 30. T is any BFS tree. Height of T?

(A)

The height of T is exactly 15.

(B)

The height of T is exactly 30.

(C)

The height of T is at least 15.

(D)

The height of T is at least 30.

Explanation

GATE→2025→CS Core→Algorithms

Q88

NAT[2 Marks]

Maximum value of x such that edge between nodes B and C is included in every minimum spanning tree of given graph.

Explanation

GATE→2024→CS Core→Algorithms

Q89

MCQ[1 Mark]

Given array of N elements, check if sorted in single pass comparing adjacent elements. Worst-case time complexity?

(A)

both O(N) and \Omega(N)

(B)

O(N) but not \Omega(N)

(C)

\Omega(N) but not O(N)

(D)

neither O(N) nor \Omega(N)

Explanation

GATE→2024→CS Core→Algorithms

Q90

MCQ[2 Marks]

Consider the following recurrence relation: T(n) = T(sqrt(n)) + n for n >= 1, T(1) = 1. Which one of the following options is CORRECT?

(A)

T(n) = \Theta(n \log \log n)

(B)

T(n) = \Theta(n \log n)

(C)

T(n) = \Theta(n^2 \log n)

(D)

T(n) = \Theta(n^2 \log \log n)

Explanation

GATE→2024→CS Core→Algorithms

Q91

MSQ[2 Marks]

Let G be a directed graph and T a depth first search (DFS) spanning tree in G rooted at v. Suppose T is also a breadth first search (BFS) tree in G. Which of the following statements is/are TRUE?

(A)

There are no back-edges in G with respect to the tree T

(B)

There are no cross-edges in G with respect to the tree T

(C)

There are no forward-edges in G with respect to the tree T

(D)

The only edges in G are the edges in T

Explanation

GATE→2024→CS Core→Algorithms

Q92

NAT[2 Marks]

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is

Explanation

GATE→2023→CS Core→Algorithms

Q93

MCQ[1 Mark]

An algorithm has to store several keys generated by an adversary in a hash table... Which one of the following is the best hashing strategy to counteract the adversary?

(A)

Division method, i.e., h(k) = k mod m.

(B)

Multiplication method...

(C)

Universal hashing method.

(D)

If k is prime...

Explanation

GATE→2023→CS Core→Algorithms

Q94

MSQ[1 Mark]

Let f and g be functions of natural numbers given by f(n) = n and g(n) = n^2. Which of the following statements is/are TRUE?

(A)

f \in O(g)

(B)

f \in \Omega(g)

(C)

f \in o(g)

(D)

f \in \Theta(g)

Explanation

GATE→2023→CS Core→Algorithms

Q95

MSQ[2 Marks]

Consider functions Function_1 and Function_2 expressed in pseudocode... Which of the following statements is/are TRUE?

(A)

f_1(n) \in \Theta(f_2(n))

(B)

f_1(n) \in o(f_2(n))

(C)

f_1(n) \in \omega(f_2(n))

(D)

f_1(n) \in O(n)

Explanation

GATE→2023→CS Core→Algorithms

Q96

MSQ[2 Marks]

Consider simple undirected graph G. Color vertices using greedy strategy. Which of the following statements is/are TRUE?

(A)

This procedure results in a proper vertex coloring of G.

(B)

The number of colors used is at most \Delta(G) + 1.

(C)

The number of colors used is at most \Delta(G).

(D)

The number of colors used is equal to the chromatic number of G.

Explanation

GATE→2023→CS Core→Algorithms

Q97

NAT[2 Marks]

Let U = {1, 2, 3}. Consider undirected graph G whose vertex set is 2^U... Cardinality of B(\emptyset) is

Explanation

GATE→2022→CS Core→Algorithms

Q98

MCQ[1 Mark]

Which one of the following statements is TRUE for all positive functions f(n)?

(A)

$f(n^{2})=\theta(f(n)^{2})$, when $f(n)$ is a polynomial

(B)

$f(n^{2})=o(f(n)^{2})$

(C)

$f(n^{2})=O(f(n)^{2})$ when $f(n)$ is an exponential function

(D)

$f(n^{2})=\Omega(f(n)^{2})$

Explanation

GATE→2022→CS Core→Algorithms

Q99

MCQ[1 Mark]

Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?

(A)

m/n

(B)

n/m

(C)

2n/m

(D)

n/(2m)

Explanation

GATE→2022→CS Core→Algorithms

Q100

NAT[1 Mark]

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is

Explanation

GATE→2022→CS Core→Algorithms

Q101

MCQ[2 Marks]

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

(A)

A^3

(B)

A^3 divided by 2

(C)

A^3 divided by 3

(D)

A^3 divided by 6

Explanation

GATE→2022→CS Core→Algorithms

Q102

MSQ[2 Marks]

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

(A)

The edge with the second smallest weight is always part of any minimum spanning tree of G.

(B)

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.

(C)

Suppose S subset V... Consider edge with minimum weight across cut... always part of MST.

(D)

G can have multiple minimum spanning trees.

Explanation

GATE→2022→CS Core→Algorithms

Q103

MSQ[2 Marks]

The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?

(A)

The chromatic number of the graph is 3.

(B)

The graph has a Hamiltonian path.

(C)

The following graph is isomorphic to the Peterson graph.

(D)

The size of the largest independent set of the given graph is 3.

Explanation

GATE→2022→CS Core→Algorithms

Q104

MSQ[2 Marks]

Consider the following recurrence... Which of the following statements is/are TRUE?

(A)

f(2^n - 1) = 2^n - 1

(B)

f(2^n) = 1

(C)

f(5 * 2^n) = 2^(n+1) + 1

(D)

f(2^n + 1) = 2^n + 1

Explanation

GATE→2022→CS Core→Algorithms

Q105

MSQ[2 Marks]

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

(A)

The diagonal entries of A^2 are the degrees of the vertices of the graph.

(B)

If the graph is connected, then none of the entries of A^(n-1) + I_n can be zero.

(C)

If the sum of all the elements of A is at most 2(n-1) then the graph must be acyclic.

(D)

If there is at least a 1 in each of A's rows and columns, then the graph must be connected.

Explanation

GATE→2022→CS Core→Algorithms

Q106

NAT[2 Marks]

The number of such directed spanning trees rooted at vertex 5 is

Explanation

Theory of Computation

23 Questions

GATE→2026→CS Core→Theory of Computation

Q107

MSQ[1 Mark]

Consider grammar S -> aSbS | bS | epsilon. Which of the following statements is/are true?

(A)

The grammar is ambiguous

(B)

The string abb has two distinct derivations in this grammar

(C)

The string abab has only one rightmost derivation

(D)

The language generated by the grammar is undecidable

Explanation

GATE→2026→CS Core→Theory of Computation

Q108

MSQ[1 Mark]

Let M be an NFA with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal DFA equivalent to M?

(A)

32

(B)

65

(C)

1

(D)

128

Explanation

GATE→2026→CS Core→Theory of Computation

Q109

MSQ[2 Marks]

Let L1 and L2 be languages such that L1 subset L2 and L2 is regular. Which of the following statements is/are always true?

(A)

L1 is regular

(B)

L1 union L2 is regular

(C)

L2 is context-free

(D)

L1 is context-free

Explanation

GATE→2026→CS Core→Theory of Computation

Q110

MSQ[2 Marks]

Consider context-free grammar G. Let n1(s) be the number of a's and n2(s) be the number of b's in s in L(G). Which statements are true?

(A)

There is a string s in L(G) such that n1(s) < n2(s)

(B)

For every string s in L(G), n1(s) >= n2(s)

(C)

There is a string s in L(G) such that n1(s) > 2 n2(s)

(D)

For every string s in L(G), n1(s) <= 2 n2(s)

Explanation

GATE→2025→CS Core→Theory of Computation

Q111

MCQ[1 Mark]

CFG G: S -> aaB | Abb, A -> a | aA, B -> b | bB. Language L(G)?

(A)

L(G) = {a^2 b^n | n >= 1} union {a^n b^2 | n >= 1}

(B)

L(G) = {a^n b^(2n) | n >= 1} union {a^(2n) b^n | n >= 1}

(C)

L(G) = {a^n b^n | n >= 1}

(D)

L(G) = {a^(2n) b^(2n) | n >= 1}

Explanation

GATE→2025→CS Core→Theory of Computation

Q112

MSQ[1 Mark]

Regular language L accepted by NFA with n states. Which are FALSE?

(A)

L may have an accepting NFA with < n states.

(B)

L may have an accepting DFA with < n states.

(C)

There exists a DFA with <= 2^n states that accepts L.

(D)

Every DFA that accepts L has > 2^n states.

Explanation

GATE→2025→CS Core→Theory of Computation

Q113

MCQ[2 Marks]

Languages L1 and L2 over {a,b}. Which is CORRECT?

(A)

Both L1 and L2 are regular languages.

(B)

L1 is a regular language but L2 is not a regular language.

(C)

L1 is not a regular language but L2 is a regular language.

(D)

Neither L1 nor L2 is a regular language.

Explanation

GATE→2025→CS Core→Theory of Computation

Q114

MCQ[2 Marks]

Languages L1 and L2 over {a,b,c}. Which is CORRECT?

(A)

Both L1 and L2 are context-free languages.

(B)

L1 is a context-free language but L2 is not a context-free language.

(C)

L1 is not a context-free language but L2 is a context-free language.

(D)

Neither L1 nor L2 are context-free languages.

Explanation

GATE→2025→CS Core→Theory of Computation

Q115

MSQ[2 Marks]

DFA over {a,b}. Which language(s) accepted?

(A)

The set of all strings containing an even number of b's.

(B)

The set of all strings containing the pattern bab.

(C)

The set of all strings ending with the pattern bab.

(D)

The set of all strings not containing the pattern aba.

Explanation

GATE→2024→CS Core→Theory of Computation

Q116

MSQ[1 Mark]

Let L1, L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?

(A)

$L_{1}=L_{2}$ if and only if $L_{1}\cap\overline{L_{2}}=\phi$

(B)

$L_{1}\cup L_{3}$ is not regular

(C)

$L_{3}$ is not regular

(D)

$\overline{L_{1}}\cup\overline{L_{2}}$ is regular

Explanation

GATE→2024→CS Core→Theory of Computation

Q117

MSQ[2 Marks]

Consider the 5-state DFA M accepting the language L(M) over {0,1}*. Which of the following statements is/are FALSE?

(A)

States 2 and 4 are distinguishable in M

(B)

States 3 and 4 are distinguishable in M

(C)

States 2 and 5 are distinguishable in M

(D)

Any string w with n_0(w) = n_1(w) is in L(M)

Explanation

GATE→2024→CS Core→Theory of Computation

Q118

NAT[2 Marks]

Let G be a CFG in Chomsky Normal Form with 3 terminals and 10 variables. String w = a^30 b^30 c^30 is derivable from S. Number of steps in derivation S ->* w is

Explanation

GATE→2024→CS Core→Theory of Computation

Q119

NAT[2 Marks]

Consider two regular expressions over {0,1}: r = 0* + 1*, s = 01* + 10*. Total number of strings of length <= 5, which are neither in r nor in s, is

Explanation

GATE→2023→CS Core→Theory of Computation

Q120

MCQ[1 Mark]

Consider the Deterministic Finite-state Automaton (DFA) A shown below... Which one of the following regular expressions correctly describes the language accepted by A?

(A)

1(0*11)*

(B)

0(0+1)*

(C)

1(0+11)*

(D)

1(110*)*

Explanation

GATE→2023→CS Core→Theory of Computation

Q121

MSQ[1 Mark]

Which of the following statements is/are CORRECT?

(A)

The intersection of two regular languages is regular.

(B)

The intersection of two context-free languages is context-free.

(C)

The intersection of two recursive languages is recursive.

(D)

The intersection of two recursively enumerable languages is recursively enumerable.

Explanation

GATE→2023→CS Core→Theory of Computation

Q122

MCQ[2 Marks]

Consider the context-free grammar G below... Which one of the following statements is CORRECT?

(A)

The language generated by G is (a+b)*

(B)

The language generated by G is a*(a+b)b*

(C)

The language generated by G is a*b*(a+b)

(D)

The language generated by G is not a regular language

Explanation

GATE→2023→CS Core→Theory of Computation

Q123

MCQ[2 Marks]

Consider the pushdown automaton (PDA) P below... Which one of the following options correctly describes the language accepted by P?

(A)

{a^m b^n | 1 <= m and n < m}

(B)

{a^m b^n | 0 <= n <= m}

(C)

{a^m b^n | 0 <= m and 0 <= n}

(D)

{a^m | 0 <= m} U {b^n | 0 <= n}

Explanation

GATE→2023→CS Core→Theory of Computation

Q124

NAT[2 Marks]

Consider the language L over the alphabet {0,1}... The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is

Explanation

GATE→2022→CS Core→Theory of Computation

Q125

MCQ[1 Mark]

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

(A)

ab*bab* + ba*aba*

(B)

(ab*b)*ab* + (ba*a)*ba*

(C)

(ab*b + ba*a)*(a* + b*)

(D)

(ba*a + ab*b)*(ab* + ba*)

Explanation

GATE→2022→CS Core→Theory of Computation

Q126

MSQ[1 Mark]

Which of the following statements is/are TRUE?

(A)

Every subset of a recursively enumerable language is recursive.

(B)

If a language L and its complement \bar{L} are both recursively enumerable, then L must be recursive.

(C)

Complement of a context-free language must be recursive.

(D)

If L1 and L2 are regular, then L1 \cap L2 must be deterministic context-free.

Explanation

GATE→2022→CS Core→Theory of Computation

Q127

MSQ[2 Marks]

Which of the following is/are undecidable?

(A)

Given two Turing machines M1 and M2, decide if L(M1) = L(M2).

(B)

Given a Turing machine M, decide if L(M) is regular.

(C)

Given a Turing machine M, decide if M accepts all strings.

(D)

Given a Turing machine M, decide if M takes more than 10^73 steps on every string.

Explanation

GATE→2022→CS Core→Theory of Computation

Q128

MSQ[2 Marks]

Consider the following languages... Which of the following is/are TRUE?

(A)

L1 and L2 are regular.

(B)

L1 and L2 are context-free.

(C)

L1 is regular and L2 is context-free.

(D)

L1 and L2 are context-free but not regular.

Explanation

GATE→2022→CS Core→Theory of Computation

Q129

MSQ[2 Marks]

Consider the following languages... Which of the following statements is/are FALSE?

(A)

L1 is not context-free but L2 and L3 are deterministic context-free.

(B)

Neither L1 nor L2 is context-free.

(C)

L2, L3 and L2 \cap L3 all are context-free.

(D)

Neither L1 nor its complement is context-free.

Explanation

Compiler Design

20 Questions

GATE→2026→CS Core→Compiler Design

Q130

MSQ[1 Mark]

Consider the following C statements: /* S1 */ char *str1 = "Hello; /* S2 */ char *str2 = "Hello;"; /* S3 */ int *str3 = "Hello"; Which options is/are correct?

(A)

S1 and S2 have syntactic errors

(B)

S2 has a lexical error and S3 has a syntactic error

(C)

S1 has a lexical error and S3 has a semantic error

(D)

S1 has a syntactic error and S3 has a semantic error

Explanation

GATE→2026→CS Core→Compiler Design

Q131

MSQ[1 Mark]

Which of the following statements is/are true?

(A)

LL(1) parser uses backtracking

(B)

For a grammar to be LL(1), it must be left-recursive

(C)

For a grammar to be LL(1) it must be left-factored

(D)

The LL(1) parsers are more powerful than the SLR parsers

Explanation

GATE→2026→CS Core→Compiler Design

Q132

MCQ[2 Marks]

Consider the control flow graph shown in the figure. Which option correctly lists redundant expressions in basic blocks B4 and B5?

(A)

B4: {b+i}, B5: {c+m}

(B)

B4: {g*k}, B5: {c+m}

(C)

B4: {g*k, b+i}, B5: {}

(D)

B4: {g*k}, B5: {}

Explanation

GATE→2026→CS Core→Compiler Design

Q133

MSQ[2 Marks]

Consider syntax-directed definitions SDD1 and SDD2. Which of the following statements is/are true?

(A)

The languages P and Q specified by G1 and G2 are the same

(B)

SDD2 is S-attributed and contains only synthesized attributes

(C)

SDD1 is L-attributed and contains only inherited attributes

(D)

The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table

Explanation

GATE→2025→CS Core→Compiler Design

Q134

MCQ[1 Mark]

Which ONE of the following statements is FALSE regarding the symbol table?

(A)

Symbol table is responsible for keeping track of the scope of variables.

(B)

Symbol table can be implemented using a binary search tree.

(C)

Symbol table is not required after the parsing phase.

(D)

Symbol table is created during the lexical analysis phase.

Explanation

GATE→2025→CS Core→Compiler Design

Q135

MCQ[1 Mark]

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

(A)

Run-time function call management

(B)

Register assignment to variables

(C)

Strength reduction

(D)

Constant folding

Explanation

GATE→2025→CS Core→Compiler Design

Q136

MSQ[2 Marks]

Which statements are TRUE while computing First and Follow during top-down parsing?

(A)

For a production A -> epsilon, epsilon will be added to First(A).

(B)

If there is any input right end marker, it will be added to First(S).

(C)

For a production A -> epsilon, epsilon will be added to Follow(A).

(D)

If there is any input right end marker, it will be added to Follow(S).

Explanation

GATE→2025→CS Core→Compiler Design

Q137

NAT[2 Marks]

Number of basic blocks in given 3-address code sequence.

Explanation

GATE→2024→CS Core→Compiler Design

Q138

MSQ[1 Mark]

Which of the following is/are Bottom-Up Parser(s)?

(A)

Shift-reduce Parser

(B)

Predictive Parser

(C)

LL(1) Parser

(D)

LR Parser

Explanation

GATE→2024→CS Core→Compiler Design

Q139

MCQ[2 Marks]

Consider the following syntax-directed definition (SDD)... Given 'MMLK' as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute S.val)?

(A)

45

(B)

50

(C)

(D)

Explanation

GATE→2024→CS Core→Compiler Design

Q140

MCQ[2 Marks]

Consider the following grammar G, with S as the start symbol. The grammar G has three incomplete productions denoted by (1), (2), and (3)... Which one of the following options CORRECTLY fills in the incomplete productions?

(A)

(1) S->Rf (2) T->\epsilon (3) R->cTR

(B)

(C)

(D)

Explanation

GATE→2024→CS Core→Compiler Design

Q141

MCQ[2 Marks]

Consider the following pseudo-code. Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively?

(A)

(B)

(C)

(D)

7 and 6

Explanation

GATE→2023→CS Core→Compiler Design

Q142

MCQ[1 Mark]

Consider the following statements regarding the front-end and back-end of a compiler. S1: The front-end includes phases that are independent of the target hardware. S2: The back-end includes phases that are specific to the target hardware. S3: The back-end includes phases that are specific to the programming language used in the source code. Identify the CORRECT option.

(A)

Only S1 is TRUE.

(B)

Only S1 and S2 are TRUE.

(C)

S1, S2, and S3 are all TRUE.

(D)

Only S1 and S3 are TRUE.

Explanation

GATE→2023→CS Core→Compiler Design

Q143

MCQ[1 Mark]

Consider the following definition of a lexical token id for an identifier in a programming language... Which one of the following Non-deterministic Finite-state Automata with \epsilon-transitions accepts the set of valid identifiers?

(A)

(B)

(C)

(D)

Explanation

GATE→2023→CS Core→Compiler Design

Q144

MCQ[2 Marks]

Consider the following program... Which one of the following options represents the activation tree corresponding to the main function?

(A)

(B)

(C)

(D)

Explanation

GATE→2023→CS Core→Compiler Design

Q145

MCQ[2 Marks]

Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?

(A)

B1: {}, B2: {a}, B3: {a}, B4: {a}

(B)

B1: {i, j}, B2: {a}, B3: {a}, B4: {i}

(C)

B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}

(D)

B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}

Explanation

GATE→2023→CS Core→Compiler Design

Q146

NAT[2 Marks]

Consider the syntax directed translation given by the following grammar and semantic rules... The value computed by the translation scheme for the input string 10#011 is

Explanation

GATE→2022→CS Core→Compiler Design

Q147

MCQ[1 Mark]

Which one of the following statements is TRUE?

(A)

The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict.

(B)

Symbol table is accessed only during the lexical analysis phase.

(C)

Data flow analysis is necessary for run-time memory management.

(D)

LR(1) parsing is sufficient for deterministic context-free languages.

Explanation

GATE→2022→CS Core→Compiler Design

Q148

NAT[1 Mark]

If I_0 is the set of two LR(0) items {[S' -> S.], [S -> S. + R]}, then goto(closure(I_0), +) contains exactly ___ items.

Explanation

GATE→2022→CS Core→Compiler Design

Q149

NAT[2 Marks]

Using this translation scheme, the computed value of S.val for root of the parse tree for the expression 20#10%5#8%2%2 is

Explanation

Operating System

26 Questions

GATE→2026→CS Core→Operating System

Q150

MSQ[1 Mark]

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

(A)

Banker's algorithm is used to prevent deadlocks

(B)

Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed

(C)

An assignment edge in a resource allocation graph is marked from a process to a resource

(D)

A safe state guarantees that all processes can finish without formation of a deadlock

Explanation

GATE→2026→CS Core→Operating System

Q151

NAT[1 Mark]

Consider a system consisting of k instances of a resource R, shared by 5 processes... The minimum value of k for the system to be deadlock-free is

Explanation

GATE→2026→CS Core→Operating System

Q152

MSQ[2 Marks]

Consider a system with cache and MMU with TLB. Evicted pages invalidate corresponding cache blocks. Which sequence of events can NEVER happen?

(A)

TLB miss, Page table hit, Cache hit

(B)

TLB hit, Page table miss, Cache hit

(C)

TLB miss, Page table miss, Cache hit

(D)

TLB miss, Page table miss, Cache miss

Explanation

GATE→2025→CS Core→Operating System

Q153

MCQ[1 Mark]

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Maximum number of entries in page table?

(A)

$2^{21}$

(B)

$2^{20}$

(C)

$2^{22}$

(D)

$2^{24}$

Explanation

GATE→2025→CS Core→Operating System

Q154

NAT[1 Mark]

Number of times process enters ready queue during lifetime (excluding initial entry) for given program segment.

Explanation

GATE→2025→CS Core→Operating System

Q155

MCQ[2 Marks]

Two processors M1 and M2, 4 processes P1, P2, P3, P4 bursts 20, 16, 25, 10. Non-preemptive priority scheduling... Average waiting time?

(A)

9.00

(B)

8.75

(C)

6.50

(D)

7.50

Explanation

GATE→2025→CS Core→Operating System

Q156

NAT[2 Marks]

Disk 512MB, block size 64KB. Linked allocation, 4 bytes pointer per block. File size 1MB. Internal fragmentation in bytes?

Explanation

GATE→2025→CS Core→Operating System

Q157

NAT[2 Marks]

Modified optimal page replacement predicting up to next 4 references. Reference string: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4. 3 frames initially empty. Number of page faults?

Explanation

GATE→2024→CS Core→Operating System

Q158

MSQ[1 Mark]

Which of the following statements about threads is/are TRUE?

(A)

Threads can only be implemented in kernel space

(B)

Each thread has its own file descriptor table for open files

(C)

All the threads belonging to a process share a common stack

(D)

Threads belonging to a process are by default not protected from each other

Explanation

GATE→2024→CS Core→Operating System

Q159

MSQ[1 Mark]

Which of the following process state transitions is/are NOT possible?

(A)

Running to Ready

(B)

Waiting to Running

(C)

Ready to Waiting

(D)

Running to Terminated

Explanation

GATE→2024→CS Core→Operating System

Q160

MCQ[2 Marks]

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a=b=1... Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

(A)

(a=4, b=4); (a=3, b=3); (a=4, b=3)

(B)

(C)

(D)

Explanation

GATE→2024→CS Core→Operating System

Q161

NAT[2 Marks]

Consider the following code snippet using fork() and wait(). Total number of times the printf statement is executed is

Explanation

GATE→2024→CS Core→Operating System

Q162

NAT[2 Marks]

Consider a memory management system... Physical address corresponding to virtual address 2500 is

Explanation

GATE→2023→CS Core→Operating System

Q163

MSQ[1 Mark]

Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process?

(A)

Page table base register

(B)

Stack pointer

(C)

Program counter

(D)

General purpose registers

Explanation

GATE→2023→CS Core→Operating System

Q164

MSQ[1 Mark]

Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?

(A)

Function Call

(B)

malloc Call

(C)

Page Fault

(D)

System Call

Explanation

GATE→2023→CS Core→Operating System

Q165

MSQ[1 Mark]

Which one or more of the following CPU scheduling algorithms can potentially cause starvation?

(A)

First-in First-Out

(B)

Round Robin

(C)

Priority Scheduling

(D)

Shortest Job First

Explanation

GATE→2023→CS Core→Operating System

Q166

NAT[1 Mark]

The ratio T1/T2 is ___ (Rounded off to one decimal place)

Explanation

GATE→2023→CS Core→Operating System

Q167

MCQ[2 Marks]

Consider the two functions incr and decr shown below... 5 threads incr, 3 threads decr. Minimum possible values of V1, V2 respectively?

(A)

15, 7

(B)

7, 7

(C)

12, 7

(D)

12, 8

Explanation

GATE→2023→CS Core→Operating System

Q168

NAT[2 Marks]

Consider two-dimensional array D[128][128]... Number of page faults generated during execution of this code snippet is

Explanation

GATE→2023→CS Core→Operating System

Q169

NAT[2 Marks]

Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels... The value of L is

Explanation

GATE→2022→CS Core→Operating System

Q170

MCQ[1 Mark]

Which initialization of the semaphores would print the sequence BCABCABCA....?

(A)

S1=1, S2=1, S3=1

(B)

S1=1, S2=1, S3=0

(C)

S1=1, S2=0, S3=0

(D)

S1=0, S2=1, S3=1

Explanation

GATE→2022→CS Core→Operating System

Q171

MSQ[1 Mark]

Which of the following statements is/are TRUE with respect to deadlocks?

(A)

Circular wait is a necessary condition for the formation of deadlock.

(B)

In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.

(C)

If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.

(D)

In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Explanation

GATE→2022→CS Core→Operating System

Q172

MCQ[2 Marks]

Which one of the following statements is FALSE?

(A)

The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.

(B)

If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.

(C)

The memory access time using a given inverted page table is always same for all incoming virtual addresses.

(D)

In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.

Explanation

GATE→2022→CS Core→Operating System

Q173

MCQ[2 Marks]

Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

(A)

P=4, Q=10, R=6, S=2

(B)

P=2, Q=9, R=5, S=1

(C)

P=4, Q=12, R=5, S=4

(D)

P=3, Q=7, R=7, S=3

Explanation

GATE→2022→CS Core→Operating System

Q174

NAT[2 Marks]

Let the number of disk accesses required to insert a block in the middle of the file in A and B be nA and nB, respectively, then the value of nA + nB is

Explanation

GATE→2022→CS Core→Operating System

Q175

NAT[2 Marks]

the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is

Explanation

Databases

21 Questions

GATE→2026→CS Core→Databases

Q176

MSQ[1 Mark]

Let P, Q, R and S be attributes. Which of the following functional dependency options is/are always true?

(A)

If ({P,Q} -> {R} and {P} -> {R}), then {Q} -> {R}

(B)

If {P,Q} -> {R} then ({P} -> {R} or {Q} -> {R})

(C)

If ({P} -> {R} and {Q} -> {S}), then {P,Q} -> {R,S}

(D)

If {P} -> {R} then {P,Q} -> {R}

Explanation

GATE→2026→CS Core→Databases

Q177

MSQ[1 Mark]

In the context of relational database normalization, which of the following statements is/are true?

(A)

It is always possible to obtain a dependency-preserving 3NF decomposition

(B)

It is always possible to obtain a dependency-preserving 1NF decomposition

(C)

It is not always possible to obtain a dependency-preserving BCNF decomposition

(D)

It is not always possible to obtain a dependency-preserving 2NF decomposition

Explanation

GATE→2026→CS Core→Databases

Q178

MCQ[2 Marks]

Consider relations R(P,Q) and S(X,Y). Let tuple relational calculus expression E = {(u) | exists v ((u,v) in R and (v,u) in S)}. Which relational algebraic expression is equivalent to E?

(A)

Pi_P(R join_{R.P=S.X} S)

(B)

Pi_P(S join_{S.X=R.Q} R)

(C)

Pi_P(R join_{R.P=S.Y} S)

(D)

Pi_P(S join_{S.Y=R.Q} R)

Explanation

GATE→2025→CS Core→Databases

Q179

MCQ[1 Mark]

Schedule: R1(X) W1(Y) R2(X) R2(Y) R3(Y) ABORT(T1). T1 aborts. Which other transactions rolled back?

(A)

Only T2

(B)

Only T3

(C)

Both T2 and T3

(D)

Neither T2 nor T3

Explanation

GATE→2025→CS Core→Databases

Q180

MSQ[1 Mark]

Inserting 23 into B+ tree with max 3 keys per node. Which are CORRECT?

(A)

None of the nodes will split.

(B)

At least one node will split and redistribute.

(C)

Total number of nodes will remain same.

(D)

The height of the tree will increase.

Explanation

GATE→2025→CS Core→Databases

Q181

MCQ[2 Marks]

Tuple relational calculus query for players playing for team 'MI'.

(A)

(B)

(C)

(D)

Explanation

GATE→2025→CS Core→Databases

Q182

MSQ[2 Marks]

Relational schema team(name, city, owner) with FDs {name->city, name->owner} decomposed into t1(name, city) and t2(name, owner). Which are TRUE?

(A)

The relation team is NOT in BCNF.

(B)

The relations t1 and t2 are in BCNF.

(C)

The decomposition constitutes a lossless join.

(D)

The relation team is NOT in 3NF.

Explanation

GATE→2025→CS Core→Databases

Q183

NAT[2 Marks]

Value returned by given SQL query on sports league tables.

Explanation

GATE→2024→CS Core→Databases

Q184

MCQ[1 Mark]

Let S be the specification: 'Instructors teach courses. Students register for courses. Courses are allocated classrooms. Instructors guide students.' Which ER diagram correctly represents S?

(A)

(i)

(B)

(ii)

(C)

(iii)

(D)

(iv)

Explanation

GATE→2024→CS Core→Databases

Q185

MCQ[1 Mark]

In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?

(A)

Only the root node

(B)

All leaf nodes

(C)

All internal nodes

(D)

Only the leftmost leaf node

Explanation

GATE→2024→CS Core→Databases

Q186

NAT[1 Mark]

Consider relations R(A,B) and S(A,C). Total number of tuples obtained by evaluating sigma_{B<C}(R join_{R.A=S.A} S) is

Explanation

GATE→2024→CS Core→Databases

Q187

MSQ[2 Marks]

Which of the following options is/are TRUE?

(A)

$(X,Y)\rightarrow(Z,W)$ implies $X\rightarrow(Z,W)$

(B)

$(X,Y)\rightarrow(Z,W)$ implies $(X,Y)\rightarrow Z$

(C)

$((X,Y)\rightarrow Z$ and $W\rightarrow Y)$ implies $(X,W)\rightarrow Z$

(D)

$(X\rightarrow Y$ and $Y\rightarrow Z)$ implies $X\rightarrow Z$

Explanation

GATE→2024→CS Core→Databases

Q188

MSQ[2 Marks]

Consider the following read-write schedule S over three transactions T1, T2, and T3... Which of the following transaction schedules is/are conflict equivalent to S?

(A)

T1 T2 T3

(B)

T1 T3 T2

(C)

T3 T2 T1

(D)

T3 T1 T2

Explanation

GATE→2023→CS Core→Databases

Q189

MCQ[1 Mark]

Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?

(A)

Number of attributes of its relation schema.

(B)

Number of tuples stored in the relation.

(C)

Number of entries in the relation.

(D)

Number of distinct domains of its relation schema.

Explanation

GATE→2023→CS Core→Databases

Q190

NAT[2 Marks]

Consider the following table named Student in a relational database... The SQL query below is executed... The number of rows returned by the query is

Explanation

GATE→2023→CS Core→Databases

Q191

NAT[2 Marks]

Consider a database of fixed-length records... Given a key, the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is

Explanation

GATE→2022→CS Core→Databases

Q192

MCQ[1 Mark]

In a relational data model, which one of the following statements is TRUE?

(A)

A relation with only two attributes is always in BCNF.

(B)

If all attributes of a relation are prime attributes, then the relation is in BCNF.

(C)

Every relation has at least one non-prime attribute.

(D)

BCNF decompositions preserve functional dependencies.

Explanation

GATE→2022→CS Core→Databases

Q193

MSQ[1 Mark]

Which of the following relational algebra expressions return the set of eIds who own all the brands?

(A)

\Pi_{eld}(\Pi_{eld,bld}(Own)/\Pi_{bld}(Brand))

(B)

\Pi_{eld}(Own)-\Pi_{cld}((\Pi_{eld}(Own)\times\Pi_{bld}(Brand))-\Pi_{eld,bld}(Own))

(C)

\Pi_{eld}(\Pi_{eld,bld}(Own)/\Pi_{bld}(Own))

(D)

\Pi_{eld}((\Pi_{eld}(Own)\times\Pi_{bld}(Own))/\Pi_{bld}(Brand))

Explanation

GATE→2022→CS Core→Databases

Q194

NAT[1 Mark]

Consider a relation R(A,B,C,D,E) with the following three functional dependencies: AB->C, BC->D, C->E. The number of superkeys in the relation R is

Explanation

GATE→2022→CS Core→Databases

Q195

MCQ[2 Marks]

Which one of the following serial schedules is conflict equivalent to S?

(A)

T1 -> T3 -> T4 -> T2

(B)

T1 -> T4 -> T3 -> T2

(C)

T4 -> T1 -> T3 -> T2

(D)

T3 -> T1 -> T4 -> T2

Explanation

GATE→2022→CS Core→Databases

Q196

NAT[2 Marks]

The number of rows returned by the above SQL query is

Explanation

Computer Networks

27 Questions

GATE→2026→CS Core→Computer Networks

Q197

MCQ[1 Mark]

With respect to a TCP connection between a client and a server, which one of the following statements is true?

(A)

The client and server use a two-way handshake mechanism before the start of data transmission

(B)

The server cannot initiate closing of the connection before the client initiates closing of the connection

(C)

The TCP connection is half-duplex

(D)

The client and server can initiate closing of the connection at the same time

Explanation

GATE→2026→CS Core→Computer Networks

Q198

MSQ[1 Mark]

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?

(A)

HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, if the objects are stored in the same server

(B)

HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, even if they are stored in different servers

(C)

HTTP 1.1 facilitates sending a request for downloading one object without waiting for a previously requested object to be downloaded completely

(D)

HTTP 1.1 facilitates downloading multiple webpages on the same server to be downloaded over a single TCP connection

Explanation

GATE→2026→CS Core→Computer Networks

Q199

MCQ[2 Marks]

A TCP sender establishes connection... slow-start threshold 10000 segments, RTT 1 ms. Time t (ms) at which transmission of segment 2000 starts is

(A)

9 <= t < 10

(B)

10 <= t < 11

(C)

11 <= t < 12

(D)

12 <= t < 13

Explanation

GATE→2026→CS Core→Computer Networks

Q200

MCQ[2 Marks]

Sliding window protocol over lossless link, window size W frames, frame size 1000 bits, bandwidth 100 kbps, propagation delay 100 ms. Minimum W for 100% link utilization is

(A)

10

(B)

21

(C)

20

(D)

11

Explanation

GATE→2026→CS Core→Computer Networks

Q201

MSQ[2 Marks]

An ISP having address block 202.16.0.0/15 assigns a block of 6000 IP addresses to a client using CIDR. Which address blocks can be assigned?

(A)

202.16.0.0/19

(B)

202.17.64.0/19

(C)

202.16.32.0/19

(D)

202.17.24.0/19

Explanation

GATE→2025→CS Core→Computer Networks

Q202

MCQ[1 Mark]

Identify correct matching between OSI layers and functionalities.

(A)

(a)-(I), (b)-(II), (c)-(III)

(B)

(a)-(I), (b)-(III), (c)-(II)

(C)

(a)-(II), (b)-(I), (c)-(III)

(D)

(a)-(III), (b)-(II), (c)-(I)

Explanation

GATE→2025→CS Core→Computer Networks

Q203

MSQ[1 Mark]

TCP 3-way handshake P1, P2, P3 flags. Which are TRUE?

(A)

P3: SYN=1, ACK=1

(B)

P2: SYN=1, ACK=1

(C)

P2: SYN=0, ACK=1

(D)

P1: SYN=1

Explanation

GATE→2025→CS Core→Computer Networks

Q204

MCQ[2 Marks]

Destination IP 145.36.109.70 arrives at router with given routing table. Which interface?

(A)

E3

(B)

E1

(C)

E2

(D)

E5

Explanation

GATE→2025→CS Core→Computer Networks

Q205

NAT[2 Marks]

5-bit message transmitted, bit flip probability 0.01 independently. Probability message delivered error-free?

Explanation

GATE→2025→CS Core→Computer Networks

Q206

NAT[2 Marks]

Message size 15000 bytes transmitted via IPv4 through two routers with MTU 5000 and 3000 bytes. Number of fragments delivered to destination?

Explanation

GATE→2024→CS Core→Computer Networks

Q207

MCQ[1 Mark]

User browsing webpage. Packets: (i) HTTP GET index, (ii) DNS request, (iii) HTTP GET image, (iv) TCP SYN. Correct chronological order?

(A)

(iv), (ii), (iii), (i)

(B)

(ii), (iv), (iii), (i)

(C)

(ii), (iv), (i), (iii)

(D)

(iv), (ii), (i), (iii)

Explanation

GATE→2024→CS Core→Computer Networks

Q208

MSQ[1 Mark]

TCP client P successfully establishes a connection to TCP server Q. Let N_P denote the sequence number in SYN, N_Q denote acknowledgement number in SYN ACK. Which of the following statements is/are CORRECT?

(A)

The sequence number N_P is chosen randomly by P

(B)

The sequence number N_P is always 0 for a new connection

(C)

The acknowledgement number N_Q is equal to N_P

(D)

The acknowledgement number N_Q is equal to N_P + 1

Explanation

GATE→2024→CS Core→Computer Networks

Q209

MSQ[1 Mark]

Which of the following fields is/are modified in the IP header of a packet going out of a network address translation (NAT) device from an internal network to an external network?

(A)

Source IP

(B)

Destination IP

(C)

Header Checksum

(D)

Total Length

Explanation

GATE→2024→CS Core→Computer Networks

Q210

MCQ[2 Marks]

Consider a network path P-Q-R between nodes P and R via router Q. Node P sends a file of size 10^6 bytes... Which one of the following options gives the time (in seconds, rounded off to 3 decimal places) at which R receives all the chunks of the file?

(A)

8.000

(B)

8.008

(C)

15.992

(D)

16.000

Explanation

GATE→2024→CS Core→Computer Networks

Q211

NAT[2 Marks]

Consider the entries shown below in the forwarding table of an IP router... Number of packets forwarded via the next hop router R2 is

Explanation

GATE→2024→CS Core→Computer Networks

Q212

NAT[2 Marks]

Consider sending an IP datagram of size 1420 bytes... Number of fragments that would be delivered at the receiver is

Explanation

GATE→2023→CS Core→Computer Networks

Q213

MCQ[1 Mark]

Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.

(A)

Longer link length and lower transmission rate

(B)

Longer link length and higher transmission rate

(C)

Shorter link length and lower transmission rate

(D)

Shorter link length and higher transmission rate

Explanation

GATE→2023→CS Core→Computer Networks

Q214

MSQ[1 Mark]

Which of the following statements is/are INCORRECT about the OSPF (Open Shortest Path First) routing protocol used in the Internet?

(A)

OSPF implements Bellman-Ford algorithm to find shortest paths.

(B)

OSPF uses Dijkstra's shortest path algorithm to implement least-cost path routing.

(C)

OSPF is used as an inter-domain routing protocol.

(D)

OSPF implements hierarchical routing.

Explanation

GATE→2023→CS Core→Computer Networks

Q215

MSQ[2 Marks]

Suppose you are asked to design a new reliable byte-stream transport protocol like TCP... Which of the following is/are valid lengths of the Sequence Number field in the myTCP header?

(A)

30 bits

(B)

32 bits

(C)

34 bits

(D)

36 bits

Explanation

GATE→2023→CS Core→Computer Networks

Q216

MSQ[2 Marks]

Suppose in a web browser, you click on www.gate-2023.in URL... Which of the following statements is/are CORRECT about the minimum elapsed time between clicking on the URL and your browser fully rendering it?

(A)

7 RTTs, non-persistent HTTP with 5 parallel TCP connections.

(B)

5 RTTs, persistent HTTP with pipelining.

(C)

9 RTTs, non-persistent HTTP with 5 parallel TCP connections.

(D)

6 RTTs, persistent HTTP with pipelining.

Explanation

GATE→2023→CS Core→Computer Networks

Q217

NAT[2 Marks]

The forwarding table of a router is shown below... A packet addressed to a destination address 200.150.68.118 arrives at the router. It will be forwarded to the interface with ID

Explanation

GATE→2022→CS Core→Computer Networks

Q218

MCQ[1 Mark]

What is the number of subnets inside the enterprise network?

(A)

3

(B)

12

(C)

6

(D)

8

Explanation

GATE→2022→CS Core→Computer Networks

Q219

NAT[1 Mark]

Consider the resolution of the domain name www.gate.org.in by a DNS resolver... The number of DNS query-response pairs involved in completely resolving the domain name is

Explanation

GATE→2022→CS Core→Computer Networks

Q220

MSQ[2 Marks]

Which of the following prefixes in CIDR notation can be collectively used to correctly aggregate all of the subnets in the routing table?

(A)

12.20.164.0/20

(B)

12.20.164.0/22

(C)

12.20.164.0/21

(D)

12.20.168.0/22

Explanation

GATE→2022→CS Core→Computer Networks

Q221

NAT[2 Marks]

The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to count-to-infinity problem, is

Explanation

GATE→2022→CS Core→Computer Networks

Q222

NAT[2 Marks]

The time taken (in milliseconds, rounded off to two decimal places) for the receiver to completely receive a packet of 1000 bytes transmitted by the sender is

Explanation

GATE→2022→CS Core→Computer Networks

Q223

NAT[2 Marks]

The minimum number of bits required for the sequence number field of the TCP header, to prevent the sequence number space from wrapping around during the MSL is

Explanation