Question 1

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Accepted Answer

(ab*b)*ab* + (ba*a)*ba*. This regular expression captures the sequences generated by the finite automaton by allowing for repetitions of 'ab*b' and 'ba*a', followed by additional 'ab*' or 'ba*' patterns, thus accurately representing the transitions and states of the automaton.

Question 2

Which one of the following statements is TRUE?

Accepted Answer

LR(1) parsing is sufficient for deterministic context-free languages.. LR(1) parsing is designed to handle deterministic context-free languages by using a lookahead symbol to make parsing decisions, ensuring that it can resolve ambiguities and conflicts that may arise in the parsing process.

Question 3

In a relational data model, which one of the following statements is TRUE?

Accepted Answer

A relation with only two attributes is always in BCNF.. A relation with only two attributes can only have a maximum of one functional dependency, which means it satisfies the conditions for Boyce-Codd Normal Form (BCNF) by default, as there are no non-trivial functional dependencies that violate the BCNF rules.

Question 4

Consider the problem of reversing a singly linked list. To take an example, given the linked list below, head -> a -> b -> c -> d -> e -> NULL, the reversed linked list should look like head -> e -> d -> c -> b -> a -> NULL. Which one of the following statements is TRUE about the time comp

Accepted Answer

The best algorithm for the problem takes θ(n) time in the worst case.. Reversing a singly linked list requires visiting each node exactly once to change the pointers, which results in a linear time complexity of θ(n). This is efficient and feasible within O(1) space, as it only requires a few additional pointers for the reversal process.

Question 5

Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?

Accepted Answer

n / m. The expected number of keys in a slot is calculated by dividing the total number of keys (n) by the number of slots (m). Since the hashing functions distribute keys uniformly across the slots, this results in an average of n/m keys per slot.

Question 6

Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

Accepted Answer

DMA based I/O transfer. DMA (Direct Memory Access) allows peripherals to transfer data directly to main memory without involving the CPU, which maximizes throughput by freeing up the processor to perform other tasks while the data transfer occurs.

Question 7

Let R1 and R2 be two 4-bit registers that store numbers in 2’s complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

Accepted Answer

R1 = 1100 and R2 = 1010. In option B, 1100 (-4) + 1010 (-6) = -10, outside the 4-bit range [-8,7]; the binary sum 10110 truncates to 0110 (+6), a sign flip from two negatives, which is overflow. The other options stay within range, so B (R1=1100, R2=1010) is the overflow case.

Question 8

Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

