Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test)


65 Questions MCQ Test GATE Past Year Papers for Practice (All Branches) | Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test)


Description
This mock test of Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test) for GATE helps you for every GATE entrance exam. This contains 65 Multiple Choice Questions for GATE Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test) (mcq) to study with solutions a complete question bank. The solved questions answers in this Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test) quiz give you a good mix of easy questions and tough questions. GATE students definitely take this Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test) exercise for a better result in the exam. You can find other Computer Science And Information Technology - CS 2012 GATE Paper (Practice Test) extra questions, long questions & short questions for GATE on EduRev as well by searching above.
QUESTION: 1

Choose the most appropriate alternative from the options given below to complete the following
sentence:
Despite several ––––––––– the mission succeeded in its attempt to resolve the conflict.

Solution:
QUESTION: 2

Choose the most appropriate alternative from the options given below to complete the following
sentence:
Suresh’s dog is the one ––––––––– was hurt in the stampede.

Solution:
QUESTION: 3

A political party orders an arch for the entrance to the ground in which the annual convention is being held. The profile of the arch follows the equation y = 2x – 0.1x2 where y is the height of the arch in meters. The maximum possible height of the arch is

Solution:

y =2x - 0.1x2
dy/dx = 2-0.2x
d2y/dx2 <0
y max imises at 2- 0.2x= 0
x =10
y= 20 - 10 =10m

QUESTION: 4

Given the sequence of terms, AD CG FK JP, the next term is _________ .

Solution:
QUESTION: 5

Q. 1 – Q. 5 carry one mark each.

The cost function for a product in a firm is given by 5q2, where q is the amount of production. The
firm can sell the product at a market price of  50 per unit. The number of units to be produced by
the firm such that the profit is maximized is

Solution:

P = 50q - 5q2

dp/dq = 50-10q; d2p/dq2 <0

 p is maximum at 50- 10q = 0 or q=5

Else check with options

QUESTION: 6

Which one of the following options is the closest in meaning to the word given below?
Mitigate

Solution:
QUESTION: 7

Choose the grammatically INCORRECT sentence:

Solution:
QUESTION: 8

Q. 6 - Q. 10 carry two marks each.

W anted Temporary, Part-time persons for the post of Field Interviewer to conduct personal
interviews to collect and collate economic data. Requirements: High School-pass, must be
available for Day, Evening and Saturday work. Transportation paid, expenses reimbursed.

Which one of the following is the best inference from the above advertisement?

Solution:

Gender is not mentioned in the advertisement and (B) clearly eliminated

QUESTION: 9

An automobile plant contracted to buy shock absorbers from two suppliers X and Y. X supplies 60% and Y supplies 40% of the shock absorbers. All shock absorbers are subjected to a quality test. The ones that pass the quality test are considered reliable. Of X’s shock absorbers, 96% are reliable. Of Y’s shock absorbers, 72% are reliable.

The probability that a randomly chosen shock absorber, which is found to be reliable, is made by Y is 

Solution:

 

QUESTION: 10

Which of the following assertions are CORRECT?
P: Adding 7 to each entry in a list adds 7 to the mean of the list
Q: Adding 7 to each entry in a list adds 7 to the standard deviation of the list
R: Doubling each entry in a list doubles the mean of the list
S: Doubling each entry in a list leaves the standard deviation of the list unchanged

Solution:

P and R always hold true
Else consider a sample set {1, 2, 3, 4} and check accordingly

QUESTION: 11

Q. 11 – Q. 35 carry one mark each.

Q.

Consider the following logical inferences.
I1: If it rains then the cricket match will not be played.
    The cricket match was played.
     Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
     It did not rain.
     Inference: The cricket match was played.


Which of the following is TRUE?

Solution:
QUESTION: 12

Which of the following is TRUE?

Solution:
QUESTION: 13

What will be the output of the following C program segment?

char inChar = ‘A’ ;
switch ( inChar ) {
case ‘A’ : printf (“Choice A n”) ;
case ‘B’ :
case ‘C’ : printf (“Choice B”) ;
case ‘D’ :
case ‘E’ :
default : printf ( “ No Choice” ) ; }

Solution:
QUESTION: 14

A ssuming P ≠ NP, which of the following is TRUE?

Solution:
QUESTION: 15

T he worst case running time to search for an element in a balanced binary search tree with n2n
elements is

Solution:
QUESTION: 16

The truth table

Solution:
QUESTION: 17

The decimal value 0.5 in IEEE single precision floating point representation has

Solution:
QUESTION: 18

A process executes the code
fork();
fork();
fork();
The total number of child processes created is

Solution:
QUESTION: 19

Consider the function f(x) = sin(x) in the interval x [π/4, 7π/4]. The number and location(s) of the
local minima of this function are

Solution:

Sin x has a maximum value of 1 at ,
π/2 and a minimum value of –1 at


3π/2 and at all angles conterminal with them.
The graph of f (x) = sin x is

 

  In the interval   
, it has one local minimum x= 3π/2

QUESTION: 20

The protocol data unit (PDU) for the application layer in the Internet stack is

Solution:

The PDU for Datalink layer, Network layer , Transport layer and Application layer are frame,
datagram, segment and message respectively.

QUESTION: 21

Let A be the 2 × 2 matrix with elements a11 = a12 = a21 = +1 and a22 = −1. Then the eigenvalues of
the matrix A19 are

Solution:

QUESTION: 22

What is the complement of the language accepted by the NFA shown below?
Assume  = {a} and ε is the empty string.

 

Solution:

Language accepted by NFA is a+, so complement of this language is {ε}

QUESTION: 23

What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”

Solution:

Option A: There exists x which is either real or rational and can be both.
Option B: All real numbers are rational
Option C: There exists a real number which is rational.
Option D: There exists some number which is not rational or which is real.

QUESTION: 24

Given the basic ER and relational models, which of the following is INCORRECT?

Solution:

The term ‘entity’ belongs to ER model and the term ‘relational table’ belongs to relational model.

A and B both are true. ER model supports both multivalued and composite attributes See this for more details.

(C) is false and (D) is true. In Relation model, an entry in relational table can can have exactly one value or a NULL.

QUESTION: 25

Which of the following statements are TRUE about an SQL query?
P : An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause
Q : An SQL query can contain a HAVING clause only if it has a GROUP BY clause
R : All attributes used in the GROUP BY clause must appear in the SELECT clause
S : Not all attributes used in the GROUP BY clause need to appear in the SELECT clause

Solution:

If we use a HAVING clause without a GROUP BY clause, the HAVING condition applies to
all rows that satisfy the search condition. In other words, all rows that satisfy the search
condition make up a single group. So, option P is true and Q is false.
S is also true as an example consider the following table and query.0

Select count (*)
From student
Group by Name
Output will be

QUESTION: 26

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with
n discs is

Solution:

Let the three pegs be A,B and C, the goal is to move n pegs from A to C using peg B
The following sequence of steps are executed recursively
1.move n−1 discs from A to B. This leaves disc n alone on peg A --- T(n-1)
2.move disc n from A to C---------1
3.move n−1 discs from B to C so they sit on disc n----- T(n-1)
So, T(n) = 2T(n-1) +1

QUESTION: 27

Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph,
then the number of bounded faces in any embedding of G on the plane is equal to

Solution:

We have the relation V-E+F=2, by this we will get the total number of faces,

F = 7. Out of 7 faces one is an unbounded face, so total 6 bounded faces.

QUESTION: 28

Let W(n) and A(n) denote respectively, the worst case and average case running time of an
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

Solution:

The average case time can be lesser than or even equal to the worst case. So A(n) would be
upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g.
Bubble Sort and merge sort).
 A(n) = O(W(n))

QUESTION: 29

The amount of ROM needed to implement a 4 bit multiplier is

Solution:

For a 4 bit multiplier there are 24 × 24 = 28 = 256 combinations.
Output will contain 8 bits.
So the amount of ROM needed is  28 ×8 bits = 2Kbits.

QUESTION: 30

Register renaming is done in pipelined processors

Solution:

Register renaming is done to eliminate WAR/WAW hazards.

QUESTION: 31

Consider a random variable X that takes values +1 and −1 with probability 0.5 each. The values of
the cumulative distribution function F(x) at x = −1 and +1 are

Solution:

The cumulative distribution function
 

F(x) = P(Xx)

