Gate1995
Question 1 
A single instruction to clear the lower four bits of the accumulator in 8085 assebly
language?
XRI OFH  
ANI FOH  
XRI FOH  
ANI OFH 
Question 1 Explanation:
Here, we use the AND as a accumulator with immediate. F leaves the high nibble whatever it is, 0 clears the lower nibble.
→ The XOR's don't reliably clear random bits and ANI OF clears the upper nibble, not the lower nibble.
→ The XOR's don't reliably clear random bits and ANI OF clears the upper nibble, not the lower nibble.
Question 2 
Which of the following statements is true?
ROM is a Read/Write memory  
PC points to the last instruction that was executed  
Stack works on the principle of LIFO  
All instructions affect the flags 
Question 2 Explanation:
We know that stack works on the principle of LIFO.
Question 3 
In a vectored interrupt
the branch address is assigned to a fixed location in memory  
the interrupt source supplies the branch information to the processor through an interrupt vector  
the branch address is obtained from a register in the processor  
none of the above 
Question 3 Explanation:
A vectored interrupt is a processing technique in which the interrupting device directs the processor to the appropriate interrupt service routine vector.
Question 4 
10  
20  
10  
None 
Question 4 Explanation:
X is remains unchanged. As the if condition is becomes false.
X = 10
X = 10
Question 5 
Merge sort uses
Divide and conquer strategy  
Backtracking approach  
Heuristic search  
Heuristic search 
Question 5 Explanation:
Merge sort uses the divide and conquer strategy.
Question 6 
The principle of locality justifies the use of
interrupts  
DMA  
Polling  
Cache Memory 
Question 6 Explanation:
The locality of reference is also known as principle of locality.
→ The things which are used more frequently those are stored in locality of reference.
→ For this purpose we use the cache memory.
→ The things which are used more frequently those are stored in locality of reference.
→ For this purpose we use the cache memory.
Question 7 
In a paged segmented scheme of memory management, the segment table itself
must have a page table because
the segment table is often too large to fit in one page  
each segment is spread over a number of pages  
segment tables point to page table and not to the physical locations of the segment  
the processor’s description base register points to a page table  
Both A and B 
Question 7 Explanation:
The segment table is often too large to fit in one page. This is true and the segment table can be divided into pages. Thus page table for each segment table, pages are created.
Segment paging is different from paged segmentation.
Segment paging is different from paged segmentation.
Question 8 
Which of the following page replacement algorithms suffers from Belady’s anamoly?
Optimal replacement  
LRU  
FIFO  
Both (A) and (C)

Question 8 Explanation:
FIFO is suffers from Belady's Anamoly.
Question 9 
In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?
(L ∪ D)^{+}  
L(L ∪ D)*  
(L⋅D)*  
L⋅(L⋅D)* 
Question 9 Explanation:
Which is to be letter followed by any number of letters (or) digits
L(L⋅D)*
L(L⋅D)*
Question 10 
Context free  
Regular  
Context sensitive  
LR(k) 
Question 10 Explanation:
S ∝→ [violates context free]
Because LHS must be single nonterminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.
Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).
Because LHS must be single nonterminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.
Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).
Question 11 
Variables  
Identifiers  
Actual parameters  
Formal parameters

Question 11 Explanation:
Formal arguments (or) formal parameters is a special kind of variables used in subroutime to refer to one of pieces of data provided as input to the subroutine.
Question 12 
What is the distance of the following code 000000, 010101, 000111, 011001, 111111?
2  
3  
4  
1 
Question 12 Explanation:
Distance = Minimum hamming distance = 2
010101 ⊕ 011001 = 001100
010101 ⊕ 011001 = 001100
Question 13 
I  
II  
III  
All of the above 
Question 13 Explanation:
Note: Out of syllabus.
Question 14 
A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?
Object code  
Relocation bits  
Names and locations of all external symbols defined in the object module
 
Absolute addresses of internal symbols