T1: while(true){ wait(S3

Accepted Answer

S1 = 1; S2 = 0; S3 = 0. The correct initialization S1 = 1, S2 = 0, S3 = 0 allows T1 to execute first, producing 'C' and signaling T2. T2 can then execute and print 'B', signaling T3, which can subsequently print 'A'. This cycle continues, producing the desired sequence BCABCABCA...

Question 9

What is printed by the following ANSI C program?

#include<stdio.h>

int main(int argc, char *argv[])
{
 int x = 1, z[2] = {10, 11};
 int *p = NULL;
 p = &x;
 *p = 10;
 p = &z[1];
 *(&z[0] + 1) += 3;
 printf("%d, %d, %d
", x, z[0], z[1]);
 return 0;
}

Accepted Answer

10, 10, 14. The program modifies the value of 'x' through the pointer 'p', setting it to 10. It then updates 'z[1]' by adding 3 to 'z[0]', which is 10, resulting in 'z[1]' becoming 14. Therefore, the final output is '10, 10, 14'.

Question 10

Which of the following statements is/are TRUE?

Accepted Answer

If a language L and its complement ̅L are both recursively enumerable, then L must be recursive.. This statement is true because if both a language and its complement are recursively enumerable, it implies that there exists a Turing machine that can enumerate the strings in both the language and its complement, allowing us to decide membership in the language, thus making it recursive.

Question 11

Consider the following three relations in a relational database.
Employee(eId, Name), Brand(bId, bName), Own(eId, bId)
Which of the following relational algebra expressions return the set of eIds who own all the brands?

Accepted Answer

Π_eId (Π_eId,bId (Own) / Π_bId (Brand)). This expression correctly identifies eIds that own all brands by performing a division operation, which effectively filters out eIds that do not have ownership of every brand listed in the Brand relation.

Question 12

Which of the following statements is/are TRUE with respect to deadlocks?

Accepted Answer

Circular wait is a necessary condition for the formation of deadlock.. Circular wait is indeed a necessary condition for deadlock because it describes a situation where a set of processes are each waiting for a resource held by another process in the set, creating a cycle that prevents any of them from proceeding.

Question 13

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

Accepted Answer

A³ divided by 6. The number of 3-cycles in an undirected graph can be found by calculating the trace of the cube of the adjacency matrix, A³, which counts each cycle three times (once for each vertex in the cycle). Therefore, to get the correct count of unique 3-cycles, we divide the trace of A³ by 6, accounting for the overcounting.

Question 14

Let R_i(z) and W_i(z) denote read and write operations on a data element z by a transaction T_i, respectively. Consider the schedule S with four transactions.
S: R4(x)R2(x)R3(x)R1(y)W1(y)W2(x)W3(y)W4(y)
Which one of the following serial schedules is conflict equivalent to S?

Accepted Answer

T1 → T4 → T3 → T2. The conflict edges from S are T1->T3, T1->T4, T3->T2, T3->T4, T4->T2, whose only topological order is T1->T3->T4->T2. Therefore the conflict-equivalent serial schedule is T1->T3->T4->T2, not T3->T1->T4->T2.

Question 15

Consider a digital display system (DDS) shown in the figure that displays the contents of register X. A 16-bit code word is used to load a word in X, either from S or from R. S is a 1024-word memory segment and R is a 32-word register file. Based on the value of mode bit M, T selects an in

Accepted Answer

P is 10:2¹⁰ decoder; Q is 5:2⁵ decoder; T is 2:1 multiplexer. The correct option describes P as a decoder that converts a 10-bit input to one of 1024 outputs, which is necessary for addressing the 1024-word memory segment S. Q is a decoder that converts a 5-bit input to one of 32 outputs, suitable for addressing the 32-word register file R. T functions as a multiplexer that selects between the outputs of P and Q based on the mode bit M, allowing the system to load the appropriate word into register X.

Question 16

What is printed by the following ANSI C program?

#include<stdio.h>
int main(int argc, char *argv[])
{
 int a[3][3][3] =
 {{1, 2, 3, 4, 5, 6, 7, 8, 9},
 {10, 11, 12, 13, 14, 15, 16, 17, 18},
 {19, 20, 21, 22, 23, 24, 25, 26, 27}};
 int i = 0, j = 0, k = 0;
 for( i = 0; i < 3; i++){
 for(k

Accepted Answer

1 2 3
10 11 12
19 20 21. The program initializes a 3D array and uses nested loops to print the elements. The outer loop iterates over the first dimension, while the inner loop accesses the second dimension with a fixed index of 'j' (which is always 0), resulting in the first slice of the array being printed for each iteration.

Question 17

Consider the following languages:
L1 = {ww | w ∈ {a,b}*}
L2 = {a^m bⁿ c^m | m,n ≥ 0}
L3 = {a^m bⁿ cⁿ | m,n ≥ 0}
Which of the following statements is/are FALSE?

Accepted Answer

Neither L1 nor L2 is context-free.. The correct option states that neither L1 nor L2 is context-free, which is true because L1 requires matching strings that cannot be generated by a context-free grammar, and L2 requires a dependency between the number of 'a's and 'c's that also cannot be captured by context-free grammars.

Question 18

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

Accepted Answer

Suppose S ⊂ V such that S ≠ ∅ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V S. Such an edge will always be part of any minimum spanning tree of G.. This statement is true due to the cut property of minimum spanning trees, which asserts that for any cut in the graph, the minimum weight edge crossing the cut must be included in any minimum spanning tree to ensure minimal total weight.

Question 19

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?

(A) The chromatic number of the graph is 3.
(B) The graph has a Hamiltonian path.
(C) The following graph is isomorphic to the Peterson graph.
(D) The size of the la

Accepted Answer

(A) The chromatic number of the graph is 3.. The chromatic number of the Petersen graph is indeed 3 because it requires three colors to color the vertices such that no two adjacent vertices share the same color, which is a characteristic of this specific graph.

Question 20

Consider the following recurrence:

f(1) = 1;

f(2n) = 2f(n) - 1, for n ≥ 1;

f(2n + 1) = 2f(n) + 1, for n ≥ 1.

Then, which of the following statements is/are TRUE?

Accepted Answer

f(2ⁿ − 1) = 2ⁿ − 1. The statement is true because when substituting n with 2ⁿ - 1 into the recurrence relation, it can be shown through induction that f(2ⁿ - 1) consistently evaluates to 2ⁿ - 1, confirming the pattern established by the recurrence.

Question 21

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

Accepted Answer

The diagonal entries of A² are the degrees of the vertices of the graph.. The diagonal entries of A² represent the sum of the products of corresponding entries in the rows and columns of the adjacency matrix, which counts the number of edges connected to each vertex, thus giving the degree of each vertex.

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

Questions