F(-1) = P(X-1) = X=-1) =0.5

F(+1)= P(X+1) = P(X=-1)+P(X=-1) = 0.5 + 0.5 =1

QUESTION: 32

Which of the following transport layer protocols is used to support electronic mail?

Solution:

E-mail uses SMTP, application layer protocol which intern uses TCP transport layer protocol.

QUESTION: 33

In the IPv4 addressing format, the number of networks allowed under Class C addresses is

Solution:

For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence
total number of networks possible is 221

QUESTION: 34

Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then, is also context-free?
3) If L is a regular language, then, is also regular?
4) If L is a recursive language, then, is also recursive?

 

Solution:

CFL’s are not closed under complementation. Regular and recursive languages are closed
under complementation.

QUESTION: 35

Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

Solution:

L ={ab, aa, baa}
Let S1 = ab , S2 = aa and S3 =baa
abaabaaabaa can be written as S1S2S3S1S2
aaaabaaaa can be written as S1S1S3S1
baaaaabaa can be written as S3S2S1S2

QUESTION: 36

Q. 36 to Q. 65 carry two marks each.

Q.

W hich of the following graphs is isomorphic to

Solution:

The graph in option (A) has a 3 length cycle whereas the original graph does not have a 3 length cycle
The graph in option (C) has vertex with degree 3 whereas the original graph does not have a
vertex with degree 3

The graph in option (D) has a 4 length cycle whereas the original graph does not have a 4 length cycle

QUESTION: 37

Consider the following transactions with data items P and Q initialized to zero:
T1 :read (P);
read (Q);
if P = 0 then Q := Q + 1 ;
write (Q).
T2 : read (Q);
read (P);
if Q = 0 then P := P + 1 ;
write (P).
Any non-serial interleaving of T1 and T2 for concurrent execution leads to

Solution:

Let S be a non-serial schedule, without loss of generality assume that T1 has started earlier than T2. The first instruction of T1 is read(P) and the last instruction of T2 is write(P), so the precedence graph for S has an edge from T1 to T2, now since S is a non-serial schedule the first instruction of T2(read(Q)) should be executed before last instruction of T1(write(Q)) and since read and write are conflicting operations, the precedence graph for S also contains an
edge from T2 to T1, So we will have a cycle in the precedence graph which implies that any non serial schedule with T1 as the earliest transaction will not be conflict serializable.
In a similar way we can show that if T2 is the earliest transaction then also the schedule is not conflict serializable.

QUESTION: 38

The bisection method is applied to compute a zero of the function f(x) = x4 – x3 – x2 – 4 in the
interval [1,9]. The method converges to a solution after ––––– iterations.

Solution:

QUESTION: 39

Let G be a weighted graph with edge weights greater than one and G’be the graph constructed by squaring the weights of edges in G. Let T and T’ be the minimum spanning trees of G and G’, respectively, with total weights t and t’. Which of the following statements is TRUE?

Solution:
QUESTION: 40

What is the minimal form of the Karnaugh map shown below? Assume that X denotes a don’t care
term.

Solution:
QUESTION: 41

Consider the 3 processes, P1, P2 and P3 shown in the table.

The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling
with CPU quantum of 2 time units) are

Solution:

For FCFS Execution order will be order of Arrival time so it is P1,P2,P3
Next For RR with time quantum=2,the arrangement of Ready Queue will be as follows:
RQ: P1,P2,P1,P3,P2,P1,P3,P2
This RQ itself shows the order of execution on CPU(Using Gantt Chart) and here it gives the completion order as P1,P3,P2 in Round Robin algorithm.

QUESTION: 42

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of
memory location X, increments it by the value i, and returns the old value of X. It is used in the
pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable
initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value
corresponds to the lock being not available.

AcquireLock(L){
while (Fetch_And_Add(L,1))
L = 1;
}
ReleaseLock(L){
L = 0;
}
This implementation

Solution:

1. Acquire lock (L) {
2. While (Fetch_And_Add(L, 1))
3. L = 1.
}
4. Release Lock (L) {
5. L = 0;
6. }
Let P and Q be two concurrent processes in the system currently executing as follows
P executes 1,2,3 then Q executes 1 and 2 then P executes 4,5,6 then L=0 now Q executes 3
by which L will be set to 1 and thereafter no process can set
L to zero, by which all the processes could starve.

