Gate-1999 – RBR

Question 1

Suppose that the expectation of a random variable X is 5. Which of the following statements is true?

A	There is a sample point at which X has the value 5.
B	There is a sample point at which X has value greater than 5.
C	There is a sample point at which X has a value greater than or equal to 5.
D	None of the above

Engineering-Mathematics Probability

Question 1 Explanation:

Expectation of discrete random variable
E(X) = x₁P₁ + x₂P₂ + ... + x_nP_n
In question, E(X) is given as 5.
E(X) = 5, 0≤P_i≤1
P₁ + P₂ + ... + P_n = 1 [Probability]
Therefore, E(X) = 5 is possible only if atleast one of the x_i value is greater than 5.

Question 2

The number of binary relations on a set with n elements is:

A	n²
B	2ⁿ
C	2^{n (²)}
D	None of the above

Engineering-Mathematics Sets-And-Relation

Question 2 Explanation:

In binary relation two elements are selected from a set. So total no. of pairs possible are
n×n = n²
Now, no. of binary relations possible is
2ⁿ²
Because each pair have two possibilities either chosen or not chosen.

Question 3

The number of binary strings of n zeroes and k ones that no two ones are adjacent is

A	^n-1C_k
B	ⁿC_k
C	ⁿC_k+1
D	None of the above

Engineering-Mathematics Combinatorics

Question 3 Explanation:

Since there are n zeroes, so
XOXOXOXOXOXOX
n+1 gaps can be possible, where 1's can be placed so that no two one's are adjacent. So, no. of ways in which k 1's can be placed in n+1 gaps are,
ⁿ⁺¹C_k

Question 4

Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite automation that recognizes the language represented by this regular expression contains

A	n states
B	n + 1 states
C	n + 2 states
D	None of the above

Theory-of-Computation Finite-Automata

Question 4 Explanation:

Let's draw both NFA and DFA and see which one requires less no. of state.
DFA:

So, DFA requires (n+2) state.
NFA:

So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1

Question 5

Context-free languages are closed under:

A	Union, intersection
B	Union, Kleene closure
C	Intersection, complement
D	Complement, Kleene closure

Theory-of-Computation Context-Free-Language

Question 5 Explanation:

Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.

Question 6

Let L_D be the set of all languages accepted by a PDA by final state and L_E the set of all languages accepted by empty stack. Which of the following is true?

A	L_D = L_E
B	L_D ⊃ L_E
C	L_E = L_D
D	None of the above

Theory-of-Computation Push-Down-Automata

Question 6 Explanation:

For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.

Question 7

A	x NAND X
B	x NOR x
C	x NAND 1
D	x NOR 1

Digital-Logic-Design Logic-Gates

Question 7 Explanation:

Question 8

A
B
C
D

Digital-Logic-Design K-Map

Question 8 Explanation:

⇒ CD+AD = D(A+C)

Question 9

A	(A) – 2 (B) – 4 (C) – 3 (D) - 1
B	(A) – 1 (B) – 2 (C) – 3 (D) – 4
C	(A) – 3 (B) – 2 (C) – 4 (D) - 1
D	(A) – 4 (B) – 1 (C) – 2 (D) – 3

Operating-Systems Match-the-Following

Question 9 Explanation:

⇒ Threads are handled by CPU.
⇒ Virtual address is a memory type.
⇒ File system is used to manage the disk.
⇒ Interrupt is a signal.

Question 10

Which of the following disk scheduling strategies is likely to give the best through put?

A	Farthest cylinder next
B	Nearest cylinder next
C	First come first served
D	Elevator algorithm

Operating-Systems Disk-Scheduling

Question 10 Explanation:

Farthest cylinder next - Longest job first
Nearest cylinder next - SSTF
First come first served - FCFS
Elevator - SCAN
SSTF always serves the request of nearest cylinder first. Due to which the necessary movement gets reduced.

Question 11

System calls are usually invoked by using

A	a software interrupt
B	polling
C	an indirect jump
D	a privileged instruction

Operating-Systems System-Calls

Question 11 Explanation:

Software interrupts are implementing device drivers (or) transitions between protected mode of operations, such as system calls.

Question 12

A sorting technique is called stable if

A	it takes O (nlog n) time
B	it maintains the relative order of occurrence of non-distinct elements
C	it uses divide and conquer paradigm
D	it takes O(n) space

