GATE CS 2015 Set 1

The sentence is a negative interrogative. In English grammar, 'any' is typically used in negative sentences and questions.

• (A) 'any paper': Correct usage. 'Didn't you buy any paper?' implies the speaker expected the person to buy paper or is asking for confirmation.
• (B) 'much paper': Grammatically possible but less idiomatic in this specific context compared to 'any'.
• (C) 'no paper': 'Didn't you buy no paper' creates a double negative which is non-standard or confusing.
• (D) 'a few paper': Incorrect because 'paper' is an uncountable noun; it should be 'a little paper' or 'a few sheets of paper'.

Therefore, option (A) is the most appropriate choice.

The phrase 'enjoyed herself immensely' means she had a very good time or a great amount of fun.

• (A) 'terrible' means very bad.
• (B) 'horrible' means very unpleasant.
• (C) 'terrific' means of great size, amount, or intensity; excellent. This matches the positive sentiment of 'enjoyed immensely'.
• (D) 'terrifying' means causing terror or fear.

Thus, option (C) is the closest in meaning.

We need to identify the pair where the words are not synonyms or related in meaning as indicated.

• (A) Acquiescence means the reluctant acceptance of something without protest; Submission is a synonym. (Correct pair)
• (B) Wheedle means to use flattery or coaxing in order to persuade someone to do something or give one something. Roundabout means not following a short direct route or method. These words are unrelated in meaning. (Incorrect pair)
• (C) Flippancy means lack of respect or seriousness; Lightness (in terms of attitude) is a synonym. (Correct pair)
• (D) Profligate means recklessly extravagant or wasteful in the use of resources; Extravagant is a synonym. (Correct pair)

Therefore, option (B) is the incorrect combination.

To determine the number of steps in the stairs extending from the first floor to the second floor, we need to relate the total vertical height between the floors to the dimensions of the steps. We are given:

• The vertical distance (height) between the two floors is $H = 9$ feet.

Let $n$ be the number of steps in the staircase, and let $h$ be the height (rise) of each step. The total vertical height is given by the formula:$$H = n \times h$$Now, let us analyze the sufficiency of each statement individually:

Analyzing Statement (I): "Each step is 3/4 foot high."

• This statement gives the height of each step: $h = \frac{3}{4}$ foot.
• Using the formula:

$$9 = n \times \frac{3}{4}$$ $$n = 9 \times \frac{4}{3} = 12 \text{ steps}$$

• Since we can uniquely determine the number of steps, Statement I alone is sufficient.

Analyzing Statement (II): "Each step is 1 foot wide."

• This statement gives the width (run) of each step.
• The width of a step does not affect the vertical height of the staircase. Without knowing the height of each step, we cannot determine the number of steps.
• Therefore, Statement II alone is not sufficient.

Conclusion

Statement I alone is sufficient to answer the question, but Statement II alone is not sufficient.Correct Option: A

To find the probability that the sum of the two randomly selected numbers (one from Set $A$ and one from Set $B$) equals $16$, we determine the total number of possible outcomes and the number of favorable outcomes.

Step 1: Find the Total Number of Possible Outcomes

Let $a \in A$ and $b \in B$.

• The number of elements in Set $A$ is $n(A) = 4$.
• The number of elements in Set $B$ is $n(B) = 5$.

Since one number is selected from each set independently, the total number of possible pairs $(a, b)$ is:$$n(S) = n(A) \times n(B) = 4 \times 5 = 20$$

Step 2: Find the Number of Favorable Outcomes

We need to find the pairs $(a, b)$ such that $a + b = 16$, where $a \in \{2, 3, 4, 5\}$ and $b \in \{11, 12, 13, 14, 15\}$.Let us check the possible values for $a$:

• If $a = 2$, then $b = 16 - 2 = 14$ (which is in $B$). $\rightarrow (2, 14)$ is a valid pair.
• If $a = 3$, then $b = 16 - 3 = 13$ (which is in $B$). $\rightarrow (3, 13)$ is a valid pair.
• If $a = 4$, then $b = 16 - 4 = 12$ (which is in $B$). $\rightarrow (4, 12)$ is a valid pair.
• If $a = 5$, then $b = 16 - 5 = 11$ (which is in $B$). $\rightarrow (5, 11)$ is a valid pair.

