CS and IT GATE 2021 SET-2 Questions with Answer

Ques 1 Compiler Design

---

In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?

A

Three address code

B

Abstract Syntax Tree (AST)

C

Control Flow Graph (CFG)

D

Symbol table

See Answer Video Solution

Ques 2 Computer Networks

---

Consider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by P and Q respectively. Suppose P sends a TCP connection request message to Q with a TCP segment having SYN bit = 1, SEQ number = X, and ACK bit = 0. Suppose Q accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by Q to P?

A

SYN bit = 1, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 0

B

SYN bit = 0, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 1

C

SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X+1, FIN bit = 0

D

SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X, FIN bit = 0

See Answer Video Solution

Ques 3 Computer Networks

---

Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below.

The objective is to find the shortest-cost path from the router R to routers P and Q. Assume that R does not initially know the shortest routes to P and Q. Assume that R has three neighbouring routers denoted as X, Y, and Z. During one iteration, R measures its distance to its neighbours X, Y, and Z as 3, 2, and 5, respectively. Router R gets routing vectors from its neighbours that indicate that the distance to router P from routers X, Y, and Z are 7, 6, and 5, respectively. The routing vector also indicates that the distance to router Q from routers X, Y, and Z are 4, 6, and 8, respectively. Which of the following statement(s) is/are correct with respect to the new routing table of R, after updation during this iteration?

A

The distance from R to P will be stored as 10.

B

The distance from R to Q will be stored as 7.

C

The next hop router for a packet from R to P is Y.

D

The next hop router for a packet from R to Q is Z.

See Answer Video Solution

Ques 4 Computer Networks

---

Consider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps (= 10⁶ bits per second). The aggregate number of transmissions across all the nodes (including new frame transmissions and retransmitted frames due to collisions) is modelled as a Poisson process with a rate of 1,000 frames per second. Throughput is defined as the average number of frames successfully transmitted per second. The throughput of the network (rounded to the nearest integer) is _______.

See Answer Video Solution

Ques 5 Computer Organization and Architecture

---

The format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows:

Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?

A

exponent = 0000000 and mantissa = 00000000000000000000000

B

exponent = 0000000 and mantissa = 00000000000000000000001

C

exponent = 00000001 and mantissa = 00000000000000000000000

D

exponent = 00000001 and mantissa = 00000000000000000000001

See Answer Video Solution

Ques 6 Computer Organization and Architecture

---

Consider a set-associative cache of size 2KB (1KB = 2¹⁰ bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for accessing the cache. If the width of the tag field is 22 bits, the associativity of the cache is _______.

See Answer Video Solution

Ques 7 Computer Organization and Architecture

---

Consider a computer system with DMA support. The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regular intervals. Consider a 2 MHz processor. If 0.5% processor cycles are used for DMA, the data transfer rate of the device is _______ bits per second.

See Answer Video Solution

Ques 8 Computer Organization and Architecture

---

Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements.
S₁: Read misses in a write through L1 cache do not result in writebacks of dirty lines to the L2.
S₂: Write allocate policy must be used in conjunction with write through caches and no-write allocate policy is used with writeback caches.
Which of the following statements is correct?

A

S₁ is true and S₂ is false

B

S₁ is false and S₂ is true

C

S₁ is true and S₂ is true

D

S₁ is false and S₂ is false

See Answer Video Solution

Ques 9 Computer Organization and Architecture

---

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?

A

0x6665

B

0x0001

C

0x4243

D

0x0100

See Answer Video Solution

Ques 10 Computer Organization and Architecture

---

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below.

The page size is 4KB (1KB = 2¹⁰ bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2GB (1GB = 2³⁰ bytes) virtual memory which is mapped to 2GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _______ KB.

See Answer Video Solution

Ques 11 Computer Organization and Architecture

---

Consider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the pipeline, except the EX stage, takes one cycle. Assume that the ID stage merely decodes the instruction and the register read is performed in the EX stage. The EX stage takes one cycle for ADD instruction and two cycles for MUL instruction. Ignore pipeline register latencies. Consider the following sequence of 8 instructions:
ADD, MUL, ADD, MUL, ADD, MUL, ADD, MUL
Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data-dependent on the MUL instruction just before it. The Speedup is defined as follows:

The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is _______.

See Answer Video Solution

Ques 12 Data Structures and Algorithms

---

Let G be a connected undirected weighted graph. Consider the following two statements.
S₁: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S₂: If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which one of the following options is correct?

A

Both S₁ and S₂ are true.

B

S₁ is true and S₂ is false.

C

S₁ is false and S₂ is true.

D

Both S₁ and S₂ are false.

See Answer Video Solution

Ques 13 Data Structures and Algorithms

---

Let H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

A

Θ(1)

B

Θ(log n)

C

Θ(n)

D

Θ(n log n)

See Answer Video Solution