Q: Consider the following C program: #include int main(){ int a = 6; int b = 0; while(a < 10) { a = a / 12 + 1; a += b;} printf("%d", a); return 0;} Which one of the following statements is CORRECT?

The program gets stuck in an infinite loop. The program enters an infinite loop because the condition 'a < 10' remains true indefinitely. The value of 'a' is updated in such a way that it never reaches or exceeds 10, causing the loop to continue without termination.

Question 1

Which one of the following statements is FALSE?

Accepted Answer

Programmed I/O mechanism has a better CPU utilization than the interrupt driven I/O mechanism. The statement is false because programmed I/O typically requires the CPU to actively wait for I/O operations to complete, leading to lower CPU utilization compared to interrupt-driven I/O, where the CPU can perform other tasks while waiting for interrupts.

Question 2

A user starts browsing a webpage hosted at a remote server. The browser opens a single TCP connection to fetch the entire webpage from the server. The webpage consists of a top-level index page with multiple embedded image objects. Assume that all caches (e.g., DNS cache, browser cache) ar

Accepted Answer

(ii), (iv), (i), (iii). The correct order starts with the DNS request to resolve the server's name, as the browser needs the IP address before establishing a connection. Next, the TCP SYN packet is sent to open a connection to the server. After the connection is established, the browser sends the HTTP GET request for the index page, followed by requests for any embedded image objects.

Question 3

Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time compl

Accepted Answer

both O(N) and Ω(N). The algorithm checks each pair of adjacent elements in a single pass through the array, which requires examining all N elements, resulting in a linear time complexity of O(N). Since it must at least look at each element once to determine the order, it also has a lower bound of Ω(N), making the correct option both O(N) and Ω(N).

Question 4

Consider the following C program:

#include <stdio.h>

int main(){

int a = 6;

int b = 0;

while(a < 10) {

a = a / 12 + 1;

a += b;}

printf("%d", a);

return 0;}

Which one of the following statements is CORRECT?

Accepted Answer

The program gets stuck in an infinite loop. The program enters an infinite loop because the condition 'a < 10' remains true indefinitely. The value of 'a' is updated in such a way that it never reaches or exceeds 10, causing the loop to continue without termination.

Question 5

Consider the following C program:

#include <stdio.h>
void fX();
int main(){
 fX();
 return 0;}

void fX(){
 char a;
 if((a=getchar()) != '
')
 fX();
 if(a != '
')
 putchar(a);}

Assume that the input to the program from the command line is 1234 followed by a newline character. Which one o

Accepted Answer

The program will terminate with 4321 as output. The program reads characters from input recursively until it encounters a newline, storing each character in reverse order due to the nature of the recursive calls. When the newline is reached, the recursion unwinds, and the characters are printed in reverse, resulting in '4321' as the output.

Question 6

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

Accepted Answer

Only the root node. The root node of a B+ tree can have fewer than half of its maximum capacity, allowing it to have just one key when the tree is small or when it is being initialized. This flexibility is essential for maintaining the tree's structure during insertions and deletions.

Question 7

Which of the following statements about a relation R in first normal form (1NF) is/are TRUE ?

Accepted Answer

R can have a multi-attribute key. A relation in first normal form (1NF) allows for multi-attribute keys, meaning that a primary key can consist of more than one attribute to uniquely identify each record in the relation.

Question 8

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

Accepted Answer

Shift-reduce Parser. The Shift-reduce Parser is a type of bottom-up parser that builds the parse tree from the leaves (input symbols) up to the root (start symbol) by shifting input symbols onto a stack and reducing them to non-terminals according to production rules.

Question 9

Let A and B be two events in a probability space with P(A) = 0.3, P(B) = 0.5, and P(A ∩ B) = 0.1. Which of the following statements is/are TRUE?

Accepted Answer

P(A ∪ B) = 0.7. The statement P(A ∪ B) = P(A) + P(B) - P(A ∩ B) simplifies to 0.3 + 0.5 - 0.1, which equals 0.7, confirming the correctness of the statement.

Question 10

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

Accepted Answer

The acknowledgement number N_Q is equal to N_P + 1. The acknowledgement number N_Q is set to N_P + 1 because it indicates that the server Q has received the SYN packet from client P and is acknowledging the next expected sequence number, which is one more than the initial sequence number sent by P.

Question 11

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?

Accepted Answer

Source IP. The source IP address is modified by the NAT device to replace the internal IP with its own public IP, allowing the packet to be correctly routed on the external network.

Question 12

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption.

T1

a = a + 1;
b = b + 1;

T2

b

Accepted Answer

(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3). Each statement is atomic and order within a thread is fixed (a=a+1 before b=b+1; b=2b before a=2a). Enumerating all valid interleavings yields exactly {(4,4),(3,3),(4,3)}: T1-then-T2 gives (4,4), T2-then-T1 gives (3,3), and the mixed orders give (4,3). The set matching this is (4,4);(3,3);(4,3), so the stored option is wrong.

Question 13

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?

Accepted Answer

131, 111, 90. In a max heap, the largest element is at the root, followed by its children, which must also be larger than their own children. After heapifying the given array, the largest value, 131, becomes the root, followed by 111 and 90, which are the next largest elements, thus forming the first three elements of the heap.

Question 14

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

Accepted Answer

T(n) = Θ(n log log n). The recurrence relation indicates that the function T(n) grows based on the size of n and its logarithmic factors, specifically due to the repeated halving of n (as seen in T(√n)). This leads to a complexity that is proportional to n multiplied by the logarithm of the logarithm of n, hence T(n) = Θ(n log log n) is the correct characterization.

Question 15

Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of k is

Accepted Answer

53. In a binary min-heap, the maximum element can only be found in the leaf nodes, which are located in the second half of the array representation. With 105 elements, the leaf nodes start from index 53 to 105, giving us a total of 53 possible indices for the maximum element.

Question 16

The symbol → indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

Accepted Answer

(X → Y and Y → Z) implies X → Z. This statement is an application of the transitive property of functional dependencies, which states that if one attribute functionally determines a second, and that second attribute functionally determines a third, then the first attribute must also functionally determine the third.

Question 17

Consider the following read-write schedule S over three transactions T1, T2, and T3, where the subscripts in the schedule indicate transaction IDs: S: r1(z); w1(z); r2(x); r3(y); w3(y); r2(y); w2(x); w2(y); Which of the following transaction schedules is/are conflict equivalent to S ?

Accepted Answer

T1 T3 T2. The correct option T1 T3 T2 maintains the order of conflicting operations from the original schedule S, ensuring that the read and write operations on the same data items occur in the same sequence, thus preserving the consistency of the transactions.

Question 18

Consider a Boolean expression given by F(X,Y,Z) = Σ(3,5,6,7). Which of the following statements is/are CORRECT ?

Accepted Answer

F(X,Y,Z) = XY + YZ + XZ. The correct option is right because the expression F(X,Y,Z) = XY + YZ + XZ accurately represents the minterms 3, 5, 6, and 7 in the given Boolean function, confirming its equivalence to the specified sum of products.

Question 19

Consider the following C function definition.

int f(int x, int y) {
 for (int i=0; i<y; i++) {
 x=x+x+y;
 }
 return x;
}

Which of the following statements is/are TRUE about the above function?

Accepted Answer

If the inputs are x=20, y=20, then the return value is greater than 2²⁰. The function doubles the value of x and adds y in each iteration of the loop, leading to exponential growth. For x=20 and y=20, the number of iterations (20) allows the value of x to increase significantly, resulting in a return value that exceeds 2²⁰.

Question 20

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let G be any graph with n vertices and chromatic number k. Which of the following statements is/are always TRUE?

Accepted Answer

G contains an independent set of size at least n/k. A graph with chromatic number k can be colored using k colors, which implies that there must be at least one independent set of vertices that can be colored with the same color. By the pigeonhole principle, if there are n vertices and k colors, at least one color must be assigned to at least n/k vertices, ensuring the existence of an independent set of that size.

Question 21

Consider two set-associative cache memory architectures: WBC, which uses the write back policy, and WTC, which uses the write through policy. Both of them use the LRU (Least Recently Used) block replacement policy. The cache memory is connected to the main memory. Which of the following st

Accepted Answer

A write hit in WBC can modify the value of the dirty bit of a cache block. In a write-back cache (WBC), a write hit occurs when data is written to a cache block that is already present, allowing the dirty bit to be set or modified to indicate that the block has been changed but not yet written back to main memory.

Question 22

Consider a digital logic circuit consisting of three 2-to-1 multiplexers M1, M2, and M3 as shown below. X1 and X2 are inputs of M1. X3 and X4 are inputs of M2. A, B, and C are select lines of M1, M2, and M3, respectively. For an instance of inputs X1=1, X2=1, X3=0, and X4=0, the number of

Accepted Answer

4. The output Y=1 can occur when M1 selects either X1 or X2 (both are 1), and M2 selects either X3 or X4 (both are 0). Since M3's selection does not affect the output when M2 outputs 0, there are 4 combinations of A, B, and C that can yield Y=1.

Question 23

Consider sending an IP datagram of size 1420 bytes (including 20 bytes of IP header) from a sender to a receiver over a path of two links with a router between them. The first link (sender to router) has an MTU (Maximum Transmission Unit) size of 542 bytes, while the second link (router to

Accepted Answer

6. Data = 1420-20 = 1400 bytes. Link1 MTU 542 gives payload floor(522/8)*8 = 520, yielding data fragments 520,520,360. Link2 MTU 360 gives payload 336, so each splits: 520->336+184, 520->336+184, 360->336+24, for 6 fragments delivered. Stored '9' is wrong; correct is 6.

GATE Technical: Computer Science and Information Technology Set 1 (CS1) questions with solutions

Questions