Thus, the set of favorable outcomes $E$ is:$$E = \{(2, 14), (3, 13), (4, 12), (5, 11)\}$$The number of favorable outcomes is $n(E) = 4$.

Step 3: Calculate the Probability

The probability $P$ that the sum of the two numbers equals $16$ is given by:$$P = \frac{n(E)}{n(S)} = \frac{4}{20} = \frac{1}{5} = 0.20$$Correct Option: A

To find the correct meaning of the underlined idiom "**took to their heels**", let us analyze its idiomatic usage: The phrase "to take to one's heels" is an established English idiom which means to run away rapidly, flee, or escape from a situation, especially out of fear or to avoid capture. In the given sentence:
> "The chain snatchers took to their heels when the police party arrived."

The arrival of the police would naturally cause criminals (chain snatchers) to flee or run away to avoid being caught.

• Option A (took shelter in a thick jungle): This is too specific and not the general meaning of the idiom.
• Option B (open indiscriminate fire): This means to start shooting, which is incorrect.
• Option C (took to flight): "To take to flight" or "take flight" means to run away or flee from danger. This directly matches the meaning of "took to their heels".
• Option D (unconditionally surrendered): This means to give up, which is the opposite of running away.

Therefore, the correct option is C.

Let's analyze each course of action based on the statement that there has been a significant drop in the water level in the lakes supplying water to the city.Course of action (I): "The water supply authority should impose a partial cut in supply to tackle the situation."
This is a direct and logical response to a water shortage. Reducing supply helps conserve the remaining water and manage the crisis. Therefore, statement I follows.Course of action (II): "The government should appeal to all the residents through mass media for minimal use of water."
This is a proactive measure to raise public awareness and encourage responsible water usage. It promotes conservation through public cooperation. Therefore, statement II follows.Course of action (III): "The government should ban the water supply in lower areas."
Banning water supply in specific areas (like "lower areas") is discriminatory and unjust. It does not address the overall water shortage equitably and could lead to social unrest and hardship for residents in those areas. This is not a fair or sustainable solution. Therefore, statement III does not follow.Based on the analysis, only statements I and II follow.The final answer is $\boxed{A}$

Let's break down the problem step-by-step:

• Given: 40 males in Electrical Engineering.
• Male to Female ratio in each department = 5:4.
• If 5 parts (males) = 40, then 1 part = $40 / 5 = 8$.
• Number of females in Electrical Engineering = 4 parts = $4 \times 8 = 32$.
• Total students in Electrical Engineering = Males + Females = $40 + 32 = 72$.

2. Calculate the total number of students in the college:

• From the pie chart, Electrical Engineering represents 20% of the total students.
• If 20% of total students = 72, then 100% (total students) = $72 \times (100 / 20) = 72 \times 5 = 360$ students.

3. Calculate female students in the Civil department:

• From the pie chart, Civil department represents 30% of the total students.
• Total students in Civil department = $360 \times 0.30 = 108$.
• Male to Female ratio in Civil = 5:4. Total parts = $5+4 = 9$.
• 1 part = $108 / 9 = 12$.
• Number of females in Civil department = 4 parts = $4 \times 12 = 48$.

4. Calculate female students in the Mechanical department:

• From the pie chart, Mechanical department represents 10% of the total students.
• Total students in Mechanical department = $360 \times 0.10 = 36$.
• Male to Female ratio in Mechanical = 5:4. Total parts = $5+4 = 9$.
• 1 part = $36 / 9 = 4$.
• Number of females in Mechanical department = 4 parts = $4 \times 4 = 16$.

5. Calculate the difference:

• Difference between female students in Civil and Mechanical departments = $48 - 16 = 32$.

The final answer is $\boxed{32}$

