## GATE 2000

 Question 1

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from some same suit is

 A 3 B 8 C 9 D 12
Question 1 Explanation:
No. of cards = 52
No. of suits = 4(P)
Apply pigeon hole principal.
Then number of pigeons = n
floor [(n-1)/P] + 1 = 3
floor [(n-1)/P] = 2
floor [(n-1)] = 8
floor (n) = 8 + 1
n ≥ 9
Minimum no. of cards, n = 9
 Question 2

An n x n array v is defined as follows:

`v[i,j] = i-j for all i,j, 1 ≤ i ≤ n, 1 ≤ j ≤ n `

The sum of the elements of the array v is

 A 0 B n -1 C n2 - 3n + 2 D n2 (n+1)/2
Question 2 Explanation:
Let us consider n=5 then we get

Add ith row and jth column if we zero, apply to all row and their corresponding column the total becomes zero.
 Question 3

The determinant of the matrix is

is:

 A 4 B 0 C 15 D 20
Question 3 Explanation:
The value of the determinant is 2 * 1 * 2 * 1 = 4
 Question 4

Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

 A S ⊂ T B T ⊂ S C S = T D S ∩ T = ɸ
Question 4 Explanation:
If we draw DFA for language S and T it will represent same.
 Question 5

Let L denotes the language generated by the grammar S → 0S0/00.
Which of the following is true?

 A L = 0+ B L is regular but not 0+ C L is context free but not regular D L is not context free
Question 5 Explanation:
The given grammar results that a string which contains even length excluding empty string i.e {00,000000,00000000,…….}. So which is regular but not 0+.
 Question 6

The number 43 in 2’s complement representation is

 A 01010101 B 11010101 C 00101011 D 10101011
Question 6 Explanation:
Positive integers are represented in its normal binary form while negative numbers are represented in its 2′s complement form. Binary representation of 43 is 00101011.
 Question 7

To put the 8085 microprocessor in the wait state

 A lower the HOLD input B lower the READY input C raise the HOLD input D raise the READY input
Question 7 Explanation:
If ready pin is high the microprocessor will complete the operation and proceeds for the next operation. If ready pin is low the microprocessor will wait until it goes high.
 Question 8

Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-pipelined but identical CPU, we can say that

 A T1 ≤ T2 B T1 ≥ T2 C T1 < T2 D T1 is T2 plus the time taken for one instruction fetch cycle
Question 8 Explanation:
PIPELINING SYSTEM:
Pipelining is an implementation technique where multiple instructions are overlapped in execution. It has a high throughput (amount of instructions executed per unit time). In pipelining, many instructions are executed at the same time and execution is completed in fewer cycles. The pipeline is filled by the CPU scheduler from a pool of work which is waiting to occur. Each execution unit has a pipeline associated with it, so as to have work pre-planned. The efficiency of pipelining system depends upon the effectiveness of CPU scheduler.
NON- PIPELINING SYSTEM:
All the actions (fetching, decoding, executing of instructions and writing the results into the memory) are grouped into a single step. It has a low throughput.
Only one instruction is executed per unit time and execution process requires more number of cycles. The CPU scheduler in the case of non-pipelining system merely chooses from the pool of waiting work when an execution unit gives a signal that it is free. It is not dependent on CPU scheduler.
 Question 9

The 8085 microprocessor responds to the present of an interrupt

 A as soon as the TRAP pin becomes ‘high’ B by checking the TRAP pin for ‘high’ status at the end of each instruction each C by checking the TRAP pin for ‘high’ status at the end of the execution of each instruction D by checking the TRAP pin for ‘high’ status at regular intervals
Question 9 Explanation:
TRAP is non maskable interrupt . TRAP is active high, level, edge triggered non maskable highest priority interrupt. When TRAP line is active microprocessor insert intervals restarts automatically at vector location of TRAP.
 Question 10

The most appropriate matching for the following pairs

```    X: Indirect addressing            1 : Loops
Y: Immediate addressing           2 : Pointers
Z: Auto decrement addressing      3: Constants  ```

is

 A X – 3 Y – 2 Z - 1 B X – 1 Y – 3 Z - 2 C X – 2 Y – 3 Z - 1 D X – 3 Y – 1 Z - 2
Question 10 Explanation:
Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.
Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.
Auto increment or decrements can be one by using loops.
 Question 11

The following C declarations

```struct node
{
int i;
float j;
};
struct node *s[10]; ```

define s to be

 A An array, each element of which is a pointer to a structure of type node B A structure of 2 fields, each field being a pointer to an array of 10 elements C A structure of 3 fields: an integer, a float, and an array of 10 elements D An array, each element of which is a structure of type node
Question 11 Explanation:
The given code represents an array of s[ ], in this each element is a pointer to structure of type node.
 Question 12

The most appropriate matching for the following pairs

```    X: m=malloc(5); m= NULL;        1: using dangling pointers
Y: free(n); n->value=5;         2: using uninitialized pointers
Z: char *p; *p = ’a’;           3. lost memory  ```

is:

 A X – 1 Y – 3 Z – 2 B X – 2 Y – 1 Z – 3 C X – 3 Y – 2 Z – 1 D X – 3 Y – 1 Z – 2
Question 12 Explanation:
X → m = NULL will results the loss of memory.
Y → n is pointer to invalid memory, a making it as a dangling pointer.
Z → p is not initialized.
p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.
 Question 13

The most appropriate matching for the following pairs

```          X: depth first search            1: heap
Z: sorting                       3: stack  ```

is

 A X – 1 Y – 2 Z – 3 B X – 3 Y – 1 Z – 2 C X – 3 Y – 2 Z – 1 D X – 2 Y – 3 Z – 1
Question 13 Explanation:
Stack is used in depth first search.
Queue is used in breadth-first search.
Heap is used in heap.
 Question 14

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

 A (1 2 (4 5 6 7)) B (1 (2 3 4) 5 6) 7) C (1 (2 3 4) (5 6 7)) D (1 (2 3 NULL) (4 5))
Question 14 Explanation:
Option C:

(Proper Representation)
 Question 15

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. Which of the following statements is true?

 A t(n) is O(1) B n ≤ t(n) ≤ n log2 n C n log2 n ≤ t(n) < (n/2) D t(n) = (n/2)
Question 15 Explanation:
Since the array is sorted. Now just pick the first two minimum elements and check if their sum is less than 1000 or not. If it is less than 1000 then we found it and if not then it is not possible to get the two elements whose sum is less than 1000. Hence, it takes constant time. So, correct option is (A).
 Question 16

Aliasing in the context of programming languages refers to

 A multiple variables having the same memory location B multiple variables having the same value C multiple variables having the same identifier D multiple uses of the same variable
Question 16 Explanation:
In computer programming, aliasing refers to the situation where the same memory location can be accessed using different names.
 Question 17

Consider the following C declaration

```struct {
short s [5]
union {
float y;
long z;
} u;
} t; ```

Assume that objects of the type short, float and long occupy 2 bytes, 4 bytes and 8 bytes, respectively. The memory requirement for variable t, ignoring alignment considerations, is

 A 22 bytes B 14 bytes C 18 bytes D 10 bytes
Question 17 Explanation:
short [5] = 5×2 = 10
max[float, long] = max [4, 8] = 8
Total = short[5] + max[float,long] = 10 + 8 = 18
There are 17 questions to complete.

Register Now