GATE CS 2008

Q1.

GATE PAPER

-1

INF

-INF

Ans .

Explanation :

Q2.

If P, Q, R are subsets of the universal set U, then GATE PAPER

Q^c U R^c

P U Q^c U R^c

P^c U Q^c U R^c

Ans .

Explanation :

Q3.

The following system of equations GATE PAPER has a unique solution. The only possible value(s) for α is/are

either 0 or 1

One of 0,1 or -1

any real number

any real number other than 5

Ans .

Explanation :

The choice E was not there in GATE paper. We have added it as the given 4 choices don't seem correct. Augment the given matrix as

1 1 2 | 1

1 2 3 | 2

1 4 a | 4

Apply R2 <- R2 - R1 and R3 <- R3 - R1

1 1 2 | 1

0 1 1 | 1

0 3 a-2 | 3

Apply R3 <- R3 - 3R2

1 1 2 | 1

0 1 1 | 1

0 0 a-5 | 0

So for the system of equations to have a unique solution,

a - 5 != 0

or

a != 5

or

a = R - {5}

Q4.

In the IEEE floating point representation, the hexadecimal value 0 ∗ 00000000 corresponds to

the normalized value 2^-127

the normalized value 2^-126

the normalized value +0

the special value +0

Ans .

Explanation :

Q5.

In the Karnaugh map shown below, X denotes a don't care term. What is the minimal form of the function represented by the Karnaugh map?

GATE PAPER

A. GATE PAPER

B. GATE PAPER

C. GATE PAPER

D. GATE PAPER

Ans .

Explanation :

Q6.

Let r denote number system radix. The only value(s) of r that satisfy the equation GATE PAPER

decimal 10

decimal 11

decimal 10 and 11

any value > 2

Ans .

Explanation :
As we can see 121 contains digit ' 2 ' which can ' t be represented directly in base ' 2 ' ( as digits should be less than base ) so number system must have " r>2 " . Ans (D) part.

Q7.

Which of the following is true for the language GATE PAPER

It is not accepted by a Turing Machine

It is regular but not context-free

It is context-free but not regular

It is neither regular nor context-free, but accepted by a Turing machine

Ans .

Explanation :

Turing machine can be designed for a^p using the concept of ' Sieve of Eratosthenes ' .

Suppose we are given an integer ' n ' and we want to find out all the prime numbers less than or equal to ' n '. We repeat the following steps. We find the smallest number in the list declare it prime and eliminate all the multiples of that number from the list. We keep doing this until each element has been declared prime or eliminated from the list.

Now, if p = 0 or p = 1 we reject the input. Else we replace the first and the last ' a ' with symbol $.

In the above steps, what we do is we find the first non-black symbol from the left. Let this symbol occur at position 'x '. Suppose ' x ' is a prime number. If this non-blank symbol is $ input string will be accepted. But if the symbol is ' a ' we mark it as a^* and replace all the multiples of ' x ' with the symbol ' blank '. If at the end, symbol $ is replaced with ' blank ' we reject the input string ( because p will be multiple of some ' x ' in that case ). Else we go back and repeat the steps.

Thus the input is neither regular nor context-free but is accepted by a Turing machine.

Please comment below if you find anything wrong in the above post.

Q8.

Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

I and II

I and IV

II and IV

Ans .

Explanation :
( A ) Intersection of two regular languages is regular and checking if a regular language is infinite is decidable. ( B ) Deciding regularity of a context free language is undecidable. We check if L ( CFG ) contains any string with length between n and 2n - 1 where n is the pumping lemma constant. If so, L ( CFG ) is infinite otherwise it is finite.

( C ) Equality problem is undecidable for all languages except in case of finite automata i.e. for regular languages. ( D ) We have to check if the grammar obeys the rules of CFG. If, it obeys such rules then it is decidable.

Thus option ( B ) is correct.

Q9.

Which of the following describes a handle ( as applicable to LR-parsing ) appropriately ?

It is the position in a sentential form where the next shift or reduce operation will occur

It is non-terminal whose production will be used for reduction in the next step

It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur

It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found

Ans .

Explanation :

Let ' s first understand the terminology used here. LR Parsing - Here ' L ' stands for Left to Right screening of input string and ' R ' stands for Right Most Derivation in Reverse ( because it is about bottom up parsing ).

Sentential Form Suppose For a given Context Free Grammar G, we have a start symbol S then to define Language generated by Grammar G i.e. L ( G ) we start the derivation starting from S using the production rules of the grammar. After one complete derivation we get a string w which consists of only terminal symbols i.e. w belongs to L ( G ).

