## Gate-1991

Question 2 |

In interleaved memory organization, consecutive words are stored in consecutive memory modules in ________ interleaving, whereas consecutive words are stored within the module in ________ interleaving.

low order, high order |

Question 2 Explanation:

→ Consecutive words in consecutive memory modules in low order interleaving as the lower order bits determine the module.

→ Consecutive words in same memory module in high order interleaving as the higher order bits determine the module.

→ Consecutive words in same memory module in high order interleaving as the higher order bits determine the module.

Question 3 |

9 |

Question 3 Explanation:

Hexadecimal representation of a given no. is,

(9753)

It's binary representation is,

1001011101010011

∴ The no. of 1's is 9.

(9753)

_{16}It's binary representation is,

1001011101010011

∴ The no. of 1's is 9.

Question 4 |

Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 8087 CPU is operated ________.

Out of syllabus. |

Question 5 |

When two 4-bit binary number A = a

_{3}a_{2}a_{1}a_{0}and B = b_{3}b_{2}b_{1}b_{0}are multiplied, the digit c_{1}of the product C is given by _________c _{1} = b_{1}a_{0} ⊕ a_{1}b_{0} |

Question 5 Explanation:

⇒ c

_{1}= b

_{1}a

_{0}⊕ a

_{1}b

_{0}

Question 7 |

The minimum number of comparisons required to sort 5 elements is _____

7 |

Question 7 Explanation:

Minimum no. of comparisons

= ⌈log(n!)⌉

= ⌈log(5!)⌉

= ⌈log(120)⌉

= 7

= ⌈log(n!)⌉

= ⌈log(5!)⌉

= ⌈log(120)⌉

= 7

Question 9 |

4, 1, 6, 7, 3, 2, 5, 8 |

Question 9 Explanation:

Inorder traversal is

(Left, Root, Right)

So, the order will be

4, 1, 6, 7, 3, 2, 5, 8

(Left, Root, Right)

So, the order will be

4, 1, 6, 7, 3, 2, 5, 8

Question 10 |

41 |

Question 10 Explanation:

The recurrence relation for the no. of calls is

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

T(n) = T(n-1) + T(n-2) + 2

T(0) = T(1) = 0 (for fib(0) and fib(1), there are no extra recursive calls)

T(2) = 2

T(3) = 4

T(4) = 8

T(5) = 14

T(6) = 24

T(7) = 40

Counting the initial call, we get

40+1 = 41

Question 11 |

The arithmetic expression : (a + b) * c - d / e * * f is to be evaluated on a two-address machine, where each operands, the number of registers required to evaluate this expression is ______. The number of memory access of operand is __________.

3 , 4 |

Question 11 Explanation:

** is used for exponentiation.

So, in total 3 registers are required and 6 memory operations in total to fetch all operands.

So, in total 3 registers are required and 6 memory operations in total to fetch all operands.

Question 12 |

A given set of processes can be implemented by using only

**parbegin/parend**statement, if the precedence graph of these processes is ________properly nested. |

Question 12 Explanation:

A given set of processes canf th be implemented by using only parbegin/parends statement, if the presedence graph of these processes is properly nested.

Question 13 |

The number of integer-triples (i.j.k) with 1 ≤ i.j.k ≤ 300 such that i + j + k is divisible by 3 is ________

Fill in the blanks. |

Question 14 |

If the longest chain in a partial order is of length n then the partial order can be written as a ______ of n antichains.

disjoint |

Question 14 Explanation:

Suppose the length of the longest chain in a partial order is n. Then the elements in the poset can be partitioned into a disjoint antichains.

Question 15 |

The maximum number of possible edges in an undirected graph with a vertices and k components is ________.

(n-k)(n-k+1)/2 |

Question 15 Explanation:

N vertices and K components.

To get maximum, take one vertex each for each component, except last component.

Now, k-1 components have 1 vertex each and so on edges.

The last component has (n-(k-1)) vertices. So make the last component complete, i.e., it has

= (n-k)(n-k+1)/2

= maximum no. of edges

To get maximum, take one vertex each for each component, except last component.

Now, k-1 components have 1 vertex each and so on edges.

The last component has (n-(k-1)) vertices. So make the last component complete, i.e., it has

^{n-(n-1)}C_{2}= (n-k)(n-k+1)/2

= maximum no. of edges

Question 18 |

A-R, B-P, C-S, D-Q |

Question 18 Explanation:

A-R

B-P

C-S

D-Q

Buddy system: The buddy system is a technique to allocate the memory by dividing the memory into partitions to try to satisfy a memory request as suitably as possible.

Interpretation: Runtime.

Pointer type: Garbage collector dereference the dangling pointer.

Virtual memory: Segmentation.

B-P

C-S

D-Q

Buddy system: The buddy system is a technique to allocate the memory by dividing the memory into partitions to try to satisfy a memory request as suitably as possible.

Interpretation: Runtime.

Pointer type: Garbage collector dereference the dangling pointer.

Virtual memory: Segmentation.

Question 20 |

lower power dissipation | |

greater speed | |

smaller chip size
| |

fewer masks for fabrication | |

none of the above |

Question 20 Explanation:

Note: Out of syllabus.

Question 21 |

faster operation | |

ease of avoiding problems due to hazards | |

lower hardware requirement | |

better noise immunity | |

none of the above |

Question 21 Explanation:

In synchronization, there is a less chance of hazards but it can increase the delay. Then the advantage is ease of avoiding problems due to hazards.

Question 22 |

the length of MAR | |

the available secondary storage | |

the available main memory | |

all of the above | |

none of the above
| |

Both A and B |

