GATE CSE 2010

Q11GATE 0MCQ1MDiscrete Mathematics

Let G=(V, E) be a graph. Define $\xi (G)=\sum_{d}i_{d}*d$ , where $i_{d}$ is the number of vertices of degree d in G. If S and T are two different trees with $\xi (S)=\xi (T)$ , then

🚀 Solve in Practice Mode

📖 Explanation

The quantity $\xi(G) = \sum_{d} i_{d} \cdot d$ represents the sum of the degrees of all vertices in a graph G. According to the Handshaking Lemma, the sum of the degrees of all vertices in a graph is equal to twice the number of edges ( $2|E|$ ). Therefore, $\xi(G) = 2|E|$ .

For any tree with $|V|$ vertices, the number of edges $|E|$ is always $|V|-1$ . Let S and T be two trees with $|S|$ and $|T|$ vertices, respectively.

For tree S, the number of edges is $|S|-1$ . Thus, $\xi(S) = 2(|S|-1)$ .
For tree T, the number of edges is $|T|-1$ . Thus, $\xi(T) = 2(|T|-1)$ .

The problem states that $\xi(S) = \xi(T)$ .
Therefore, we have the equation: $2(|S|-1) = 2(|T|-1)$ .

Dividing both sides by 2, we get:
$|S|-1 = |T|-1$

Adding 1 to both sides gives:
$|S| = |T|$

This shows that if the sum of degrees is the same for two trees, they must have the same number of vertices.

Q12GATE 0MCQ1MEngineering Mathematics

Newton-Raphson method is used to compute a root of the equation $x^{2} -13=0$ with 3.5 as the initial value. The approximation after one iteration is

🚀 Solve in Practice Mode

📖 Explanation

The Newton-Raphson method is an iterative technique for finding the roots of a real-valued function, $f(x)$ . The formula for the next approximation, $x_{n+1}$ , based on the current approximation, $x_n$ , is:

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

In this problem, we need to find a root for the equation $x^2 - 13 = 0$ . So, our function is $f(x) = x^2 - 13$ .

The first derivative of this function is $f'(x) = 2x$ .

We are given the initial value $x_0 = 3.5$ . We need to find the approximation after one iteration, which is $x_1$ .

First, let's calculate the values of the function and its derivative at $x_0 = 3.5$ :
$f(3.5) = (3.5)^2 - 13 = 12.25 - 13 = -0.75$
$f'(3.5) = 2 \times 3.5 = 7$

Now, substitute these values into the Newton-Raphson formula:
$x_1 = 3.5 - \frac{-0.75}{7}$
$x_1 = 3.5 + \frac{0.75}{7}$
$x_1 \approx 3.5 + 0.10714$
$x_1 \approx 3.60714$

Thus, the approximation after one iteration is approximately 3.607.

Q13GATE 0MCQ1MDiscrete Mathematics

What is the possible number of reflexive relations on a set of 5 elements?

🚀 Solve in Practice Mode

📖 Explanation

A relation on a set A is a subset of the Cartesian product $A \times A$ . If the set A has $n$ elements, then $A \times A$ has $n^2$ ordered pairs. The total number of possible relations on A is the number of subsets of $A \times A$ , which is $2^{n^2}$ .

A relation R is defined as reflexive if for every element $a \in A$ , the pair $(a, a)$ is in R. These pairs correspond to the main diagonal of the relation matrix.

For a set with $n$ elements, there are $n$ such diagonal pairs. For a relation to be reflexive, all of these $n$ pairs must be included in the relation. This means we have no choice for these $n$ pairs; their inclusion is mandatory.

For the remaining $n^2 - n$ off-diagonal pairs, each one can either be included in the relation or not. This gives us 2 choices for each of these off-diagonal pairs.

Therefore, the total number of possible reflexive relations is $2^{n^2 - n}$ .

Given a set with 5 elements, we have $n=5$ . The number of reflexive relations is:
$2^{5^2 - 5} = 2^{25 - 5} = 2^{20}$ .

Q14GATE 0MCQ1MComputer Organization

The following are some events that occur after a device controller issues an interrupt while process L is under execution. (P) The processor pushes the process status of L onto the control stack. (Q) The processor finishes the execution of the current instruction. (R) The processor executes the interrupt service routine. (S) The processor pops the process status of L from the control stack. (T) The processor loads the new PC value based on the interrupt. Which one of the following is the correct order in which the events above occur?

🚀 Solve in Practice Mode

Q15GATE 0MCQ1MOperating System

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?

🚀 Solve in Practice Mode

📖 Explanation

The problem asks for the page fault rate, which can be derived from the formula for Effective Memory Access Time (EAT).

Let's define the given variables:

$p$ = Page fault rate (the value we want to find).
$M$ = Memory access time when the page is in memory (a 'hit').
$D$ = Memory access time when a page fault occurs (a 'miss'). This includes the time to handle the fault and access the page.
$X$ = Experimentally measured average memory access time (EAT).

The effective access time (X) is a weighted average of the access times for hits and misses:
$X = (\text{Probability of a hit}) \times (\text{Time for a hit}) + (\text{Probability of a miss}) \times (\text{Time for a miss})$

The probability of a hit is $(1-p)$ , and the probability of a miss (a page fault) is $p$ . Substituting the variables:
$X = (1 - p) \cdot M + p \cdot D$

Our goal is to solve this equation for $p$ . Let's rearrange the terms:
$X = M - pM + pD$
$X - M = pD - pM$
$X - M = p(D - M)$

Finally, isolate $p$ by dividing both sides by $(D - M)$ :
$p = \frac{X - M}{D - M}$

This expression correctly represents the page fault rate.

Q16GATE 0MCQ1MDatabase Management System

In an Entity-Relationship (ER) model, suppose R is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in R and that the cardinality of E1 is greater than the cardinality of E2. Which one of the following is true about R?

🚀 Solve in Practice Mode

Q17GATE 0MCQ1MDatabase Management System

Consider the following two tables and four queries in SQL. Which one of the queries above is certain to have an output that is a superset of the outputs of the other three queries?

🚀 Solve in Practice Mode

Q18GATE 0MCQ1MDiscrete Mathematics

