Question 1

Which one of the following options is correct for the given data in the table?

Iteration (i): 0, 1, 2, 3
Input (I): 20, -4, 10, 15
Output (X): 20, 16, 26, 41
Output (Y): 20, -80, -800, -12000

Accepted Answer

X(i) = X(i − 1) + I(i); Y(i) = Y(i − 1)I(i); i > 0. The correct option accurately describes the relationship between the inputs and outputs, where the output X is the cumulative sum of the inputs, while Y is the product of the previous Y value and the current input, reflecting the operations performed at each iteration.

Question 2

Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?

Accepted Answer

(n - 1) / 2. In a binary tree where every node has either zero or two children, the number of nodes with two children is always one less than the total number of leaf nodes. Since there are n nodes in total, the formula (n - 1) / 2 correctly represents the count of nodes with two children.

Question 3

Let L, M, and N be non-singular matrices of order 3 satisfying the equations L² = L⁻¹, M = L⁸ and N = L². Which ONE of the following is the value of the determinant of (M - N)?

Accepted Answer

0. Since L² = L⁻¹, we can deduce that L⁸ = (L²)⁴ = (L⁻¹)⁴ = (L⁴)⁻¹. Therefore, M = L⁸ = (L⁴)⁻¹ and N = L². This implies that M and N are inverses of each other, leading to M - N being singular, which results in a determinant of 0.

Question 4

Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?

Accepted Answer

(P(0) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x)). This statement is an application of mathematical induction, where proving that a property holds for the base case (P(0)) and that if it holds for an arbitrary case (P(x)), it also holds for the next case (P(x + 1)) ensures that the property is true for all natural numbers.

Question 5

