Question 1

Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps

Accepted Answer

(iii), (i), (ii). The correct sequence is (iii), (i), (ii) because the processor must first complete the current instruction to ensure data integrity, then save the program counter to remember where to return after handling the interrupt, and finally load the program counter with the ISR's address to begin executing the interrupt service routine.

Question 2

Which ONE of the following statements is FALSE regarding the symbol table?

Accepted Answer

Symbol table is not required after the parsing phase.. The symbol table is essential during the semantic analysis and code generation phases, as it maintains information about variable types and scopes, making it necessary beyond just parsing.

Question 3

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

Accepted Answer

Register assignment to variables. Register assignment to variables relies on live variable analysis to determine which variables are actively needed at a given point in the program, allowing the compiler to allocate registers more efficiently and minimize unnecessary memory access.

Question 4

Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?

Accepted Answer

2²¹. Logical address is 32 bits and page size is 2048=2^11 bytes, so the page-number field is 32-11=21 bits. The page table has at most 2^21 entries, not 2^22.

Question 5

A schedule of three database transactions T1, T2, and T3 is shown. Ri(A) and Wi(A) denote read and write of data item A by transaction Ti, i = 1,2,3. The transaction T1 aborts at the end. Which other transaction(s) will be required to be rolled back?

R1(X) W1(Y) R2(X) R2(Y) R3(Y) ABORT(T1

Accepted Answer

Both T2 and T3. T1 writes Y then aborts. T2 reads Y (R2(Y)) after W1(Y), a dirty read, so T2 must roll back. T3 also reads Y (R3(Y)) which carries T1's uncommitted value, so T3 must roll back too. Both T2 and T3 are rolled back.

Question 6

Identify the ONE CORRECT matching between the OSI layers and their corresponding functionalities as shown.

OSI Layers — Functionalities
(a) Network layer — (I) Packet routing
(b) Transport layer — (II) Framing and error handling
(c) Datalink layer — (III) Host to host communication

Accepted Answer

(a)-(I), (b)-(III), (c)-(II). The correct option matches the functionalities accurately: the Network layer is responsible for packet routing (I), the Transport layer facilitates host-to-host communication (III), and the Datalink layer handles framing and error detection (II). This alignment reflects the specific roles each layer plays in the OSI model.

Question 7

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d1(u,v) and d2(u,v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, and v?

Accepted Answer

d1(u,v) ≤ d2(u,v). The shortest path distance in the original graph G, denoted as d1(u,v), can be equal to or less than the distance in the minimum spanning tree T, denoted as d2(u,v), because T may not include all edges of G and thus cannot provide a shorter path than the shortest path available in G.

Question 8

Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G are described as:

S → aaB | Abb
A → a | aA
B → b | bB

Which ONE of the languages L(G) is accepted by G?

Accepted Answer

L(G) = {a² bⁿ | n ≥ 1} ∪ {aⁿ b² | n ≥ 1}. The correct option describes the language generated by the grammar, where the productions allow for the generation of strings with two 'a's followed by one or more 'b's, or any number of 'a's followed by exactly two 'b's, thus matching the specified patterns.

Question 9

Let X be a 3-variable Boolean function that produces output as ‘1’ when at least two of the input variables are ‘1’. Which of the following statement(s) is/are CORRECT, where a,b,c,d,e are Boolean variables? (A) X(a,b,X(c,d,e)) = X(X(a,b,c),d,e) (B) X(a,b,X(a,b,c)) = X(a,b,c) (C) X(a,b,X(a

Accepted Answer

(B). Option (B) is correct because the function X produces a '1' when at least two inputs are '1'. In this case, if a and b are both '1', adding another '1' (from c) does not change the output, confirming that X(a,b,X(a,b,c)) equals X(a,b,c).

Question 10

The number −6 can be represented as 1010 in 4-bit 2’s complement representation. Which of the following is/are CORRECT 2’s complement representation(s) of −6?

Accepted Answer

11111010 in 8-bits. The correct option, 11111010 in 8-bits, accurately represents -6 in 2's complement form, as it is derived by inverting the binary representation of +6 (00000110) and adding 1, resulting in 11111010.

Question 11

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?

Accepted Answer

An inorder traversal will always produce a sorted sequence of elements.. In a binary search tree, the left subtree contains only nodes with values less than the parent node, and the right subtree contains only nodes with values greater than the parent node. Therefore, an inorder traversal, which visits the left subtree, the parent node, and then the right subtree, will always yield the elements in sorted order.

Question 12

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

Accepted Answer

Every DFA that accepts L has > 2ⁿ states.. This statement is false because while a DFA can have up to 2ⁿ states in the worst case when converting from an NFA with n states, it is not guaranteed that every DFA accepting the same language must exceed that number of states; some DFAs may have fewer states.

Question 13

#include <stdio.h>
void foo(int *p, int x){
 *p=x;
}

int main(){
 int *z;
 int a = 20, b = 25;
 z = &a;
 foo(z,b);
 printf("%d",a);
 return 0;
}

The output of the given C program is _________. (A answer in integer)

Accepted Answer

25. The function 'foo' takes a pointer and an integer, assigning the integer value to the location pointed to by the pointer. Since 'z' points to 'a' and 'foo' sets '*p' (which is 'a') to 'b' (25), the value of 'a' is updated to 25, resulting in the output.

Question 14

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory

Accepted Answer

6 × 2¹⁰. To determine the number of bits required to store all the tag values in a direct-mapped cache, we first calculate the number of cache lines, which is the cache size divided by the block size. With 16K bytes of cache and a block size of 16 bytes, there are 1024 cache lines. The main memory has 1M bytes, which corresponds to 20 bits for addressing. The index requires 10 bits (since 1024 = 2¹⁰), leaving 10 bits for the tag (20 total bits - 10 index bits). Thus, the total number of bits for all tag values is 1024 lines multiplied by 10 bits, resulting in 6 × 2¹⁰ bits.

Question 15

A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided a

Accepted Answer

9.00. At t=0 M1 takes its top-priority P1 (0-20) and M2 takes its top-priority P2 (0-16). At t=16 M2 frees and takes P3 (16-41); at t=20 M1 frees and takes P4 (20-30). Waiting times are P1=0, P2=0, P3=16, P4=20, average = 36/4 = 9.00 ms.

Question 16

Consider two relations describing teams and players in a sports league:
• teams(tid, tname): tid, tname are team-id and team-name, respectively
• players(pid, pname, tid): pid, pname, and tid denote player-id, player-name and the team-id of the player, respectively
Which ONE of the followi

Accepted Answer

{ p.pname | p ∈ players ∧ ∃t (t ∈ teams ∧ p.tid = t.tid ∧ t.tname = 'MI') }. This option correctly identifies players from the 'players' relation and checks for the existence of a corresponding team in the 'teams' relation that matches the specified team name 'MI', ensuring that only players from that team are selected.

Question 17

Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value of d(u,v), u,v ∈ V such that u ≠ v, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given o

Accepted Answer

The height of T is at least 15.. The height of the breadth-first search tree T must be at least 15 because the maximum distance between any two vertices in the graph is 30, and in a BFS tree, the height represents the longest path from the root to any leaf. Since the maximum distance is 30, the tree must span at least half of that distance to connect vertices, ensuring a minimum height of 15.

Question 18

Consider the following two languages over the alphabet {a, b, c}, where m and n are natural numbers.

L1 = {a^m b^m c^(m+n) | m, n ≥ 1}
L2 = {a^m bⁿ c^(m+n) | m, n ≥ 1}

Which ONE of the following statements is CORRECT?

Accepted Answer

Both L1 and L2 are context-free languages.. Both L1 and L2 can be generated by context-free grammars, as they can be expressed with rules that allow for the balanced counting of 'a's and 'b's while accommodating the unrestricted number of 'c's, which can be derived from the context-free language properties.

Question 19

Which of the following statement(s) is/are TRUE while computing First and Follow during top down parsing by a compiler?

Accepted Answer

If there is any input right end marker, it will be added to Follow(S), where S is the start symbol.. The correct option is true because the Follow set of a non-terminal includes the end-of-input marker to indicate that the parsing can successfully complete when reaching the start symbol, allowing the parser to recognize the end of the input.

Question 20

Which of the following predicate logic formulae/formulae is/are CORRECT representation(s) of the statement: “Everyone has exactly one mother”? The meanings of the predicates used are: mother(y, x): y is the mother of x; noteq(x, y): x and y are not equal

Accepted Answer

∀x∃y[mother(y,x) ∧ ¬∃z(noteq(z,y) ∧ mother(z,x))]. The correct option accurately captures the idea that for every individual x, there exists a unique mother y such that no other individual z can also be a mother of x, ensuring that y is the only mother.

Question 21

Suppose a 5-bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is 0.01. Flipping of each bit is independent of one another. The probability that the message is delivered error-free to

Accepted Answer

0.9509900499. Each bit is correct with probability 0.99 and bits are independent, so the message is error-free with probability 0.99^5 = 0.95099. The stored answer 0.96059601 is 0.99^4 (only 4 bits) and is wrong; the correct value is option 0.

Question 22

Consider the following C program:

#include <stdio.h>
int gate (int n) {
 int d, t, newnum, turn;
 newnum = turn = 0; t=1;
 while (n>=t) t *= 10;
 t /= 10;
 while (t>0) {
 d = n/t;
 n = n%t;
 t /= 10;
 if (turn) newnum = 10*newnum + d;
 turn = (turn + 1) % 2;
 }
 return newnum;
}
int main

Accepted Answer

The value printed by the given C program is ________ (An answer in integer). The function 'gate' processes the digits of the input number by alternating between skipping and including digits, effectively reversing the order of every second digit starting from the least significant one. For the input 14362, it retains the digits 4, 3, and 2, resulting in the output 42.

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

Questions