Consider the set S = {1, $\omega ,\omega ^{2}$ }, where $\omega$ and $\omega ^{2}$ are cube roots of unity. If * denotes the multiplication operation, the structure (S, *) forms

🚀 Solve in Practice Mode

📖 Explanation

To determine the algebraic structure of (S, ), we check if it satisfies the four axioms of a group. The set is S = {1, $\omega, \omega^2$ }, where $\omega$ and $\omega^2$ are complex cube roots of unity, which means $\omega^3 = 1$ . The operation is multiplication ().

Closure: The product of any two elements in S must also be in S.
- $\omega \times \omega = \omega^2 \in S$
- $\omega \times \omega^2 = \omega^3 = 1 \in S$
- All other products (e.g., $1 \times \omega = \omega$ ) are also in S. The property holds.
Associativity: Multiplication of complex numbers is associative. For any elements a, b, c in S, $(a * b) * c = a * (b * c)$ . This property holds.
Identity Element: There must be an element 'e' in S such that $a * e = a$ for all 'a' in S. The number 1 is the identity element in this set, as $1 * x = x$ for any x in S.
Inverse Element: For each element 'a' in S, there must be an inverse 'a⁻¹' in S such that $a * a⁻¹ = 1$ .
- The inverse of 1 is 1 (since $1 * 1 = 1$ ).
- The inverse of $\omega$ is $\omega^2$ (since $\omega * \omega^2 = 1$ ).
- The inverse of $\omega^2$ is $\omega$ (since $\omega^2 * \omega = 1$ ).

Since all four properties are satisfied, the structure (S, *) forms a group. It cannot be a ring, integral domain, or field as these structures require two operations (e.g., addition and multiplication), and only one operation is defined here.

Q19GATE 0MCQ1MEngineering Mathematics

What is the value of $\lim_{n\rightarrow \infty }(1-\frac{1}{n})^{2n}$ ?

🚀 Solve in Practice Mode

📖 Explanation

This limit can be evaluated using the standard definition of the exponential function, $e$ . One of the fundamental forms of this limit is:

$\lim_{x\to \infty } (1 + \frac{a}{x})^{bx} = e^{ab}$

The given expression is $\lim_{n\rightarrow \infty }(1-\frac{1}{n})^{2n}$ .

We can rewrite this expression to match the standard form:

$\lim_{n\rightarrow \infty }(1+\frac{-1}{n})^{2n}$

By comparing this to the general formula $(1 + \frac{a}{x})^{bx}$ , we can see that $a = -1$ and $b = 2$ .

Therefore, the value of the limit is $e^{a \times b} = e^{-1 \times 2} = e^{-2}$ .

Q20GATE 0MCQ1MDigital Logic

The minterm expansion of f(P,Q,R)=PQ+QR'+PR' is

🚀 Solve in Practice Mode

📖 Explanation

To find the minterm expansion, we need to express the function $f(P,Q,R)=PQ+QR'+PR'$ as a sum of its fundamental products (minterms). A minterm is a product term that includes every variable in either its true or complemented form. We can expand each term in the function to include all variables.

Term PQ: Missing the variable R. We expand it as $PQ = PQ(R+R') = PQR + PQR'$ .
- $PQR$ corresponds to minterm $m_7$ (binary 111).
- $PQR'$ corresponds to minterm $m_6$ (binary 110).
Term QR': Missing the variable P. We expand it as $QR' = QR'(P+P') = PQR' + P'QR'$ .
- $PQR'$ corresponds to minterm $m_6$ (binary 110).
- $P'QR'$ corresponds to minterm $m_2$ (binary 010).
Term PR': Missing the variable Q. We expand it as $PR' = PR'(Q+Q') = PQR' + PQ'R'$ .
- $PQR'$ corresponds to minterm $m_6$ (binary 110).
- $PQ'R'$ corresponds to minterm $m_4$ (binary 100).

The function is the logical OR (sum) of these terms. By collecting all the unique minterms, we get:

$f(P,Q,R) = m_7 + m_6 + m_2 + m_4$

Rearranging them in numerical order, the expansion is $m_2 + m_4 + m_6 + m_7$ .

Q21GATE 0MCQ1MComputer Organization

A main memory unit with a capacity of 4 megabytes is built using 1Mx1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

🚀 Solve in Practice Mode

📖 Explanation

The key principle of DRAM refresh is that it is performed on a row-by-row basis, and this operation occurs in parallel across all chips in the memory bank. Therefore, the total time required to refresh the entire memory unit depends on the number of rows in a single chip, not the total number of chips or the memory capacity.

Identify the number of rows: Each DRAM chip has 1K rows. In computer architecture, K stands for Kilo, which is $2^{10}$ . So, there are $2^{10}$ rows.
Identify the time for one refresh: The time taken for a single refresh operation (refreshing one row) is given as 100 nanoseconds.
Calculate the total time: Since all rows must be refreshed, we multiply the number of rows by the time it takes to refresh one row.
Total Refresh Time = (Number of rows per chip) × (Time for a single row refresh)
Total Refresh Time = $2^{10} \times 100$ nanoseconds.

The memory capacity (4 megabytes) and chip configuration (1Mx1-bit) are provided to determine the number of chips required to build the memory, but this information is not needed to calculate the total refresh time due to the parallel nature of the refresh operation.

Q22GATE 0MCQ1MDigital Logic

P is a 16-bit signed integer. The 2's complement representation of P is $(F87B)_{16}$ . The 2's complement representation of 8*P is

🚀 Solve in Practice Mode

📖 Explanation

This problem involves arithmetic operations on a 2's complement number. Multiplying a binary number by 8 is equivalent to multiplying by $2^3$ .

Understanding the Operation: In binary, multiplication by a power of 2 (like $2^n$ ) can be efficiently performed by an arithmetic left shift of n positions.
Initial Value: The number P is given as $(F87B)_{16}$ in 16-bit 2's complement representation. Let's convert this to binary:
$F \rightarrow 1111$
$8 \rightarrow 1000$
$7 \rightarrow 0111$
$B \rightarrow 1011$
So, P = 1111 1000 0111 1011.
Perform the Shift: To calculate 8 * P, we need to perform an arithmetic left shift by 3 positions.
Original: 1111 1000 0111 1011
After shifting left by 3, the three most significant bits (111) are discarded, and three 0s are appended to the right:
Result: 1000 0111 1011 000 -> 1100 0011 1101 1000
Check for Overflow: The original number is negative (MSB is 1). The resulting number is also negative (MSB is 1). The sign has not changed, indicating no overflow has occurred.
Convert to Hexadecimal: Now, we convert the binary result back to hexadecimal by grouping it into 4-bit chunks:
1100 $\rightarrow$ C
0011 $\rightarrow$ 3
1101 $\rightarrow$ D
1000 $\rightarrow$ 8

Therefore, the 2's complement representation of 8 * P is $(C3D8)_{16}$ .

Q23GATE 0MCQ1MDigital Logic

The Boolean expression for the output f of the multiplexer shown below is

🚀 Solve in Practice Mode

📖 Explanation

To determine the Boolean expression for the multiplexer's output f, we first write the expression based on its select lines (P, Q) and data inputs.

A 4-to-1 multiplexer with select lines P and Q generates an output based on the following logic:
$f = \overline{P}\overline{Q}I_0 + \overline{P}QI_1 + P\overline{Q}I_2 + PQI_3$
From the circuit diagram (represented by the table in the PDF), the data inputs are tied to R or its complement:
- Input $I_0$ (for PQ=00) is R.
- Input $I_1$ (for PQ=01) is $\overline{R}$ .
- Input $I_2$ (for PQ=10) is $\overline{R}$ .
- Input $I_3$ (for PQ=11) is R.
Substitute these input values into the multiplexer equation:
$f = \overline{P}\overline{Q}(R) + \overline{P}Q(\overline{R}) + P\overline{Q}(\overline{R}) + PQ(R)$
Now, we simplify the expression by grouping terms with P and $\overline{P}$ :
$f = \overline{P}(\overline{Q}R + Q\overline{R}) + P(\overline{Q}\overline{R} + QR)$
Recognize the standard expressions for XOR and XNOR:
- The term $(\overline{Q}R + Q\overline{R})$ is the definition of $Q \oplus R$ .
- The term $(\overline{Q}\overline{R} + QR)$ is the definition of the XNOR operation, which is equivalent to $\overline{Q \oplus R}$ .
Substitute these back into the simplified expression for f:
$f = \overline{P}(Q \oplus R) + P(\overline{Q \oplus R})$
This final form is the definition of an XOR operation between P and the term $(Q \oplus R)$ .
$f = P \oplus (Q \oplus R)$
Since the XOR operation is associative, this is equivalent to $P \oplus Q \oplus R$ .

Q24GATE 0MCQ1MData Structure

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

🚀 Solve in Practice Mode

Q25GATE 0MCQ1MC Programming

What does the following program print? #include < stdio.h >

void f (int *p, int * q)  {
    p=q;
    *p=2;
}

int i= 0, j= 1;

int main ( ) {
    f(&i, & j);
    printf( "%d%d \ n", i,j);
    return 0;
}

🚀 Solve in Practice Mode

Q26GATE 0MCQ1MAlgorithm

Two alternative packages A and B are available for processing a database having $10^{k}$ records. Package A requires 0.0001 $n^{2}$ time units and package B requires $10n \log _{{10}} n$ time units to process n records. What is the smallest value of k for which package B will be preferred over A?

🚀 Solve in Practice Mode

📖 Explanation

To determine when package B is preferred over package A, we need to find the smallest value of k for which the time taken by B is less than the time taken by A. Let n be the number of records, where $n = 10^k$ .

Time for Package A: $T_A = 0.0001n^2$
Time for Package B: $T_B = 10n \log_{10} n$

We are looking for the smallest k such that $T_B < T_A$ :
$10n \log_{10} n < 0.0001n^2$

Since n (the number of records) must be positive, we can divide both sides by 10n:
$\log_{10} n < 0.00001n$
$\log_{10} n < 10^{-5}n$

Now, substitute $n = 10^k$ into the inequality:
$\log_{10}(10^k) < 10^{-5}(10^k)$
$k < 10^{k-5}$

Let's test the integer values of k starting from the options to find the smallest one that satisfies this condition:

If k = 5: $5 < 10^{5-5} \implies 5 < 10^0 \implies 5 < 1$ . This is false.
If k = 6: $6 < 10^{6-5} \implies 6 < 10^1 \implies 6 < 10$ . This is true.

Since the condition is false for k=5 and true for k=6, the smallest integer value of k for which package B is preferred is 6.

Q27GATE 0MCQ1MCompiler Design

Which data structure in a compiler is used for managing information about variables and their attributes?

🚀 Solve in Practice Mode

Q28GATE 0MCQ1MCompiler Design

Which languages necessarily need heap allocation in the runtime environment?

🚀 Solve in Practice Mode

Q29GATE 0MCQ1MComputer Network

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

🚀 Solve in Practice Mode

Q30GATE 0MCQ1MComputer Network

Which one of the following is not a client server application?

🚀 Solve in Practice Mode

Q31GATE 0MCQ1MTheory of Computation

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

🚀 Solve in Practice Mode

Q32GATE 0MCQ1MData Structure

Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

🚀 Solve in Practice Mode

Q33GATE 0MCQ1MDatabase Management System

A relational schema for a train reservation database is given below What pids are returned by the following SQL query for the above instance of the tables? SELECT pid FROM Re servation WHERE class = 'AC' AND EXISTS (SELECT * FROM Passenger WHERE age > 65 AND Passenger.pid = Reservation.pid)

🚀 Solve in Practice Mode

Q34GATE 0MCQ1MDatabase Management System

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? I. 2-phase locking II. Time-stamp ordering

🚀 Solve in Practice Mode

Q35GATE 0MCQ1MSoftware Engg

The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?

🚀 Solve in Practice Mode

Q36GATE 0MCQ1MSoftware Engg

What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?

🚀 Solve in Practice Mode

Q37GATE 0MCQ1MOperating System

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned. Which one of the following statements describes the properties achieved?

🚀 Solve in Practice Mode

Q38GATE 0MCQ1MOperating System

A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?