Then we can say that w is a sentence of the Grammar G. Now while the derivation process if it gets some form q where q may contain some Non terminal then we say that q is a sentential form of the Grammar G. Even the start symbol S is also the sentential form of the Grammar G ( because it also contains Non-terminal S (.

For Ex :

Grammar is :

S-> aAcBe

A->Ab|b

B->d

Input string : abbcde

Derivation : ( Top-Down, Right Most Derivation)

S - > aAcBe

- > aAcde

- > aAbcde

- > abbcde
: abbcde - > aAbcde ( using A - > b ) - > aAcde ( using A - > Ab ) - > aAcBe ( using B - > d ) - > S ( using S - > aAcBe )

Q10.

Some code optimizations are carried out on the intermediate code because

they enhance the portability of the compiler to other target processors

program analysis is more accurate on intermediate code than on machine code

the information from dataflow analysis cannot otherwise be used for optimization

the information from the front end cannot otherwise be used for optimization

Ans .

Explanation :
Option ( B )is also true. But the main purpose of doing some code-optimization on intermediate code generation is to enhance the portability of the compiler to target processors. So Option ( A ) is more suitable here. Intermediate code is machine architecture independent code. So a compiler can optimize it without worrying about the architecture on which the code is going to execute ( it may be the same or the other ).

So that kind of compiler can be used by multiple different architectures. In contrast to that, suppose code optimization is done on target code, which is machine architecture dependent, then the compiler has be specific about the optimizations on that kind of code.

In this case the compiler cant be used by multiple different architectures because the target code produced on different architectures would be different. Hence portability reduces here.

Q11.

If L and L' are recursively enumerable, then L is

regular

context free

context sensitive

recursive

Ans .

Explanation :
If L is recursively enumerable then L ' is recursively enumerable if and only if L is also recursive.

Q12.

What is the maximum size of data that the application layer can pass on to the TCP layer below?

Any size

2¹⁶ bytes size of TCP header

2¹⁶bytes

1500 bytes

Ans .

Explanation :
The default TCP Maximum Segment Size is 536. Where a host wishes to set the maximum segment size to a value other than the default, the maximum segment size is specified as a TCP option, initially in the TCP SYN packet during the TCP handshake. Because the maximum segment size parameter is controlled by a TCP option, a host can change the value in any later segment.

Q13.

A clustering index is defined on the fields which are of type

non key and ordering

non key and non-ordering

key and ordering

key and non-ordering

Ans .

Explanation :

A clustering index as the name suggests is created when the data can be grouped in the form of clusters.

Q14.

Which of the following system calls results in the sending of SYN packets

socket

bind

listen

connect

Ans .

Explanation :
socket ( ) creates a new socket of a certain socket type identified by an integer number and allocates system resources to it. bind ( ) is typically used on the server side, and associates a socket with a socket address structure i.e. a specified local port number and IP address

listen( ) is used on the server side, and causes a bound TCP socket to enter listening state. connect( ) is used on the client side, and assigns a free local port number to a socket. In case of a TCP socket it causes an attempt to establish a new TCP connection. When connect ( ) is called by client following three way handshake happens to establish the connection in TCP.

1 ) The client requests a connection by sending a SYN ( synchronize ) message to the server. 2 ) The server acknowledges this request by sending SYN ACK back to the client. 3 ) The client responds with an ACK and the connection is established. Sources Berkeley sockets TCP Connection Establishment and Termination

Q15.

Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression

a = ( x > y ) ? ( ( x > z ) ? x : z) : ( ( y > z ) ? y : z )

x = 3 ) y = 4 ) z = 2

x = 6 ) y = 5 ) z = 3

x = 6 ) y = 3 ) z = 5

x = 5 ) y = 4 ) z = 5

Ans .

Explanation :
The given expression assigns maximum among three elements ( x y and z ) to a.

Q16.

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

&thetha ; ( n )

&thetha ; ( m )

&thetha ; ( m + n )

&thetha ; ( mn )

Ans .

Explanation :
Number of connected components in undirected graph can simply calculated by doing a BFS or DFS. The best possible time complexity of BFS and DFS is O ( m + n ).

Q17.

The data blocks of a very large file in the Unix file system are allocated using

contiguous allocation

linked allocation

indexed allocation

an extension of indexed allocatio

Ans .

Explanation :
The Unix file system uses an extension of indexed allocation. It uses direct blocks, single indirect blocks, double indirect blocks and triple indirect blocks. Following diagram shows implementation of Unix file system. The diagram is taken from Operating System Concept book.

Q18.

Which of the following statements is true for every planar graph on n vertices

The graph is connected

The graph is Eulerian

The graph has a vertex-cover of size at most 3n/4

The graph has an independent set of size at least n/3

Ans .

Explanation :
A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A is FALSE A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B is FALSE An Eulerian Graph may or may not be planar. An undirected graph is eulerian if all vertices have even degree. For example, the following graph is Eulerian, but not planar Complete graph K5.svg C is TRUE: D is FALSE:

Q19.

GATE PAPER

-1

INF

-INF

Ans .

Explanation :

Q20.

A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve GATE PAPER

Ans .

Explanation :

Q21.

GATE PAPER

PQ '

PR '

PQ ' + R

PQ ' ' + Q

Ans .

Explanation :

Q22.

Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday what is the probability that she studies computer science on Wednesday

0.24

0.36

0.4

0.6

Ans .

Explanation :

Q23.

How many of the following matrices have an eigenvalue 1 GATE PAPER

One

Two

Three

Four

Ans .

Explanation :

Q24.

GATE PAPER

sqrt ( 2 )

Ans .

Explanation :

Q25.

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to

non-uniform distribution of requests

arm starting and stopping inertia

higher capacity of tracks on the periphery of the platter

use of unfair arm scheduling policies

Ans .

Explanation :
Whenever head moves from one track to other then its speed and direction changes which is noting but change in motion or the case of inertia. So answer B

Q26.

GATE PAPER

I only

II only

III only

II and III only

Ans .

Explanation :
In auto-increment addressing mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store. Self relocating code takes always some address in memory and statement says that this mode is used for self relocating code so option 1 is incorrect and no additional ALU is required

Q27.

GATE PAPER

Only I and II

Only I, II and III

Only I, II and IV

All of I, II, III and IV

Ans .

Explanation :
I and II are same by Demorgan's law The IIIrd can be simplified to I.

Q28.

GATE PAPER

I onl

II only

I and II only

I, II and III only

Ans .

Explanation :
RFE Return From Exception is a privileged trap instruction that is executed when exception occurs so an exception is not allowed to execute. In computer architecture for a general purpose processor, an exception can be defined as an abrupt transfer of control to the operating system. Exceptions are broadly classified into 3 main categories: a. Interrupt: it is mainly caused due to I/O device. b. Trap: It is caused by the program making a syscall. c. Fault: It is accidentally caused by the program that is under execution such as( a divide by zero, or null pointer exception etc). The processor’s fetch instruction unit makes a poll for the interrupts. If it finds something unusual happening in the machine operation it inserts an interrupt pseudo- instruction in the pipeline in place of the normal instruction. Then going through the pipeline it starts handling the interrupts. The operating system explicitly makes a transition from kernel mode to user mode, generally at the end of an interrupt handle pr kernel call by using a privileged instruction RFE Return From Exception instruction.

Q29.

GATE PAPER

IV only

I and IV only

I, III and IV only

I, II, III and IV

Ans .

Explanation :
Answer is B i.e. i and iv are true. Because inclusion says the L2 cache should be Superset of L1 cache. If Write Through update" is not used and Write Back update is used at L1 cache then the modified data in L1 cache will not be present in L2 cache for some time unless the block in L1 cache is replaced by some other block. Hence Write Through Update should be used. Associativity dose not matter. L2 cache must be at least as large as L1 cache since all the words in L1 are also is L2.

Q30.

GATE PAPER

I and II only

I and III only

II and III only

I, II and III

Ans .

Explanation :
I - False Bypassing cannot handle all RAW hazard consider when any instruction depends on the result of LOAD instruction, now LOAD updates register value at Memory Access Stage MA so data will not be available directly on Execute stage. II True register renaming can eliminate all WAR Hazard. III False It cannot completely eliminate though it can reduce Control Hazard Penalties

Q31.

GATE PAPER

I only

II only

III only

I, II and III

Ans .

Explanation :
I is true as by using multiple register windows we eliminate the need to access the variable values again and again from the memory. Rather we store them in the registers. II is false as register saves and restores would still be required for each and every variable. III is also false as instruction fetch is not affected by memory access using multiple register windows. So only I is true. Hence A is the correct option. Please comment below if you find anything wrong in the above post.

Q32.

In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is

before effective address calculation has started

during effective address calculation

after effective address calculation has completed

after data cache lookup has completed

Ans .

Explanation :
When we calculate effective address first of all we access TLB to access the Frame number. Logical address generated by CPU breaks in two parts page number and page offset for faster accessing of data we place some page table entries in a small hardware TLB whose access time is same as cache memory. So initially when page no. is mapped to find the corresponding frame no. first it is look up in TLB and then in page table in case if TLB miss. During effective address calculation TLB is accessed. So B is correct option.

Q33.

GATE PAPER

Ans .

Explanation :

Q34.

GATE PAPER

Ans .

Explanation :

Q35.

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place

Ans .

Explanation :

Q36.

G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G

For every subset of k vertices, the induced subgraph has at most 2k-2 edges

The minimum cut in G has at least two edges

There are two edge-disjoint paths between every pair to vertices

There are two vertex-disjoint paths between every pair of vertices

Ans .

Explanation :

Q37.

