## GATE 2010

 Question 1

Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then

 A |S| = 2|T| B |S| = |T| - 1 C |S| = |T| D |S| = |T| + 1
Engineering-Mathematics       Graph-Theory
Question 1 Explanation: id= no. of vertices of degree ‘d’ in ‘G’
Eg: No. of vertices with degree ‘2’ = 3
ξ(G') = 3 × 2 = '6' i.e., sum of degrees
By Handshaking Theorem,
The sum of degrees would be equal to twice the no. of edges
|V| = 2|E|
It is given that ξ(G) = ξ(S) then
Sum of degrees of vertices in G is equal to sum of degrees of vertices in S
i.e., 2*(no. of edges in G) = 2*no. of edges in S no. of edges in G = no. of edges in S
Eg: ξ(G) = (2 × 2) + (2 × 3) = 4 + 6 = 10 ξ(S) = 2 × 5 = 10
You can observe that, though no. of vertices are different, but still no. of edges are same.
 Question 2

Newton-Raphson method is used to compute a root of the equation x2 - 13 = 0 with 3.5 as the initial value. The approximation after one iteration is

 A 3.575 B 3.676 C 3.667 D 3.607
Engineering-Mathematics       Newton-Raphson-Method
Question 2 Explanation:
Note: Out of syllabus.
 Question 3

What is the possible number of reflexive relations on a set of 5 elements?

 A 210 B 215 C 220 D 225
Engineering-Mathematics       Sets-And Relation
Question 3 Explanation:
Let set = ‘A’ with ‘n’ elements,
Definition of Reflexive relation:
A relation ‘R’ is reflexive if it contains xRx ∀ x∈A
A relation with all diagonal elements, it can contain any combination of non-diagonal elements.
Eg:
A={1, 2, 3}  So for a relation to be reflexive, it should contain all diagonal elements. In addition to them, we can have possible combination of (n2-n)non-diagonal elements (i.e., 2n2-n)
Ex:
{(1,1)(2,2)(3,3)} ----- ‘0’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)} ----- ‘1’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)(1,3)} “
___________ “
___________ “
{(1,1)(2,2)(3,3)(1,2)(1,3)(2,1)(2,3)(3,1)(3,2)} (n2-n) diagonal elements
____________________
Total: 2n2-n
For the given question n = 5.
The number of reflexive relations = 2(25-5) = 220
 Question 4

Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If * denotes the multiplication operation, the structure (S,*) forms

 A A group B A ring C An integral domain D A field
Engineering-Mathematics       Sets-And Relation
Question 4 Explanation:
A Group is an algebraic structure which satisfies
1) Closure
2) Associativity
3) Have Identity element
4) Invertible
Over ‘*’ operation the S = {1, ω, ω2} satisfies the above properties.
The identity element is ‘1’ and inverse of 1 is 1, inverse of ‘w’ is 'w2' and inverse of 'w2' is 'w'.
 Question 5

What is the value of A 0 B e-2 C e-1/2 D 1
Engineering-Mathematics       Calculus
Question 5 Explanation: Question 6

The minterm expansion of is

 A m2+m4+m6+m7 B m0+m1+m3+m5 C m0+m1+m6+m7 D m2+m3+m4+m5
Digital-Logic-Design       Boolean-Algebra
Question 6 Explanation:
Convert PQ + QR' + PR' into canonical form
= PQR + PQR' + PQR' + P'QR' + PQR' + PQ'R'
= PQR + PQR' + P'QR' + PQ'R'
= m7 + m6 + m2 + m4
 Question 7

A main memory unit with a capacity of 4 megabytes is built using 1M 1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

 A 100 nanoseconds B 100*210 nanoseconds C 100*220 nanoseconds D 3200*220 nanoseconds
Digital-Logic-Design       Memory-Interfacing
Question 7 Explanation:
Each chip capacity = 1M x 1-bit
Required capacity = 4MB
Number of chips needed = 4M*8 bits / 1M x 1-bit = 32 (1M x 1-bit)/(1M x 1-bit) = 32
Irrespective of the number of chips, all chips can be refreshed in parallel.
And all the cells in a row are refreshed in parallel too. So, the total time for refresh will be number of rows times the refresh time of one row.
Here we have 1K rows in a chip and refresh time of single row is 100ns.
So total time required = 1K × 100
= 100 × 210 nanoseconds
 Question 8

P is a 16-bit signed integer. The 2's complement representation of P is (F87B)16. The 2's complement representation of 8*P is

 A (C3D8)16 B (187B)16 C (F878)16 D (987B)16
Digital-Logic-Design       Number-Systems
Question 8 Explanation:
(F87B)16 is 2's complement representation of P.
(F87B)16=(1111 1000 0111 1011)2. (It is a negative number which is in 2's complement form)
P = 1111 1000 0111 1011 (2's complement form)
8 * P = 23* P = 1100 0011 1101 1000. ( NOTE: Left shift k times is equivalent to Multiplication by 2k)
Hence, 1100 0011 1101 1000 is 2's complement representation of 8P.
1100 0011 1101 1000 = (C3D8)16.
 Question 9

The Boolean expression for the output 'f' of the multiplexer shown below is A B P⊕Q⊕R C P+Q+R D Digital-Logic-Design       Multiplexer
Question 9 Explanation:
f = P’Q’ R + P’Q R’ + PQ’ R’ + PQR
= (P’Q’ + PQ)R + (P’Q+PQ’)R’
= (P⊕Q)’R + (P⊕Q)R’
= (P⊕Q⊕R)
 Question 10

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

 A 0 B 1 C (n-1)/2 D n-1
Data-Structures       Binary-Trees
Question 10 Explanation:
Given a Binary Tree with n nodes.
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant. ― This is even number of descendants (2), because A is also considered as a descendant. ― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.
 Question 11

What does the following program print?

```#include
void f(int *p, int *q)
{
p = q;
*p = 2;
}
int i = 0, j = 1;
int main()
{
f(&i, &j);
printf("%d %d n", i, j);
getchar();
return 0;
}```
 A 2 2 B 2 1 C 0 1 D 0 2
Programming       C-Programming
Question 11 Explanation: Both pointers points to j = 1
now *p = 2
where j is updated with value 2.
printf (i, j) i = 0, j = 2
 Question 12

Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records.What is the smallest value of k for which package B will be preferred over A?

 A 12 B 10 C 6 D 5
Algorithms        Time-Complexity
Question 12 Explanation:
As per given information Package B 10nlog10n is lesser than or equals to Package A 0.0001n2 0 because n2 is asymptotically larger than nlogn. Finally, 10nlog10n ≤ 0.0001n2
Let n = 10k records. Substitute into 10nlog10n ≤ 0.0001n2
10(10k)log1010k ≤ 0.0001(10k)2
10k+1k ≤ 0.0001 × 102k
k ≤ 102k−k−1−4
k ≤ 10k−5
According to the problem value 6 is suitable for K.
 Question 13

Which data structure in a compiler is used for managing information about variables and their attributes?

 A Abstract syntax tree B Symbol table C Semantic stack D Parse Table
Compiler-Design       Compilers
Question 13 Explanation:
Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the analysis phases of a compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its character string (or lexeme) , its type, its position in storage, and any other relevant information.
 Question 14

Which languages necessarily need heap allocation in the runtime environment?

 A Those that support recursion B Those that use dynamic scoping C Those that allow dynamic data structures D Those that use global variables
Compiler-Design       Run-Time-Environments
Question 14 Explanation:
Dynamic memory is allocated on the heap by the system. So the languages which allow dynamic data structure require heap allocation at runtime.
 Question 15

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

 A It can be used to prioritize packets B It can be used to reduce delays C It can be used to optimize throughput D It can be used to prevent packet looping
Computer-Networks       IP-Packet
Question 15 Explanation:
Time to Live (TTL) is a limit on the period of time or transmissions in computer and computer network technology that a unit of data (e.g. a packet) can experience before it should be discarded. If the limit is not defined then the packets can go into an indefinite loop. The packet is discarded when the Time to Live field reaches 0 to prevent looping.
 Question 16

Which one of the following is not a client server application?

 A Internet chat B Web browsing C E-mail D ping
Computer-Networks       Client-Server-Application
Question 16 Explanation:
Ping is used for knowing status of a host by another host. it is not a client server application.
There are 16 questions to complete.

Register Now