Gate1998
Question 1 
Total no. of possibilities are 8.
Probability of getting exactly one odd = 3/8
Question 2 
has unique solution  
has no solutions  
has finite number of solutions  
has infinite number of solutions

Question 3 
converges within a few iterations  
guaranteed to work for all continuous functions  
is faster than the NewtonRaphson method  
requires that there be no error in determining the sign of the function

Question 4 
continuous and differentiable  
continuous but not differentiable  
differentiable but not continuous  
neither continuous nor differentiable 
→ The left side values of x=0 be negative and right side values are positive.
→ If the function is said to be differentiable then left side and right side values are to be same.
Question 5 
I stay if you go  
If I stay then you go  
If you do not go then I do not stay  
If I do not stay then you go 
⇒ i.e., A→B
Where A = If I stay; B = you go
Converse for (A→B) is (B→A)
⇒ If you go then I stay.
Question 6 
n  
n^{2}  
1  
n +1 
⇒ n×n
⇒ n^{2}
Question 7 
Both assertions are true  
Assertion (i) is true but assertion (ii) is not true  
Assertion (ii) is true but assertion (i) is not true  
Neither (i) nor (ii) is true 
(i) R_{1} ∩ R_{2} is also transitive.
(ii) R_{1} ∪ R_{2} is need not to be transitive.
Question 8 
m + n  
m^{n}  
n^{m}  
m*n 
n×n×n×n×...×n (m times)
= n^{m}
Question 9 
A ⊂ B  
B ⊂ A  
A and B are incomparable  
A = B 
Question 10 
The numbers 1, 2, 4, 8, ……………., 2^{n}, ………… written in binary  
The numbers 1, 2, 4, ………………., 2^{n}, …………..written in unary  
The set of binary string in which the number of zeros is the same as the number of ones  
The set {1, 101, 11011, 1110111, ………..} 
10, 100, 1000, 10000 .... = 10*
which is reguar and recognized by deterministic finite automata.
Question 11 
The nondeterministic finitestate automata are equivalent to deterministic finitestate automata.  
Nondeterministic Pushdown automata are equivalent to deterministic Push down automata.  
Nondeterministic Turing machines are equivalent to deterministic Pushdown automata.  
Both B and C 
C: Power (TM) > NPDA > DPDA.
Question 12 
110*(0 + 1)  
1 ( 0 + 1)* 101  
(10)* (01)* (00 + 11)*  
Both C and D 
C & D are not generate string 1101.
Question 13 
complements when n is even  
complements when n is odd
 
divides by 2^{n} always  
remains unchanged when n is even 
Consider:
B⊕(B⊕B)
= B⊕0
= 0 (if consider n times it remains unchanged)
Question 14 
4:1 multiplexor  
2:1 multiplexor  
16:1 multiplexor  
8:1 multiplexor