Algorithms Sorting

Question 12 Explanation:

Sorting techniques are said to be stable if it maintains the relative order of occurence of non-distinct element.

Question 13

Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

A	n - 1
B	n
C	n + 1
D	None of the above

Algorithms Time-Complexity

Question 13 Explanation:

Minimum no. of exchanges required in worst case will be when 1^st half will contain all +ve nos and 2^nd half will conain all -ve nos.
Now we will swap 1^st no. with n^th no. and then 2^nd no. with (n-1)^th no. and then 3^rd no. with (n-2)^th and so on. Like this we will have to do n/2 swaps in worst case.

Question 14

A	8, 9, 15, 20, 47, 4, 12, 17, 30, 40
B	8, 15, 20, 47, 4, 9, 30, 40, 12, 17
C	15, 20, 47, 4, 8, 9, 12, 30, 40, 17
D	4, 8, 9, 15, 20, 47, 12, 17, 30, 40

Algorithms Sorting

Question 14 Explanation:

Question 15

A	0
B	1
C	2
D	3

Data-Structures Graphs

Question 15 Explanation:

Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3

Question 16

If n is a power of 2, then the minimum number of multiplications needed to compute a* is

A	log₂ n
B	√n
C	n-1
D	n

Algorithms Time-Complexity

Question 16 Explanation:

We require 4 multiplications to calculate a¹⁶ .....(I)
→ Like that 3 multiplications requires to calculate a⁸ .....(II)
I, II are satisfied with the option A.

Question 17

Which of the following is the most powerful parsing method?

A	LL (1)
B	Canonical LR
C	SLR
D	LALR

Compiler-Design Parsers

Question 17 Explanation:

Canonical LR is most powerful.
LR > LALR > SLR

Question 18

Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are

A	m + n and 0
B	mn and 0
C	m + n and \|m – n\|
D	mn and m + n

Database-Management-System Relational-Algebra

Question 18 Explanation:

For maximum:
Suppose there is no common attribute in R and S due to which natural join will act as cross product. So then in cross product total no. of tuples will be mn.
For minimum:
Suppose there is common attribute in R and S, but none of the row of R matches with rows of S then minimum no. of tuples will be 0.

Question 19

A	σ_{(A=10∨B=20)} (r)
B	σ_(A=10) (r) ∪ σ_(B=20) (r)
C	σ_(A=10) (r) ∩ σ_(B=20) (r)
D	σ_(A=10) (r) - σ_(B=20) (r)

Database-Management-System Relational-Algebra

Question 19 Explanation:

The given relational algebra expression represents tuples having A=10 and B=20 which is equivalent to
σ_(A=10) (r) ∩ σ_(B=20) (r)

Question 20

Booth’s coding in 8 bits for the decimal number –57 is

A	0 – 100 + 1000
B	0 – 100 + 100 -1
C	0 – 1 + 100 – 10 + 1
D	00 – 10 + 100 - 1

Digital-Logic-Design Number-Systems

Question 20 Explanation:

Represent the multiplier in 2's complement form.
-57 = 1100 0111
In Booth's algorithm, an operation (ADD or SUB) or/and Arithmetic Right Shift (ARS) operation is performed based on two least significant bits(Q0 Q-1) of Multiplier.
(Note: After RIGHT shift operation bits in higher significant positions move to lower significant position)

Question 21

The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is

A	On²
B	O(n)
C	O(log n)
D	O(1)

Digital-Logic-Design Multiplexer

Question 21 Explanation:

Total no. of gates being used for 'n' bit multiplication in an array multiplier (n*n) = (2n-1)
Total delay = 1 * 2n - 1 = O(2n - 1) = n

Question 22

The main memory of a computer has 2 cm blocks while the cache has 2 c blocks. If the cache uses the set associative mapping scheme with 2 blocks per set, then block k of the main memory maps to the set

A	(k mod m) of the cache
B	(k mod c) of the cache
C	(k mod 2c) of the cache
D	(k mod 2 cm) of the cache

Computer-Organization Cache

Question 22 Explanation:

No. of sets in cache = No. of blocks in cache/No. of blocks per set
= 2c/c
= c
∴ Cache set no. to which block k of main memory maps to
= (Main memory block no.) mod (Total set in cache)
= k mod c

Question 23

The Newton-Raphson method is to be used to find the root of the equation f(x)=0 where x_o is the initial approximation and f' is the derivative of f. The method converges

A	always
B	only if f is a polynomial
C	only if f(x₀) < 0
D	None of the above

Engineering-Mathematics Newton-Raphson-Method

Question 23 Explanation:

Note: Out of syllabus.

Question 24

Let R = (a, b, c, d, e, f) be a relation scheme with the following dependencies c → f, e → a, ec → d, a → b. Which of the following is a key for R?

A	CD
B	EC
C	AE
D	AC

Database-Management-System Functional-Dependency

Question 24 Explanation:

Let's check closure for each option,
A) (CD)⁺ = cdf
Not a key.
B) (EC)⁺ = ecdabf
Yes, it is a key.
C) (AE)⁺ = aeb
Not a key. D) (AC)⁺ = abcf
Not a key.

Question 25

Which of the following is correct?

A	B-trees are for storing data on disk and B⁺ trees are for main memory.
B	Range queries are faster on B* trees.
C	B-trees are for primary indexes and B* trees are for secondary indexes.
D	The height of a B* tree is independent of the number of records.

Database-Management-System B+-Trees

Question 25 Explanation:

Range queries are faster on B⁺ trees.

Question 26

A
B	Events E₁ and E₂ are independent
C	Events E₁ and E₂ are not independent
D

Engineering-Mathematics Probability

Question 26 Explanation:

Question 27

Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers amongst themselves?

A	1638
B	2100
C	2640
D	None of the above

Engineering-Mathematics Combinatorics

Question 27 Explanation:

Formula for distributing n identical objects into r persons is,
^n+r-1C_r-1
So for 10 roses,
^10+2-1C_2-1 = ¹¹C₁ = 11
For 15 sunflowers,
^15+2-1C_2-1 = ¹⁶C₁ = 16
For 15 daffodils,
^15+2-1C_2-1 = ¹⁶C₁ = 16
∴ The final answer is,
11×16×16 = 2816

Question 28

Let L be a set with a relation R which is transitive, anti-symmetric and reflexive and for any two elements a, b ∈ L let the least upper bound lub (a,b) and the greatest lower bound glb (a,b) exist. Which of the following is/are true?

A	L is a poset
B	L is a Boolean algebra
C	-L1 is context free
D	-L2 is regular
E	Both A and C

Engineering-Mathematics Sets-And-Relation

Question 28 Explanation:

Note: Options given are wrong.

Question 29

If L is context free language and L2 is a regular language which of the following is/are false?

A	L1 – L2 is not context free
B	L1 ∩ L2 is context free
C	~L1 is context free
D	~L2 is regular
E	Both A and C

Theory-of-Computation Identify-Class-Language

Question 29 Explanation:

(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 - L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 - L2 is CFL.
So False.
(B) As we said that CFL is closed under regular intersection.
So True.
(C) CFL is not closed under complementation.
Hence False.
(D) Regular language is closed under complementation.
Hence True.

Question 30

Given the programming constructs (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) if-then-else (iv) forward go to (v) arbitrary go to (vi) non-recursive procedure call (vii) recursive procedure/function call (viii) repeat loop, which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming language.

A	(ii), (iii), (iv)
B	(v), (vii), (viii)
C	(vi), (vii), (viii)
D	(iii), (vii), (viii)

Programming Programming-Constructs

Question 30 Explanation:

Arbitrary goto, recursive call and repeat loop may enter infinite loop and the program might never terminate.

Question 31

A	This schedule is serialized and can occur in a scheme using 2PL protocol
B	This schedule is serializable but cannot occur in a scheme using 2PL protocol
C	This schedule is not serialiable but can occur in a scheme using 2PL protocol
D	This schedule is not seralisable and cannot occur in a scheme using 2PL protocol.

Database-Management-System Transactions

Question 31 Explanation:

Let's draw precedence graph,

Since cycle exist so not conflict serializable.
And we know that if the schedule is not serializable then it is not 2PL.
Hence correct option is (D).

Question 32

Consider the schema R = (S T U V) and the dependencies S → T, T → U, U → V and V → S. Let R = (R1 and R2) be a decomposition such that R1 ∩ R2 ≠ ∅ . The decomposition is

A	not in 2NF
B	in 2NF but not 3NF
C	in 3NF but not in 2NF
D	in both 2NF and 3NF

Database-Management-System Normalization

Question 32 Explanation:

Since R1 ∩ R2 = ∅, so the decomposition is lossless join. Now since all the attributes are keys, so R1 ∩ R2 will be a key of the decomposed relation.
And since every attribute is key so the decomposed relation will be in BCNF and hence in 3NF.

Question 33

A	A = 0, B = 0, C = 1
B	A = 0, B = 1, C = 1
C	A = 1, B = 0, C = 1
D	A = 1, B = 1, C = 1

Database-Management-System Logic-Gates

Question 33 Explanation:

So the above equation is satisfied if either C=0 or A=0 and B=1.
Hence, Option (B) is correct.

Question 34

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

A	XOR gates, NOT gates
B	2 to 1 multiplexors
C	AND gates, XOR gates
D	Three-input gates that output (A⋅B) + C for the inputs A⋅B and C
E	Both B and C

Database-Management-System Boolean-Functions

Question 34 Explanation:

(A) Not complete because, XOR can be used to make only NOT gate and NOT gate is already available. Hence not complete.
(B) 2 to 1 multiplexors is functionally complete.
(C) XOR gate can be used to make a NOT gate. So, (AND, NOT) is functionally complete.
(D) With given gates and inputs NOT gate cannot be derived.
Hence, not complete.

Question 35

A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

A	Address translation
B	DMA for disk transfer
C	At least two modes of CPU execution (privileged and non-privileged)
D	Demand paging
E	Both A and C

Operating-Systems Virtual Memory

Question 35 Explanation:

Address translation and atleast two modes of CPU execution (Privileged and non-privileged) are needed to implement multiuser and multiprocessing operating system, because address translation provides memory protection which ensures that a given process does not interfere with another, and we need privileged and non-privileged instruction, so that user and OS interconnects properly.

Question 36

Which of the following is/are advantage of virtual memory?

A	Faster access to memory on an average.
B	Processes can be given protected address spaces.
C	Linker can assign addresses independent of where the program will be loaded in physical memory.
D	Programs larger than the physical memory size can be run.
E	Both B and D

Operating-Systems Virtual Memory

Question 36 Explanation:

A) False. Because in virtual memory concept address translation is required due to which access is slow.
B) True. Because in virtual memory concept of address translation provides protected address space so that one process do not interfere the other process.
C) False.
D) True.

Question 37

Which of the following actions is/are typically not performed by the operating system when switching context from process A to process B?

A	Saving current register values and restoring saved register values for process B.
B	Changing address translation tables.
C	Swapping out the memory image of process A to the disk.
D	Invalidating the translation look-aside buffer.

Operating-Systems Context-Switching

Question 37 Explanation:

A) True.
B) True.
C) False, because swapping is done when the process is suspended and not during context switching.
D) True, Invalidation of TLB is necessary because, if the TLB is not invalidated then the new process might end up using the translation of old process. Note that Invalidation of TLB is necessary but saving and reuse of TLB is not necessary.

Question 38

A	0.125 0.125
B	0.25 0.25
C	0.25 0.125
D	0.125 0.25

Operating-Systems Dynamic-Scoping

Question 38 Explanation:

Note: Out of syllabus.

Question 39

The number of tokens in the Fortran statement DO 10 I = 1.25 is

A	3
B	4
C	5
D	None of the above

Compiler-Design Compilers

Question 39 Explanation:

DO → 1
10 → 2
I → 3
= → 4
1.25 → 5

Question 40

A grammar that is both left and right recursive for a non-terminal, is

A	Ambiguous
B	Unambiguous
C	Information is not sufficient to decide whether it is ambiguous or unambiguous
D	None of the above

Theory-of-Computation Grammar

Question 40 Explanation:

If a grammar is both left and right recursion, then grammar may or may not be ambiguous.

Question 41

The number of full and half-adders required to add 16-bit numbers is

A	8 half-adders, 8 full-adders
B	1 half-adder, 15 full-adders
C	16 half-adders, 0 full-adders
D	4 half-adders, 12 full-adders

Digital-Logic-Design Adder

Question 41 Explanation:

For Least Significant Bit we do not need a full adder since initially carry is not present.
But for rest of bits we need full address since carry from previous addition has to be included into the addition operation.
So, in total 1 half adder and 15 full adders are required.

