GATE 2005

Question 1

What does the following C-statement declare?

    int ( * f) (int * ) ; 
A
A function that takes an integer pointer as argument and returns an integer.
B
A function that takes an integer as argument and returns an integer pointer.
C
A pointer to a function that takes an integer pointer as argument and returns an integer.
D
A function that takes an integer pointer as argument and returns a function pointer.
Question 1 Explanation: 
int ( * f) (int * )
→ A pointer to a function which takes integer as a pointer and return an integer value.
Question 2

An Abstract Data Type (ADT) is:

A
Same as an abstract class
B
A data type that cannot be instantiated
C
A data type type for which only the operations defined on it can be used, but none else
D
All of the above
Question 2 Explanation: 
An Abstract datatype is a type for objects whose behaviour is defined by set of values and set of operations.
Question 3

A common property of logic programming languages and functional languages is:

A
both are procedural languages
B
both are based on λ-calculus
C
both are declarative
D
both use Horn-clauses
Question 3 Explanation: 
Functional and logic programming languages are also called declarative languages; programs in these languages are said to describe (declaratively) what to do and not (operationally) how to do it.
Question 4

Which one of the following are essential features of an object-oriented programming language?

    (i) Abstraction and encapsulation
    (ii) Strictly-typedness
    (iii) Type-safe property coupled with sub-type rule
    (iv) Polymorphism in the presence of inheritance
A
(i) and (ii) only
B
(i) and (iv) only
C
(i), (ii) and (iv) only
D
(i), (iii) and (iv) only
Question 4 Explanation: 
Abstraction, encapsulation and inheritance are three main features of OOP language.
Question 5

A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

A
An array of 50 numbers
B
An array of 100 numbers
C
An array of 500 numbers
D
A dynamically allocated array of 550 numbers
Question 5 Explanation: 
→ Here we are storing values above 50 and we are ignoring the scores which is less than 50.
→ Then using array of 50 numbers is the best way to store the frequencies.
Question 6

An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are l's. Which one of the following is TRUE?

A
Graph G has no minimum spanning tree (MST)
B
Graph G has a unique MST of cost n-1
C
Graph G has multiple distinct MSTs, each of cost n-1
D
Graph G has multiple spanning trees of different costs
Question 6 Explanation: 
From given data, we can say that the given graph is complete graph with all edge weights 1. Hence weight of MST is n-1.
Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n-1).
Question 7

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:

A
O(n)
B
O(n log n)
C
O(n3/2)
D
O(n3)
Question 7 Explanation: 
First of all, In mathematics the transitive closure of a binary relation R on a set X is defined as the smallest relation on X that contains R and is transitive. More formally, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal.
For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.
To find the transitive closure of given relation, we can represent the given relation by the graph such that if x R y then there should be directed edge between x and y in a graph. For this graph, we have to apply modified Floyd_Warshall Algorithm to find the transitive closure of the graph.
The time complexity of this algorithm is O(V3) where V is the number of vertices in the given graph. You can take here V as the number of elements is set i.e., N. Therefore time complexity for the given question is O(n3).
Question 8

Let A, B and C be non-empty sets and let X = (A - B) - C and Y = (A - C) - (B - C). Which one of the following is TRUE?

A
X = Y
B
X ⊂ Y
C
Y ⊂ X
D
None of these
Question 8 Explanation: 
Consider, A = {1, 2, 3, 4, 5, 6}
B = {1, 3, 4, 5}
C = {2, 4, 5, 6}
X = (A - B) - C
X = {2, 6} - {2, 4, 5, 6}
= ∅
Y = (A - C) - (B - C)
= {1, 3} - { 1, 3}
= ∅
X = Y
X = (A - B) - C
= (1, 5) - (5, 7, 4, 3)
= (1)
Y = (A - C) - (B - C)
= (1, 4) - (2, 4)
= (1)
X = Y
Question 9

The following is the Hasse diagram of the poset [{a,b,c,d,e},<]

The poset is

A
not a lattice
B
a lattice but not a distributive lattice
C
a distributive lattice but not a Boolean algebra
D
a Boolean algebra
Question 9 Explanation: 
It is lattice because both LUB and GLB exist for each pair of the vertex in above Hasse diagram.
But it is not distributed because for some element there are more than one complement. Moreover if it is not distributive then it can't be boolean.
Question 10

Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:

A
6
B
8
C
9
D
13
Question 10 Explanation: 
No. of faces in a planar embedding of a graph is
F = E - V + 2 [From Euler's formula i.e., F + V - E = 2]
F = 19 - 13 +2
F = 8
Question 11

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is

A
12
B
8
C
Less than 8
D
More than 12
Question 11 Explanation: 
No. of vertices = 20
Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices - Minimum cover of vertex G
= 20 - 8
= 12
Question 12

Let f(x) be the continuous probability density function of a random variable X. The probability that a < X ≤ b, is:

A
f(b - a)
B
f(b) - f(a)
C
D
Question 12 Explanation: 
f(x) be the continuous probability density function of random variable X.
Then the probablity be area of the corresponding curve i.e.,
Question 13

The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively:

A
3 and 13
B
2 and 11
C
4 and 13
D
8 and 14
Question 13 Explanation: 
Let say,
Inverse of 4 = m; Inverse of 7 = n
(4×m)%15=1; (7*n)%15=1
Option A: m=3 n=13
12%15≠1 (✖️) 91%15=1 (✔️)
Option B: m=2 n=11
8%15≠1 (✖️) 11%15≠1 (✖️)
Option C: m=4 n=13
16%15=1(✔️) 91%15=1 (✔️)
Option D: m=8 n=14
120%15≠1(✖️) 98%15≠1(✖️)
Question 14

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:

A
ambiguous
B
left-recursive
C
right-recursive
D
an operator-grammar
Question 14 Explanation: 
The given grammar can be turned into a infinite parse tree. So it is ambiguous.
It have A → AA has left recursion.
Question 15

Consider the following circuit.

Which one of the following is TRUE?

A
f is independent of X
B
f is independent of Y
C
f is independent of Z
D
None of X, Y, Z is redundant
Question 15 Explanation: 
f(X,Y,Z) = ((XY’)’ (YZ))’
= ((X’+Y) YZ)’
= (X’YZ + YZ)’
= ((X’+1) YZ)’
= (YZ)’
Question 16

The range of integers that can be represented by an n bit 2's complement number system is:

A
- 2n-1 to (2n-1 - 1)
B
- (2n-1 - 1) to (2n-1 - 1)
C
- 2n-1 to 2n-1
D
- (2n-1 + 1) to (2n-1 - 1)
Question 16 Explanation: 
The maximum (positive) n bit number is 011….1 (i.e., 0 followed by n-1 ones) which is equal to 2n-1 - 1.
The smallest (negative) n bit number is 100..0 (i.e., 1 followed by n-1 zeros) which is equal to - 2n-1.
1000...00
0111...11 <- 1’s complement
1000..00 <- 2’s complement
= - 2n-1
Question 17

The hexadecimal representation of 6578 is

A
1AF
B
D78
C
D71
D
32F
Question 17 Explanation: 
(657)8 = (110 101 111)2
Make 3 zeros on the left side so that the number of bits is multiple of 4.
= (0001 1010 1111)2
= (1 A F)16
Question 18

The switching expression corresponding to f(A, B, C, D) = Σ (1, 4, 5, 9, 11, 12) is:

A
BC'D' + A'C'D + AB'D
B
ABC' + ACD + B'C'D
C
ACD' + A'BC' + AC'D'
D
A'BD + ACD' + BCD'
Question 18 Explanation: 

f(A,B,C,D) = A'C'D + BC'D' + AB'D
Question 19

Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?

A
Neither vectored interrupt nor multiple interrupting devices are possible.
B
Vectored interrupts are not possible but multiple interrupting devices are possible.
C
Vectored interrupts and multiple interrupting devices are both possible.
D
Vectored interrupt is possible but multiple interrupting devices are not possible.
Question 19 Explanation: 
We can use one Interrupt line for all the devices connected.
Also for vectored Interrupts it is always possible if we implement in daisy chain mechanism.
Question 20

Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?

A
I/O protection is ensured by operating system routine(s)
B
I/O protection is ensured by a hardware trap
C