Dijkstras single source shortest path algorithm when run from vertex a in the below graph computes the correct shortest path distance to GATE PAPER

only vertex a

only vertices a, e, f, g, h

only vertices a, b, c, d

all the vertices

Ans .

Explanation :

Q38.

You are given the postorder traversal P of a binary search tree on the n elements 1 2 ... n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this

O(Logn)

O(n)

O(nLogn)

none of the above as the tree cannot be uniquely determined.

Ans .

Explanation :
One important thing to note is it is Binary Search Tree not Binary Tree. In BST inorder traversal can always be obtained by sorting all keys.

Q39.

Which of the following statements is false?

Every NFA can be converted to an equivalent DFA

Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

Every regular language is also a context-free language

Every subset of a recursively enumerable set is recursive

Ans .

Explanation :
A language is recursively enumerable if there exists a Turing machine that accepts every string of the language and does not accept strings that are not in the language. Strings that are not in the language may be rejected or may cause the Turing machine to go into an infinite loop. A recursive language can't go into an infinite loop it has to clearly reject the string, but a recursively enumerable language can go into an infinite loop. So every recursive language is also recursively enumerable. Thus the statement Every subset of a recursively enumerable set is recursive is false. Thus option D is the answer.

Q40.

GATE PAPER

I, II, III and IV

I, III and IV only

I, II and IV only

Ans .

Explanation :
I is true as we can always remove left recursion from any given grammar. For better understanding, see this. II is false as we can remove all epsilon productions only if grammar doesnt contain epsilon in the language. III is true as it is the definition of regular grammar. For better understanding see type 3 languages in this article. IV is true because in chomsky normal form all the productions are of type X gives YZ or X gives t where X Y Z are variables and t is terminal string. When we draw the derivation tree for every node there are at most 2 children. Thats why Derivation trees of grammars in chomsky normal form are Binary trees.For better understanding, see this. Thus C is the correct choice.

Q41.

If L and L' are recursively enumerable, then L is

regular

context free

context sensitive

recursive

Ans .

Explanation :
If L is recursively enumerable then L ' is recursively enumerable if and only if L is also recursive.

Q42.

Which of the following is true for the language GATE PAPER

It is not accepted by a Turing Machine

It is regular but not context-free

It is context-free but not regular

It is neither regular nor context-free, but accepted by a Turing machine

Ans .

Explanation :

Turing machine can be designed for a^p using the concept of ' Sieve of Eratosthenes ' .

Suppose we are given an integer ' n ' and we want to find out all the prime numbers less than or equal to ' n '. We repeat the following steps. We find the smallest number in the list declare it prime and eliminate all the multiples of that number from the list. We keep doing this until each element has been declared prime or eliminated from the list.

Now, if p = 0 or p = 1 we reject the input. Else we replace the first and the last ' a ' with symbol $.

In the above steps, what we do is we find the first non-black symbol from the left. Let this symbol occur at position 'x '. Suppose ' x ' is a prime number. If this non-blank symbol is $ input string will be accepted. But if the symbol is ' a ' we mark it as a^* and replace all the multiples of ' x ' with the symbol ' blank '. If at the end, symbol $ is replaced with ' blank ' we reject the input string ( because p will be multiple of some ' x ' in that case ). Else we go back and repeat the steps.

Thus the input is neither regular nor context-free but is accepted by a Turing machine.

Please comment below if you find anything wrong in the above post.

Q43.

If P, Q, R are subsets of the universal set U, then GATE PAPER

Q^c U R^c

P U Q^c U R^c

P^c U Q^c U R^c

Ans .

Explanation :

Q44.

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

&thetha ; ( n )

&thetha ; ( m )

&thetha ; ( m + n )

&thetha ; ( mn )

Ans .

Explanation :
Number of connected components in undirected graph can simply calculated by doing a BFS or DFS. The best possible time complexity of BFS and DFS is O ( m + n ).

Q44.

The following system of equations GATE PAPER has a unique solution. The only possible value(s) for α is/are

either 0 or 1

One of 0,1 or -1

any real number

any real number other than 5

Ans .

Explanation :

The choice E was not there in GATE paper. We have added it as the given 4 choices don't seem correct. Augment the given matrix as

1 1 2 | 1

1 2 3 | 2

1 4 a | 4

Apply R2 <- R2 - R1 and R3 <- R3 - R1

1 1 2 | 1

0 1 1 | 1

0 3 a-2 | 3

Apply R3 <- R3 - 3R2

1 1 2 | 1

0 1 1 | 1

0 0 a-5 | 0

So for the system of equations to have a unique solution,

a - 5 != 0

or

a != 5

or

a = R - {5}

Q45.

GATE PAPER

-1

INF

-INF

Ans .

Explanation :

upscfever.com

Journey of a Thousand Miles begins with One Click!!!

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments