## Gate-1992

Question 1 |

ABC + B'C' + A'C' |

Question 1 Explanation:

We can write this as

⇒ ABC + B'C' + A'C'

⇒ ABC + B'C' + A'C'

Question 2 |

Consider a 3-bit error detection and 1-bit error correction hamming code for 4-bit date. The extra parity bits required would be ________ and the 3-bit error detection is possible because the code has a minimum distance of ________

Fill in the blanks |

Question 3 |

Many microprocessors have a specified lower limit on clock frequency (apart from the maximum clock frequency limit) because ______

clock frequency can't go below this value. |

Question 3 Explanation:

Clock frequency becomes low memory time period of clock becomes high. When this time period increases beyond the time period in which the non-volatile memory contents must be refreshed, we loose those contents. So clock frequency can't go below this value.

Question 4 |

Many of the advanced microprocessors prefetch instructions and store it in an instruction buffer to speed up processing. This speed up is achieved because _________

prefetching the instructions to be executed can save considerable amount of waiting time. |

Question 4 Explanation:

Because CPU is faster than memory. Fetching the instructions from memory would require considerable amount of time while CPU is much faster. So, prefetching the instructions to be executed can save considerable amount of waiting time.

Question 5 |

A simple and reliable data transfer can be accomplished by using the ‘handshake protocol’. It accomplishes reliable data transfer because for every data item sent by the transmitter __________.

in this case receiver has to respond that receiver can be able to receive the data item. |

Question 6 |

In an 11-bit computer instruction format, the size of address field is 4-bits. The computer uses expanding OP code technique and has 5 two-address instructions and 32 two-address instructions and the number of zero-address instructions it can support is _________

256 |

Question 6 Explanation:

In encoding no. of possible instructions = 2

The possibility of no. of encoding taken by two-address instructions = 5×2

By one-address instructions = 32×24 = 512

So, the possibility of zero-address instructions =2048-(1280+512) = 256

^{11}= 2048The possibility of no. of encoding taken by two-address instructions = 5×2

^{4}×2^{4}= 1280By one-address instructions = 32×24 = 512

So, the possibility of zero-address instructions =2048-(1280+512) = 256

Question 7 |

Macro expansion is done in pass one instead of pass two in a pass macro
assembler because _________

all macro definitions are processed during the first pass only due to all macro expansions done during pass 1 only not in pass 2. |

Question 8 |

The purpose of instruction location counter in an assembler is _______

used to assign storage address to the program's statements. |

Question 8 Explanation:

is used to assign storage address to the program's statements. As the instruction of a source module are being assembled, the location counter keeps track of current location in storage.

Question 9 |

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of
an undirected graph containing n vertices and m edges if the edges are sorted is __________

O(m log n) |

Question 9 Explanation:

Though the edges are to be sorted still due to union find operation complexity is O(m log n).

Question 10 |

Maximum number of edges in a planar graph with n vertices is ________

3n - 6 |

Question 10 Explanation:

The maximum is 3(n - 8) for every n>2.

⇒ (3n - 2) = 3n - 6

⇒ (3n - 2) = 3n - 6

Question 11 |

The operation which is commutative but not associative is:

AND | |

OR | |

EX-OR | |

NAND |

Question 11 Explanation:

NAND and NOR operation follow commutativity but do not follow associativity.

Question 12 |

All digital circuits can be realized using only

Ex-OR gates | |

Multiplexers | |

Half adders | |

OR gates | |

Both B and C |

Question 12 Explanation:

NOR gate, NAND gate, Multiplexers and Half adders can also be used to realize all digital circuits.

Question 13 |

Bit-slice processors

Can be cascaded to get any desired word length processor | |

speed of operation is independent of the word length configured | |

don’t contain anything equivalent of program counter in a ‘normal’ microprocessor | |

contain only the data path of a ‘normal’ CPU |

Question 13 Explanation:

Bit string is a technique for constructing a processor from modules of processors of smaller bit width, for the purpose of increasing word length.

Question 14 |

PCHL is an instruction in 8085 which transfers the contents of the register
pair HL to PC. This is not a very commonly used instruction as it changes the
flow of control in rather ‘unstructured’ fashion. This instruction can be useful
in implementing.