Let $M$, $P$, and $C$ be the events of passing in Mathematics, Physics, and Chemistry, respectively. The probabilities are $P(M)=m$, $P(P)=p$, and $P(C)=c$.We are given the following probabilities:Let's define:

• $P_1 = P(\text{exactly one subject})$
• $P_2 = P(\text{exactly two subjects})$
• $P_3 = P(\text{exactly three subjects})$

From the given information:
$P_2 = 0.40$We know that $P(\text{at least two subjects}) = P_2 + P_3$.
So, $0.50 = 0.40 + P_3 \implies P_3 = 0.10$.We also know that $P(\text{at least one subject}) = P_1 + P_2 + P_3$.
So, $0.75 = P_1 + 0.40 + 0.10 \implies 0.75 = P_1 + 0.50 \implies P_1 = 0.25$.Now, let's evaluate the sum of individual probabilities, $m+p+c$:
$m+p+c = P_1 + 2P_2 + 3P_3$
$m+p+c = 0.25 + 2(0.40) + 3(0.10)$
$m+p+c = 0.25 + 0.80 + 0.30$
$m+p+c = 1.35$Now let's check the given relations:Relation (I): $p+m+c=27/20$
$27/20 = 1.35$. Since $m+p+c = 1.35$, Relation (I) is TRUE.Relation (II): $p+m+c=13/20$
$13/20 = 0.65$. Since $m+p+c = 1.35 \neq 0.65$, Relation (II) is FALSE.Relation (III): $(p)\times(m)\times(c) = 1/10$
In the context of such problems, $(p)\times(m)\times(c)$ often refers to the probability of passing all three subjects, i.e., $P(P \cap M \cap C)$. This is exactly $P_3$.
We calculated $P_3 = 0.10$.
Since $1/10 = 0.10$, Relation (III) is TRUE (assuming $(p)\times(m)\times(c)$ represents $P(P \cap M \cap C)$).Therefore, Relations I and III are true.The final answer is $\boxed{D}$

First, calculate the total number of students in the class. From row 1: $21 + 17 + 6 = 44$. Checking other rows confirms the total is consistently 44.Next, calculate the total marks obtained by the entire class for each question:

• Q1: $21 \text{ correct} \times 2 \text{ marks} = 42$
• Q2: $15 \text{ correct} \times 3 \text{ marks} = 45$
• Q3: $11 \text{ correct} \times 1 \text{ mark} = 11$
• Q4: $23 \text{ correct} \times 2 \text{ marks} = 46$
• Q5: $31 \text{ correct} \times 5 \text{ marks} = 155$

Total Marks = $42 + 45 + 11 + 46 + 155 = 299$Average Marks = $\frac{\text{Total Marks}}{\text{Total Students}} = \frac{299}{44} \approx 6.7954$The closest option is 6.795.

Given $g(x) = 1-x$ and $h(x) = \frac{x}{x-1}$.$$g(h(x)) = 1 - h(x) = 1 - \frac{x}{x-1} = \frac{x-1-x}{x-1} = \frac{-1}{x-1} = \frac{1}{1-x}$$$$h(g(x)) = \frac{g(x)}{g(x)-1} = \frac{1-x}{(1-x)-1} = \frac{1-x}{-x} = \frac{x-1}{x}$$$$\frac{g(h(x))}{h(g(x))} = \frac{\frac{1}{1-x}}{\frac{x-1}{x}} = \frac{1}{1-x} \cdot \frac{x}{x-1} = \frac{x}{-(x-1)(x-1)} = \frac{-x}{(x-1)^2}$$Now check the options:
(A) $\frac{h(x)}{g(x)} = \frac{\frac{x}{x-1}}{1-x} = \frac{x}{(x-1)(1-x)} = \frac{x}{-(x-1)^2}$. This matches.
(B) $\frac{-1}{x}$. Incorrect.
(C) $\frac{g(x)}{h(x)} = \frac{1-x}{\frac{x}{x-1}} = \frac{-(x-1)^2}{x}$. Incorrect.
(D) $\frac{x}{(1-x)^2}$. Incorrect sign.Thus, option (A) is correct.

Let $y = \lim_{x\to\infty} x^{1/x}$.
Take the natural logarithm of both sides:
$\ln y = \lim_{x\to\infty} \ln(x^{1/x}) = \lim_{x\to\infty} \frac{1}{x} \ln x = \lim_{x\to\infty} \frac{\ln x}{x}$.This limit is of the form $\frac{\infty}{\infty}$. Applying L'Hopital's Rule:
$\lim_{x\to\infty} \frac{\frac{d}{dx}(\ln x)}{\frac{d}{dx}(x)} = \lim_{x\to\infty} \frac{1/x}{1} = 0$.So, $\ln y = 0$, which implies $y = e^0 = 1$.

The correct matching is:

• Prim's algorithm uses the Greedy method to build a Minimum Spanning Tree (MST).
• Floyd-Warshall algorithm uses Dynamic programming to find all-pairs shortest paths.
• Mergesort is a classic example of the Divide and conquer paradigm.
• Finding a Hamiltonian circuit is an NP-complete problem often solved using Backtracking.

Thus, the matching is P-ii, Q-iii, R-iv, S-i.

In the worst case of Quicksort, the partition function splits the array into two subarrays of size $n-1$ and $1$ (or $0$, depending on implementation, but effectively one element is placed and the rest are on one side). The partitioning step takes $O(n)$ time (represented by $cn$).The recurrence relation is:$$T(n) = T(n-1) + T(1) + cn$$Since $T(1)$ is a constant time operation, this simplifies to $T(n) = T(n-1) + O(n)$, which solves to $O(n^2)$.Option (A) represents the best case (or Merge Sort).
Option (C) represents $O(2^n)$.
Option (D) represents a binary search-like recurrence but with linear work.

The question defines height as the length of the longest root-to-leaf path, which implies the number of edges on the path.For a binary tree of height $h=5$:Maximum number of nodes:
This occurs in a full/complete binary tree.$$N_{max} = 2^{h+1} - 1 = 2^{5+1} - 1 = 2^6 - 1 = 64 - 1 = 63$$Minimum number of nodes:
This occurs in a skewed binary tree (essentially a linked list structure).$$N_{min} = h + 1 = 5 + 1 = 6$$Thus, the maximum and minimum number of nodes are 63 and 6 respectively.

The matching is as follows:

• (P) Condition coverage: This is a technique used in White-box testing (iii) where every condition in a decision takes all possible outcomes at least once.
• (Q) Equivalence class partitioning: This is a Black-box testing (i) technique that divides input data of a software unit into partitions of equivalent data from which test cases can be derived.
• (R) Volume testing: This is a type of Performance testing (iv) where the software is subjected to a large volume of data.
• (S) Alpha testing: This is a type of System testing (ii) performed to identify bugs before releasing the product to real users or to the public.

Thus, the correct mapping is P-iii, Q-i, R-iv, S-ii.

The inorder traversal of a Binary Search Tree (BST) always yields the keys in sorted (ascending) order.Let's check each sequence:

• I. 3, 5, 7, 8, 15, 19, 25: This sequence is sorted in ascending order. (Correct)
• II. 5, 8, 9, 12, 10, 15, 25: This sequence is NOT sorted ($12 > 10$). (Incorrect)
• III. 2, 7, 10, 8, 14, 16, 20: This sequence is NOT sorted ($10 > 8$). (Incorrect)
• IV. 4, 6, 7, 9, 18, 20, 25: This sequence is sorted in ascending order. (Correct)

Therefore, only sequences I and IV are correct.

In shift-reduce parsing, the stack contents at any point must form a viable prefix of a right sentential form. A viable prefix is a prefix of a right sentential form that can appear on the stack of a shift-reduce parser. This property ensures that as long as the stack contains a viable prefix, it is possible to continue parsing to reach the start symbol. Therefore, the stack contains only a set of viable prefixes (meaning the content of the stack is always a viable prefix).

The biconditional $p \leftrightarrow q$ is true if and only if $p$ and $q$ have the same truth value.Therefore, option (C) is the correct answer.

Given $A = \{5, \{6\}, \{7\}\}$. The power set $2^A$ is the set of all subsets of $A$.

• Statement I: $\emptyset \in 2^A$. Since the empty set $\emptyset$ is a subset of any set $A$, it must be an element of the power set $2^A$. Thus, I is TRUE.
• Statement II: $\emptyset \subseteq 2^A$. The empty set is a subset of every set, including $2^A$. Thus, II is TRUE.
• Statement III: $\{5, \{6\}\} \in 2^A$. For $\{5, \{6\}\}$ to be an element of $2^A$, it must be a subset of $A$. Since $5 \in A$ and $\{6\} \in A$, the set $\{5, \{6\}\}$ is indeed a subset of $A$. Thus, III is TRUE.
• Statement IV: $\{5, \{6\}\} \subseteq 2^A$. For this to be true, every element of $\{5, \{6\}\}$ must be an element of $2^A$. This means $5 \in 2^A$ and $\{6\} \in 2^A$. However, $5$ and $\{6\}$ are elements of $A$, not subsets of $A$. The subsets of $A$ are elements of $2^A$ (e.g., $\{5\} \in 2^A$ and $\{\{6\}\} \in 2^A$). Since $5 \notin 2^A$ and $\{6\} \notin 2^A$, IV is FALSE.

Statements I, II, and III are true. Therefore, option (C) is correct.

A 4-bit Johnson counter (also known as a twisted ring counter) operates by shifting bits and feeding the complement of the last bit back into the first bit. Assuming a right-shift operation:The sequence is 0, 8, 12, 14, 15, 7, 3, 1, 0. This matches option (D).

In a three-address instruction format (e.g., ADD dest, src1, src2), each address field explicitly specifies an operand location. Thus, only S1 and S2 are correct.

Let's evaluate each statement:

• I. FALSE: TCP sequence numbers are byte-oriented, not segment-oriented. If a segment starts with sequence number $m$ and contains $L$ bytes of data, the next segment's sequence number will be $m + L$.
• II. TRUE: The Retransmission Timeout (RTO) is calculated as $RTO = SRTT + 4 \times RTTVAR$. Since the variation ($RTTVAR$) is non-negative, $RTO$ is always $\geq$ the estimated RTT ($SRTT$, denoted as $t$ here).
• III. FALSE: The advertised window (receiver window) is used for flow control and changes dynamically based on the available buffer space at the receiver.
• IV. TRUE: This is the fundamental rule of TCP flow control; the sender cannot have more outstanding (unacknowledged) data than the receiver's advertised window size.

Statements I and III are FALSE.

In a symmetric key cryptographic system, for two people to communicate securely such that no one else can decode the message, they must share a unique secret key.
In a group of $N$ people, every possible pair of individuals needs such a unique key. The number of ways to choose a pair of 2 people from a group of $N$ is given by the combination formula:$$\binom{N}{2} = \frac{N!}{2!(N-2)!} = \frac{N(N-1)}{2}$$Thus, $\frac{N(N-1)}{2}$ keys are required.

The height of a tree is defined as the length of the longest root-to-leaf path, which is the number of edges in that path. A tree with a single node has a height of 0.Maximum number of nodes:
A binary tree of a given height $h$ has the maximum number of nodes when it is a full binary tree. In a full binary tree of height $h$, every level is completely filled with nodes.
The number of nodes at level $i$ is $2^i$ (assuming root is at level 0).
The total number of nodes for a height $h$ is the sum of nodes at all levels from 0 to $h$:$$N_{max} = \sum_{i=0}^{h} 2^i = 2^{h+1} - 1$$For a height of $h=5$, the maximum number of nodes is:$$N_{max} = 2^{5+1} - 1 = 2^6 - 1 = 64 - 1 = 63$$Minimum number of nodes:
A binary tree of a given height $h$ has the minimum number of nodes when it is a skewed tree (either left-skewed or right-skewed). In a skewed tree, each node has at most one child, forming a single path.
To achieve a height of $h$, there must be a path of length $h$, which requires $h+1$ nodes.
For a height of $h=5$, the minimum number of nodes is:$$N_{min} = 5 + 1 = 6$$Therefore, the maximum and minimum number of nodes in a binary tree of height 5 are 63 and 6, respectively. This corresponds to option (A).

