CS and IT Gate 2017 Set-2 Questions with Answer

Given:
L₁ and L₂ are context-free languages (CFLs).
R is a regular language.
To find:
Which of the given statements are correct.
Solution:
Let me check statement I first.
Statement I says: L₁ ∪ L₂ is context-free.
I know that context-free languages are closed under union, so this statement is true.
Now let me check statement II.
Statement II says: L₁' is context-free.
CFLs are not closed under complementation, so L₁' is not necessarily context-free.
Thus, statement II is false.
Now checking statement III.
Statement III says: L₁ - R is context-free.
I can rewrite set difference as: L₁ - R = L₁ ∩ R'
Since regular languages are closed under complement, R' is also a regular language.
Also, the intersection of a CFL and a regular language is always a CFL.
So, L₁ ∩ R' is context-free, which means statement III is true.
Now checking statement IV.
Statement IV says: L₁ ∩ L₂ is context-free.
CFLs are not closed under intersection, so this is not necessarily context-free.
Thus, statement IV is false.
So only statements I and III are correct.
Answer: (B) I and III only

Given:
Variables x, y, q, and r are of type unsigned int.
Code fragment:
while(r >= y)
{
  r = r - y;
  q = q + 1;
}
To find:
The initial condition on the variables before the loop starts to ensure termination with x == (y × q + r).
Solution:
Let me trace the values inside the loop first.
In each iteration of the loop, r decreases by y and q increases by 1.
Let q₀ and r₀ be the values before entering the loop.
After k iterations, the values become:
q = q₀ + k
r = r₀ - k × y
Now let me evaluate the expression y × q + r:
y × q + r = y × (q₀ + k) + (r₀ - k × y)
Multiplying and opening the brackets gives:
y × q + r = y × q₀ + k × y + r₀ - k × y = y × q₀ + r₀
So the quantity (y × q + r) is a loop invariant, which always stays equal to the initial value (y × q₀ + r₀).
We want the final state to satisfy:
x == y × q + r
Therefore, the initial values must satisfy:
x = y × q₀ + r₀
If we set q₀ = 0, then we immediately get:
r₀ = x
Now let me check loop termination.
If y = 0, r >= 0 will always be true since r is unsigned int, and r - 0 stays unchanged, so the loop will never terminate.
Thus, to ensure termination, we must have:
y > 0
Combining these conditions, before execution we must have:
( q == 0 ) && ( r == x ) && ( y > 0 )
Answer:
(C) ( q == 0 ) && ( r == x ) && ( y > 0 )

Given:
The C function printxy(int x, int y) and the function call printxy(1, 1).
To find:
The output printed by printxy(1, 1).
Solution:
Let me trace the function step-by-step with the initial arguments x = 1 and y = 1.
First, the function sets x = 0, so the value of x is updated to 0.
Next, the pointer ptr is assigned the address of x, so ptr = &x.
Now, y is assigned the value pointed to by ptr, which means y = *ptr = x = 0.
So, at this point, y becomes 0.
Next, the statement *ptr = 1 modifies the memory location pointed to by ptr.
Since ptr points to x, this directly changes x to 1.
Notice that y is a separate variable, so its value remains 0.
Finally, the printf("%d,%d", x, y) statement executes.
Substituting the current values of x and y, it prints: 1,0.
Answer:
(C) 1,0

Given:
Three statements about parsing power:
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than canonical LR.
To find:
Which of the statements is/are correct.
Solution:
Let me recall the hierarchy of power for bottom-up LR parsers.
The parsing power increases as follows:
LR(0) < SLR(1) < LALR(1) < CLR(1)<br>This means every SLR(1) grammar is an LALR(1) grammar, and every LALR(1) grammar is a CLR(1) grammar.
So CLR(1) is the most powerful among them, followed by LALR(1), then SLR(1), and LR(0) is the least powerful.
Now let's check statement I:
"Canonical LR is more powerful than SLR."
Since CLR(1) > SLR(1), this statement is correct.
Now checking statement II:
"SLR is more powerful than LALR."
Since LALR(1) is actually more powerful than SLR(1), this statement is false.
Now checking statement III:
"SLR is more powerful than canonical LR."
CLR(1) is more powerful than SLR(1), so this statement is also false.
Therefore, only statement I is correct.
Answer: (A) I only

Let me recall the standard order of phases in a compiler and their respective inputs.
First, the Lexical analyser takes the source code as a stream of characters and produces tokens.
So, Character Stream is the input to the Lexical analyser, which gives Q → (iv).
Next, the Syntax analyser takes the stream of tokens generated by the lexical analyser and builds a parse tree or syntax tree.
So, Token stream is the input to the Syntax analyser, which gives S → (ii).
Next, the Semantic analyser takes the syntax tree to check for semantic consistency and type checking.
So, Syntax Tree is the input to the Semantic analyser, which gives P → (iii).
Finally, the Code generator takes the intermediate representation (IR) to generate target machine code.
So, Intermediate representation is the input to the Code generator, which gives R → (i).
Combining all the pairs, I get:
P → (iii), Q → (iv), R → (i), S → (ii).
Looking at the options, this directly matches Option C.
Answer:
(C) P -> (iii), Q -> (iv), R -> (i), S -> (ii)

