Gate-1998

Question 1
A die is rolled three times. The probability that exactly one odd number turns up among the three outcomes is
A
B
C
D
Question 1 Explanation: 
The possibilities of getting exactly one odd number is {OEE, EOE, EEO}.
Total no. of possibilities are 8.
Probability of getting exactly one odd = 3/8
Question 2
 
A
has unique solution
B
has no solutions
C
has finite number of solutions
D
has infinite number of solutions
Question 2 Explanation: 
Question 3
Which of the following statements applies to the bisection method used for finding roots of functions:  
A
converges within a few iterations
B
guaranteed to work for all continuous functions
C
is faster than the Newton-Raphson method
D
requires that there be no error in determining the sign of the function
Question 3 Explanation: 
The Bisection method guranteed to converge to a root of f if f is a continuous function on the interval [a,b] and f[a] and f[b] can have opposite signs.
Question 4
Consider the function y = |x| in the interval [-1,1]. In this interval, the function is  
A
continuous and differentiable
B
continuous but not differentiable
C
differentiable but not continuous
D
neither continuous nor differentiable
Question 4 Explanation: 
The given function y = |x| be continuous but not differential at x= 0.
→ 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
 
A
I stay if you go
B
If I stay then you go
C
If you do not go then I do not stay
D
If I do not stay then you go
Question 5 Explanation: 
"I stay only you go" = "If I 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
Suppose A is a finite set with n elements. The number of elements in the largest equivalence relation of A is
A
n
B
n2
C
1
D
n +1
Question 6 Explanation: 
In a largest equivalence relation the every element is related to other element
⇒ n×n
⇒ n2
Question 7
 
A
Both assertions are true
B
Assertion (i) is true but assertion (ii) is not true
C
Assertion (ii) is true but assertion (i) is not true
D
Neither (i) nor (ii) is true
Question 7 Explanation: 
If R1 and R2 be two equivalence relations on a set 'S' then the transitive property tells
(i) R1 ∩ R2 is also transitive.
(ii) R1 ∪ R2 is need not to be transitive.
Question 8
The number of functions from an m element set to an n element set is
A
m + n
B
mn
C
nm
D
m*n
Question 8 Explanation: 
Here each m element we have n choices i.e.,
n×n×n×n×...×n (m times)
= nm
Question 9
If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?
A
A ⊂ B
B
B ⊂ A
C
A and B are incomparable
D
A = B
Question 9 Explanation: 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
Question 10
Which of the following set can be recognized by a Deterministic Finite state Automaton?  
A
The numbers 1, 2, 4, 8, ……………., 2n, ………… written in binary
B
The numbers 1, 2, 4, ………………., 2n, …………..written in unary
C
The set of binary string in which the number of zeros is the same as the number of ones
D
The set {1, 101, 11011, 1110111, ………..}
Question 10 Explanation: 
The numbers are to be like
10, 100, 1000, 10000 .... = 10*
which is reguar and recognized by deterministic finite automata.
Question 11
Regarding  the power of recognition of languages, which of the following statements is false?
A
The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.
B
Non-deterministic Push-down automata are equivalent to deterministic Push- down automata.
C
Non-deterministic Turing machines are equivalent to deterministic Push-down automata.
D
Both B and C
Question 11 Explanation: 
B: No conversion possible from NPDA to DPDA.
C: Power (TM) > NPDA > DPDA.
Question 12
The string 1101 does not belong to the set represented by
A
110*(0 + 1)
B
1 ( 0 + 1)* 101
C
(10)* (01)* (00 + 11)*
D
Both C and D
Question 12 Explanation: 
Options A & B are generates string 1101.
C & D are not generate string 1101.
Question 13
 
A
complements when n is even
B
complements when n is odd
C
divides by 2n always
D
remains unchanged when n is even
Question 13 Explanation: 
B⊕(B⊕(B⊕...) n times
Consider:
B⊕(B⊕B)
= B⊕0
= 0 (if consider n times it remains unchanged)
Question 14
A multiplexor with a 4 bit data select input is a
A
4:1 multiplexor
B
2:1 multiplexor
C
16:1 multiplexor
D
8:1 multiplexor
Question 14 Explanation: 
For 'n' bit data it selects 2n : 1 input
For 4 bit data it selects 24 : 1 = 16: 1 input
Question 15
The threshold level for logic 1 in the TTL family is
A
any voltage above 2.5 V
B
any voltage between 0.8 V and 5.0 V
C
any voltage below 5.0 V
D
any voltage below Vcc but above 2.8 V
Question 15 Explanation: 
Voltage is to be below Vcc = 5V but above 2.8V
Question 16
In serial communication employing 8 data bits, a parity bit and 2 stop bits, the minimum band rate required to sustain a transfer rate of 300 characters per second is
A
2400 band
B
19200 band
C
4800 band
D
1200 band
Question 16 Explanation: 
Stop bit is given, it is asynchronous communication and 1 start bit also implied then
(8+2+1+1) * 300
= 3600
Minimum band rate required is 4800 band.
Question 17
The octal representation of an integer is (342)8. If this were to be treated as an eight-bit integer is an 8085 based computer, its decimal equivalent is
A
226
B
-98
C
76
D
-30
Question 17 Explanation: 
(342)8 = (011 100 010)2 = (1110 0010)2
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
Which of the following devices should get higher priority in assigning interrupts?
A
Hard disk
B
Printer
C
Keyboard
D
Floppy disk
Question 18 Explanation: 
Hard disk has the higher priority in assigning interrupts.
Question 19
Which of the following addressing modes permits relocation without any change whatsoever in the code?
A
Indirect addressing
B
Indexed addressing
C
Base register addressing
D
PC relative addressing
Question 19 Explanation: 
In PC relative addressing there is no change in the code.
Question 20
Which of the following is true?
A
Unless enabled, a CPU will not be able to process interrupts.
B
Loop instructions cannot be interrupted till they complete.
C
A processor checks for interrupts before executing a new instruction.
D
Only level triggered interrupts are possible on microprocessors.
Question 20 Explanation: 
Option B & D are false.
Option 'C' also false. A processor checks for the interrupt before fetching an instruction.
Question 21
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
A
Dynamic programming
B
Backtracking
C
Greedy
D
Divide and Conquer
Question 21 Explanation: 
In Dynamic programming Floyd Warshall algorithm is used to calculate the all pairs shortest path distance.
Question 22
 
A
A – R B – P C – Q D – S
B
A – R B – P C – S D – Q
C
A – P B – R C – S D – Q
D
A – P B – S C – R D – Q
Question 22 Explanation: 
Binary search = O(log n)
Selection = O(n)
Merge sort = O(n log n)
Insertion sort = O(n2)
Question 23
How many sub strings of different lengths (non-zero) can be found formed from a character string of length n?      
A
n
B
n2
C
2n
D
Question 23 Explanation: 
Let us consider an example S = {APB}
Possible sub-strings 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
Which of the following statements is false?
A
A tree with a n nodes has (n – 1) edges
B
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results
C
A complete binary tree with n internal nodes has (n + 1) leaves
D
Both B and C
Question 24 Explanation: 
A: Tree with n nodes must have (n-1) edges.
D: The maximum no. of nodes in a binary tree of height h is 2h+1 - 1.
h=2 ⇒ 23 - 1 ⇒ 7
Question 25
In a resident – OS computer, which of the following systems must reside in the main memory under all situations?
A
Assembler
B
Linker
C
Loader
D
Compiler
Question 25 Explanation: 
In many operating system loader is permanently resident in memory.
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
Which of the following statements is true?
A
SLR parser is more powerful than LALR
B
LALR parser is more powerful than Canonical LR parser
C
Canonical LR parser is more powerful than LALR parser
D
The parsers SLR, Canonical CR, and LALR have the same power
Question 26 Explanation: 
LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser.
Question 27
Type checking is normally done during
A
lexical analysis
B
syntax analysis
C
syntax directed translation
D
code optimization
Question 27 Explanation: 
Type checking is normally done during syntax directed translation.
Question 28
A linker reads four modules whose lengths are 200, 800, 600 and 500 words, respectively. If they are loaded in that order, what are the relocation constants?
A
0, 200, 500, 600
B
0, 200, 1000, 1600
C
200, 500, 600, 800
D
200, 700, 1300, 2100
Question 28 Explanation: 
First module loaded starting at address 0. Size is 200. Hence it will occupy first 200 address, last address being 199.
Now 2nd will start loading at 200, since size is 800, so last address is 999.
Now 3rd module will start loading at 1000, since size is 600. So last address is 1599.
Now 4th module will start loading at 1600 and go till 2099.
Question 29
Which of the following is an example of a spooled device?
A
The terminal used to enter the input data for the C program being executed
B
An output device used to print the output of a number of jobs
C
The secondary memory device in a virtual storage system
D
The swapping area on a disk used by the swapper
Question 29 Explanation: 
Spooling is a technique in which an intermediate device such as disk is interposed between process and low speed i/o device.
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
When  the  result  of  a  computation  depends  on  the  speed  of  the  processes involved there is said to be
A
cycle steating
B
rare condition
C
a time lock
D
a deadlock
Question 30 Explanation: 
When first result depends on ordering of processes it is called race condition.
Speed of processes corresponds to ordering of processes.
Question 31
A counting semaphore was initialized to 10. Then 6P (wait) operations and 4V (signal) operations were completed on this semaphore. The resulting value of the semaphore is
A
0
B
8
C
10
D
12
Question 31 Explanation: 
Let the semaphore be S which is initially 10.
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
A  computer  has  six  tape  drives,  with  n  processes  competing  for  them.  Each process may need two drives. What is the maximum value of n for the system to be deadlock free?
A
6
B
5
C
4
D
3
Question 32 Explanation: 
Each process needs 2 drives. So for deadlock just give each process one drive. So total 6 process can be given 1 drive each and can cause deadlock. So to break deadlock just reduce 1 process.
So maximum no. of process for the system to be deadlock free is 5.
Question 33
Given two union compatible relations R1(A,B) and R2 (C,D), what is the result of the operation R1A = CAB = DR2?
A
R1 ∪ R2
B
R1 × R2
C
R1 - R2
D
R1 ∩ R2
Question 33 Explanation: 
The join here will be selecting only those tuples where A=C and B=D, meaning it is the intersection.
Question 34
Which normal form is considered adequate for normal relational database design?
A
2 NF
B
5 NF
C
4 NF
D
3 NF
Question 34 Explanation: 
3NF, is considered as adequate for normal relational database design, because we can have a 3NF decomposition which is dependency preserving and lossless (not possible for any higher forms).
Question 35
 
A
Age
B
Name
C
Occupation
D
Category
Question 35 Explanation: 
Indexing will be on occupation field because occupation field lexigraphically sorted will give the sequence 1, 3, 2, 5, 4.
Question 36
   
A
3
B
1
C
2
D
4
Question 36 Explanation: 
Question 37
   
A
a+b
B
a-b
C
a+b+c
D
abc
Question 37 Explanation: 
Question 38
The binary relation R = {(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4) on the set A = {1,2,3,4} is
A
reflexive, symmetric and transitive
B
neither reflexive, nor irreflexive but transitive
C
irreflexive, symmetric and transitive
D
irreflexive and antisymmetric
Question 38 Explanation: 
→ Not reflexive because (4, 4) not present.
→ 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?

A
9
B
8
C
7
D
6
Question 39 Explanation: 
Let A be the people who speaks English.
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

A
2
B
5
C
8
D
3
Question 40 Explanation: 
NFA:

Equivalent DFA:

Hence, 5 states.
Question 41
Which of the following statements is false?
A
Every finite subset of a non-regular set is regular
B
Every subset of a regular set is regular
C
Every finite subset of a regular set is regular
D
The intersection of two regular sets is regular
Question 41 Explanation: 
Let regular language L = a*b* and subset of L is anbn, n ≥ 0, which is not regular. Hence option (B) is false.
Question 42
   
A
A⋅B
B
AB+BC+CA
C
D
None of the above
Question 42 Explanation: 
Question 43
Which of the following operations is commutative but not associative?
A
AND
B
OR
C
NAND
D
EXOR
Question 43 Explanation: 
NAND operation is commutative but not associative.
Question 44
Formatting for a floppy disk refers to
A
arranging the data on the disk in contiguous fashion
B
writing the directory
C
erasing the system area
D
writing identification information on all tracks and sectors
Question 44 Explanation: 
The formatted disk capacity is always less than the 'raw' unformatted capacity specified by the disk manufacturers, because some portion of each track is used for sector identification and for gaps between sectors and at the end of track.
Question 45
The address space of 8086 CPU is
A
one Megabyte
B
256 Kilobytes
C
1 K Megabytes
D
64 Kilobytes
Question 45 Explanation: 
Note: Out of syllabus.
Question 46
A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by
A
x(n-1) + 1
B
xn - 1
C
xn + 1
D
x(n+1)
Question 46 Explanation: 
No. of internal node = x
Let no. of leaf nodes = L
Let nt be total no. of nodes.
So, L+x = nt -----(I)
Also for n-ary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = nt -----(II)
So, equating (I) & (II),
L+x = nx+1
L = x(n-1) + 1
Question 47
 
A
89
B
90
C
91
D
92
Question 47 Explanation: 
Value returned by
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
 
A
5
B
25
C
36
D
42
Question 48 Explanation: 
If it is call by reference then answer is 42.
If it is call by value then answer is 36.
Question 49
 
A
15i + j + 84
B
15j + i + 84
C
10i + j + 89
D
10j + i + 89
Question 49 Explanation: 
The address of element A[i][j] will be,
100 + 15 * (i-1) + (j-1)
= 100 + 15i - 15 + j - 1
= 15i + j + 84
Question 50
Faster access to non-local variables is achieved using an array of pointers to activation records called a
A
stack
B
heap
C
display
D
activation tree
Question 50 Explanation: 
Properties of displays:
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for non-local variables but may be complicated to maintain.
Question 51
 
A
12 KB
B
14 KB
C
10 KB
D
8 KB
Question 51 Explanation: 
To enable a process which is larger than the amount of memory allocated to it, we can use overlays. The idea of overlays is to heap only those instructions and data that are needed at any given time. When some instructions are needed, they are loaded into space occupied previously by instructions that are no longer needed.
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 round-robin 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?

A
B
C
D
Question 52 Explanation: 
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:

 
A
B
C
D
Question 53 Explanation: 
Effective memory access time
= 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? R1 and R2 are relations, C1, C2 are selection conditions and A1, A2 are attributes of R1?

 
A
σC1C1(R1)) → σC2C2(R1))
B
σC1A1(R1)) → σA1C1(R1))
C
σC1(R1 ∪ R2) → σC1(R1) ∪ σC1(R2)
D
πA1C1(R1)) → σC1A1(R1))
Question 54 Explanation: 
If the selection condition is on attribute A2, then we cannot replace it by RHS as there will not be any attribute A2 due to projection of A1 only.
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?

A
80%
B
20%
C
60%
D
40%
Question 55 Explanation: 
We assume byte addressable memory - nothing smaller than a byte can be used.
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%
There are 55 questions to complete.