Consider the following statements:
(i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address.
(ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment

Accepted Answer

(i) is TRUE and (ii) is FALSE. Statement (i) is correct because ARP indeed maps IP addresses to hardware addresses, facilitating communication over a network. Statement (ii) is incorrect as TCP segments can carry both data and acknowledgements in the same segment, allowing for efficient communication.

Question 6

A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X. Which ONE of the following is NOT a possible candidate for X?

Accepted Answer

Routing Information Protocol (RIP). RIP is a routing protocol used for managing how routers communicate routing information, but it does not operate directly at the transport layer like the other options, which are protocols that handle data transmission and control.

Question 7

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
(I) Backpatching can be used to generate code for Boolean expression in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass.
Which

Accepted Answer

Both (I) and (II) are correct.. Backpatching allows a compiler to handle jumps and branches in control flow and Boolean expressions efficiently by postponing the actual address resolution until all necessary information is available, enabling code generation in a single pass for both types of statements.

Question 8

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Accepted Answer

Any regular language.. A deterministic pushdown automaton can recognize all regular languages because these languages can be represented by finite automata, which are a subset of the capabilities of deterministic pushdown automata.

Question 9

Let G1, G2 be Context Free grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is decidable?

(A) Is L(G1) = L(G2)?
(B) Is L(G1) ∩ L(G2) = ∅?
(C) Is L(G1) = L(R)?
(D) Is L(G1) = ∅?

Accepted Answer

Is L(G1) = ∅?. Determining whether the language generated by a context-free grammar is empty is decidable because there exists an algorithm that can analyze the grammar's production rules to check if any strings can be derived from it.

Question 10

Processes P1, P2, P3, P4 arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.

Whi

Accepted Answer

19. The average turnaround time is calculated by finding the total time each process takes from arrival to completion and then averaging these times. In this case, the SRTF scheduling allows for efficient execution, resulting in a total turnaround time of 76 milliseconds for all processes, which when divided by 4 gives an average of 19 milliseconds.

Question 11

An audit of a banking transactions system has found that on an earlier occasion, two joint holders of account A attempted simultaneous transfers of Rs. 10000 each from account A to account B. Both transactions read the same value, Rs. 11000, as the initial balance in A and were allowed to

Accepted Answer

Isolation. The violation of isolation occurs because the two simultaneous transactions were processed without recognizing that they were competing for the same account balance, leading to both transactions seeing the same initial balance and resulting in an incorrect final state.

Question 12

Which of the following is/are part of an Instruction Set Architecture of a processor?

Accepted Answer

The total number of registers. The total number of registers is a fundamental aspect of the Instruction Set Architecture (ISA) because it defines how many data storage locations are available for instructions to use during execution, directly impacting the processor's performance and capabilities.

Question 13

Consider the two lists List I and List II given below:

List I
(i) Context free languages
(ii) Recursive languages
(iii) Regular languages

List II
(a) Closed under union
(b) Not closed under complementation
(c) Closed under intersection

For matching of items in List I with those in List

Accepted Answer

(i) – (b), (ii) – (a), and (iii) – (c). The correct option matches context-free languages with not being closed under complementation, recursive languages with being closed under union, and regular languages with being closed under intersection, accurately reflecting the properties of these language classes.

Question 14

Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and the propagation delay between the two nodes is 100 milliseconds. Assume that the processing times at the source

Accepted Answer

88.23. Transmission time Tt = 3000/2000 = 1.5 s and propagation Tp = 0.1 s. Stop-and-Wait utilization = Tt/(Tt+2Tp) = 1.5/(1.5+0.2) = 1.5/1.7 = 88.23%. Option 0.

Question 15

For a direct-mapped cache, 4 bits are used for the tag field and 12 bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block.

Which ONE of the following is the CORRECT option for the sizes of

Accepted Answer

64 KB and 4 KB. The main memory size can be calculated using the total number of addressable locations, which is determined by the tag and index bits. With 4 bits for the tag and 12 bits for the index, the total addressable memory is 2^(4+12) = 64 KB. The cache size is determined by the number of cache blocks, which is 2¹² = 4096 blocks, and since each block is 1 byte, the cache size is 4 KB.

Question 16

An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for th

Accepted Answer

Θ(log n). The correct option is Θ(log n) because a bitonic array can be efficiently searched using a modified binary search approach. This method allows us to find the peak element in logarithmic time, and then we can perform binary searches on the two sorted halves, resulting in an overall search time of Θ(log n).

Question 17

Let F be the set of all functions from {1,...,n} to {0,1}. Define the binary relation ≼ on F as follows:

∀f,g ∈ F, f ≼ g if and only if ∀x ∈ {1,...,n}, f(x) ≤ g(x), where 0 ≤ 1.

Which of the following statement(s) is/are TRUE?

Accepted Answer

(F, ≼) is a lattice. (F, ≼) is a lattice because it satisfies the properties of a partially ordered set where every pair of elements has both a least upper bound (join) and a greatest lower bound (meet), which can be defined in terms of the pointwise maximum and minimum of the functions.

Question 18

Given the following Karnaugh Map for a Boolean function F(w,x,y,z):

The 4×4 K-map has rows labeled by wx and columns labeled by yz, with cell values:
Row 1: 1 0 0 1
Row 2: 0 1 1 0
Row 3: 0 1 1 0
Row 4: 1 0 0 1

Which one or more of the following Boolean expression(s) represent(s) F?

Accepted Answer

x̅z̅ + xz. The expression x̅z̅ + xz simplifies to cover the cases where z is either 0 or 1, regardless of the value of x, which matches the output of the K-map. This indicates that the function F is true for both conditions of x when z is fixed, making it the correct representation.

Question 19

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct.

We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer to the record w

Accepted Answer

Keep with every record in the stack, a pointer to the record with the smallest key below it.. This approach allows each record to directly reference the smallest key below it, enabling O(1) access to the minimum key without altering the time complexity of standard stack operations like PUSH and POP.

Question 20

Consider the following relational schema along with all the functional dependencies that hold on them.
R1(A, B, C, D, E): {D → E, EA → B, EB → C}
R2(A, B, C, D): {A → D, A → B, C → A}
Which of the following statement(s) is/are TRUE?

Accepted Answer

(D) R2 is NOT in 3NF. R2 is not in 3NF because the functional dependency C → A violates the condition for 3NF, as C is not a superkey and A is not a prime attribute.

Question 21

Three floating point numbers X, Y, and Z are stored in three registers Rₓ, R_y, and R_z, respectively in IEEE 754 single precision format as given below in hexadecimal:
Rₓ = 0xC1100000, R_y = 0x40C00000, and R_z = 0x41400000
Which of the following option(s) is/are CORRECT?

Accepted Answer

2Y - Z = 0. The equation 2Y - Z = 0 is correct because when you calculate the values of Y and Z from their hexadecimal representations, you find that doubling Y results in the same value as Z, confirming the equality.

Question 22

Let Σ = {a,b,c}. For x ∈ Σ*, and α ∈ Σ, let #α(x) denote the number of occurrences of α in x.
Which one or more of the following option(s) define(s) regular language(s)?

Accepted Answer

{w | w ∈ {a,b}*, #a(w) ≡ 2 (mod 7), and #b(w) ≡ 3 (mod 9)}. Option C defines a regular language because it specifies constraints on the counts of 'a' and 'b' using modular arithmetic, which can be represented by finite automata. Regular languages can handle such conditions, as they can track a finite number of states corresponding to the remainders of the counts.

GATE Technical: Computer Science and Information Technology (CS2) questions with solutions

Questions