Question 22 Explanation:

Virtual memory is independent of size of main memory and depends on available secondary storage.

MAR can hold the address that is generated from CPU and limits the total virtual memory address space.

MAR can hold the address that is generated from CPU and limits the total virtual memory address space.

Question 23 |

executes an instruction supplied by an external device through the INTA signal | |

executes an instruction from memory location 20H | |

executes a NOP | |

none of the above |

Question 23 Explanation:

Note: Out of syllabus.

Question 24 |

latch the output of an I/O instruction into an external latch | |

deactivate the chip-select signal from memory devices | |

latch the 8 bits of address lines AD7-AD0 into an external latch | |

find the interrupt enable status of the TRAP interrupt | |

None of the above |

Question 24 Explanation:

Note: Out of syllabus.

Question 25 |

O(n ^{2}) | |

O(mn) | |

O(m+n) | |

O(m logn) | |

O(m ^{2}) | |

B, D and E |

Question 25 Explanation:

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

→ Where m is no. of edges and n is number of vertices then n = O(m

→ O(m logn) < O(mn)

→ Where m is no. of edges and n is number of vertices then n = O(m

^{2})→ O(m logn) < O(mn)

Question 26 |

20, 10, 20, 10, 20 | |

20, 20, 10, 10, 20 | |

10, 20, 20, 10, 20 | |

20, 20, 10, 20, 10 |

Question 26 Explanation:

PUSH(10), PUSH(20), POP = 20 (i)

→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)

→ PUSH(10), PUSH(10), POP = 10 (iii)

→ PUSH(10), POP = 10 (iv)

→ PUSH(20)

→ PUSH(20), POP = 20 (v)

⇒

→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)

→ PUSH(10), PUSH(10), POP = 10 (iii)

→ PUSH(10), POP = 10 (iv)

→ PUSH(20)

→ PUSH(20), POP = 20 (v)

⇒

**20, 20, 10, 10, 20**Question 27 |

None of the above |

Question 27 Explanation:

Note: Out of syllabus.

Question 28 |

matches the parameters of the macro-definition with locations of the parameters of the macro call | |

matches external names of one program with their location in other programs | |

matches the parameters of subroutine definition with the location of parameters of subroutine call | |

acts as link between text editor and the user | |

acts as a link between compiler and user program. |

Question 28 Explanation:

Linked editor can be able to perform

1) external symbol resolution

2) relocation

1) external symbol resolution

2) relocation

Question 29 |

Recursive descent parsing cannot be used for grammar with left recursion. | |

The intermediate form the representing expressions which is best suited for code optimization is the post fix form.
| |

A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation. | |

Although C does not support call by name parameter passing, the effect can be correctly simulated in C.
| |

No feature of Pascal violates strong typing in Pascal. | |

A and D |

Question 29 Explanation:

(A) It is true. Left recursive grammar if used directly in recursive descent parsing causes an infinite loop. So, left recursion must be removed before giving to a recursive descent parser.

(B) False.

(C) It is false. The language can have dynamic data types which required dynamically growing memory when data type size increases.

(D) Is true and using macro we can do this.

(E) Out of syllabus now.

(B) False.

(C) It is false. The language can have dynamic data types which required dynamically growing memory when data type size increases.

(D) Is true and using macro we can do this.

(E) Out of syllabus now.

Question 30 |

The amount of virtual memory available is limited by the availability of secondary storage. | |

Any implementation of a critical section requires the use of an indivisible machine-instruction, such as test-and-set. | |

The LRU page replacement policy may cause hashing for some type of programs.
| |

The best fit techniques for memory allocation ensures the memory will never be fragmented.
| |

B and D |

Question 30 Explanation:

(A) Is true.

(B) Is false, because one of the solution is Peterson's solution which is purely software based solution without use of hardware.

(C) Is true.

(D) False, memory can get fragmented with best fit technique.

(B) Is false, because one of the solution is Peterson's solution which is purely software based solution without use of hardware.

(C) Is true.

(D) False, memory can get fragmented with best fit technique.

Question 31 |

Both F _{1} and F_{2} are tautologies | |

The conjunction F _{1} ∧ F_{2} is not satisfiable | |

Neither is tautologous | |

Neither is satisfiable | |

None of the above |

Question 31 Explanation:

For the propositional formula A→B to be tautology the T→F condition should never arise.

So, in option (B) it is saying that F< sub>1 ∧ F

And False → anything is always true.

So, in option (B) it is saying that F< sub>1 ∧ F

_{2}is not satisfiable means F_{1}∧ F_{2}is always false.And False → anything is always true.

Question 32 |

L(s) ⊆ L(r) and L(s) ⊆ L(t) | |

L(r) ⊆ L(s) and L(s) ⊆ L(t) | |

L(s) ⊆ L(t) and L(s) ⊆ L(r) | |

L(t) ⊆ L(s) and L(s) ⊆ L(r) | |

None of the above | |

A and C |

Question 32 Explanation:

L(s) ⊆ L(r), because 'r' generates all strings which 's' does but 'r' also generates '101' which 's' does not generate.

L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.

L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.

Question 33 |

It could be undecidable | |

It is Turing-machine recognizable | |

It is a context-sensitive language | |

It is a regular language | |

None of the above | |

B, C and D |

Question 33 Explanation:

(B), (C) and (D) are true. But the strongest answer would be (D), a regular language. Because every finite language is a regular language.

And, regular language ⊂ context-free ⊂ context-sensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.

And, regular language ⊂ context-free ⊂ context-sensitive ⊂ Turing recognizable, would imply that regular language is the strongest answer.

There are 33 questions to complete.