Let's analyze and match each item from List I with the appropriate item from List II.

• (P) Condition coverage: This is a white-box testing technique that checks if each boolean sub-expression in the code has been evaluated to both true and false. Therefore, P matches with (iii) White-box testing.
• (Q) Equivalence class partitioning: This is a black-box testing technique where the input domain of a program is divided into partitions of equivalent data from which test cases are derived. The focus is on the input/output behavior without knowledge of the internal code structure. Therefore, Q matches with (i) Black-box testing.
• (R) Volume testing: This is a type of non-functional testing where the system is subjected to a large volume of data to check its performance and behavior under heavy load. This falls under the umbrella of performance testing. Therefore, R matches with (iv) Performance testing.
• (S) Alpha testing: This is a form of acceptance testing performed by in-house testers at the developer's site before the product is released to external customers. It is a type of system testing. Therefore, S matches with (ii) System testing.

The correct matching is:

• P → iii
• Q → i
• R → iv
• S → ii

This corresponds to the sequence P-iii, Q-i, R-iv, S-ii, which is given in option (C).

A key property of a Binary Search Tree (BST) is that an inorder traversal of the tree visits the nodes in a sorted (non-decreasing) order of their keys. We need to check which of the given sequences are sorted.

• Sequence I: 3, 5, 7, 8, 15, 19, 25

This sequence is in strictly increasing order. Therefore, it can be the inorder traversal of a BST.

• Sequence II: 5, 8, 9, 12, 10, 15, 25

This sequence is not sorted because the element 12 is followed by 10, which is smaller. Therefore, it cannot be the inorder traversal of a BST.

• Sequence III: 2, 7, 10, 8, 14, 16, 20

This sequence is not sorted because the element 10 is followed by 8, which is smaller. Therefore, it cannot be the inorder traversal of a BST.

• Sequence IV: 4, 6, 7, 9, 18, 20, 25

This sequence is in strictly increasing order. Therefore, it can be the inorder traversal of a BST.Since only sequences I and IV are sorted, they are the only ones that can be correct inorder traversal sequences of a binary search tree. Thus, option (A) is the correct answer.

Statement I: $L_1$ is Context-Free. All Context-Free Languages (CFLs) are recursive (decidable). The complement of a recursive language is always recursive. Thus, $\bar{L}_1$ is recursive. Statement I is TRUE.Statement II: $L_2$ is Recursively Enumerable (RE) but not recursive. The complement of an RE language that is not recursive is NOT RE. Thus, $\bar{L}_2$ is not recursive. Statement II is FALSE.Statement III: $L_1$ is Context-Free. The class of Context-Free Languages is not closed under complementation. Thus, $\bar{L}_1$ is not necessarily context-free. Statement III is FALSE.Statement IV: $L_1$ is recursive, which implies $L_1$ is also RE. The complement $\bar{L}_1$ is recursive, so $\bar{L}_1$ is RE. $L_2$ is RE. The union of two RE languages is always RE. Thus, $\bar{L}_1 \cup L_2$ is RE. Statement IV is TRUE.Since I and IV are true, the correct option is (D).

The size of the page table is 4 megabytes.

Initial value: $B = 2$. Let $R_1, W_1$ be the read and write of $B$ in $P1$, and $R_2, W_2$ be the read and write of $B$ in $P2$.

• $P1$: $R_1$ reads $B$, calculates $C = B - 1$; $W_1$ writes $B = 2 \times C$.
• $P2$: $R_2$ reads $B$, calculates $D = 2 \times B$; $W_2$ writes $B = D - 1$.

Possible interleavings:The distinct possible values for $B$ are $\{2, 3, 4\}$. The number of distinct values is 3.