Question 1

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processo

Accepted Answer

28 bits and 0 bits. Block size 16 bytes needs 4 offset bits; a fully associative cache has zero index bits since any block maps anywhere. Tag = 32 - 4 - 0 = 28 bits. So 28 bits tag and 0 bits index, which is the last option, not '24 and 0'.

Question 2

Which one of the following kinds of derivation is used by LR parsers?

Accepted Answer

Rightmost in reverse. LR parsers utilize a rightmost in reverse derivation because they construct the parse tree from the leaves up to the root, effectively processing the input from the end to the beginning, which aligns with the rightmost derivation approach.

Question 3

In 16-bit 2’s complement representation, the decimal number −28 is:

Accepted Answer

1111 1111 1110 0100. The correct option represents the 2's complement of the positive value 28, which is calculated by first converting 28 to binary (0000 0000 0001 1100), then inverting the bits and adding 1, resulting in 1111 1111 1110 0100 for -28 in 16-bit representation.

Question 4

Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|.
I. |A| = n2^(n−1)
II. |A| = ∑(k=1 to n) k C(n,k)
Which of the above statements is/are TRUE?

Accepted Answer

Both I and II. Both statements are true because they represent different ways to count the number of pairs (x, X) where x is an element of the subset X of U. The first statement counts all possible subsets and their elements, while the second uses combinatorial counting to arrive at the same total.

Question 5

Which one of the following is NOT a valid identity?

Accepted Answer

(x + y) ⊕ z = x ⊕ (y + z). Option B is incorrect because it misapplies the properties of the XOR operation (⊕) and addition (+). Unlike addition, XOR does not distribute over addition, making this identity invalid.

Question 6

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

Accepted Answer

{ww^R | w ∈ L}. The language {ww^R | w ∈ L} is not regular because it requires matching a string with its reverse, which cannot be done by a finite automaton, as it lacks the memory to store an arbitrary length of 'w' for comparison.

Question 7

Let X be a square matrix. Consider the following two statements on X.
I. X is invertible.
II. Determinant of X is non-zero.
Which one of the following is TRUE?

Accepted Answer

I and II are equivalent statements.. A square matrix is invertible if and only if its determinant is non-zero, meaning that both statements are true simultaneously or false simultaneously. Therefore, I and II are equivalent statements.

Question 8

Let G be an arbitrary group. Consider the following relations on G:
R1: ∀a, b ∈ G, a R1 b if and only if ∃g ∈ G such that a = g^−1bg
R2: ∀a, b ∈ G, a R2 b if and only if a = b^−1
Which of the above is/are equivalence relation/relations?

Accepted Answer

R1 only. R1 (a = g^-1 b g) is conjugacy, which is reflexive, symmetric, and transitive in any group, so it is an equivalence relation. R2 (a = b^-1) fails reflexivity since a = a^-1 requires a^2 = e, not true for all a. Only R1, index 1, not 'R1 and R2'.

Question 9

Consider the following two statements about database transaction schedules:
I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas' Write Rule can generate view serializable s

Accepted Answer

Both I and II. Both statements are true because the strict two-phase locking protocol ensures that transactions are executed in a way that maintains conflict serializability and recoverability. Additionally, the timestamp-ordering concurrency control with Thomas' Write Rule allows for the generation of view serializable schedules that may not adhere to conflict serializability due to its handling of write operations.

Question 10

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

Accepted Answer

(n - 1)! / 2. In a complete graph with n vertices, each Hamiltonian cycle can be represented by fixing one vertex and arranging the remaining (n-1) vertices in a cycle. Since each cycle can be traversed in two directions (clockwise and counterclockwise), we divide by 2, resulting in (n - 1)! / 2 distinct Hamiltonian cycles.

Question 11

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

Accepted Answer

Non-leaf nodes have pointers to data records. Non-leaf nodes in a B+ tree do not contain pointers to actual data records; instead, they only store keys and pointers to child nodes, which helps in navigating the tree structure. This characteristic distinguishes B+ trees from other tree structures, ensuring efficient searching and maintaining balance.

Question 12

Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

Accepted Answer

SMTP, POP3. SMTP (Simple Mail Transfer Protocol) is used to send emails from a client to a server, while POP3 (Post Office Protocol version 3) is used to retrieve emails from the server to the client, making this pair suitable for the specified order of operations.

Question 13

Consider the following C function.

void convert(int n){
 if(n<0)
 printf("%d",n);
 else{
 convert(n/2);
 printf("%d",n%2);
 }
}