🚀 Solve in Practice Mode

📖 Explanation

This problem analyzes page faults using the First-In, First-Out (FIFO) replacement policy. We can break down the process into two phases.

System Parameters:

Page Frames: 4
Page Replacement Policy: FIFO
Initial State: No pages loaded.

Phase 1: First access to 100 distinct pages
Let the sequence of distinct pages be $p_1, p_2, ..., p_{100}$ .

The first 4 accesses ( $p_1, p_2, p_3, p_4$ ) will each cause a page fault because the frames are initially empty. The frames will contain $[p_1, p_2, p_3, p_4]$ .
For every subsequent access to a new, distinct page ( $p_5$ to $p_{100}$ ), the page will not be in memory, causing a page fault.
Since all 100 pages are distinct, every access in this phase results in a page fault.
After this phase, the 4 frames will hold the last 4 pages accessed: $[p_{97}, p_{98}, p_{99}, p_{100}]$ .
Page Faults in Phase 1 = 100

Phase 2: Accessing the same 100 pages in reverse order
The access sequence is now $p_{100}, p_{99}, p_{98}, p_{97}, p_{96}, ..., p_1$ .

Access $p_{100}$ : This is a hit, as $p_{100}$ is in memory. Faults = 0.
Access $p_{99}$ : This is a hit, as $p_{99}$ is in memory. Faults = 0.
Access $p_{98}$ : This is a hit, as $p_{98}$ is in memory. Faults = 0.
Access $p_{97}$ : This is a hit, as $p_{97}$ is in memory. Faults = 0.
Access $p_{96}$ : This is a fault. The page $p_{96}$ is not in memory. According to FIFO, the oldest page ( $p_{97}$ ) is replaced. The frames become $[p_{98}, p_{99}, p_{100}, p_{96}]$ .
This pattern continues for the remaining 95 accesses (from $p_{95}$ down to $p_1$ ). Each access will cause a fault because the required page will have been replaced long ago.

Number of faults in this phase corresponds to the accesses from $p_{96}$ to $p_1$ , which is 96 pages.
Page Faults in Phase 2 = 96

Total Page Faults
Total Faults = Faults (Phase 1) + Faults (Phase 2) = $100 + 96 = 196$ .

Q39GATE 0MCQ1MOperating System

Which of the following statements are true? I. Shortest remaining time first scheduling may cause starvation II. Preemptive scheduling may cause starvation III. Round robin is better than FCFS in terms of response time

🚀 Solve in Practice Mode

Q40GATE 0MCQ2MDiscrete Mathematics

Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?

🚀 Solve in Practice Mode

📖 Explanation

To find the probability of a computer being declared faulty, we can use the law of total probability. A computer can be declared faulty in two mutually exclusive scenarios:

The computer is actually faulty, and the test correctly identifies it as faulty.
The computer is not faulty, and the test incorrectly identifies it as faulty.

Let's define the events:

$F$ : The event that a computer has a faulty assembly. $P(F) = p$ .
$NF$ : The event that a computer is not faulty. $P(NF) = 1 - p$ .
$DF$ : The event that a computer is declared faulty by the test.

We are given that the test gives the correct result with probability $q$ . This can be interpreted as:

The probability of declaring a faulty computer as faulty is $q$ . This is the conditional probability $P(DF | F) = q$ .
The probability of declaring a non-faulty computer as non-faulty is also $q$ . Therefore, the probability of incorrectly declaring a non-faulty computer as faulty is $1-q$ . This is $P(DF | NF) = 1 - q$ .

The total probability of being declared faulty, $P(DF)$ , is the sum of the probabilities of the two scenarios:

$P(DF) = P(\text{scenario 1}) + P(\text{scenario 2})$

Using the formula for conditional probability, $P(A \cap B) = P(A|B) \times P(B)$ :

Probability of Scenario 1 (is faulty AND declared faulty):
$P(DF \cap F) = P(DF | F) \times P(F) = q \times p = pq$
Probability of Scenario 2 (is not faulty AND declared faulty):
$P(DF \cap NF) = P(DF | NF) \times P(NF) = (1 - q) \times (1 - p)$

Summing these gives the total probability:

$P(DF) = pq + (1 - p)(1 - q)$

Q41GATE 0MCQ2MDiscrete Mathematics

What is the probability that divisor of $10^{99}$ is a multiple of $10^{96}$ ?

🚀 Solve in Practice Mode

📖 Explanation

To solve this problem, we need to find the total number of divisors of $10^{99}$ and the number of those divisors that are multiples of $10^{96}$ . The ratio of these two numbers will give us the required probability.

Total Number of Divisors (Total Outcomes):
First, we find the prime factorization of the number: $10^{99} = (2 \times 5)^{99} = 2^{99} \times 5^{99}$ .
Any divisor of this number will be of the form $2^a \times 5^b$ , where the exponents 'a' and 'b' can range from 0 to 99.
The number of choices for 'a' is $99+1 = 100$ .
The number of choices for 'b' is $99+1 = 100$ .
The total number of divisors is the product of these choices: $100 \times 100 = 10000$ .
Favorable Divisors (Favorable Outcomes):
We are looking for divisors that are multiples of $10^{96}$ . Let the divisor be $D$ . For $D$ to be a multiple of $10^{96}$ , the exponents in its prime factorization must be greater than or equal to the exponents in the prime factorization of $10^{96}$ .
The prime factorization of the multiple is $10^{96} = 2^{96} \times 5^{96}$ .
So, for our divisor $D = 2^a \times 5^b$ , we must have $a \ge 96$ and $b \ge 96$ .
Since $D$ is a divisor of $10^{99}$ , we also know $a \le 99$ and $b \le 99$ .
Thus, the possible values for 'a' are {96, 97, 98, 99}, which are 4 choices.
Similarly, the possible values for 'b' are {96, 97, 98, 99}, which are 4 choices.
The total number of favorable divisors is $4 \times 4 = 16$ .
Calculate the Probability:
Probability = (Favorable Outcomes) / (Total Outcomes) = $\frac{16}{10000}$ .
Simplifying this fraction gives $\frac{1}{625}$ .

Q42GATE 0MCQ2MDiscrete Mathematics

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2 III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1