QUESTION: 43

Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a
second time. What is the probability that the sum total of values that turn up is at least 6?

Solution:
QUESTION: 44

An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available
with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses to Organization A,
and a quarter to Organization B, while retaining the remaining with itself. Which of the following is
a valid allocation of addresses to A and B?

Solution:

Since half of 4096 host addresses must be given to organization A, we can set 12th bit to 1 and include that bit into network part of organization A, so the valid allocation of addresses to A is 245.248.136.0/21
Now for organization B, 12th bit is set to ‘0’ but since we need only half of 2048 addresses,
13th bit can be set to ‘0’ and include that bit into network part of organization B so the valid allocation of addresses to B is 245.248.128.0/22

QUESTION: 45

Suppose a circular queue of capacity (n −1) elements is implemented with an array of n elements.
Assume that the insertion and deletion operations are carried out using REAR and FRONT as array
index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full
and queue empty are

Solution:

The counter example for the condition full : REAR = FRONT is
Initially when the Queue is empty REAR=FRONT=0 by which the above full condition is satisfied which is false
The counter example for the condition full : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=3, so after inserting one element REAR=1 and FRONT=0, at this point the condition full above is satisfied, but still there is place for one more element in Queue, so this condition is also false
The counter example for the condition empty : (REAR+1)mod n = FRONT is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
The counter example for the condition empty : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here

QUESTION: 46

Consider the program given below, in a block-structured pseudo-language with lexical scoping and
nesting of procedures permitted.

Program main;
  Var ...
Procedure A1;
  Var ...
  Call A2;
  End A1
Procedure A2;
  Var ...
Procedure A21;
  Var ...
  Call A1;
  End A21

  Call A21;
  End A2
    Call A1;
End main.
Consider the calling chain: Main → A1 → A2 → A21 → A1
The correct set of activation records along with their access links is given by

Solution:

Access link is defined as link to activation record of closest lexically enclosing block in
program text, so the closest enclosing blocks respectively for A1 ,A2 and A21 are main , main and A2

QUESTION: 47

How many onto (or surjective) functions are there from an n-element (n  2) set to a 2-element set?

Solution:

Total number of functions is 2n, out of which there will be exactly two functions where all
elements map to exactly one element, so total number of onto functions is 2n-2

QUESTION: 48

Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of
distinct cycles of length 4 in G is equal to

Solution:
QUESTION: 49

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort
algorithm. The worst case running time of this computation is

Solution:

The height of the recursion tree using merge sort is logn and n2 comparisons are done at each
level, where at most n pairs of strings are compared at each level and n comparisons are
required to compare any two strings, So the worst case running time is O( n2 log n )

QUESTION: 50

Consider the directed graph shown in the figure below. There are multiple shortest paths between
vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in
any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is
discovered.

Solution:

Let d[v] represent the shortest path distance computed from ‘S’
Initially d[S]=0, d[A] = ∞, d[B] = ∞.− − − −,d[T] = ∞
And let P[v] represent the predecessor of v in the shortest path from ‘S’ to ‘v’ and let P[v]=-1
denote that currently predecessor of ‘v’ has not been computed
→ Let Q be the set of vertices for which shortest path distance has not been computed
→ Let W be the set of vertices for which shortest path distance has not been computed
→ So initially, Q = {S,A,B,C,D,E,F,G,T},W = f
We will use the following procedure
Repeat until Q is empty
{
1 u = choose a vertex from Q with minimum d[u] value
2. Q = Q − u
3. update all the adjacent vertices of u
4. W = W U{u}
}

d[S] = 0, d[A] = ∞, d[B] = ∞ ,………, d[T] = ∞

Step 1 : u = S
Step 2 : Q ={A,B,C,D,E,F,G,T}
Step 3: final values after adjustment
d[S] = 0,d[A] = 4, d[B] = 3,d[C] = ∞,d[D] = 7,d[E] = ∞ − −−,d[T] = ∞
P[A] = S, P[B] = S,P[C] = −1,P[D] = S,P[E] = −1− −−,P[T] = −1
Step 4 : W={S}