Question 14 Explanation:
In object module it includes names and locations of all external symbols defined in the object module.
To link to external symbols it must know the location of external symbols.
To link to external symbols it must know the location of external symbols.
Question 15 
Which scheduling policy is most suitable for a time shared operating system?
Shortest Job First  
Round Robin  
First Come First Serve  
Elevator 
Question 15 Explanation:
In Round robin, we use the time quentum based on this execution can be done. Then it is said to be time shared operating system.
Question 16 
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of
O(m)  
O(n)  
O(m+n)  
O(logm+logn) 
Question 16 Explanation:
In best case, no. of comparisons is Min(m,n).
In worst case, no. of comparisons is m+n1.
Then we require O(m+n) comparisons to merging two sorted lists.
In worst case, no. of comparisons is m+n1.
Then we require O(m+n) comparisons to merging two sorted lists.
Question 17 
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:
log_{2} n  
n  1  
n  
2^{n} 
Question 17 Explanation:
A binary tree is a tree data structure in which each node has atmost two child nodes.
The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
The number of nodes of degree 2 in T is "n  1".
The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
The number of nodes of degree 2 in T is "n  1".
Question 18 
The probability that a number selected at random between 100 and 999 (both inclusive) will not contain the digit 7 is:
Question 18 Explanation:
Question 19 
Let R be a symmetric and transitive relation on a set A. Then
R is reflexive and hence an equivalence relation  
R is reflexive and hence a partial order
 
R is reflexive and hence not an equivalence relation  
None of the above 
Question 19 Explanation:
If a relation is equivalence then it must be
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is said to be symmetric and transitive then we can't say the relation is reflexive and equivalence.
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is said to be symmetric and transitive then we can't say the relation is reflexive and equivalence.
Question 20 
The number of elements in he power set P (S) of the set S = {(φ), 1, (2, 3)} is:
2  
4  
8  
None of the above 
Question 20 Explanation:
S = {(φ), 1, (2, 3)}
P(S) = {φ, {{φ}}, {1}, {{2, 3}}, {{φ}, 1}, {1, {2, 3}}, {{φ}, 1, {2, 3}}}
In P(S) it contains 8 elements.
P(S) = {φ, {{φ}}, {1}, {{2, 3}}, {{φ}, 1}, {1, {2, 3}}, {{φ}, 1, {2, 3}}}
In P(S) it contains 8 elements.
Question 21 
In the interval [0, π] the equation x = cos x has
No solution  
Exactly one solution  
Exactly two solutions  
An infinite number of solutions