🚀 Solve in Practice Mode

📖 Explanation

A sequence of numbers can be the degree sequence of a simple graph only if it satisfies certain properties. Let's check the given sequences against two fundamental properties of simple graphs.

Let 'n' be the number of vertices in the graph.

Property 1: Maximum Degree
In a simple graph (no self-loops or multiple edges between the same two vertices), the maximum degree of any vertex cannot exceed $n-1$ .

Property 2: Handshaking Lemma
The sum of all degrees in a graph must be an even number, as it is equal to twice the number of edges.

Let's analyze each sequence:

I. 7, 6, 5, 4, 4, 3, 2, 1

Number of vertices, $n=8$ .
The maximum degree is 7, which is equal to $n-1 = 7$ . This is valid.
The sum of degrees is $7+6+5+4+4+3+2+1 = 32$ , which is even. This is valid.
This sequence is graphical (can be verified with the Havel-Hakimi theorem).

II. 6, 6, 6, 6, 3, 3, 2, 2

Number of vertices, $n=8$ .
The maximum degree is 6, which is less than $n-1 = 7$ . This is valid.
The sum of degrees is $6+6+6+6+3+3+2+2 = 34$ , which is even. This is valid.
Although it passes the basic checks, applying the Havel-Hakimi algorithm (a recursive test) reveals it is not a graphical sequence. After a few steps, the algorithm results in a sequence with a negative number, which is impossible.

III. 7, 6, 6, 4, 4, 3, 2, 2

Number of vertices, $n=8$ .
The maximum degree is 7, which is equal to $n-1 = 7$ . This is valid.
The sum of degrees is $7+6+6+4+4+3+2+2 = 34$ , which is even. This is valid.
This sequence is graphical.

IV. 8, 7, 7, 6, 4, 2, 1, 1

Number of vertices, $n=8$ .
The sequence contains a degree of 8. In a simple graph with 8 vertices, a single vertex can be connected to at most 7 other vertices. Therefore, the maximum possible degree is 7.
Since $8 > (n-1)$ , this sequence violates the maximum degree property and cannot be the degree sequence of a simple graph.

Therefore, sequences II and IV cannot be the degree sequences of any simple graph.

Q43GATE 0MCQ2MEngineering Mathematics

Consider the following matrix

A=\begin{bmatrix} 2 & 3\\ X&Y \end{bmatrix}

If the eigenvalues of A are 4 and 8, then

🚀 Solve in Practice Mode

📖 Explanation

To find the values of X and Y, we can use two fundamental properties that relate a matrix to its eigenvalues:

Sum of Eigenvalues = Trace of the Matrix
The trace of a matrix is the sum of the elements on its main diagonal. For matrix

A=\begin{bmatrix} 2 & 3\\ X&Y \end{bmatrix}

, the trace is $2+Y$ .
The given eigenvalues are $\lambda_1 = 4$ and $\lambda_2 = 8$ . Their sum is $4+8=12$ .
Equating the sum of eigenvalues to the trace:
$12 = 2 + Y$
Solving for Y, we get:
$Y = 12 - 2 = 10$

Product of Eigenvalues = Determinant of the Matrix
The determinant of a 2x2 matrix

\begin{bmatrix} a & b\\ c&d \end{bmatrix}

is $ad-bc$ . For matrix A, the determinant is $(2 \times Y) - (3 \times X) = 2Y - 3X$ .
The product of the given eigenvalues is $4 \times 8 = 32$ .
Equating the product of eigenvalues to the determinant:
$32 = 2Y - 3X$

Now, we can substitute the value of Y we found in the first step into this equation:
$32 = 2(10) - 3X$
$32 = 20 - 3X$
$3X = 20 - 32$
$3X = -12$
Solving for X, we get:
$X = -4$

Thus, the values are $X = -4$ and $Y = 10$ .

Q44GATE 0MCQ2MDiscrete Mathematics