Question 42

Zero has two representations in

A	Sign magnitude
B	1’s complement
C	2’s complement
D	None of the above
E	Both A and B

Digital-Logic-Design Number-Systems

Question 42 Explanation:

Sign magnitude:
+0 = 0000
-0 = 1000
1's complement:
+0 = 0000
-0 = 1111

Question 43

Raid configurations of the disks are used to provide

A	Fault-tolerance
B	High speed
C	High data density
D	None of the above

Computer-Organization RAID

Question 43 Explanation:

Raid is a way of storing the same data in different places on multiple hard disks to protect data in the case of drive failure.
So, we can say that RAID is used to provide fault tolerence.

Question 44

Arrange the following configuration for CPU in decreasing order of operating speeds: Hard wired control, vertical microprogramming, horizontal microprogramming.

A	Hard wired control, vertical micro-programming, horizontal micro- programming.
B	Hard wired control, horizontal micro-programming, vertical micro- programming.
C	Horizontal micro-programming, vertical micro-programming, Hard wired control.
D	Vertical micro-programming, horizontal micro-programming, hard wired control.

Computer-Organization Micro-Programming

Question 44 Explanation:

Hardwired control involves only hardware which is definitely faster than microprogramming approach.
Now between horizontal and vertical microprogramming, the signals in vertical microprogramming are in encoded form which has to be decoded first using decoder. So, horizontal microprogramming is faster than vertical microprogramming.

Question 45

The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:

A	165
B	90
C	75
D	65

Algorithms Greedy-Algorithm

Question 45 Explanation:

Always merge two files with minimum no. of records.
10, 20, 15, 5, 25
Merge 5 & 10:
5+10=15 movements
Now the list is
15, 20, 15, 25
Merge 15 & 15:
15+15=30 movements
Now the list is
30, 20, 25
Merge 20 & 25:
20+25=45 movements
Now the list is
30, 45
Merge 30 & 45:
30+45=75 movements
∴ Total no. of movements
= 15+30+45+75
= 165

Question 46

A	M – W N – V O – U P - X
B	M – W N – U O – X P - V
C	M – V N – W O – X P - U
D	None of the above

Algorithms Time-Complexity

Question 46 Explanation:

(M) T(n) = Sum of first n matural nos. = n(n+1)/2 = O(n²)
(N) Apply Master's theorem
T(n) = θ(n) = O(n)
(O) Apply Master's theorem
T(n) = θ(n logn) = O(n logn)
(P) Here we are adding the log of firstn natural numbers.
So,
T_n = log1 + log2 + log3 + ... + logn
= log (1×2×...n)
= log(n!)
= θ(n logn)

Question 47

The main differences(s) between a CSIC and A RISC processor is/are that a RISC processor typically

A	has fewer instructions
B	has fewer addressing modes
C	has more registers
D	is easier to implement using hard-wired control logic
E	All the above

Computer-Organization CISC-and-RISC

Question 47 Explanation:

All are properties of RISC processor.

Question 48

A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this processor?

A	Pointers
B	Arrays
C	Records
D	Recursive procedures with local variable
E	All the above

Computer-Organization Addressing-Modes

Question 48 Explanation:

A) Cannot be implemented because pointers need indirect addressing mode.
B) Cannot be implemented because arrays need Register indexing.
C) Records also needs pointers which needs indirect addressing modes, so this also cannot be implemented.
D) Recursive procedures needs stack, and so it needs stack pointers which inturn needs indirect addressing. So this also cannot be implemented.

Question 49

A	Finds the maximum of a, b, and c
B	Finds the minimum of a, b and c
C	Finds the middle number of a, b, c
D	None of the above

Programming C-Programming

Question 49 Explanation:

Try for (3,2,2), it will go for infinite loop.

Question 50

Which of the following is/are correct?

A	An SQL query automatically eliminates duplicates
B	An SQL query will not work if there are no indexes on the relations
C	SQL permits attribute names to be repeated in the same relation
D	None of the above

Database-Management-System SQL

Question 50 Explanation:

→ SQL won't remove duplicates like relational algebra projection, we have to remove it explicitly by distinct.
→ If there are no indexes on the relation SQL, then also it works.
→ SQL does not permit 2 attributes to have same name in a relation.