Question 1

The truth table
X Y f(X,Y)
0 0 0
0 1 0
1 0 1
1 1 1
represents the Boolean function

Accepted Answer

X. The truth table shows that the output is true (1) only when X is true (1), regardless of the value of Y, which directly corresponds to the Boolean function represented by X.

Question 2

The decimal value 0.5 in IEEE single precision floating point representation has

Accepted Answer

fraction bits of 000...000 and exponent value of -1. In IEEE single precision, the value 0.5 is represented with a fraction (mantissa) of all zeros, as it is exactly 1/2, and an exponent of -1, which indicates the position of the binary point. This representation aligns with the format where the exponent is adjusted to reflect the normalized form of the number.

Question 3

A process executes the code
fork();
fork();
fork();
The total number of child processes created is

Accepted Answer

7. Each call to fork() creates a new process, and the number of processes doubles with each fork. After three fork calls, the total number of processes is 2³ - 1 (the original process is not counted as a child), resulting in 7 child processes.

Question 4

The protocol data unit (PDU) for the application layer in the Internet stack is

Accepted Answer

Message. The application layer's protocol data unit is referred to as a 'Message' because it encompasses the data that applications send and receive, which is distinct from the transport, network, and data link layers that use segments, datagrams, and frames respectively.

Question 5

Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then is L̄ also context-free?
3) If L is a regular language, then is L̄ also regular?
4) If L is a recursive language, then is L̄ also recursive?

Accepted Answer

3, 4. Options 3 and 4 are correct because the complement of a regular language is always regular, and the complement of a recursive language is also recursive, making both problems decidable. In contrast, the other options involve undecidable problems.

Question 6

A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² × y². Which one of the following statements is TRUE about ⊕?

Accepted Answer

Commutative but not associative. x(+)y = x^2*y^2 = y^2*x^2 so it is commutative. But (x(+)y)(+)z = (x^2 y^2)^2 z^2 = x^4 y^4 z^2 while x(+)(y(+)z) = x^2 (y^2 z^2)^2 = x^2 y^4 z^4, which differ, so it is not associative. Answer: commutative but not associative.

Question 7

The smallest integer that can be represented by an 8-bit number in 2's complement form is

Accepted Answer

-128. In 2's complement representation, the range of an 8-bit number is from -128 to 127. The smallest integer, which is represented by setting the most significant bit to 1 (indicating a negative number) and all other bits to 0, is -128.

Question 8

In the following truth table, V = 1 if and only if the input is valid.

Inputs | Outputs
D0 D1 D2 D3 | X0 X1 V
0 0 0 0 | x x 0
1 0 0 0 | 0 0 1
x 1 0 0 | 0 1 1
x x 1 0 | 1 0 1
x x x 1 | 1 1 1

What function does the truth table represent?

Accepted Answer

Priority encoder. The truth table represents a priority encoder because it outputs a binary representation of the highest-priority active input (D2, D1, D0) while indicating validity (V) when at least one input is active.

Question 9

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Accepted Answer

O(n). Selection sort requires a linear number of swaps, specifically one swap for each of the n elements in the worst case, making O(n) the tightest upper bound for the number of swaps.

Question 10

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

Accepted Answer

O(n). The time complexity for inserting an object into a binary search tree can be O(n) in the worst case, which occurs when the tree is unbalanced and resembles a linked list, requiring traversal of all n nodes.

Question 11

Consider the languages L1 = {ε} and L2 = {a}. Which one of the following represents L1 ∪ L2 ?

Accepted Answer

{ε, a}. The union of two sets includes all unique elements from both sets. Since L1 contains the empty string ε and L2 contains the string 'a', their union results in the set {ε, a}.

Question 12

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e. of type A → ε and A → a) to parse a string with n tokens?

Accepted Answer

n-1. In a bottom-up parsing process, each reduce move corresponds to reducing a production rule, and since the parser must eventually reduce the entire input string to the start symbol, the maximum number of reduce moves is one less than the number of tokens, which is n-1.

Question 13

A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every time unit and decides the next process to schedule. Which one of the following is TR

Accepted Answer

This algorithm is equivalent to the first-come-first-serve algorithm.. The algorithm assigns priorities based on waiting time, which means that processes are scheduled in the order they arrive without preemption, similar to first-come-first-serve. Since all processes start with the same priority and there are no I/O operations, the order of execution remains unchanged, making it equivalent to FCFS.

Question 14

Match the problem domains in GROUP I with the solution technologies in GROUP II.

GROUP I
(P) Service oriented computing
(Q) Heterogeneous communicating systems
(R) Information representation
(S) Process description

GROUP II
(1) Interoperability
(2) BPMN
(3) Publish-find-bind
(4) XML

Accepted Answer

P-3, Q-1, R-4, S-2. The correct option matches service-oriented computing with publish-find-bind (P-3), which facilitates service discovery; heterogeneous communicating systems with interoperability (Q-1), which ensures different systems can work together; information representation with XML (R-4), a standard for data encoding; and process description with BPMN (S-2), which is specifically designed for modeling business processes.

Question 15

The transport layer protocols used for real time multimedia, file transfer, DNS and email, respectively are

Accepted Answer

UDP, TCP, UDP and TCP. UDP is preferred for real-time multimedia due to its low latency, while TCP is used for file transfer and email because it ensures reliable delivery. DNS also uses UDP for quick query responses.

Question 16

Using public key cryptography, X adds a digital signature σ to message M, encrypts <M, σ>, and sends it to Y, where it is decrypted. Which one of the following sequences of keys is used for the operations?

Accepted Answer

Encryption: X's private key followed by Y's public key; Decryption: Y's private key followed by X's public key. The correct option involves X using their private key to create a digital signature, ensuring authenticity, and then encrypting the message with Y's public key, which ensures that only Y can decrypt it with their private key. This sequence maintains both the integrity of the message and the confidentiality of its content.

Question 17

Assume that source S and destination D are connected through two intermediate routers labeled R. Determine how many times each packet has to visit the network layer and the data link layer during a transmission from S to D.

Accepted Answer

Network layer - 4 times and Data link layer - 6 times. Each packet must pass through the network layer at the source, each router, and the destination, totaling four visits to the network layer. Additionally, the packet must traverse the data link layer at the source, each router, and the destination, resulting in six visits to the data link layer.

Question 18

An index is clustered, if

Accepted Answer

the data records of the file are organized in the same order as the data entries of the index.. A clustered index organizes the actual data records in the database according to the order of the index entries, allowing for efficient data retrieval based on the indexed fields.

Question 19

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P oper

Accepted Answer

X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d). The correct option avoids circular wait conditions by ensuring that each process acquires semaphores in a consistent order. By having X acquire b before a, Y acquire b before c, and Z acquire a before c, it prevents any possibility of deadlock since no process will hold a semaphore while waiting for another that is held by a different process.

Question 20

Which of the following statements is/are FALSE ?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection

Accepted Answer

2 only. Statement 2 is false because Turing recognizable languages are not closed under complementation; while they are closed under union, the complement of a recognizable language may not be recognizable.

Question 21

Which of the following statements are TRUE ?
1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there exists a cycle in a directed graph is in NP.
3. If a problem A is NP-Complete, there exists a non-deterministi

Accepted Answer

1, 2 and 3. All three statements are true: the cycle detection problem in undirected graphs can be solved in polynomial time (thus in P), the directed graph cycle problem is verifiable in polynomial time (hence in NP), and NP-Complete problems are defined by the existence of non-deterministic polynomial time algorithms.

Question 22

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Accepted Answer

Θ(n³). The Bellman-Ford algorithm has a time complexity of Θ(n * m), where n is the number of vertices and m is the number of edges. In a complete graph, the number of edges m is Θ(n²), leading to a total time complexity of Θ(n³).

Question 23

In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in sets are sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards. A main memory bl

Accepted Answer

(j mod v) * k to (j mod v) * k + (k-1). The correct option accurately describes how a main memory block is mapped to a specific range of cache lines in a k-way set associative cache. It indicates that the block indexed by j can occupy any of the k lines within the set determined by the modulo operation with v, ensuring that the mapping adheres to the structure of the cache.

Question 24

Which one of the following expressions does NOT represent exclusive NOR of x and y?

Accepted Answer

x ⊕ y. The expression x ⊕ y represents the exclusive OR (XOR) operation, which outputs true when exactly one of the inputs is true, while exclusive NOR (XNOR) outputs true when both inputs are the same. Therefore, x ⊕ y does not represent exclusive NOR.

Question 25

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

Accepted Answer

7. There are C(8,3)=56 vertex triples; each forms a triangle with probability (1/2)^3=1/8. Expected triangles = 56*(1/8) = 7. Stored '1' is wrong; correct is 7.

Question 26

Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

Accepted Answer

Both P and Q. In undirected graphs, the sum of the degrees of all vertices is always even because each edge contributes two to the total degree count. Additionally, the number of vertices with an odd degree must be even due to the Handshaking Lemma, which states that the sum of the degrees is equal to twice the number of edges.

Question 27

The line graph L(G) of a simple graph G is defined as follows:
• There is exactly one vertex v(e) in L(G) for each edge e in G.
• For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G.
Which of the following

Accepted Answer

P only. The statement P is true because the line graph of a cycle retains the cyclic structure, where each edge corresponds to a vertex in the line graph, and edges in the original cycle connect these vertices in a cyclic manner. The other statements do not hold true universally for their respective graph types.

Question 28

What is the logical translation of the following statement?
"None of my friends are perfect."

Accepted Answer

∀x [F x ⊃ ¬P x]. The correct option states that for all individuals x, if x is a friend, then x is not perfect. This accurately captures the meaning of the original statement that none of the friends possess perfection.

Question 29

Consider a hard disk with 16 recording surfaces (0-15) having 16384 cylinders (0-16383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512 bytes. Data are organized cylinder-wise and the addressing format is < cylinder no., surface no., sector no. >.

Accepted Answer

1284. Sectors per cylinder = 16*64 = 1024. File = 42797 KB / 0.5 KB = 85594 sectors. Start linear address = 1200*1024 + 9*64 + 40 = 1229416; last = 1229416 + 85594 - 1 = 1315009; cylinder = 1315009 / 1024 = 1284.

Question 30

Consider the following function:

int unknown(int n){
 int i, j, k = 0;
 for (i = n/2; i <= n; i++)
 for (j = 2; j <= n; j = j * 2)
 k = k + n/2;
 return (k);
}

The return value of the function is

Accepted Answer

Θ(n² log n). Outer loop runs about n/2 times, inner loop (j doubling to n) runs log2(n) times, and each iteration adds n/2. Total return value ~ (n/2)(log n)(n/2) = Theta(n^2 log n).

Question 31

Consider the following relational schema.
Students(rollno: integer, sname: string)
Courses(courseno: integer, cname: string)
Registration(rollno: integer, courseno: integer, percent: real)
Which of the following queries are equivalent to this query in English?
"Find the distinct names of a

Accepted Answer

I, II, III and IV. All four options accurately express the requirement to find distinct student names who scored above 90% in course 107, using different representations of relational algebra and SQL, thus confirming their equivalence.

Question 32

Determine the maximum length of the cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s.

Accepted Answer

2. The maximum length of the cable is determined by the propagation delay and the transmission time of the frames. Given the data rate and frame size, the transmission time is 0.02 seconds, and with a signal speed of 200,000 km/s, the maximum distance that can be covered without collisions is 2 km.

Question 33

In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and the fragment offset value is 300. The position of the datagram, the sequence numbers of the first and the last bytes of the payload, respectively are

Accepted Answer

Last fragment, 2400 and 2759. The M bit being 0 indicates that this is the last fragment. The HLEN of 10 means the header is 40 bytes, and with a total length of 400 bytes, the payload is 360 bytes. The fragment offset of 300 indicates that the first byte of the payload starts at byte 2400 (300 * 8) and ends at byte 2759 (2400 + 360 - 1), confirming the correct option.

Question 34

What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.

int f (int &x, int c) {
 c = c - 1;
 if (c == 0) return 1;
 x = x + 1;
 return f(x, c) * x;
}

Accepted Answer

6561. Because x is passed by reference, all recursive frames share it. The recursion increments x to 6,7,8,9 until c reaches 0, so at unwind x=9 everywhere; the product is 1 * 9 * 9 * 9 * 9 = 9^4 = 6561, not 161051.

Question 35

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

Accepted Answer

15, 10, 23, 25, 20, 35, 42, 39, 30. The postorder traversal visits the left subtree, then the right subtree, and finally the root node. In this case, the sequence correctly reflects that order, with the root (30) appearing last after all left and right children have been processed.

Question 36

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q){
 m = k
 while (Q is not empty) and (m > 0) {
 Dequeue(Q)
 m = m - 1
 }
}

What is the worst case time complexity of a sequence of queue operations on an in

Accepted Answer

Θ(n). The worst-case time complexity is Θ(n) because each Dequeue operation takes constant time, and even if MultiDequeue attempts to dequeue up to k elements, it will only process as many elements as are present in the queue, which is n in total.

Question 37

Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) and Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are 5 ns, 7 ns, 10 ns, 8 ns and 6 ns, respective

Accepted Answer

165. The total time to complete the program is calculated by considering the pipeline stages and the delays, including the impact of the branch instruction. Since the branch is taken during the execution of I4, it causes a stall that adds extra cycles, resulting in a total time of 165 ns for the execution of all 12 instructions.

Question 38

Statement for Linked Answer Questions 52 and 53:
A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry

Accepted Answer

8. With a 4-byte PTE the entries per page are 2^(p-2), so each level uses p-2 index bits and the first-level table fits one page. The VPN has 46-p bits = 3(p-2), giving p=13, i.e. an 8 KB page. The stored 4 KB is wrong.

Question 39

Which of the following statements are TRUE?
1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there exists a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a non-determinis

Accepted Answer