Given:
A UDP socket on a Linux machine with the connect() system call.
Statement I: A connected UDP socket can be used to communicate with multiple peers simultaneously.
Statement II: A process can successfully call connect() again for an already connected UDP socket.
To find:
Which of the statements is/are correct.
Solution:
Let me check Statement I first.
When we call connect() on a UDP socket, the kernel binds the socket to a specific peer's IP address and port number.
After this, the socket only sends packets to and receives packets from that specific peer.
So, it cannot communicate with multiple peers at the same time.
That makes Statement I false.
Now let me look at Statement II.
In Linux socket programming, calling connect() on a UDP socket does not establish a 3-way handshake because UDP is connectionless.
It simply records the peer's IP and port in the socket structure.
A process can call connect() again on an already connected UDP socket to change the peer address to a new IP/port, or to disconnect the socket by passing AF_UNSPEC.
So, a process can definitely call connect() again successfully.
This means Statement II is true.
Hence, only Statement II is correct.
Answer:
(B) II only

Given:
Circular queue implemented using a singly linked list.
Two pointers: FRONT pointing to the front node, and REAR pointing to the rear node.
Both insertion (enqueue) and deletion (dequeue) operations must be done in O(1) time.
To find:
Which statement(s) among I and II is/are correct.
Solution:
Let me recall how a queue works with a singly linked list.
In a queue, elements are removed from FRONT and added at REAR.
For a singly linked list, we can easily delete the first node in O(1) if links point from FRONT towards REAR, because FRONT can simply move to FRONT->next.
If links were reversed (pointing from REAR towards FRONT), deleting the front node would require finding the node before FRONT to update its pointer, which takes O(n) time without a doubly linked list.
So the nodes must be linked in order: FRONT → next node → ... → REAR.
Now, to make it circular, the last node (REAR) must point back to the first node (FRONT).
Let me check the operations with REAR->next = FRONT:
For insertion of a new node at REAR:
newNode->next = REAR->next
REAR->next = newNode
REAR = newNode
This takes O(1) time.
For deletion of the front node:
temp = FRONT
FRONT = FRONT->next
REAR->next = FRONT
free(temp)
This also takes O(1) time.
So, the next pointer of the REAR node must point to the FRONT node.
This matches Statement II.
Statement I says the next pointer of the front node points to the rear node, which is not true in general for a queue of size greater than 2.
Hence, only statement II is correct.
Answer:
(B) II only

Given:
Items to match:
(P) static char var;
(Q) m = malloc(10); m = NULL;
(R) char *ptr[10];
(S) register int var1;
Descriptions:
(i) Sequence of memory locations to store addresses
(ii) A variable in data section of memory
(iii) Request to allocate a CPU register to store data
(iv) A lost memory which cannot be freed
To find:
The correct mapping from the given options.
Solution:
Let me analyze each item one by one.
First, look at item (P): static char var;
Static variables have lifetime throughout the program execution and are allocated in the data segment (data section) of memory.
So, P maps to (ii).
Now, look at item (Q): m = malloc(10); m = NULL;
Here, 10 bytes of memory are dynamically allocated on the heap, and then the only pointer pointing to it, m, is set to NULL without calling free(m).
This creates a memory leak, which is lost memory that can no longer be freed.
So, Q maps to (iv).
Next, look at item (R): char *ptr[10];
This is an array of 10 character pointers.
An array is a contiguous sequence of memory locations, and pointers store addresses.
So, it represents a sequence of memory locations to store addresses.
So, R maps to (i).
Finally, look at item (S): register int var1;
The register storage class specifier tells the compiler to place the variable in a CPU register instead of RAM, if possible.
It is a request to allocate a CPU register to store data.
So, S maps to (iii).
Putting it all together, I get P → (ii), Q → (iv), R → (i), S → (iii).
This matches option A.
Answer:
(A) P->(ii), Q->(iv), R->(i), S->(iii)

Given:
Algorithms: (P) Tower of Hanoi with n disks, (Q) Binary Search given n sorted numbers, (R) Heap sort of n numbers at the worst case, (S) Addition of two n×n matrices.
Time complexities: (i) θ(n²), (ii) θ(nlogn), (iii) θ(2ⁿ), (iv) θ(logn).
To find:
The correct matching between the algorithms and their time complexities.
Solution:
Let me check each algorithm one by one.
First, for (P) Tower of Hanoi with n disks:
The recurrence relation is T(n) = 2T(n - 1) + 1.
Solving this gives T(n) = 2ⁿ - 1, which is θ(2ⁿ).
So, P matches with (iii).
Now looking at (Q) Binary Search on n sorted numbers:
Each step divides the search space into half, giving recurrence T(n) = T(n/2) + c.
This solves to θ(logn).
So, Q matches with (iv).
Next, (R) Heap sort of n numbers in the worst case:
Building the heap takes O(n) time, and then we perform n delete-max operations, each taking O(logn).
So the overall time complexity in the worst case is θ(nlogn).
So, R matches with (ii).
Finally, (S) Addition of two n×n matrices:
Each matrix has n × n = n² elements, and adding them element-wise requires n² additions.
Therefore, the time complexity is θ(n²).
So, S matches with (i).
Putting them together, we get P -> (iii), Q -> (iv), R -> (ii), S -> (i).
This directly matches option C.
Answer:
(C)