# Recent exams in Tests by Mentors

## Select an Exam

 Exam Category Select GATE ISRO TIFR UGC NET GATE Overflow Tests Tests by Mentors External Tests Exam Type Full Length Random Subject Wise
1
You would need to know some examples (not all) of NP Complete problems and why they are NP Complete. For example 3SAT problem is NPC and in GATE they have asked about 2SAT. So, just learning some examples won't be enough.
2
Worst case complexity can never be lower than the average case complexity, but it can be higher. So, $(C)$ is the answer. $A(n) = O(W(n))$.
3
Register renaming is done to eliminate WAR (Write after Read) and WAW (Write after Write) dependency between instructions which could have caused pipieline stalls. Hence, (C) is the answer. Example: I1: Read $A$ to $B$ I2: Write $C$ to $A$ Here, there ... same memory location. Register renaming can avoid this. Similarly WAW also. http://people.ee.duke.edu/~sorin/ece252/lectures/4.2-tomasulo.pdf
4
Answer is (A) Commutative but not associative. $y \oplus x = y^2 + x^2 = x \oplus y$. Hence, commutative. $(x \oplus y) \oplus z = (x^2 + y^2) \oplus z = (x^2 + y^2)^2 + z^2$ $x \oplus (y \oplus z) = x \oplus (y^2 + z^2) = x^2 + (y^2 + z^2)^2$ So, $( (x \oplus y) \oplus z) \neq (x \oplus (y \oplus z))$, hence not associative.
5
Answer is (B)Adapt to. Often seen in newspaper "Indian players could not adapt to foreign conditions". Adopt - means legally take care of. Also means to take up and use as in "He adopted my point of view." Adept in - means smart in. Example- "Sachin is adept in batting."
6
A useful rule: $\forall x (\alpha) = \neg \exists (x) (\neg \alpha)$i.e.; If some property $\alpha$ is true for all $x$, then it is equivalent ot say that no $x$ exists such that property $\alpha$ does not hold for it. Starting with choices: ... statement in question. Thus both (A) and (D) are not logically equivalent to the given statement. In GATE 2013 marks were given to all for this question
7
Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$ ? $∀ x(∃ z(¬β )→∀ y(α))$ $∀x(∀ z(β )→∃ y(¬α))$ $∀x(∀ y(α)→∃z(¬β ))$ $∀x(∃ y(¬α)→∃z(¬β ))$
8
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\}$ A. $L$ is RE but $L'$ is not RE B. Both $L$ and $L'$ are RE C. $L$ is not RE but $L'$ is RE D. Both $L$ and $L'$ are not RE
9
Consider the following languages $L_1$ = $\{a^nb^n\mid n \ge 0\}$ $L_2$ = Complement($L_1$) Chose the appropriate option regarding the languages $L_1$ and $L_2$ (A) $L_1$ and $L_2$ are context free (B) $L_1$ is context free but $L_2$ is regular (C) $L_1$ is context free and $L_2$ is context sensitive (D) None of the above
10
B is the answer- A is not Turing recognizable while B is Turing recognizable. A is Turing recognizable if TM for A, say $T_A$ outputs "yes" for "yes" cases of A- i.e.; when M accepts at most 2 distinct inputs. But M can loop forever without ... A. The complement of a Turing recognizable but not Turing decidable language is always not Turing recognizable.) : http://www.xamuel.com/dovetailing/
11
Regular. $L_1 \cap L_2$ $= \{abcd,aabbcd,aaabbbccdd,\dots\} \cap \{ab, aabb, aaabbb,\dots\}$ $= \emptyset.$
12
There are three possible operations on queue- Enqueue, Dequeue and MultiDequeue. MultiDequeue is calling Dequeue multiple times based on a global variable $k$. Since, the queue is initially empty, whatever be the order of these operations, there cannot be more number of Dequeue operations than Enqueue operations. Hence, the total number operations will be $n$ only. Correct Answer: $A$
13
In GATE 2013 marks were given to all as the same code in C/C++ produces undefined behavior. This is because $*$ is not a sequence point in C/C++. The correct code must replace: return f(x,c) * x; with res = f(x,c); // ... http://stackoverflow.com/questions/41775973/is-this-undefined-behaviour-in-c-if-not-predict-the-output-logically https://gateoverflow.in/108445/c-programming?show=108582#a108582
14
Register renaming is done in pipelined processors: as an alternative to register allocation at compile time for efficient access to function parameters and local variables to handle certain kinds of hazards as part of address translation
15
The amount of ROM needed to implement a $4-bit$ multiplier is $64$ bits $128$ bits $1$ Kbits $2$ Kbits
16
Let $W(n)$ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE? $A(n) = \Omega (W(n))$ $A(n) = \Theta (W(n))$ $A(n) = \text{O} (W(n))$ $A(n) = \text{o} (W(n))$
17
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to (A) 3 (B) 4 (C) 5 (D) 6
18
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is $T(n) = 2T(n − 2) + 2$ $T (n) = 2T(n − 1) + n$ $T (n) = 2T(n/2) + 1$ $T (n) = 2T(n − 1) + 1$
19
Which of the following statements are TRUE about an SQL query? P : An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause Q : An SQL query can contain a HAVING clause only if it has a GROUP BY clause R : All attributes used in the GROUP BY clause ... S : Not all attributes used in the GROUP BY clause need to appear in the SELECT clause P and R P and S Q and R Q and S
20
Given the basic ER and relational models, which of the following is INCORRECT? An attribute of an entity can have more than one value An attribute of an entity can be composite In a row of a relational table, an attribute can have more than one value In a row of a relational table, an attribute can have exactly one value or a NULL value