Suppose the predicate F(x,y,t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula $\forall x \exists y \exists t(\neg F (x, y, t))$ ?

🚀 Solve in Practice Mode

📖 Explanation

Let's break down the given logical formula and translate it into plain English. The predicate $F(x,y,t)$ means 'person x can fool person y at time t'.

The formula is: $\forall x \exists y \exists t (\neg F(x,y,t))$

We can translate this piece by piece from left to right:

$\forall x$ : This means "For every person x" or "Everyone".
$\exists y$ : This means "there exists a person y" or "for some person y".
$\exists t$ : This means "there exists a time t" or "at some time t".
$\neg F(x,y,t)$ : This is the negation, meaning "person x cannot fool person y at time t".

Combining these parts, the formula reads: "For every person x, there exists some person y and some time t, such that x cannot fool y at t."

Now, let's analyze the given options to find the one that is logically equivalent to this statement:

A. Everyone can fool some person at some time: This translates to $\forall x \exists y \exists t (F(x,y,t))$ . This is the opposite of our formula.
B. No one can fool everyone all the time: Let's translate this carefully.
- "No one can..." is equivalent to "For all people, it is not the case that...". This is $\forall x (\neg ...)$ .
- "...fool everyone all the time." For a person x, this means they fool every person y at every time t. This translates to $\forall y \forall t (F(x,y,t))$ .
- So, option B translates to: $\forall x (\neg (\forall y \forall t (F(x,y,t))))$ .
- Using De Morgan's laws for quantifiers, which state that $\neg(\forall z P(z)) \equiv \exists z (\neg P(z))$ , we can simplify the inner part:
  $\neg (\forall y \forall t (F(x,y,t))) \equiv \exists y (\neg (\forall t (F(x,y,t)))) \equiv \exists y \exists t (\neg F(x,y,t))$ .
- Substituting this back into the full expression for option B gives: $\forall x \exists y \exists t (\neg F(x,y,t))$ .
- This matches the original formula exactly.
C. Everyone cannot fool some person all the time: This statement is ambiguous in English but doesn't naturally map to the given formula.
D. No one can fool some person at some time: This translates to $\forall x \neg(\exists y \exists t (F(x,y,t)))$ , which simplifies to $\forall x \forall y \forall t (\neg F(x,y,t))$ . This means "nobody can ever fool anybody," which is different.

Therefore, option B is the best English expression for the given logical formula.

Q45GATE 0MCQ2MDigital Logic

What is the Boolean Algebra for the output f of the combinational logic circuit of NOR gates given below?

🚀 Solve in Practice Mode

📖 Explanation

To determine the Boolean expression for the output f of a logic circuit, we must trace the logic from the inputs (P, Q, R) to the final output. The fundamental gate used here is the NOR gate, whose logical function is $A \text{ NOR } B = \overline{A+B}$ .

Since the specific circuit diagram is not provided, we must analyze the problem based on the provided correct answer, $f = \overline{Q+R}$ . This means the final output f is the result of a NOR operation on inputs Q and R, and it is independent of input P. Many complex-looking circuits can simplify to a much simpler expression. A common way this occurs in exam questions is through logical redundancy.

Let's construct a plausible example circuit made of NOR gates that demonstrates this principle and yields the correct output:

Assume a part of the circuit is designed to create a constant logical '0'. This can be done by feeding a signal and its inverse into a NOR gate. For example, let's create a signal G1 using input P:
- First, create an inverter from a NOR gate: $\overline{P} = \overline{P+P}$ .
- Now, feed P and $\overline{P}$ into another NOR gate: $G_1 = \overline{P + \overline{P}}$ .
- Since $P + \overline{P} = 1$ in Boolean algebra, the expression becomes $G_1 = \overline{1} = 0$ .
Now, let's assume this G1 signal (which is always 0) is fed into a final NOR gate along with the other inputs, Q and R. Let the final output be f.
- $f = \overline{G_1 + Q + R}$
Substitute the value of G1 into the final expression:
- $f = \overline{0 + Q + R}$
Simplify the expression. The '0' in a logical OR operation has no effect ( $0+X=X$ ).
- $f = \overline{Q+R}$

This hypothetical circuit demonstrates how an input like P can be part of a circuit but ultimately have no effect on the final output, which simplifies to $\overline{Q+R}$ .

Q46GATE 0MCQ2MDigital Logic

In the sequential circuit shown below, if the initial value of the output $Q_{1}Q_{0}$ is 00, what are the next four values of $Q_{1}Q_{0}$ ?

🚀 Solve in Practice Mode

📖 Explanation

The sequence of states 11, 10, 01, 00 following an initial state of 00 indicates that the circuit is a 2-bit synchronous down-counter that wraps around (i.e., the full sequence is 00 → 11 → 10 → 01 → 00). Let's determine the logic for the T-flip-flops that would produce this sequence, where the state is $Q_1Q_0$ .

A T-flip-flop toggles its output ( $Q^+ = Q'$ ) if T=1, and holds its state ( $Q^+ = Q$ ) if T=0.

Transition 00 → 11: Both $Q_1$ and $Q_0$ toggle. Required inputs: $T_1=1, T_0=1$ .
Transition 11 → 10: $Q_1$ holds, $Q_0$ toggles. Required inputs: $T_1=0, T_0=1$ .
Transition 10 → 01: Both $Q_1$ and $Q_0$ toggle. Required inputs: $T_1=1, T_0=1$ .
Transition 01 → 00: $Q_1$ holds, $Q_0$ toggles. Required inputs: $T_1=0, T_0=1$ .

From this analysis, we can deduce the input logic:

The input $T_0$ is always 1.
The input $T_1$ is 1 when $Q_0$ is 0, and 0 when $Q_0$ is 1. Thus, $T_1 = Q_0'$ .

Given this circuit logic, if the initial state is $Q_1Q_0 = 00$ , the next clock pulse will cause a transition to 11. The subsequent three pulses will produce the states 10, 01, and 00, respectively. Therefore, the next four values are 11, 10, 01, 00.

Q47GATE 0MCQ2MComputer Organization

A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL instruction, and 6 clock cycles for DIV instruction respectively. Operand forwarding is used in the pipeline. What is the number of clock cycles needed to execute the following sequence of instructions?

🚀 Solve in Practice Mode

Q48GATE 0MCQ2MEngineering Mathematics

The weight of a sequence $a_{0},a_{1},...,a_{n-1}$ of real numbers is defined as $a_{0}+a_{1}/2+...+a_{n-1}/2^{n-1}$ A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of $a_{0},a_{1},...,a_{n-1}$ and Y the maximum possible weight of a subsequence of $a_{0},a_{1},...,a_{n-1}$ . Then X is equal to

🚀 Solve in Practice Mode

📖 Explanation

Let's define the problem formally. The weight of a sequence $b = (b_0, b_1, ..., b_{k-1})$ is $W(b) = \sum_{i=0}^{k-1} \frac{b_i}{2^i}$ .
$X$ is the maximum weight of a subsequence of $S = (a_0, a_1, ..., a_{n-1})$ .
$Y$ is the maximum weight of a subsequence of $S' = (a_1, a_2, ..., a_{n-1})$ .

To find the maximum weight subsequence for $S$ , we can consider two possibilities regarding the first element, $a_0$ .

Case 1: The optimal subsequence does not include $a_0$ .
If the subsequence with the maximum weight does not contain $a_0$ , it must be formed entirely from the elements of $S' = (a_1, a_2, ..., a_{n-1})$ . By definition, the maximum weight that can be achieved from a subsequence of $S'$ is $Y$ .

Case 2: The optimal subsequence includes $a_0$ .
If we include $a_0$ , it will be the first term of the subsequence. Its contribution to the total weight will be $a_0/2^0 = a_0$ . The rest of the subsequence will be chosen from $S' = (a_1, a_2, ..., a_{n-1})$ . Let this be a subsequence $S'_{sub}$ . The total weight will be $a_0$ plus the weight contribution from $S'_{sub}$ . When elements of $S'_{sub}$ follow $a_0$ , their positions in the weight calculation are shifted by one. For example, an element $a_k$ which was at index $k-1$ in $S'$ is now at index $k$ in the full subsequence. Its weight contribution changes from $a_k/2^{k-1}$ to $a_k/2^k$ . This means the total weight contribution from $S'_{sub}$ is halved.
To maximize the total weight, we should choose $S'_{sub}$ to be the subsequence from $S'$ with the maximum possible weight, which is $Y$ . The weight of this part will be $Y/2$ . So, the maximum total weight in this case is $a_0 + Y/2$ .

Conclusion:
The overall maximum weight $X$ is the greater of the values from the two cases.
Therefore, $X = \max(Y, a_0 + Y/2)$ .

Q49GATE 0MCQ2MC Programming

What is the value printed by the following C program? #include < stdio.h >

int f(int * a, int n)  {
    if(n<=0)return 0;
    else if(*a% 2 ==0) return *a+f(a+1,n-1);
    else return *a-f(a+1,n-1);
}

int main ( )  {
    int a[ ]  {
        12, 7, 13, 4, 11, 6
    }
    ;
    printf ("%d", f(a,6));
    return 0;
}

🚀 Solve in Practice Mode

Q50GATE 0MCQ2MData Structure

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef struct node { int value; struct node *next; } Node; Node *move_to_front(Node *head) { Node *p, *q; if ((head = = NULL: || (head->next = = NULL)) return head; q = NULL; p = head; while (p-> next !=NULL) { q=P; p=p->next; } _______________________________ return head; } Choose the correct alternative to replace the blank line.

🚀 Solve in Practice Mode

Q51GATE 0MCQ2MCompiler Design

The program below uses six temporary variables a, b, c, d, e, f. a =1 b= 10 c =20 d= a +b e= c +d f =c +e b= c+ e e =b +f d =5 +e return d +f Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

🚀 Solve in Practice Mode

Q52GATE 0MCQ2MCompiler Design

The grammar S $\rightarrow$ aSa|bS|c is

🚀 Solve in Practice Mode

📖 Explanation

To determine if the grammar S $\rightarrow$ aSa|bS|c is LL(1) and/or LR(1), we analyze its properties.

LL(1) Analysis:
A grammar is LL(1) if, for a non-terminal S, the FIRST sets of the right-hand sides of its productions are disjoint.
The productions for S are:

S $\rightarrow$ aSa
S $\rightarrow$ bS
S $\rightarrow$ c

Let's find the FIRST set for each production's right-hand side:

FIRST(aSa) = {a}
FIRST(bS) = {b}
FIRST(c) = {c}

The sets {a}, {b}, and {c} are mutually disjoint. This means a top-down parser can uniquely choose which production to use by looking at just one next input symbol (the '1' in LL(1)). Therefore, the grammar is LL(1).

LR(1) Analysis:
A grammar is LR(1) if an LR(1) parsing table can be constructed for it without any shift-reduce or reduce-reduce conflicts. Every LL(1) grammar is also an LR(1) grammar. Since we have already established that the grammar is LL(1), it must also be LR(1). The grammar is simple, unambiguous, and not left-recursive, and the productions start with distinct terminals, which avoids the common causes of conflicts in LR parsers.

Since the grammar is both LL(1) and LR(1), the correct option is C.

Q53GATE 0MCQ2MTheory of Computation

Let L = {w $\in$ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?

🚀 Solve in Practice Mode

Q54GATE 0MCQ2MTheory of Computation

Consider the languages $L1=\{0^{i}1^{j}\;| \; i\neq j\}$ . $L2=\{0^{i}1^{j}\;| \; i=j\}$ . $L3=\{0^{i}1^{j}\;| \; i=2j+1\}$ . $L4=\{0^{i}1^{j}\;| \; i \neq 2j\}$ Which one of the following statements is true?

🚀 Solve in Practice Mode

📖 Explanation

A language is context-free (CFL) if it can be accepted by a Pushdown Automaton (PDA). Let's analyze each language:

$L2 = \{0^i1^j \| \; i=j\}$ : This is a classic example of a CFL. A PDA can push a symbol onto the stack for each '0' it reads. Then, for each '1' it reads, it pops a symbol. If the stack is empty exactly when the input string ends, the string is accepted. Thus, L2 is context-free.
$L3 = \{0^i1^j \| \; i=2j+1\}$ : This language also involves comparing counts, which a PDA can handle. A PDA can push a symbol for each '0'. Then, for each '1', it can pop two symbols. After reading all '1's, if there is exactly one symbol remaining on the stack, the condition $i=2j+1$ is met, and the string is accepted. Thus, L3 is context-free.
$L1 = \{0^i1^j \| \; i \neq j\}$ : This language is the union of two other languages: $L_{i>j} = \{0^i1^j \| \; i>j\}$ and $L_{i<j} = \{0^i1^j \| \; i<j\}$ .
- For $L_{i>j}$ , a PDA can push for '0's and pop for '1's. It accepts if the input ends and the stack is not empty.
- For $L_{i<j}$ , a PDA can push for '0's and pop for '1's. It accepts if the stack becomes empty but there are still '1's left in the input.
  Both $L_{i>j}$ and $L_{i<j}$ are context-free. Since CFLs are closed under union, L1 is also context-free. A PDA for L1 would non-deterministically guess whether $i>j$ or $i<j$ and follow the appropriate logic.
$L4 = \{0^i1^j \| \; i \neq 2j\}$ : Similar to L1, this language is the union of $L_{i>2j}$ and $L_{i<2j}$ . A PDA can handle the $i=2j$ comparison (as shown for L3). By slightly modifying the acceptance condition (accepting if the stack is not empty when it should be, or vice-versa), we can create PDAs for both $i>2j$ and $i<2j$ . Since L4 is the union of these two CFLs, L4 is also context-free.

Since all four languages are context-free, the statement 'All are context free' is true.

Q55GATE 0MCQ2MTheory of Computation

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

🚀 Solve in Practice Mode

📖 Explanation

The language L is the set of all substrings of a given string w of length n. We need to find the minimum number of states for an NFA that accepts L.

Let's establish a lower bound. Consider a special case where w = a^n (the character 'a' repeated n times). The substrings of w are ε, a, a^2, ..., a^n. To accept this language, an NFA must be able to distinguish between counts of 'a's up to n. The longest string to accept is a^n. An NFA that accepts a^n but no string longer than a^n (since a^{n+1} is not a substring) cannot contain a cycle that can be traversed. A simple, acyclic path of length n requires n+1 states. Therefore, at least n+1 states are required.

Now, let's show that n+1 states are also sufficient for any string w. We can construct an NFA as follows:

Create n+1 states, labeled q_0, q_1, ..., q_n.
Let q_0 be the start state.
To accept any substring, we must be able to start and end our match at any position. We can make all states q_0, ..., q_n final (accepting) states. This allows substrings of any length to be accepted, including the empty string ε (by starting and ending at q_0).
Let w = w_1w_2...w_n. Create a 'backbone' of transitions: for each i from 1 to n, add a transition from q_{i-1} to q_i on character w_i.
To allow a substring to start at any position, add ε-transitions from the initial state q_0 to all other states q_1, ..., q_n.

This construction is slightly more complex than needed. A simpler NFA with n+1 states is possible:

Create n+1 states q_0, ..., q_n.
q_0 is the start state.
Create the backbone: a transition from q_{i-1} to q_i on w_i for i = 1 to n.
From q_0, add a transition on any character c to q_j for all j where w_j = c.

The most standard and simple construction that proves sufficiency is:

Create n+1 states, q_0, ..., q_n.
For i from 1 to n, add a transition from q_{i-1} to q_i on w_i.
To start a substring from any character w_i, add an ε-transition from the start state q_0 to each state q_{i-1}.
To end a substring at any character w_j, make all states q_1, ..., q_n final states. (If ε is a substring, q_0 must also be final).

Since we have a lower bound of n+1 and a construction that achieves it, the minimum number of states is n+1.

Q56GATE 0MCQ2MDatabase Management System

Consider the following schedule for transactions T1, T2 and T3: Which one of the schedules below is the correct serialization of the above?

🚀 Solve in Practice Mode

Q57GATE 0MCQ2MDatabase Management System

The following functional dependencies hold for relations R(A, B, C) and S(B, D, E) B $\rightarrow$ A, A $\rightarrow$ C The relation R contains 200tuples and the relation S contains 100tuples. What is the maximum number of tuples possible in the natural join R $\Join$ S?

🚀 Solve in Practice Mode

Q58GATE 0MCQ2MSoftware Engg

The following program is to be tested for statement coverage: begin if (a ==b) {S1; exit;} else if (c ==d) {S2;} else {S3; exit;} S4; end The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given. T1 : a, b, c and d are all equal T2 : a, b, c and d are all distinct T3 : a=b and c !=d T4 : a !=b and c=d Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?

🚀 Solve in Practice Mode

Q59GATE 0MCQ2MOperating System

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0. How many times will process P0 print '0'? How many times will process P0 print '0'?

🚀 Solve in Practice Mode

Q60GATE 0MCQ2MOperating System

A system has n resources $R_{0},...R_{n-1}$ , and k processes $P_{0},...P_{k-1}$ . The implementation of the resource request logic of each process $P_{i}$ is as follows: if (i%2= = 0) { if (i < n) request [latex]R_{i}[/latex] ; if (i+2 < n)request [latex]R_{i+2}[/latex]; } else { if (i < n) request [latex]R_{n-i}[/latex]; if (i+2 < n)request [latex]R_{n-i-2}[/latex] ; } In which one of the following situations is a deadlock possible?

🚀 Solve in Practice Mode

📖 Explanation

A deadlock can occur if a circular wait condition arises among processes competing for resources. Let's analyze the resource request patterns:

An even process P_i requests resources in increasing order of index: first R_i, then R_{i+2}.
An odd process P_j requests resources in decreasing order of index: first R_{n-j}, then R_{n-j-2}.

A circular wait, and thus a potential deadlock, can occur between an even-indexed process and an odd-indexed process. Let's formalize the deadlock condition:
Suppose an even process P_i acquires R_i and waits for R_{i+2}. A deadlock happens if an odd process P_j has acquired R_{i+2} and is waiting for R_i.

For this scenario to be possible, the request sequence of P_j must be request(R_{i+2}) followed by request(R_i). Comparing this with P_j's logic (request(R_{n-j}) then request(R_{n-j-2})), we get:

R_{i+2} = R_{n-j} => i + 2 = n - j
R_i = R_{n-j-2} => i = n - j - 2

Both equations simplify to i + j = n - 2. A deadlock is possible if we can find an even process index i and an odd process index j such that 0 <= i, j < k and they satisfy this equation.

Let's check the given options:

A. n = 40, k = 26: Requires i + j = 38. If i is even and j is odd, their sum i + j must be odd. Since 38 is even, this is impossible.
B. n = 21, k = 12: Requires i + j = 19. The sum is odd, which is consistent with i being even and j being odd. We need to find if such i, j exist within the process limit k=12. For example, if we pick i=8 (even, <12), then j = 19 - 8 = 11. Since j=11 is odd and also <12, this pair of processes exists. P_8 would request R_8 then R_{10}, while P_{11} would request R_{21-11}=R_{10} then R_{21-11-2}=R_8. This creates a circular wait. Thus, deadlock is possible.
C. n = 20, k = 10: Requires i + j = 18. Sum is even. Impossible for an even i and an odd j.
D. n = 41, k = 19: Requires i + j = 39. Sum is odd, so this is potentially possible. The maximum possible i is 18 (even, <19) and the maximum possible j is 17 (odd, <19). The maximum possible sum is i_{max} + j_{max} = 18 + 17 = 35. Since 35 < 39, no pair (i, j) can satisfy i + j = 39. Deadlock is not possible.

Therefore, only the situation in B can lead to a deadlock.

Q61GATE 0MCQ2MComputer Network

Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used if A and B should belong to the same network?

🚀 Solve in Practice Mode

Q62GATE 0MCQ2MComputer Organization

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively. When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?

🚀 Solve in Practice Mode

Q63GATE 0MCQ2MAlgorithm

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry $W_{ij}$ in the matrix W below is the weight of the edge {i, j}.

\begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

🚀 Solve in Practice Mode

Q64GATE 0MCQ2MData Structure

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

🚀 Solve in Practice Mode

Q65GATE 0MCQ2MComputer Network

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?

🚀 Solve in Practice Mode

Practice GATE CSE 2010 questions with full analytics — free

General Aptitude10 questions

CSE55 questions