Iteration 2:
Step 1: u= B
Step 2 :Q ={A,C,D,E,F,G,T}
step 3: final values after adjustment
d[S] = 0,d[A] = 4, d[B] = 3,d[C] = ∞,d[D] = 7,d[E] = ∞ − −−,d[T] = ∞
P[A] = S, P[B] = S,P[C] = −1,P[D] = S,P[E] = −1− −−,P[T] = −1
Step 4 : W={S,B}

Iteration 3:
Step 1: u= A
Step 2 :Q ={C,D,E,F,G,T}
step 3: final values after adjustment
d[S] = 0,d[A] = 4, d[B] = 3,d[C] = 5,d[D] = 7,d[E] = ∞ − −−,d[T] = ∞
P[A] = S, P[B] = S,P[C] = A,P[D] = S,P[E] = −1− −−,P[T] = −1
Step 4 : W={S,B,A}

Iteration 4:
Step 1: u= A
Step 2 :Q ={D,E,F,G,T}
step 3: final values after adjustment
d[S] = 0,d[A] = 4, d[B] = 3,d[C] = 5,d[D] = 7,d[E] = 6 − −−,d[T] = ∞
P[A] = S, P[B] = S,P[C] = A,P[D] = S,P[E] = −1− −−,P[T] = −1
Step 4 : W={S,B,A,C}

Iteration 5:
Step 1: u= E
Step 2 :Q ={D,F,G,T}
step 3: final values after adjustment
d[S] = 0,d[A] = 4, d[B] = 3,d[C] = 5,d[D] = 7,d[E] = 6,d[F] = ∞,d[G] = 8,d[T] = 10
P[A] = S, P[B] = S,P[C] = A,,P[D] = S,P[E] =C, P[F]= −1, P[G]=E, P[T] = E
Step 4 : W={S,B,A,C,E}

After iteration 5, we can observe that P[T]=E , P[E]=C , P[C]=A , P[A]=S,
So the shortest path from S to T is SACET

QUESTION: 51

A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1 indirect
block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the
size of each disk block address is 8 Bytes. The maximum possible file size in this file system is

Solution:

Each block size = 128 Bytes
Disk block address = 8 Bytes
Each disk can contain =
128
16
8
= addresses
Size due to 8 direct block addresses: 8 x 128
Size due to 1 indirect block address: 16 x 128
Size due to 1 doubly indirect block address: 16 x 16 x 128
Size due to 1 doubly indirect block address: 16 x 16 x 128

QUESTION: 52

Consider the virtual page reference string
1, 2, 3, 2, 4, 1, 3, 2, 4, 1
on a demand paged virtual memory system running on a computer system that has main memory
size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number
of page faults under the corresponding page replacement policy. Then

Solution:

FIFO
1 1 1 4 4 4
2 2 2 1 1
3 3 3 2                           → (6) faults
Optimal
1 1 1 1 1
2 2 4 4
3 3 2                               → (5) faults
LRU
1 1 1 4 4 4 2 2 2
2 2 2 2 3 3 3 1
3 3 1 1 1 4 4                    → (9) faults
Optimal < FIFO < LRU

QUESTION: 53

Suppose R1(A, B) and R2(C, D) are two relation schemas. Let r1 and r2 be the corresponding
relation instances. B is a foreign key that refers to C in R2. If data in r1 and r2 satisfy referential
integrity constraints, which of the following is ALWAYS TRUE?

Solution:

QUESTION: 54

Consider a source computer (S) transmitting a file of size 106 bits to a destination computer (D)
over a network of two routers (R1 and R2) and three links (L1, L2, and L3). L1 connects S to R1; L2
connects R1 to R2; and L3 connects R2 to D. Let each link be of length 100 km. Assume signals
travel over each link at a speed of 108 meters per second. Assume that the link bandwidth on each
link is 1Mbps. Let the file be broken down into 1000 packets each of size 1000 bits. Find the total
sum of transmission and propagation delays in transmitting the file from S to D?

Solution:

Transmission delay for 1 packet from each of S, R1 and R2 will take 1ms
Propagation delay on each link L1, L2 and L3 for one packet is 1ms
Therefore the sum of transmission delay and propagation delay on each link for one packet is
2ms.
The first packet reaches the destination at 6thms
The second packet reaches the destination at 7thms
So inductively we can say that 1000th packet reaches the destination at 1005th ms

