.png)
.png)
GATE 2026 Computer Science & Information Technology (CS2) Question Paper
Welcome to The GateVerse! If you are preparing for the Graduate Aptitude Test in Engineering (GATE) 2026 in Computer Science and Information Technology (CS2), this online question paper is a valuable resource for your exam preparation. It provides an opportunity to practice questions, test your understanding, and become familiar with the level and style of GATE examination questions.
This practice paper includes 65 questions covering important concepts and problem-solving areas of Computer Science and Information Technology. You can attempt the questions directly on this page without downloading any additional software. Each question includes an interactive answer-checking feature to help you evaluate your performance while practicing.
Practice Questions with Instant Answer Checking
One of the most useful features of this online GATE question paper is instant answer checking. After attempting a question, click the Check Answer button to see whether your response is correct or incorrect. Correct answers are highlighted in green, while incorrect responses are indicated in red along with the correct answer. This helps you identify mistakes and understand where you need more practice.
Step-by-Step Solutions for Better Understanding
Learning does not stop after checking your answer. Each question also provides a Show Solution option. You can open the solution whenever you need help understanding the concept or calculation. These explanations can help strengthen your fundamentals, improve analytical thinking, and develop a better approach to solving technical problems.
Why Practice on The GateVerse?
Regular practice is an important part of GATE preparation. Solving a complete question paper helps you improve accuracy, build confidence, revise important concepts, and develop effective time-management skills. Try to attempt every question independently before viewing its solution. Review your mistakes and revisit the topics that require more attention.
Whether you are revising your syllabus or evaluating your preparation level, this GATE 2026 CS2 question paper with answers and solutions can support your learning journey.
Attempt all 65 questions, check your answers, learn from the solutions, and keep improving with The GateVerse.
The GateVerse – Learn, Practice & Succeed!
Fill the blank by choosing a word with a meaning similar to that of the words given above.
Accelerate means to make something happen faster or to increase its speed. It has a meaning similar to Expedite, Hasten and Hurry.
The given black square has been divided into two complementary pieces. The missing piece must fit exactly into the cut-out region without overlapping or leaving any gap.
Among the four choices, only (iii) matches the required shape and completes the original square correctly.
Probability of a cloudy day = 0.5
Probability of a sunny day = 0.5
We need exactly 3 cloudy days and 1 sunny day in 4 days.
= 4 × 1/8 × 1/2
= 1/4 ×?
Therefore, based strictly on the stated probability model, the probability is 1/4.
Stock A:
Initial value = Rs. 50
Investment = Rs. 100
Number of shares = 100 ÷ 50 = 2
Selling value = 2 × 55 = Rs. 110
Stock B:
Initial value = Rs. 80
Investment = Rs. 80
Number of shares = 80 ÷ 80 = 1
Selling value = 1 × 70 = Rs. 70
Total investment = 100 + 80 = Rs. 180
Total selling value = 110 + 70 = Rs. 180
Profit = 180 − 180 = Rs. 0
Correct Answer: Option (A) – 0
Based only on this sentence, which one of the following options is necessarily true?
Given statement:
If it is raining, then peacocks dance.
Let:
P = It is raining
Q = Peacocks dance
The given statement is:
P → Q
Its logically equivalent contrapositive is:
¬Q → ¬P
This means:
If peacocks are not dancing, then it is not raining.
Correct Answer: Option (C)
Choose the P and Q combination from the options below to form a meaningful analogy.
Water is associated with thirst because we drink water to satisfy thirst.
Similarly, food is associated with hunger because we eat food to satisfy hunger.
Therefore:
P = Thirst
Q = Hunger
Correct Answer: Option (A)
Count the black dots in each tile of Panel I:
Row 1: 8, 1, 6
Row 2: 3, 5, ?
Row 3: 4, 9, ?
Notice that the numbers form a 3×3 magic square. Every row and column adds up to 15.
For the missing upper tile:
3 + 5 + x = 15
x = 15 − 8
x = 7
For the missing lower tile:
4 + 9 + y = 15
y = 15 − 13
y = 2
Therefore, the missing tiles must contain 7 black dots on top and 2 black dots below.
Only option (i) matches this pattern.
Correct Answer: Option (A) – (i)
A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.
Which one of the following options is then true?
The question asks whether a Hamiltonian cycle exists in each graph.
Figure (i):
The 4×4 grid has a Hamiltonian cycle. We can start at one corner, follow the outer boundary, and visit every vertex exactly once before returning to the starting vertex.
Figure (ii):
The two vertices at the top-right and left-bottom each have degree 2. The inner vertex also has degree 2 and must use both its connecting edges in any Hamiltonian cycle.
This forces the cycle to use the path through the inner vertex, leaving no way to include all the other vertices exactly once and return to the start.
Therefore, a Hamiltonian cycle exists in (i), but not in (ii).
Correct Answer: Option (A)
Given conditions:
- Each column must contain exactly 2 shaded cells.
- Row 1 must contain 3 shaded cells.
- Row 2 must contain 1 shaded cell.
- Row 3 must contain 2 shaded cells.
- Row 4 must contain 2 shaded cells.
Check option (ii):
Row 1 = 3 shaded cells ✓
Row 2 = 1 shaded cell ✓
Row 3 = 2 shaded cells ✓
Row 4 = 2 shaded cells ✓
Each of the four columns also contains exactly 2 shaded cells.
Therefore, option (ii) satisfies all the given conditions.
Correct Answer: Option (B) – (ii)
A dice has 6 possible outcomes. It is rolled twice.
Total possible outcomes:
6 × 6 = 36
Prime numbers possible as the sum are:
2, 3, 5, 7 and 11.
Favourable outcomes:
Sum = 2: (1,1) → 1 outcome
Sum = 3: (1,2), (2,1) → 2 outcomes
Sum = 5: 4 outcomes
Sum = 7: 6 outcomes
Sum = 11: 2 outcomes
Total favourable outcomes:
1 + 2 + 4 + 6 + 2 = 15
Probability = Favourable outcomes / Total outcomes
= 15/36
Correct Answer: Option (C) – 15/36
There is a person who does not know anyone else, but that person is known by everyone else.
Which one of the following expressions represents the above statement?
Given: M(x, y) means x knows y.
The statement says there exists one person y who satisfies two conditions:
1. Everyone else knows that person:
M(x, y)
2. That person does not know anyone else:
¬M(y, x)
The phrase "There is a person" means we use the existential quantifier: ∃y
The phrase "everyone else" means we use the universal quantifier: ∀x
Combining both conditions: (∃y)(∀x) ((x ≠ y) → (M(x, y) ∧ ¬M(y, x))) Therefore, the correct expression is: Option (A)
| Set T | Set S |
|---|---|
| I: Inorder | L: left subtree, node, right subtree |
| II: Preorder | M: node, left subtree, right subtree |
| III: Postorder | N: left subtree, right subtree, node |
There are three main types of binary tree traversals:
1. Inorder (Left – Root – Right)
First visit the left subtree, then the node, and finally the right subtree.
Therefore, I → L
2. Preorder (Root – Left – Right)
First visit the node, then the left subtree, and finally the right subtree.
Therefore, II → M
3. Postorder (Left – Right – Root)
First visit the left subtree, then the right subtree, and finally the node.
Therefore, III → N
The correct matching is:
I – L, II – M, III – N
Correct Answer: Option (A)
A Turing machine is said to decide a language L if it satisfies two conditions:
1. Acceptance:
For every string belonging to L, the machine must halt and accept it.
2. Rejection:
For every string not belonging to L, that is, in {0,1}* − L, the machine must halt and reject it.
Therefore, a deciding Turing machine must accept all strings in L and reject all strings outside L.
Option (A) only says that the machine halts on every input. It does not specify which strings are accepted or rejected.
Hence, the correct answer is: Option (D)
The given probability density function is:
f(x) = 1/(3√(2π)) × exp(−x²/18)
The standard probability density function of a normal random variable is:
f(x) = 1/(σ√(2π)) × exp(−(x−μ)²/(2σ²))
Comparing both equations:
Mean (μ) = 0
Variance (σ²) = 9
Standard deviation (σ) = 3
Therefore, X follows a normal distribution:
X ~ N(0, 9)
Hence, the correct answer is:
Option (B) – X is a normal random variable.
| T | S |
|---|---|
| I: Logical schema | L: Views |
| II: Physical schema | M: File organization and indexes |
| III: External schema | N: Relations |
DBMS has three important levels of database schemas:
1. Logical Schema
It describes the logical structure of the database, including tables and relationships.
Therefore, I → N (Relations).
2. Physical Schema
It describes how data is actually stored in the system, including file organization and indexes.
Therefore, II → M (File organization and indexes).
3. External Schema
It describes the different views of the database for different users.
Therefore, III → L (Views).
The correct matching is:
I – N, II – M, III – L
Correct Answer: Option (C)
In C, memory is divided into different sections such as Stack, Heap, Data Segment, and Code Segment.
Option A: Static variable declared inside a function
A static local variable is stored in the Data Segment, not in the heap.
Option B: Array of integers declared inside a function
A local array with automatic storage duration is generally stored on the Stack.
Option C: Dynamically allocated array using malloc()
The malloc() function dynamically allocates memory from the Heap. Therefore, the array created using malloc() is stored in the Heap.
Option D: Return address of a function
The return address is typically stored as part of the function's stack frame.
Hence, the correct answer is:
Option (C) – A dynamically allocated array of integers created using malloc() function call.
S1: In non-vectored interrupt mechanism, it usually takes more time to start the Interrupt Service Routine (ISR) when compared to that in a vectored interrupt mechanism.
S2: In daisy-chain interrupt mechanism, the CPU polls all the input devices individually to determine the source of the interrupt.
Which one of the following options is correct with respect to S1 and S2?Explanation:
S1 is true: In a vectored interrupt, the address of the ISR is provided directly or identified through the interrupt vector. In a non-vectored interrupt, additional steps are generally required to identify the ISR, so starting it usually takes more time.
S2 is false: In a daisy-chain mechanism, devices are connected in a serial priority chain. The interrupt acknowledge signal passes through the devices, and the requesting device identifies itself. The CPU does not individually poll every device.
P1: The global variable
a is declared outside the function. The local variable a inside main() is valid because it shadows the global variable. Therefore, P1 compiles successfully.
P2: Two variables named
a are declared in the same function scope. This causes a redefinition error.
P3: Two variables named
a are declared in the same function scope with different types (int and float). This causes a conflicting declaration error.
Therefore, only P1 compiles without any error.
Two operations conflict when they access the same data object, belong to different transactions, and at least one of them is a write operation.
- Read–Read: No conflict.
- Read–Write: Conflict.
- Write–Read: Conflict.
- Write–Write: Conflict.
Therefore, both transactions must only read A to avoid a conflict.
Which one of the following is the total time (in seconds) to transfer the file?
Note: 1M = 10⁶, 1k = 10³
**Step 1: Convert the file size into bits.**
File size = 4 million bytes
= 4 × 10⁶ × 8 bits
= 32 × 10⁶ bits
Step 2: Find the bottleneck bandwidth.
The three link bandwidths are:
- 2 Mbps
- 500 kbps
- 1 Mbps
The minimum bandwidth is 500 kbps.
Step 3: Calculate the transfer time.
Time = File size / Bottleneck bandwidth
= 32 × 10⁶ / (500 × 10³)
= 64 seconds
Therefore, the correct answer is Option (B) 64 seconds.
DHCP (Dynamic Host Configuration Protocol) may use broadcast messages when a client does not yet know the DHCP server's IP address.
During the DHCP discovery process, a client broadcasts a DHCPDISCOVER message to locate available DHCP servers on the local network.
SMTP, FTP, and HTTP generally use communication between specific hosts rather than broadcast messages for their normal operation.
Therefore, the correct answer is Option (C) DHCP.
FCFS is a non-preemptive CPU scheduling algorithm. Once a process gets the CPU, it continues execution until it terminates or enters a waiting state.
- SRTF: Preemptive version of Shortest Job First scheduling.
- FCFS: Non-preemptive scheduling algorithm.
- Round Robin: Preemptive scheduling using a time quantum.
- Priority Scheduling: Can be either preemptive or non-preemptive.
Therefore, the correct answer is Option (B) FCFS Scheduling.
Note: Assume the base of log to be 2.
We need to arrange the functions in increasing order of asymptotic growth.
Step 1: Compare log(n) and n1/3.
Logarithmic growth is slower than polynomial growth.
Therefore:
log(n) < n1/3
Step 2: Simplify 2log(n).
Since the base of log is 2:
2log₂(n) = n
Step 3: Compare log(n!) with n.
Using Stirling's approximation:
log(n!) = Θ(n log n)
Hence:
n < log(n!)
Final increasing order:
log(n) < n1/3 < 2log(n) < log(n!)
Therefore, the correct answer is Option (A).
(B) T(n) = 2T(n/2) + 1, T(1) = 1
(C) T(n) = 2T(n/2) + n, T(1) = 1
(D) T(n) = T(n − 1) + n, T(1) = 1
Option (A):
T(n) = T(n − 1) + 1
Expanding the recurrence gives:
T(n) = T(1) + (n − 1)
Therefore, T(n) = Θ(n).
Option (B):
T(n) = 2T(n/2) + 1
Using the Master Theorem:
a = 2, b = 2, f(n) = 1
nlog₂2 = n
Therefore, T(n) = Θ(n).
Option (C):
T(n) = 2T(n/2) + n
This gives T(n) = Θ(n log n).
Option (D):
T(n) = T(n − 1) + n
This gives T(n) = Θ(n²).
Hence, only options (A) and (B) have time complexity Θ(n).
(A) Reflexive — True
For every x in the set, x × x = x², which is always a perfect square. Therefore, R is reflexive.
(B) Symmetric — True
If x × y is a perfect square, then y × x is also the same perfect square. Therefore, R is symmetric.
(C) Transitive — True
If xy and yz are perfect squares, then x and z have the same prime-factor parity. Consequently, xz is also a perfect square. Therefore, R is transitive.
(D) Antisymmetric — False
Consider x = 1 and y = 4.
1 × 4 = 4 = 2².
Thus, (1, 4) and (4, 1) both belong to R, but 1 ≠ 4. Hence, R is not antisymmetric.
Therefore, the correct options are (A), (B) and (C).
Given:
I(a) = ∫−11 (3x² − ax + 1) dx
Integrating:
I(a) = [x³ − (ax²/2) + x]−11
Substituting the limits:
I(a) = (1 − a/2 + 1) − (−1 − a/2 − 1)
I(a) = 2 − a/2 + 2 + a/2
I(a) = 4
Therefore:
- (A) True: I(a) = 4, so its value is independent of a.
- (B) False: The value does not vary with a.
- (C) True: I(a) = 4 is always positive.
- (D) False: I(a) can never be negative.
Hence, the correct options are (A) and (C).
N1 = 1011, N2 = 1101, N3 = 1010 and N4 = 1001
Which of the following operations will result in arithmetic overflow?
In 4-bit two's complement representation, the range of numbers is:
−8 to +7
Convert the given binary numbers into decimal:
N1 = 1011 = −5
N2 = 1101 = −3
N3 = 1010 = −6
N4 = 1001 = −7
Option (A): N1 + N2
−5 + (−3) = −8
Within the valid range. No overflow.
Option (B): N2 + N3
−3 + (−6) = −9
−9 is outside the valid range. Overflow occurs.
Option (C): N3 − N4
−6 − (−7) = 1
Within the valid range. No overflow.
Option (D): N1 + N4
−5 + (−7) = −12
−12 is outside the valid range. Overflow occurs.
Therefore, the correct answers are (B) and (D).
A grammar is ambiguous if at least one string generated by it has more than one distinct parse tree or more than one leftmost derivation.
Option (A): S → aSb | ε
This grammar generates strings of the form aⁿbⁿ. Each string has a unique derivation. Therefore, it is unambiguous.
Option (B): E → E + E | E * E | id
The string id + id * id can have different parse trees:
(id + id) * id
id + (id * id)
Therefore, this grammar is ambiguous.
Option (C): S → aS | Sa | ε
The string "a" can be generated in two different ways:
1. S → aS → aε → a
2. S → Sa → εa → a
Since two different derivations generate the same string, the grammar is ambiguous.
Option (D): S → aS | ε
This grammar generates a*. Every string has a unique derivation. Therefore, it is unambiguous.
Hence, the correct answers are (B) and (C).
h(k) = k mod 9
The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is __________.
(Answer in integer)
The hash function is:
h(k) = k mod 9
Calculate the hash value of each key:
5 mod 9 = 5
28 mod 9 = 1
19 mod 9 = 1
15 mod 9 = 6
26 mod 9 = 8
33 mod 9 = 6
12 mod 9 = 3
17 mod 9 = 8
10 mod 9 = 1
Hash table using chaining:
Index 1: 28 → 19 → 10 (Length = 3)
Index 3: 12 (Length = 1)
Index 5: 5 (Length = 1)
Index 6: 15 → 33 (Length = 2)
Index 8: 26 → 17 (Length = 2)
The longest chain is at index 1, containing 3 keys.
Therefore, the correct answer is 3.
ax + y = b
16x + ay = 24
Suppose the values of a and b are chosen such that the system of linear equations produces multiple solutions. Then the product of a and b is __________.
(Answer in integer)
The given equations are:
ax + y = b ...(1)
16x + ay = 24 ...(2)
For a system of two linear equations to have infinitely many solutions, the ratios of corresponding coefficients and constants must be equal:
a/16 = 1/a = b/24
Comparing the first two ratios:
a/16 = 1/a
a² = 16
a = ±4
Now, using:
1/a = b/24
ab = 24
Therefore, the product of a and b is:
ab = 24
Hence, the correct answer is 24.
A merge operation on sorted left array L and sorted right array R is said to be void if the output of the merge operation is the elements of array L followed by the elements of array R.
The number of void merge operations among these 7 merge operations is __________.
(Answer in integer)
A merge operation is void when every element of the sorted left array is smaller than or equal to every element of the sorted right array.
Step 1: Divide the array into smaller parts.
[10, 7] [8, 19] [41, 35] [25, 31]
Step 2: Perform the first four merge operations.
1. [10] and [7] → [7, 10] — Not void.
2. [8] and [19] → [8, 19] — Void.
3. [41] and [35] → [35, 41] — Not void.
4. [25] and [31] → [25, 31] — Void.
Step 3: Perform the next two merge operations.
5. [7, 10] and [8, 19] → [7, 8, 10, 19] — Not void.
6. [35, 41] and [25, 31] → [25, 31, 35, 41] — Not void.
Step 4: Perform the final merge operation.
7. [7, 8, 10, 19] and [25, 31, 35, 41]
Since 19 is smaller than 25, all elements of the left array come before the right array.
Therefore, this merge is void.
Total void merge operations = 3
Hence, the correct answer is 3.
(Answer in integer)
Given subnet mask:
255.255.240.0
Step 1: Convert the subnet mask into binary.
255 = 11111111
255 = 11111111
240 = 11110000
0 = 00000000
Therefore, the subnet mask contains 20 network bits.
So, the CIDR notation is /20.
Step 2: Calculate the host bits.
Host bits = 32 − 20 = 12
Step 3: Calculate the total number of IP addresses.
Total IP addresses = 2¹² = 4096
Step 4: Calculate usable IP addresses.
Usable IP addresses = 2¹² − 2
= 4096 − 2
= 4094
Two addresses are reserved: the network address and the broadcast address.
Hence, the correct answer is 4094.
The number in decimal representation is __________.
(Rounded off to two decimal places)
Given IEEE 754 representation:
0xC2710000
Step 1: Convert hexadecimal into binary.
C2710000 =
11000010 01110001 00000000 00000000
Step 2: Divide into three fields.
Sign bit = 1
Exponent = 10000100
Mantissa = 11100010000000000000000
Step 3: Calculate the sign.
Sign bit = 1, so the number is negative.
Step 4: Calculate the exponent.
10000100₂ = 132
Actual exponent = 132 − 127 = 5
Step 5: Calculate the mantissa.
1 + 1/2 + 1/4 + 1/8 + 1/128
= 1.8828125
Step 6: Calculate the final value.
Value = (−1)¹ × 1.8828125 × 2⁵
= −1.8828125 × 32
= −60.25
Hence, the correct answer is −60.25.
letter → [A–Z a–z]
digit → [0–9]
id → letter (letter | digit)*
number → digit+
ws → (blank | tab | newline)+
For the string given below,
x1 23mm 78 y 7z zz5 14A 8H AaYcD
the number of tokens (excluding ws) that will be produced by the lexical analyzer is __________.
(Answer in integer)
According to the given definitions:
- An identifier (id) must start with a letter and can contain letters or digits.
- A number must contain one or more digits.
- Whitespace is excluded from the token count.
Tokenization of the given string:
1. x1 → id (1 token)
2. 23mm → number (23), id (mm) (2 tokens)
3. 78 → number (1 token)
4. y → id (1 token)
5. 7z → number (7), id (z) (2 tokens)
6. zz5 → id (1 token)
7. 14A → number (14), id (A) (2 tokens)
8. 8H → number (8), id (H) (2 tokens)
9. AaYcD → id (1 token)
Total number of tokens:
1 + 2 + 1 + 1 + 2 + 1 + 2 + 2 + 1 = 13
Hence, the correct answer is 13.
Note that multiple spanning trees can be constructed over Kn. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.
Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of Kn?
A spanning tree of a graph with n vertices always contains exactly (n − 1) edges.
For a complete graph Kn (n > 4), we can construct two edge-disjoint spanning trees. This means that the two spanning trees have no common edges.
Therefore:
Intersection = 0
Jaccard coefficient = Intersection / Union
= 0 / (2n − 2)
= 0
GATE Computer Science
Data Structures & Algorithms
Solution
Given graph G is a Directed Acyclic Graph (DAG).
A DAG allows us to find shortest paths using Topological Sorting. First, we arrange vertices in topological order and then relax the outgoing edges of each vertex in that order.
Time Complexity:
- Topological Sorting: Θ(m+n)
- Relaxing all edges: Θ(m)
Therefore, the total time complexity is:
Θ(m+n)
Correct Answer: Option (A)
GATE Computer Science
Data Structures & Algorithms
∀ i, j ∈ {1, …, n − 1} such that i > j,
(A[i + 1] − A[i]) > (A[j + 1] − A[j])
Solution
Given condition ka matlab hai ki array ke consecutive elements ke differences strictly increasing hone chahiye.
Step 1: Differences calculate karo
D[i] = A[i+1] − A[i]
Humein check karna hai ki:
D[1] < D[2] < D[3] < ... < D[n−1]
Step 2: Efficient algorithm
Har consecutive difference calculate karke previous difference se compare kar sakte hain. Agar current difference previous difference se greater nahi hai, toh condition fail ho jayegi.
Step 3: Time Complexity
- Consecutive differences calculate karna: O(n)
- Differences compare karna: O(n)
Isliye total worst-case time complexity:
Θ(n)
Saare elements ko worst case mein check karna pad sakta hai, isliye linear time se better worst-case complexity possible nahi hai.
Correct Answer: Option (A) Θ(n)
GATE Computer Science
Dynamic Programming
for k = 0, 1, 2, ..., n
T[i][j] = 2T[i−1][j] + 3T[i][j−1]
for 1 ≤ i, j ≤ n
Algorithm B1:
For j = 1, 2, ..., n
T[i][j] = 2T[i−1][j] + 3T[i][j−1]
Algorithm B2:
For i = 1, 2, ..., n
For j = 1, 2, ..., n
If (i + j == s)
T[i][j] = 2T[i−1][j] + 3T[i][j−1]
Solution
Given recurrence relation:
T[i][j] = 2T[i−1][j] + 3T[i][j−1]
1. Algorithm B1
B1 mein outer loop i par aur inner loop j par hai. Har row mein j left to right increase hota hai.
- T[i−1][j] previous row mein hota hai, jo already calculate ho chuka hai.
- T[i][j−1] current row ka previous element hai, jo pehle calculate ho chuka hai.
Isliye B1 har entry ko correct order mein calculate karta hai.
2. Algorithm B2
B2 mein s = i + j ke according entries calculate hoti hain. Yaani same diagonal ki entries ek saath process hoti hain.
- T[i−1][j] ka index sum (i−1)+j = s−1 hai.
- T[i][j−1] ka index sum i+(j−1) = s−1 hai.
Dono required entries previous diagonal mein hoti hain. Isliye current diagonal calculate hone se pehle unki values available hoti hain.
Isliye B2 bhi correct values calculate karta hai.
Both B1 and B2 are correct.
Correct Answer: Option (A)
GATE Computer Science
Digital Logic – Boolean Algebra
Note: + is OR operation, . is AND operation, and ′ is NOT operation.
Solution
Given Boolean function:
F(A,B,C,D) = Σm(0,1,2,3,8,9,10,11)
Step 1: Convert minterms into binary
| Minterm | A | B | C | D |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
| 10 | 1 | 0 | 1 | 0 |
| 11 | 1 | 0 | 1 | 1 |
Step 2: Find the common variable
Sabhi minterms mein B ki value 0 hai. A, C aur D ki values change ho rahi hain.
Isliye sirf B′ common rahega.
F(A,B,C,D) = B′
Step 3: Final Answer
Minimal sum of products form B′ hai.
Correct Answer: Option (B) B′
GATE Computer Science
Compiler Design – LR(0) Parsing
A → aA | ε
C → cC | ε
B → bB | b
Solution
Step 1: Understand Shift-Reduce Conflict
Shift-Reduce Conflict tab hota hai jab kisi LR(0) state mein same terminal ke liye ek taraf SHIFT action aur doosri taraf REDUCE action available ho.
Step 2: Identify the conflicting states
A → ε complete item hai, isliye REDUCE possible hai.
A → ·aA ki wajah se terminal a par SHIFT bhi possible hai.
Conflict on terminal a
A → a·A ke saath A → ·aA aur A → ε items present hain.
Terminal a par SHIFT aur REDUCE dono possible hain.
Conflict on terminal a
C → ε complete item REDUCE deta hai.
C → ·cC ki wajah se terminal c par SHIFT bhi possible hai.
Conflict on terminal c
C → c·C ke saath C → ·cC aur C → ε items present hain.
Terminal c par SHIFT aur REDUCE dono possible hain.
Conflict on terminal c
B → b· complete item REDUCE deta hai.
B → b·B ki wajah se terminal b par SHIFT bhi possible hai.
Conflict on terminal b
Step 3: Total conflicts
Correct Answer: Option (D) – 5
GATE Computer Science
DBMS – Functional Dependencies
Consider X, Y, and Z as sets of attributes over a relational schema. The three rules of Armstrong’s Axioms are described as follows:
Reflexivity: If Y ⊆ X, then X → Y
Augmentation: If X → Y, then XZ → YZ for any Z
Transitivity: If X → Y and Y → Z, then X → Z
Solution
Given:
Step 1: Apply Reflexivity
According to Reflexivity, since X ⊆ X:
Step 2: Apply Augmentation
Using X → Z, augment both sides with X:
Now, using X → Y, augment both sides with Z:
Step 3: Apply Transitivity
We have:
XZ → YZ
By Transitivity:
Hence, the Union rule is proved using all three Armstrong's Axioms.
Correct Answer: Option (A)
GATE Computer Science
Computer Networks – CRC
If the generator bit pattern is given to be 1001, which one of the following options shows the remainder bit pattern appended to the data bits before transmission?
Generator = 1001
Solution
Step 1: Given Data
Generator = 1001
Step 2: Append zeros
Generator has 4 bits, so its degree is 3. Therefore, append 3 zeros to the original data.
Step 3: Perform XOR Division
Divide 110001011000 by 1001 using modulo-2 division. In modulo-2 division, subtraction is performed using XOR.
Continue the XOR division until all data bits have been processed.
Divisor = 1001
Remainder = 100
Step 4: Final Answer
The last 3 bits obtained after modulo-2 division are 100. These are appended to the original data bits before transmission.
Correct Answer: Option (D) 100
GATE Computer Science
Computer Organization – Instruction Format
There are three different types of instructions; M-type, R-type, and C-type.
Each M-type instruction has 2 register operands and a 6-bit immediate operand.
Each R-type instruction has 3 register operands.
Each C-type instruction has a register operand and a 6-bit offset value.
If there are 2 unique M-type opcodes and 7 unique R-type opcodes, which one of the following options gives the maximum number of unique opcodes possible for C-type instructions?Solution
Step 1: Calculate register bits
Total registers = 16
Step 2: Calculate opcode lengths
M-type:
2 register operands = 2 × 4 = 8 bits
Immediate operand = 6 bits
R-type:
3 register operands = 3 × 4 = 12 bits
C-type:
1 register operand = 4 bits
Offset = 6 bits
Step 3: Calculate available opcodes
M-type has 2-bit opcodes. Total possible 2-bit patterns:
Out of these, 2 are used by M-type instructions. Therefore, remaining 2 prefixes are available.
Each remaining 2-bit prefix can be extended into 2⁴ = 16? No. For a 4-bit opcode, each prefix has 2² = 4 possible extensions.
R-type uses 7 of these 4-bit patterns.
Step 4: Calculate C-type opcodes
One remaining 4-bit prefix can be extended into 2² = 4 different 6-bit opcodes.
Final Answer
Correct Answer: Option (B) 4
GATE Computer Science
Compiler Design – Live Variable Analysis
Solution
Live Variable Analysis mein kisi variable ko live maana jaata hai agar uski current value future mein use ho sakti hai.
Step 1: USE and DEF sets
| Block | USE | DEF |
|---|---|---|
| B1 | {b, c} | {a} |
| B2 | {a, e} | {d} |
| B3 | {a, f} | {e} |
| B4 | {d, e} | {g} |
Step 2: Apply Live Variable Equations
Step 3: Calculate B4
B4 ke baad EXIT hai. Isliye:
B4 mein d aur e use ho rahe hain:
Step 4: Calculate B2
B2 ka successor B4 hai:
Step 5: Calculate B3 and B1
B3 ka successor B1 hai aur B1 ke successors B2 aur B3 hain. Isliye loop ke kaaran equations ko repeatedly solve karna hoga.
Fixed-point calculation se:
B3 ka IN set:
Ab B1 ke dono successors ke IN sets ka union:
Step 6: Final Answer
| Basic Block | Live Variables at Exit |
|---|---|
| B1 | {a, b, c, e, f} |
| B2 | {d, e} |
| B3 | {b, c, e, f} |
| B4 | ∅ |
Correct Answer: Option (A)
S1: A hash index must be a dense index
S2: A B+ tree index can be a sparse index
Which one of the following options is correct?
Statement S1: A hash index must be dense because hash indexing requires an index entry for every search-key value. Therefore, S1 is true.
Statement S2: A B+ tree index can be sparse when the data file is ordered on the search key. In a sparse index, entries need not be present for every search-key value. Therefore, S2 is also true.
The intersection of the languages accepted by D₁ and D₂ contains only the empty string ε. Hence, statement (C) is true.
The union, when concatenated with itself any number of times, generates all binary strings whose length is divisible by 3. Hence, statement (D) is true.
Therefore, statements (A) and (B) are false.
Which of the following constraints ensure(s) that the language L is context-free?
Option (A): i + k = j + ℓ. A pushdown automaton can maintain the difference between the two sides using its stack. Therefore, this language is context-free.
Option (B): i = k and j = ℓ. This gives aibjcidj, which has crossing dependencies and is not context-free.
Option (C): i = ℓ and j = k. This gives aibjcjdi. The dependencies are nested, so a pushdown automaton can recognize it.
Option (D): i + j = k + ℓ. A pushdown automaton can push while reading a and b, and pop while reading c and d. Hence, this language is context-free.
For a node V, let Suc(V) denote the node that is its inorder successor. If a node V does not have an inorder successor, then Suc(V) is NULL. As there are no duplicates, if Suc(V) is not NULL, then Val(V) < Val(Suc(V)).
Corresponding to every leaf node Li that has a non-NULL Suc(Li), a new key ki with the following property is to be inserted into the BST.
Which of the following statements is/are true?
Option (A) — True: Each leaf node with a non-NULL inorder successor has a key inserted between two consecutive keys in the inorder sequence. These intervals do not overlap, so the inserted keys cannot be duplicates.
Option (B) — False: A BST containing only one node has one leaf, but that leaf has no inorder successor. Therefore, K can be empty.
Option (C) — True: Each new key is inserted as a child of its corresponding leaf node. Thus, every affected leaf gains one child, and the height of the BST can increase by at most one.
Option (D) — False: The number of inserted keys is not necessarily equal to the original number of nodes. Therefore, the total number of nodes need not double.
Given the output, the objective is to predict whether an element was assigned to S or Q.
Which of the following options is/are possible valid assignment(s)?
Note: In the options, the notation xS denotes that element x was assigned to S and yQ denotes that element y was assigned to Q.
Option (A) — Correct:
Stack elements: 1, 3, 4. Popping gives 4, 3, 1. Queue elements: 2, 5. Dequeueing gives 2, 5. Final output: 4, 3, 1, 2, 5.Option (B) — Correct:
Stack elements: 3, 4. Popping gives 4, 3. Queue elements: 1, 2, 5. Dequeueing gives 1, 2, 5. Final output: 4, 3, 1, 2, 5.Option (C) — Incorrect:
Stack output is 5, 4 and queue output is 1, 2, 3. Final output: 5, 4, 1, 2, 3.Option (D) — Incorrect:
Stack output is 3, 2, 1 and queue output is 4, 5. Final output: 3, 2, 1, 4, 5.Therefore, only options (A) and (B) produce the required output.
Which of the following patterns is/are possible to be generated as an outcome of the execution of these three processes?
Step 1: Semaphore A ensures that only one process at a time executes the first critical section. Therefore, the first two processes print `*` and increment X. When X becomes 2, `$` is printed and semaphore B is signaled.
Step 2: The third process also prints `*`, but it does not print `$` because X is already 3.
Option (A) — Possible: All three processes print `*` before proceeding to print `#`. Output: **$*###.
Option (B) — Possible: One process prints `#` before the third process prints `*`. Output: **$#*##.
Option (C) — Possible: Two processes print `#` before the third process prints `*`. Output: **$##*#.
Option (D) — Not possible: The second `*` is immediately followed by `$` before the third process can print its `*`. Therefore, `***$###` cannot be generated.
Assume that the cache memory is initially empty. The physical addresses of the words are given below (1 word =1 byte).
Q: 0x845B26
R: 0x845B36
S: 0x846B32
Note: 1K = 210 and 1M = 220
Step 1: Calculate the number of cache lines.
Cache size = 4 KB = 4096 bytes
Block size = 16 bytes
Number of cache lines = 4096 / 16 = 256
Step 2: Identify the memory blocks.
P = 0x845B32 and R = 0x845B36 belong to the same memory block.
Q = 0x845B26 belongs to a different block.
S = 0x846B32 belongs to a different block but maps to the same cache line as P and R.
Step 3: Analyze the access sequence.
P causes a miss because S replaces its cache block before the next P access. Therefore, every access to P is a cache miss. Option (A) is true.
R belongs to the same memory block as P. P is loaded immediately before Q and R, and Q maps to a different cache line. Hence, R always results in a cache hit. Option (B) is true.
Q causes a miss only on its first access. Its cache line is not replaced by P, R or S. Therefore, option (C) is false.
S causes a miss on every access because P replaces its cache block before the next S access. Therefore, option (D) is false.
Final Answer: A and B
Note: 1K = 210 and 1G = 230
Step 1: Calculate the total number of disk blocks.
Disk size = 16 GB = 16 × 230 bytes
Block size = 2 KB = 2 × 210 bytes
Total blocks = (16 × 230) / (2 × 210) = 223 = 8,388,608
Step 2: Calculate the space available in each list block.
Block size = 2 KB = 2048 bytes
Pointer size = 4 bytes
Remaining space = 2048 − 4 = 2044 bytes
Step 3: Calculate the number of block numbers stored.
Each block number = 32 bits = 4 bytes
Number of block numbers per list block = 2044 / 4 = 511
Step 4: Calculate the required number of list blocks.
Required blocks = ⌈8,388,608 / 511⌉
= ⌈16,416.0626...⌉
Final Answer = 16417
Note: 1K = 210, 1M = 220, 1G = 230
Step 1: Calculate the number of TLB entries.
TLB reach = 1 MB = 220 bytes
Page size = 4 KB = 212 bytes
Number of TLB entries = 220 / 212 = 28 = 256
Step 2: Calculate page number bits.
Virtual address space = 64 GB = 236 bytes
Page size = 212 bytes
Number of virtual pages = 236 / 212 = 224
Page number bits = 24 bits
Step 3: Calculate frame number bits.
Physical address space = 1 GB = 230 bytes
Number of frames = 230 / 212 = 218
Frame number bits = 18 bits
Step 4: Calculate the size of one TLB entry.
Process ID = 4 bits
Page number = 24 bits
Frame number = 18 bits
Control field = 2 bits
Total bits per entry = 4 + 24 + 18 + 2 = 48 bits
Size per entry = 48 / 8 = 6 bytes
Step 5: Calculate total TLB size.
Total TLB size = 256 × 6
Final Answer = 1536 bytes
Note: 1K = 210
Step 1: Initial memory holes
20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, 12 KB
Step 2: Allocate memory to P1 (16 KB).
Using Best Fit, the smallest hole that can accommodate 16 KB is 18 KB.
Remaining hole = 18 − 16 = 2 KB
Step 3: Allocate memory to P2 (9 KB).
The smallest available hole that can accommodate 9 KB is 9 KB itself. Therefore, this hole is completely allocated.
Step 4: Count holes smaller than 8 KB.
Remaining holes are: 20 KB, 4 KB, 25 KB, 2 KB, 7 KB, 15 KB, 12 KB
Holes smaller than 8 KB are: 2 KB, 4 KB and 7 KB
Final Answer = 3
Note: 1K = 210 and 1M = 220
Step 1: Convert physical address into decimal.
Physical address = 0xA2C28
Block size is 64 bytes for the valid mapping:
Block number = 0xA2C28 / 64
= 10416
Step 2: Find the number of cache blocks.
In a direct mapped cache:
Cache block number = Memory block number MOD Number of cache blocks
10416 MOD N = 176
N = 2048 (maximum possible power of 2)
Step 3: Calculate cache size.
Cache size = Number of cache blocks × Block size
= 2048 × 64 bytes
= 131072 bytes
Convert into KB:
= 131072 / 1024
= 128 KB
Final Answer = 128
Note: 1G = 109
Step 1: Non-pipelined execution time
Clock frequency = 1.6 GHz
Average CPI = 5
Time per instruction = 5 / 1.6 GHz
= 3.125 ns
Step 2: Pipelined average CPI
Ideal CPI = 1
30% instructions experience 2 stall cycles.
Average CPI = 1 + (0.30 × 2)
= 1.6
Step 3: Pipelined execution time
Clock frequency = 1.2 GHz
Time per instruction = 1.6 / 1.2 GHz
= 1.3333 ns
Step 4: Calculate speed-up
Speed-up = Non-pipelined time / Pipelined time
= 3.125 / 1.3333
= 2.34375
Rounded off to two decimal places:
Final Answer = 2.34
Note: 1K = 210
Step 1: Given values
Receiver window = 48 KB
MSS = 2 KB
Slow start threshold (ssthresh) = 16 KB
Step 2: Initial congestion window
Initial cwnd = 1 MSS = 2 KB
Step 3: Congestion window growth
During slow start, congestion window doubles after each round:
Start: 2 KB
After Round 1: 4 KB
After Round 2: 8 KB
After Round 3: 16 KB
Step 4: Enter congestion avoidance
When congestion window reaches the slow start threshold of 16 KB, TCP enters the congestion avoidance phase.
Therefore, the number of rounds required is:
Final Answer = 4
Note: One input combination is an instance of [A B S1 S0].
Step 1: Understand the decoder.
A 2:4 active-high decoder generates four outputs:
D0 = 1 for AB = 00
D1 = 1 for AB = 01
D2 = 1 for AB = 10
D3 = 1 for AB = 11
Step 2: Understand the multiplexer inputs.
MUX inputs are:
I0 = D0
I1 = 0
I2 = 1
I3 = D3
Step 3: Count combinations producing Y = 1.
When S1S0 = 00, output = D0.
D0 = 1 for one combination of AB.
When S1S0 = 01, output = 0.
Number of combinations = 0.
When S1S0 = 10, output = 1.
All four combinations of AB produce Y = 1.
When S1S0 = 11, output = D3.
D3 = 1 for one combination of AB.
Step 4: Total combinations
Total = 1 + 0 + 4 + 1
= 6
Final Answer = 6
#include <stdio.h>
int main(){
int *ptr, a, b, c;
a=5; b=11; c=20;
ptr=&a; *ptr=c; ptr=&c;
a=*(&b); c=*ptr-a;
printf("%d",c);
return(0);
}
Note: Assume that the program compiles and runs successfully.
Step-by-step Explanation:
Initially:
a = 5, b = 11, c = 20
Statement 1: ptr = &a;
Pointer ptr now stores the address of variable a.
Statement 2: *ptr = c;
The value of c (20) is assigned to a.
Therefore, a = 20.
Statement 3: ptr = &c;
Now ptr points to variable c.
Statement 4: a = *(&b);
The value of b is assigned to a.
Therefore, a = 11.
Statement 5: c = *ptr - a;
Since ptr points to c, *ptr = 20.
Therefore:
c = 20 - 11 = 9
Final Output = 9
int func(int start, int end){
int length=end+1-start;
if((length<1)||(start<0)||(end<0)){
return(0);
}
if(length%3==0){
return(func(start+1, end));
} else if(length%3==1){
return(1+func(start, end-1));
} else {
return(func(start+2, end));
}
}
Note: Ignore syntax errors (if any) in the function.
Step 1: Understand the length.
The function calculates:
length = end + 1 - start
If length is less than 1, the function returns 0.
Step 2: Analyze the conditions.
There are three possible cases:
- If length % 3 = 0, the function calls func(start+1, end). Length decreases by 1.
- If length % 3 = 1, the function adds 1 and calls func(start, end-1). Length decreases by 1.
- If length % 3 = 2, the function calls func(start+2, end). Length decreases by 2.
Step 3: Find the maximum return value.
The only condition that adds 1 is:
length % 3 == 1
After this condition executes, length decreases by 1. Its remainder becomes 0, so the function cannot reach remainder 1 again during the same recursive execution.
Therefore, at most one can be added to the return value. This value is achievable by choosing an initial length of 1.
Maximum possible return value = 1
Step 1: Use the determinant property.
For an n × n matrix A:
det(kA) = kn × det(A)
Step 2: Substitute the given values.
Here, n = 4, k = 2 and det(A) = 3.
Therefore:
det(2A) = 24 × 3
Step 3: Calculate.
= 16 × 3
= 48
Final Answer = 48
The conditional probability P(E1 | E2) is equal to ____________. (rounded off to one decimal place)
Step 1: Understand event E1.
E1 requires at least two heads among tosses 2, 4 and 6.
Step 2: Understand event E2.
E2 requires an equal number of heads and tails among tosses 1, 2, 3 and 5. Therefore, exactly two of these four tosses must be heads.
Step 3: Use conditional probability.
Given E2, the probability that toss 2 is Head is 1/2. The probability that toss 2 is Tail is also 1/2.
Tosses 4 and 6 are independent of E2.
Case 1: Toss 2 is Head.
At least one of tosses 4 and 6 must be Head.
Probability = 1 − (1/2 × 1/2) = 3/4
Case 2: Toss 2 is Tail.
Both tosses 4 and 6 must be Heads.
Probability = 1/2 × 1/2 = 1/4
Step 4: Calculate the conditional probability.
P(E1 | E2) = (1/2 × 3/4) + (1/2 × 1/4)
= 3/8 + 1/8
= 4/8
= 0.5
Final Answer = 0.5
For a real number r ∈ (0,1), f(r) = 1 if the second digit after the decimal point in r is one of the four digits 2, 3, 6 and 7. Otherwise, f(r) = 0.
The number of points in (0,1) at which f is discontinuous is __________.
(Answer in integer)
The function depends on the second digit after the decimal point.
The value of the function changes only at points where the second decimal digit changes from one category to another.
The selected digits are 2, 3, 6 and 7.
Within each interval of length 0.1, the changes occur at:
0.02, 0.04, 0.06 and 0.08
Thus, there are 4 discontinuity points in each interval of length 0.1.
The interval (0,1) contains 10 such intervals.
Therefore,
Number of discontinuities = 10 × 4 = 40
Final Answer: 40
Let N be the minimum number of bits needed for the sequence number field in the protocol header such that
i. the sequence numbers do not wrap around before 60 seconds, and
ii. the maximum utilization of the link is achieved.
The value of N is ______. (answer in integer)
Step 1: Calculate the number of bytes transmitted in 60 seconds.
Link bandwidth = 108 bits/second
Time = 60 seconds
Total bits transmitted:
= 108 × 60
= 6 × 109 bits
Total bytes transmitted:
= (6 × 109) / 8
= 750,000,000 bytes
Step 2: Calculate the sequence number bits.
Since sequence numbers must not wrap around before 60 seconds:
2N ≥ 750,000,000
Taking logarithm:
N ≥ log2(750,000,000)
N ≥ 29.48
Therefore, the minimum integer value is:
N = 30 bits
Step 3: Check maximum link utilization.
One-way propagation delay:
= 3000 × 1000 × 5 × 10-9
= 0.015 seconds
Round-trip propagation delay:
= 2 × 0.015 = 0.03 seconds
Bytes in flight:
= (108 × 0.03) / 8
= 375,000 bytes
This requires approximately 19 sequence-number bits, which is less than 30 bits. Hence, the 30-bit sequence number space also satisfies the link-utilization requirement.
Final Answer: 30
.png)
.png)
 Question Paper with Solutions – Free Online Practice Test){kind=link}
0 Comments