Which one of the following will happen when the function convert is called with any positive integer n as argument?

Accepted Answer

It will not print anything and will not terminate. For any positive n the recursion reaches convert(0), which takes the else branch and calls convert(0/2)=convert(0) endlessly, never returning, so no printf in the else branch ever executes. The function prints nothing and does not terminate (index 3), not the stored index 2.

Question 14

Consider three machines M, N, and P with IP addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the following is true?

Accepted Answer

Only N and P belong to the same subnet. With mask 255.255.255.252 (/30) the network is the address with its last two bits cleared. .2 gives network .0, while .5 and .6 both give network .4. So M is alone in subnet .0 and N and P share subnet .4: only N and P belong to the same subnet (index 2).

Question 15

Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?

Accepted Answer

X sends an ARP request packet with broadcast MAC address in its local subnet. The correct option is effective because ARP (Address Resolution Protocol) uses a broadcast MAC address to reach all devices on the local subnet, allowing machine X to request the MAC address of machine Y, which will respond with its MAC address.

Question 16

Consider the following sets:
S1. Set of all recursively enumerable languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet {0,1}
S4. Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are unco

Accepted Answer

S3 and S4. S3, the set of all languages over the alphabet {0,1}, is uncountable because it includes all possible subsets of strings formed from that alphabet, which corresponds to the power set of the natural numbers. S4, the set of all non-regular languages, is also uncountable since it contains infinitely many languages that cannot be described by finite automata, further contributing to the uncountability.

Question 17

Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let X1, X2, X3, X4, X5, and X6 be the placeholders for the non-terminals D, T, L or L1 in the following table:

Production rule | Semantic action
D → T L | X1.type = X2.type
T → in

Accepted Answer

X1 = L, X2 = T, X3 = L1, X4 = L. The correct option is right because it accurately reflects the relationships defined in the grammar: the type of the declaration (D) is derived from the type of the type (T) and the list (L), ensuring that the type of the entire declaration matches the type of its components.

Question 18

Let G be any connected, weighted, undirected graph.

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above two stateme

Accepted Answer

Both I and II. Both statements are true because the uniqueness of the minimum spanning tree is guaranteed by the absence of equal edge weights in the first case, and by the presence of a unique minimum-weight edge crossing every cut in the second case. These conditions ensure that there is only one way to construct the minimum spanning tree.

Question 19

Consider the following snapshot of a system running n concurrent processes. Process i is holding X_i instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for up to Y_i additional instances of R while ho

Accepted Answer

Xₚ + X_q < Min {Yₖ | 1 ≤ k ≤ n, k ≠ p, k ≠ q}. This condition ensures that the total resources held by processes p and q are less than the minimum resources that any other process can request, effectively preventing those processes from obtaining the resources they need to proceed, thus blocking their execution.

Question 20

Consider the following statements:
I. The smallest element in a max-heap is always at a leaf node
II. The second largest element in a max-heap is always a child of the root node
III. A max-heap can be constructed from a binary search tree in Θ(n) time
IV. A binary search tree can be constr

Accepted Answer

I, II and III. In a max-heap the smallest element is at a leaf (I true) and the second largest must be a child of the root (II true). Building a max-heap from any array (including a BST's nodes) is Theta(n) (III true). Building a BST from a max-heap in Theta(n) would sort in linear time, which is impossible (IV false). So I, II and III, index 0, not the stored option.

Question 21

Consider the following relations P(X,Y,Z), Q(X,Y,T) and R(Y,V).

P
X Y Z
X1 Y1 Z1
X1 Y1 Z2
X2 Y2 Z2
X2 Y4 Z4

Q
X Y T
X2 Y1 2
X1 Y2 5
X1 Y1 6
X3 Y3 1

R
Y V
Y1 V1
Y3 V2
Y2 V3
Y2 V2

How many tuples will be returned by the following relational algebra query?

πX (σ(P.Y=R.Y ∧ R.V=V2)(P × R))

Accepted Answer

1. The query first retrieves tuples from the Cartesian product of P and R where P.Y matches R.Y and R.V equals V2, resulting in one matching tuple. Then, it excludes tuples from the Cartesian product of Q and R where Q.Y matches R.Y and Q.T is greater than 2, which yields no tuples to exclude. Thus, the final result contains only one tuple.

GATE Technical: Computer Science and Information Technology Set-2 questions with solutions

Questions