Question 21 Explanation:
x & cos(x) are intersecting at only one point.
Question 22 
a straight line  
a parabola  
a circle  
an ellipse 
Question 22 Explanation:
Note: Out of syllabus.
Question 23 
The value of k for which 4x^{2}  8xy + ky^{2} = 0 does not represent a pair of straight lines (both passing through the origin) is:
0  
2  
9  
3 
Question 23 Explanation:
Note: Out of syllabus.
Question 24 
1  
2  
n  
Depends on the value of a 
Question 24 Explanation:
Question 25 
The minimum number of edges in a connected cyclic graph on n vertices is:
n  1  
n  
n + 1  
None of the above 
Question 25 Explanation:
In a normal graph number of edges required for n vertices is n1, and in cyclic graph it is n.
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
Question 26 
The capacity of a memory unit is defined by the number of words multiplied by the number of bits/word. How many separate address and data lines are needed for a memory of 4K × 16?
10 address, 16 data lines  
11 address, 8 data lines  
12 address, 16 data lines  
12 address, 12 data lines 
Question 26 Explanation:
ROM memory size = 2^{m} × n
m = no. of address lines
n = no. of data lines
Given, 4K × 16 = 2^{12} × 16
Address lines = 12
Data lines = 16
m = no. of address lines
n = no. of data lines
Given, 4K × 16 = 2^{12} × 16
Address lines = 12
Data lines = 16
Question 27 
Computes the LCM of two numbers  
Divides the larger number by the smaller number  
Computes the GCD of two numbers  
None of the above 
Question 27 Explanation:
Let X=3 and Y=5
1^{st} pass : X=3 and Y=2
2^{nd} pass : X=1 and Y=2
3^{rd} pass : X=1 and Y=1
Write(X), which writes 1. Which is nothing but GCD of 3 & 5.
1^{st} pass : X=3 and Y=2
2^{nd} pass : X=1 and Y=2
3^{rd} pass : X=1 and Y=1
Write(X), which writes 1. Which is nothing but GCD of 3 & 5.
Question 28 
2  
Run time error  
None of the above 
Question 28 Explanation:
Since nothing is said in question. So we will assume by default call by value.
X in the procedure FIND is a local variable. No change will be reflected in global variable X.
X in the procedure FIND is a local variable. No change will be reflected in global variable X.
Question 29 
A = 1, B = 0, C = 0, D = 1  
A = 1, B = 1, C = 0, D = 0  
A = 1, B = 0, C = 1, D = 1  
A = 1, B = 0, C = 0, D = 0 
Question 29 Explanation:
For verification, just put up the values and check for AND, OR operations and their outputs.
Question 30 
{3,2,1),1  
(2,1,3},0  
{3,2,1),0  
{1,2,3},5 
Question 30 Explanation:
Here, in option (B) and (C) they have given CPU idle time is 0 which is not possible as per schedule (B) and (C).
So, (B) and (C) will be eliminated.
Now in (A) and (D):
For r(A),
So, idle time is between 0 to 1 which in case of option (A).
For option(D),
We can see there is no idle time at all, but in option given idle time is 5, which is not matching with our chart. So option (D) is eliminated.
Therefore, the correct sequence is option (A).
So, (B) and (C) will be eliminated.
Now in (A) and (D):
For r(A),
So, idle time is between 0 to 1 which in case of option (A).
For option(D),
We can see there is no idle time at all, but in option given idle time is 5, which is not matching with our chart. So option (D) is eliminated.
Therefore, the correct sequence is option (A).
Question 31 
13  
8  
7  
10 
Question 31 Explanation:
Page are fitted in frames, so first we need to determine the pages but given request are just the record request in decimal. We can assume that first page to address from 0000 to 0099 and page 2 contains records from 0100 to 0199 and so on (it is given in question that each page contains 100 records) and so on. So page request string is
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
Question 32 
If the cube roots of unity are 1, ω and ω^{2}, then the roots of the following equation are (x  1)^{3} + 8 = 0
1, 1 + 2ω, 1 + 2ω^{2}  
1, 1  2ω, 1  2ω^{2}
 
1, 1  2ω, 1  2ω^{2}  
1, 1 + 2ω, 1 + 2ω^{2} 
Question 32 Explanation:
Just put values of (C) in place of x. It will satisfy the equation.
Question 33 
ac  
bc  
ab  
cc 
Question 33 Explanation:
concat (a, head (tail (tail (acbc))))
concat (a, head (tail (cbc)))
concat (a, head (bc))
concat (a, b)
ab
concat (a, head (tail (cbc)))
concat (a, head (bc))
concat (a, b)
ab
Question 34 
23131  
11233  
11231  
33211 
Question 34 Explanation:
⇒ 23131
Note SR is bottom up parser.
Question 35 
2800  
2400  
2000  
1200 
Question 35 Explanation:
Note: Out of syllabus.
Question 37 
A unit vector perpendicular to both the vectors a = 2i  2j + k and b = 1 + j  2k is:
None of the above. 
Question 37 Explanation:
Question 38 
A bag contains 10 white balls and 15 black balls. Two balls are drawn in succession. The probability that one of them is black and the other is white is:
Question 38 Explanation:
Probability of first ball white and second one black is,
Probability of first ball black and second one white is,
Probability of first ball black and second one white is,
Question 39 
The iteration formula to find the square root of a positive real number b using the Newton Raphson method is
None of the above 
Question 39 Explanation:
Note: Out of syllabus.
Question 40 
In a virtual memory system the address space specified by the address lines of the CUP must be __________ than the physical memory size and _______ than the secondary storage size.
smaller, smaller  
smaller, larger  
larger, smaller  
larger, larger 
Question 40 Explanation:
Primary memory < Virtual memory < Secondary memory.
Question 41 
Let A be the set of all nonsingular matrices over real number and let* be the matrix multiplication operation. Then
A is closed under* but < A, *> is not a semigroup  
Question 41 Explanation:
As the matrices are nonsingular so their determinant ±0. Hence, the inverse matrix always exist. But for a group to be Abelian it should follow commutative property. As matrix multiplication is not commutative, is a group but not an abelian group.
Question 42 
The solution of differential equation y'' + 3y' + 2y = 0 is of the form
Question 42 Explanation:
Note: Out of syllabus.
Question 43 
If the proposition ¬p ⇒ ν is true, then the truth value of the proposition ¬p ∨ (p ⇒ q), where ¬ is negation, ‘∨’ is inclusive or and ⇒ is implication, is
true  
multiple valued  
false  
cannot be determined 
Question 43 Explanation:
From the axiom ¬p → q, we can conclude that p ∨ q.
So, either p or q must be True.
Now,
¬p ∨ (p → q)
= ¬p ∨ (¬p ∨ q)
= ¬p ∨ q
Since nothing c an be said about the truth values of p, it implies that ¬p ∨ q can also be True or False. Hence, the value cannot be determined.
So, either p or q must be True.
Now,
¬p ∨ (p → q)
= ¬p ∨ (¬p ∨ q)
= ¬p ∨ q
Since nothing c an be said about the truth values of p, it implies that ¬p ∨ q can also be True or False. Hence, the value cannot be determined.
Question 44 
I only  
I and II  
II and III  
II only 
Question 44 Explanation:
(I) is the correct definition and the other two is wrong because the other two can have any no. of x and y. There is no such restriction over the number of both being equal.
Question 45 
AB + CD + *F/D + E*  
ABCD + *F/DE*++
 
A *B + CD/F *DE++  
A + *BCD/F* DE++  
None of the above 
Question 45 Explanation:
The postfix expression will be,
A B C D + * F / + D E * +
A B C D + * F / + D E * +
Question 46 
I and II  
II and III  
I and IV  
I and III 
Question 46 Explanation:
Binary search using linked list is not efficient as it will not give O(log n), because we will not be able to find the mid in constant time. Fnding mid in linked list takes O(n) time.
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind ietrative one in terms of performance.
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind ietrative one in terms of performance.
Question 47 
01  
10  
101  
110 
Question 47 Explanation:
If A is the start state, shortest sequence is 10 'or' 00 to reach C.
If B is the start state, shortest sequence is 0 to reach C.
If C is the start state, shortest sequence is 10 or 00 to reach C.
If D is the start state, shortest sequence is 0 to reach C.
∴ (B) is correct.
Question 48 
Let Σ = {0,1}, L = Σ* and R = {0^{n}1^{n} such that n >0} then the languages L ∪ R and R are respectively
regular, regular  
not regular, regular  
regular, not regular  
not regular, no regular 
Question 48 Explanation:
L∪R is nothing but L itself. Because R is subset of L and hence regular. R is deterministic context free but not regular as we require a stack to keep the count of 0's to make that of 1's.
Question 49 
A computer system has a 4K word cache organized in blocksetassociative manner with 4 blocks per set, 64 words per block. The number of its in the SET and WORD fields of the main memory address format is:
15, 40  
6, 4  
7, 2  
4, 6 
Question 49 Explanation:
No. of sets = 4K/ (64×4) = 2^{12}/ 2^{8} = 2^{4}
So we need 4 set bits.
And,
64 words per block means WORD bit is 6bits.
So, answer is option (D).
So we need 4 set bits.
And,
64 words per block means WORD bit is 6bits.
So, answer is option (D).
There are 49 questions to complete.