QUESTION: 55

Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where
the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first
transmission is 8 MSS. Assume that a timeout occurs during the fifth transmission. Find the
congestion window size at the end of the tenth transmission.

Solution:
QUESTION: 56

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros.
For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less
than 3 are also in the language. A partially completed DFA that accepts this language is shown
below.

 

The missing arcs in the DFA are

Solution:
QUESTION: 57

The height of a tree is defined as the number of edges on the longest path in the tree. The function
shown in the pseudocode below is invoked as height(root) to compute the height of a binary
tree rooted at the tree pointer root.
int height (treeptr n)
{ if (n == NULL) return -1;
if (n → left == NULL)
if (n → right == NULL) return 0;
else return  ;  // Box 1
else { h1 = height (n → left);
if (n → right == NULL) return (1+h1);
else { h2 = height (n → right);
return  ; // Box 2
}
}
}
The appropriate expressions for the two boxes B1 and B2 are

Solution:

int height (treeptr n)
{ if (n = = nu11) return – 1;
→/* If there is no node, return -1 */
if (n→left ==NULL) ® / * If there is no left child for node 'n ' * /
if (n→right == NULL) return O;
→ / *If no left child & no right child for 'n ', return */
else return (1+height (n→right ) );
→/* If no left child, but there is a right child, then compute height
for right sub tree. Therefore total height is 1+ height (n→right ) */
else { → / * If there exist left child node for node ‘n’ */
h1 = height (n→left );
→ / * First Find the height of left sub tree for node ‘n’ */
If (n → right == NULL) return (1+ h1);
|CS-GATE-2012 PAPER|
 India’s No.1 institute for GATE Training  1 Lakh+ Students trained till date  65+ Centers across India
11
→/ * If there exist left child and no right child and no right child
for a node ‘n’, then total height
= height from (n to n→left ) + left sub tree height
=1 + height (n →left ) = 1 + h1 */
else {h2 = height (n →right ) ;
→/* If there exist right child also, then compute height of right
sub tree for a node ‘n’ */
return ( ( )) 1 2 1+ max h , h ;
→ / * Total height for node ‘n’=
1 + Max (Left Subtree height, Right sub tree height)
= 1 + Max (h1, h2) */
}
}

QUESTION: 58

Consider the following C code segment.
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1; /* Line 1 */
prtFun( );
a += 1;
prtFun( );
printf(“ %d %d ”, a, b);
}
void prtFun(void)
{ static int a = 2; /* Line 2 */
int b = 1;
a += ++b;
printf(“ %d %d ”, a, b);
}

What output will be generated by the given code segment?

Solution:
QUESTION: 59

Consider the following C code segment.
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1; /* Line 1 */
prtFun( );
a += 1;
prtFun( );
printf(“ %d %d ”, a, b);
}
void prtFun(void)
{ static int a = 2; /* Line 2 */
int b = 1;
a += ++b;
printf(“ %d %d ”, a, b);
}

What output will be generated by the given code segment if:
Line 1 is replaced by auto int a = 1;
Line 2 is replaced by register int a = 2;

Solution:
QUESTION: 60

Consider the following relations A, B and C:

How many tuples does the result of the following relational algebra expression contain? Assume
that the schema of A∪B is the same as that of A.

Solution:
QUESTION: 61

Consider the following relations A, B and C:

 

How many tuples does the result of the following SQL query contain?

Solution:
QUESTION: 62

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that
need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, |
separates alternate right hand sides of productions.

The FIRST and FOLLOW sets for the non-terminals A and B are

Solution:

QUESTION: 63

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that
need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, |
separates alternate right hand sides of productions.

The appropriate entries for E1, E2, and E3 are

Solution:
QUESTION: 64

A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The
processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in
addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit.

The number of bits in the tag field of an address is

Solution:
QUESTION: 65

A computer has a 256 KByte, 4-way set associative, write back data cache with block size of 32 Bytes. The
processor sends 32 bit addresses to the cache controller. Each cache tag directory entry contains, in
addition to address tag, 2 valid bits, 1 modified bit and 1 replacement bit.

The size of the cache tag directory is

Solution: