GATE CS 2024 Set 1

Every node of a B+ tree except the root must be at least half full: an internal node of order \(p\) needs at least \(\lceil p/2 \rceil\) children, and a leaf must fill about half of its key slots. This keeps the tree shallow and its space use predictable.

The root cannot always meet the rule. When the root splits, the new root starts with a single key and two children, and a small tree may hold fewer keys than half a node. So the root alone is exempt: it needs only two children, or a single key when it is also a leaf.

Leaves, internal nodes and the leftmost leaf get no such exception, so B, C and D are wrong.

Answer: A

First normal form asks only that every attribute hold atomic (indivisible) values, so a 1NF relation has no composite or multivalued attributes. It says nothing about keys.

• A: true. A key made of several attributes, such as (RollNo, CourseNo), is allowed; atomicity is about values, not keys.
• B: false. A relation in any normal form may have a foreign key referring to another relation.
• C: true. A composite attribute such as Address (street, city, PIN) is not atomic, so in 1NF it must be split into simple attributes.
• D: false. A relation can have several candidate keys, for example both RollNo and Email in a student table.

Answer: A, C

Regular languages are closed under complement, union and intersection.

• A: false. \(L_{1} \cap \overline{L_{2}} = \phi\) says only that no string of \(L_{1}\) lies outside \(L_{2}\), that is, \(L_{1} \subseteq L_{2}\). With \(L_{1} = \phi\) and \(L_{2} = \Sigma^{*}\) the condition holds but \(L_{1} \ne L_{2}\).
• B: false. If \(L_{1} = \Sigma^{*}\), then \(L_{1} \cup L_{3} = \Sigma^{*}\), which is regular.
• C: true. If \(\overline{L_{3}}\) were regular, its complement \(L_{3}\) would be regular too, which it is not.
• D: true. \(\overline{L_{1}}\) and \(\overline{L_{2}}\) are regular, and so is their union.

Answer: C, D

• A: false. Threads can also be implemented in user space by a thread library, with the kernel seeing only one process (the many-to-one model).
• B: false. Open files belong to the process, so all its threads share one file descriptor table; a file opened by one thread can be used by the others.
• C: false. Each thread runs its own chain of function calls, so it needs its own stack, along with its own registers and program counter.
• D: true. The threads of a process share one address space, so any of them can read or overwrite the data of the others. The operating system puts no protection boundary between them; that is the price of cheap sharing.

Answer: D

In the process state diagram the moves are: Ready to Running (dispatch), Running to Ready (preemption, for example when the time slice ends), Running to Waiting (an I/O request or a wait for an event), Waiting to Ready (the event completes) and Running to Terminated (exit).

• Waiting to Running is not possible: when its event completes, a waiting process joins the ready queue, and only the scheduler can dispatch it from there.
• Ready to Waiting is not possible: a process blocks only by doing something, such as requesting I/O, and a ready process is not executing.

Running to Ready and Running to Terminated are normal transitions, so A and D are possible.

Answer: B, C

A bottom-up parser starts from the input tokens and repeatedly replaces a substring that matches the right side of a production by its left side, until only the start symbol remains. It traces a rightmost derivation in reverse.

• A shift-reduce parser is exactly this method: it shifts tokens onto a stack and reduces the handle on top of it.
• LR parsers (SLR, LALR and canonical LR) are table-driven shift-reduce parsers, so they are bottom-up as well.
• Predictive and LL(1) parsers start from the start symbol and expand nonterminals to match the input, following a leftmost derivation. They are top-down, so B and C are wrong.

Answer: A, D

• A: false. Independence needs \(P(A \cap B) = P(A)P(B) = 0.3 \times 0.5 = 0.15\), but \(P(A \cap B) = 0.1\).
• B: true. \(P(A \cup B) = P(A) + P(B) - P(A \cap B) = 0.3 + 0.5 - 0.1 = 0.7\).
• C: true. \(A\) splits into the disjoint parts \(A \cap B\) and \(A \cap B^{c}\), so \(P(A \cap B^{c}) = 0.3 - 0.1 = 0.2\).
• D: false. By De Morgan's law \(A^{c} \cap B^{c} = (A \cup B)^{c}\), so \(P(A^{c} \cap B^{c}) = 1 - 0.7 = 0.3\), not 0.4.

Answer: B, C

The AND gate receives \(X\) directly and \(\overline{X}\) through the inverter, so ideally \(Y = X \cdot \overline{X} = 0\) for every input: A is true and B is false.

Now let the NOT gate take time \(t\) to respond.

• \(X\) rises from 0 to 1: the direct input becomes 1 at once, but for time \(t\) the inverter still outputs its old value 1. Both AND inputs are briefly 1, so \(Y\) shows a short glitch to logic One (a static hazard). C is true.
• \(X\) falls from 1 to 0: the direct input drops to 0 at once, while the inverter output is still 0 and rises only after \(t\). The two inputs are never 1 together, so \(Y\) simply stays at 0. With no 1 to dip from, no transient Zero can appear, so D is false.

Answer: A, C

• A: true. In the three-way handshake each side picks its initial sequence number (pseudo-)randomly. This stops stray segments of an old connection between the same ports from being accepted, and makes it hard for an attacker to guess the numbers and forge segments.
• B: false. Starting every connection at 0 is exactly what the random choice avoids; packet analysers that show 0 are displaying relative numbers.
• C and D: a SYN uses up one sequence number even though it carries no data. The acknowledgement number in the SYN ACK is the next sequence number Q expects from P, so \(N_{Q} = N_{P} + 1\). C is false and D is true.

Answer: A, D

• A: true. This is what forwarding (bypassing) means: a result goes straight from the stage that produces it in an earlier instruction to the stage that needs it in a later one, without waiting for the register write in WB.
• B: true. The MEM/WB pipeline register holds what leaves the MEM stage, such as a loaded word, and a forwarding path takes it to the ALU inputs in EX. A loaded value reaches the very next instruction this way after one stall cycle.
• C: true. That stall is unavoidable: a loaded value appears only at the end of MEM, while the next instruction needs it at the start of EX in the same cycle.
• D: false. Forwarding needs extra paths, multiplexers at the ALU inputs and a forwarding unit that compares register numbers.

Answer: A, B, C