1, 2 and 3. All three statements are true: determining the existence of a cycle in an undirected graph can be solved in polynomial time (making it in P), it is also verifiable in polynomial time (placing it in NP), and NP-Complete problems have non-deterministic polynomial time algorithms, which is a defining characteristic.

Question 40

Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection a

Accepted Answer

2 only. Statements 1, 3, and 4 are true. Statement 2 is false: Turing-recognizable (RE) languages are closed under union but NOT under complementation. So only statement 2 is false.

Question 41

An index is clustered if

Accepted Answer

the data records of the file are organized in the same order as the data entries of the index.. A clustered index organizes the actual data records in the database table in the same order as the index entries, allowing for faster retrieval of data since the physical storage aligns with the logical ordering of the index.

Question 42

Using public key cryptography, X adds a digital signature s to message M, encrypts <M, s>, and sends it to Y, where it is decrypted. Which one of the following sequences of keys is used for the operations?

Accepted Answer

Encryption: X's private key followed by Y's public key; Decryption: X's public key followed by Y's private key. The correct option involves encrypting the message with X's private key to create a digital signature, ensuring authenticity, and then using Y's public key to encrypt the entire package for confidentiality. During decryption, Y uses their private key to access the message and X's public key to verify the signature, confirming that the message originated from X.

Question 43

Consider the languages L1 = ∅ and L2 = {a, ε}. Which one of the following represents L1 ∪ L2 ?

Accepted Answer

{ε, a}. The union of L1 and L2 combines all elements from both languages. Since L1 is empty and L2 contains the elements {a, ε}, the result of L1 ∪ L2 is simply {ε, a}.

Question 44

A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² - y². Which one of the following statements is TRUE about ⊕?

Accepted Answer

Neither commutative nor associative. The operation ⊕ is not commutative because x ⊕ y = x² - y² is not equal to y ⊕ x = y² - x² for all integers x and y. It is also not associative since (x ⊕ y) ⊕ z does not equal x ⊕ (y ⊕ z) when calculated, demonstrating that the grouping of operations affects the result.

Question 45

What is the return value of f(p, p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.

int f (int &x, int c) {
 c = c - 1;
 if (c == 0) return 1;
 x = x + 1;
 return f(x, c) * x;
}

Accepted Answer

6561. x is passed by reference to p throughout, while c (by value) counts 5->4->3->2->1->0, incrementing the shared p four times from 5 to 9. The base case returns 1, and each of the four returns multiplies by the final shared value 9, giving 9^4 = 6561.

Question 46

Consider the following function:
int unknown(int n){
 int i, j, k=0;
 for (i=n/2; i<=n; i++)
 for (j=2; j<=n; j=j*2)
 k = k + n/2;
 return (k);
}
The return value of the function is

Accepted Answer

Θ(n² log n). The function has two nested loops: the outer loop runs for n/2 to n, which is Θ(n), and the inner loop runs logarithmically with respect to n (specifically, it doubles j each iteration). Therefore, the total complexity is the product of these two, resulting in Θ(n² log n).

Question 47

Consider a hard disk with 16 recording surfaces (0-15) having 6384 cylinders (0-6383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512 bytes. Data are organized cylinder-wise and the addressing format is < cylinder no., surface no., sector no. >. A

Accepted Answer

1284. To find the cylinder number of the last sector, first calculate the total number of sectors needed for the file size of 42797 KB, which is 42797 * 1024 bytes. This results in 83,000 sectors. Starting from the initial location <1200, 9, 40>, the last sector will be located at <1200 + (83000 / 64), 9, (40 + (83000 % 64))>. This calculation leads to the last sector being in cylinder 1284.

Question 48

In the following truth table, V = 1 if and only if the input is valid.

What function does the truth table represent?

Accepted Answer

Priority encoder. The truth table represents a priority encoder because it outputs a binary code corresponding to the highest-priority active input, indicating which input is valid. This function is distinct from decoders, multiplexers, and demultiplexers, which serve different roles in digital logic.

Question 49

Which of the following statements are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

Accepted Answer

Both P and Q. In undirected graphs, the sum of the degrees of all vertices is always even because each edge contributes two to the total degree count. Additionally, the number of vertices with odd degrees must be even due to the Handshaking Lemma, which states that the sum of the degrees of all vertices is equal to twice the number of edges.

Question 50

Assume that source S and destination D are connected through two intermediate routers labeled R. D determine how many times each packet has to visit the network layer and the data link layer during a transmission from S to D.

S — R — R — D

Accepted Answer

Network layer - 4 times and Data link layer - 6 times. Each packet must traverse the network layer at the source and each router, totaling four visits. Additionally, the data link layer is engaged at the source, each router, and the destination, resulting in six visits overall.

GATE Technical: COMPUTER SCIENCE & INFORMATION TECH. - CS questions with solutions

Questions