For 4 bit data it selects 2^{4} : 1 = 16: 1 input
Question 15 
any voltage above 2.5 V  
any voltage between 0.8 V and 5.0 V  
any voltage below 5.0 V  
any voltage below V_{cc} but above 2.8 V 
Question 16 
2400 band  
19200 band  
4800 band  
1200 band 
(8+2+1+1) * 300
= 3600
Minimum band rate required is 4800 band.
Question 17 
226  
98  
76  
30 
If this can be treated as 8 bit integer, then the first becomes sign bit i.e., '1' then the number is negative.
8085 uses 2's complement then
⇒ 30
Question 18 
Hard disk  
Printer  
Keyboard  
Floppy disk 
Question 19 
Indirect addressing  
Indexed addressing  
Base register addressing  
PC relative addressing 
Question 20 
Unless enabled, a CPU will not be able to process interrupts.  
Loop instructions cannot be interrupted till they complete.  
A processor checks for interrupts before executing a new instruction.  
Only level triggered interrupts are possible on microprocessors. 
Option 'C' also false. A processor checks for the interrupt before fetching an instruction.
Question 21 
Dynamic programming  
Backtracking  
Greedy  
Divide and Conquer 
Question 22 
A – R B – P C – Q D – S  
A – R B – P C – S D – Q  
A – P B – R C – S D – Q  
A – P B – S C – R D – Q 
Selection = O(n)
Merge sort = O(n log n)
Insertion sort = O(n^{2})
Question 23 
n  
n^{2}  
2^{n}  
Possible substrings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 24 
A tree with a n nodes has (n – 1) edges  
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results  
A complete binary tree with n internal nodes has (n + 1) leaves  
Both B and C 
D: The maximum no. of nodes in a binary tree of height h is 2^{h+1}  1.
h=2 ⇒ 2^{3}  1 ⇒ 7
Question 25 
Assembler  
Linker  
Loader  
Compiler 
Some OS may allow virtual memory may allow the loader to be located in a region of memory that is in page table.
Question 26 
SLR parser is more powerful than LALR  
LALR parser is more powerful than Canonical LR parser  
Canonical LR parser is more powerful than LALR parser  
The parsers SLR, Canonical CR, and LALR have the same power 
Canonical LR parser is more powerful than LALR parser.
Question 27 
lexical analysis  
syntax analysis  
syntax directed translation  
code optimization 
Question 28 
0, 200, 500, 600  
0, 200, 1000, 1600  
200, 500, 600, 800  
200, 700, 1300, 2100 
Now 2^{nd} will start loading at 200, since size is 800, so last address is 999.
Now 3^{rd} module will start loading at 1000, since size is 600. So last address is 1599.
Now 4^{th} module will start loading at 1600 and go till 2099.
Question 29 
The terminal used to enter the input data for the C program being executed  
An output device used to print the output of a number of jobs  
The secondary memory device in a virtual storage system  
The swapping area on a disk used by the swapper 
For example in printer if a process attempt to print a document but printer is busy printing another document, the process, instead of waiting for printer to become available, write its output to disk. When the printer becomes available the data on disk is printed.
Spooling allows process to request operation from peripheral device without requiring that the device is ready to service the request.
Question 30 
cycle steating  
rare condition  
a time lock  
a deadlock 
Speed of processes corresponds to ordering of processes.
Question 31 
0  
8  
10  
12 
S = 10
Now 6P operations and uv operations were completed on this semaphore. So final value of S will be
S = 10  6 + 4 = 8
Question 32 
6  
5  
4  
3 
So maximum no. of process for the system to be deadlock free is 5.
Question 33 
R_{1} ∪ R_{2}  
R_{1} × R_{2}  
R_{1}  R_{2}  
R_{1} ∩ R_{2} 
Question 34 
2 NF  
5 NF  
4 NF  
3 NF 
Question 35 
Age  
Name  
Occupation  
Category 
Question 38 
reflexive, symmetric and transitive  
neither reflexive, nor irreflexive but transitive  
irreflexive, symmetric and transitive  
irreflexive and antisymmetric 
→ Not irreflexive becuaes (1, 1) is present.
→ Not symmetric because (2, 1) is present but not (1, 2).
→ Not antisymmetric  (2, 3) and (3, 2) are present.
It is transitive so correct option is (B).
Question 39 
In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada. 9 persons speak both English and Hindi, 11 persons speak both Hindi and Kannada whereas 13 persons speak both Kannada and English. How many people speak all three languages?
9  
8  
7  
6 
Let B be the people who speaks Hindi.
Let C be the people who speaks Kannada.
(A∪B∪C) = A + B + C  (A∩B)  (B∩C)  (C∩A) + (A∩B∩C)
28 = 18 + 15 + 22  9  11  13 + (A∩B∩C)
∴ (A∩B∩C) = 6
Question 40 
Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is
2  
5  
8  
3 
Equivalent DFA:
Hence, 5 states.
Question 41 
Every finite subset of a nonregular set is regular  
Every subset of a regular set is regular  
Every finite subset of a regular set is regular  
The intersection of two regular sets is regular 
Question 43 
AND  
OR  
NAND  
EXOR 
Question 44 
arranging the data on the disk in contiguous fashion  
writing the directory  
erasing the system area  
writing identification information on all tracks and sectors 
Question 45 
one Megabyte  
256 Kilobytes  
1 K Megabytes  
64 Kilobytes 
Question 46 
x(n1) + 1  
xn  1  
xn + 1  
x(n+1) 
Let no. of leaf nodes = L
Let n_{t} be total no. of nodes.
So, L+x = n_{t} (I)
Also for nary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = n_{t} (II)
So, equating (I) & (II),
L+x = nx+1
L = x(n1) + 1
Question 47 
89  
90  
91  
92 
fun(95) = fun(fun(106))
= fun(96)
= fun(fun(107))
= fun(97)
= fun(fun(108))
= fun(98)
= fun(fun(109))
= fun(99)
= fun(110)
= fun(100)
= fun(fun(111))
= fun(101)
= 91
Question 48 
5  
25  
36  
42 
If it is call by value then answer is 36.
Question 49 
15i + j + 84  
15j + i + 84  
10i + j + 89  
10j + i + 89 
100 + 15 * (i1) + (j1)
= 100 + 15i  15 + j  1
= 15i + j + 84
Question 50 
stack  
heap  
display  
activation tree 
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for nonlocal variables but may be complicated to maintain.
Question 51 
12 KB  
14 KB  
10 KB  
8 KB 
For the above program, maximum memory will be required when running code portion present at leaves.
Maximum requirement
= MAX(12, 14, 10, 14)
= 14
Question 52 
Consider n processes sharing the CPU in a roundrobin fashion. Assuming that each process switch takes s seconds, what must be the quantum size q such that the overhead resulting from process switching is minimized but at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?
Question 53 
If an instruction takes i microseconds and a page fault takes an additional j microseconds, the effective instruction time if on the average a page fault occurs every k instruction is:
= service time + page fault rate * page fault service time
= i + 1/k * j
= i + j/k
Question 54 
Which of the following query transformations (i.e. replacing the l.h.s. expression by the r.h.s. expression) is incorrect? R_{1} and R_{2} are relations, C_{1}, C_{2} are selection conditions and A_{1}, A_{2} are attributes of R_{1}?
σ_{C1}(σ_{C1}(R_{1})) → σ_{C2}(σ_{C2}(R_{1}))  
σ_{C1}(σ_{A1}(R_{1})) → σ_{A1}(σ_{C1}(R_{1}))  
σ_{C1}(R_{1} ∪ R_{2}) → σ_{C1}(R_{1}) ∪ σ_{C1}(R_{2})  
π_{A1}(σ_{C1}(R_{1})) → σ_{C1}(σ_{A1}(R_{1})) 
Question 55 
Suppose the domain set of an attribute consists of signed four digit numbers. What is the percentage of reduction in storage space of this attribute if it is stored as an integer rather than in character form?
80%  
20%  
60%  
40% 
We have four digits. So to represent signed 4 digit numbers we need 5 bytes, 4 bytes for four digits and 1 for the sign.
So required memory = 5 bytes.
Now, if we use integer, the largest no. needed to represent is 9999 and this requires 2 bytes of memory for signed representation.
9999 in binary requires 14 bits. So, 2 bits remaining and 1 we can use for sign bit.
So, memory savings,
= 5  2/5 × 100
= 60%