if ……. then ….. else ….. construct | |

while …… construct | |

case …… construct | |

call …… construct |

Question 14 Explanation:

Note: Out of syllabus.

Question 15 |

Start and stop bits do not contain an ‘information’ but are used in serial communication for

Error detection | |

Error correction
| |

Synchronization | |

Slowing down the communications |

Question 15 Explanation:

The start and stop bits are used to synchronize the serial receivers.

Question 16 |

Which of the following problems is not NP-hard?

Hamiltonian circuit problem | |

The 0/1 Knapsack problem | |

Finding bi-connected components of a graph | |

The graph colouring problem |

Question 16 Explanation:

Note: Out of syllabus.

Question 17 |

4 | |

5 | |

6 | |

7 | |

Both A and D |

Question 17 Explanation:

Case 1:

Where L is leaf node.

So, no. of internal node is 4.

Case 2:

Where L is leaf node.

So, no. of internal node is 7.

Where L is leaf node.

So, no. of internal node is 4.

Case 2:

Where L is leaf node.

So, no. of internal node is 7.

Question 18 |

A non-planar graph with minimum number of vertices has

9 edges, 6 vertices | |

6 edges, 4 vertices | |

10 edges, 5 vertices | |

9 edges, 5 vertices |

Question 18 Explanation:

The above graph with 5 vertices and 10 edges is non-planar.

Question 19 |

Following algorithm(s) can be used to sort n integers in the range [1...n

^{3}] in O(n) timeHeapsort | |

Quicksort | |

Mergesort | |

Radixsort |

Question 19 Explanation:

As no comparison based sort can ever do any better than nlogn. So option (A), (B), (C) are eliminated. O(nlogn) is lower bound for comparison based sorting.

As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.

As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.

Question 20 |

At a particular time of computation the value of a counting semaphore is 7. Then 20 P operations and 15 V operations were completed on this semaphore. The resulting value of the semaphore is:

42 | |

2 | |

7 | |

12 |

Question 20 Explanation:

Let the semaphore be S.

Initial value of S is 7.

So after 20P operations and 15V operations the value of semaphore S will be,

S = 7-20+15 = 2

Initial value of S is 7.

So after 20P operations and 15V operations the value of semaphore S will be,

S = 7-20+15 = 2

Question 21 |

A computer system has 6 tape drives, with n process completing for them. Each process may need 3 tape drives. The maximum value of n for which the system is guaranteed to be deadlock free is:

2 | |

3 | |

4 | |

1 |

Question 21 Explanation:

Lets give 2 tape driver to each process, so that there will be deadlock. So 3 processes will be given two drives each so that there will be deadlock. So to avoid deadlock maximum no. of process should be 1 less than the minimum no. of process that will cause deadlock. So for n=2, the system is guaranteed to be deadlock free.

Question 22 |

Which of the following is an example of a spooled device?

The terminal used to the input data for a program being executed. | |

The secondary memory device in a virtual memory system | |

A line printer used to print the output of a number of jobs. | |

None of the above |

Question 22 Explanation:

Spool stands for simultaneous peripheral operations online.

Question 23 |

FOLLOW(A) and FOLLOW (A) may be different. | |

FOLLOW(A) and FOLLOW (A) are always the same. | |

All the three sets are identical. | |

All the three sets are different.
| |

Both A and B |

Question 23 Explanation:

LFOLLOW may be different but RFOLLOW and FOLLOW will be same.

Question 24 |

Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statements is/are true?

The go to part of both tables may be different. | |

The shift entries are identical in both the tables. | |

The reduce entries in the tables may be different. | |

The error entries in the tables may be different. | |

B, C and D. |

Question 24 Explanation:

Goto parts and shift entry must be same.

Reduce entry and error entry may be different due to conflicts.

Reduce entry and error entry may be different due to conflicts.

Question 25 |

Which of the following predicate calculus statements is/are valid:

(∀x) P(x) ∨ (∀x)Q(x) → (∀x){P(x) ∨ Q(x)}
| |

(∃x)P(x) ∧ ∃(x)Q(x) → (∃x){P(x) ∧ Q(x)} | |

(∀x){P(x) ∨ Q(x)} → (∀x)P(x) ∨ (∀x)Q(x) | |

(∃x){P(x) ∨ Q(x)} → ~(∀x)P(x) ∨ (∃x)Q(x) |

Question 25 Explanation:

(A) Valid

(B) Invalid

(C) Invalid

(D) Invalid

(B) Invalid

(C) Invalid

(D) Invalid

Question 26 |

Which of the following is/are tautology

a ∨ b → b ∧ c | |

a ∧ b → b ∨ c
| |

a ∨ b → (b → c) | |

a → b → (b → c) |

Question 26 Explanation:

Question 27 |

Which of the following regular expression identifies are true?

r(*) = r* | |

(r*s*) = (r+s)* | |

(r+s)* = r* + s* | |

r*s* = r* + s* |

Question 27 Explanation:

(A) Answer.

(B) RHS generates Σ* while LHS can't generate strings where r comes after s like sr, srr, etc.

LHS ⊂ RHS.

(C) LHS generates Σ* while RHS can't generate strings where r comes after an s.

RHS ⊂ LHS.

(D) LHS contains all strings where after an s, no r comes. RHS contains all strings of either r or s but no combination of them.

So, RHS ⊂ LHS.

(B) RHS generates Σ* while LHS can't generate strings where r comes after s like sr, srr, etc.

LHS ⊂ RHS.

(C) LHS generates Σ* while RHS can't generate strings where r comes after an s.

RHS ⊂ LHS.

(D) LHS contains all strings where after an s, no r comes. RHS contains all strings of either r or s but no combination of them.

So, RHS ⊂ LHS.

Question 28 |

If G is a context-free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is Chomsky normal form?

2l | |

2l + 1 | |

2l - 1 | |

l |

Question 28 Explanation:

For CNF, it is

2l - 1

For GNF, it is

l

2l - 1

For GNF, it is

l

Question 29 |

Context-free languages are

closed under union | |

closed under complementation | |

closed under intersection | |

closed under Kleene closure | |

Both A and D |

Question 29 Explanation:

CFL's are not closed under intersection and complementation.

Question 30 |

M _{1} is non-deterministic finite automaton | |

M _{1} is a non-deterministic PDA | |

M _{1} is a non-deterministic Turing machine | |

For no machine M _{1} use the above statement true | |

Both A and C |

Question 30 Explanation:

For every NFA there exists a DFA.

For every NPDA there does not exist a deterministic PDA.

Every non-deterministic TM has an equivalent deterministic TM.

For every NPDA there does not exist a deterministic PDA.

Every non-deterministic TM has an equivalent deterministic TM.

Question 32 |

a-2, b-1, c-2, d-1 |

Question 32 Explanation:

Two pass assembler.

Pass 1:

→ Assign addresses to all statements.

→ Save the values assigned to all labels for use in pass 2.

→ Perform some processing of assembler directives.

Pass 2:

→ Assembler instructions by translating opcode and symbolic operands.

→ Generate data values defined by BYTE, WORD.

→ Perform processing of assembler directives not done in pass 1.

→ Write the object program and the assembly listing.

Pass 1:

→ Assign addresses to all statements.

→ Save the values assigned to all labels for use in pass 2.

→ Perform some processing of assembler directives.

Pass 2:

→ Assembler instructions by translating opcode and symbolic operands.

→ Generate data values defined by BYTE, WORD.

→ Perform processing of assembler directives not done in pass 1.

→ Write the object program and the assembly listing.

Question 33 |

How many edges are there in a forest with p components having n vertices in all?

n-p |

Question 33 Explanation:

Forest is a graph with no cycle.

Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).

So, total of n-p edges for p components.

Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).

So, total of n-p edges for p components.

Question 34 |

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…..n] are to be sorted, give an input for which Quicksort takes maximum time.

n |

Question 34 Explanation:

For n distinct elements the algorithm will take maximum time when:

→ The array is already sorted in ascending order.

→ The array is already sorted in descending order.

→ The array is already sorted in ascending order.

→ The array is already sorted in descending order.

Question 35 |

Which page replacement policy sometimes leads to more page faults when size of memory is increased?

FIFO |

Question 35 Explanation:

FIFO, because it sometimes leads to more page faults when size of memory is increased.

There are 35 questions to complete.