2008

Question. 1

www.gatehelp.com

CS

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity. (A) (n) (C) (m + n)
Question. 2

(B) (m) (D) (mn)

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

(A) MNOPQR (C) QMNPRO

Question. 3

(B) NQMPOR (D) QMNPOR

Consider the following function; f (n) = 2n g (n) = n! h (n) = n log n Which of the following statements about the asymptotic behavior of f (n). g (n) and h (n) is true? (A) f (n) = O (g (n)); g (n) = O (h (n)) (B) f (n) = (g (n)); g (n) = O (h (n)) (C) g (n) = O (f (n)); h (n) = O (f (n)) (D)h (n) = O (f (n)); g (n) = (f (n))

CS

1/31

2008
Question. 4

www.gatehelp.com

CS

The minimum number of comparison required to determine if an integer appears more than n/2 times in a sorted array of n integers is (A) (n) (C) (log * n)
Question. 5

(B) (log n) (D) (1)

AB -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? (A) 3 (C) 5
Question. 6

(B) 4 (D) 6

G is a graph on n vertices and 2n 2 edges. The edges of G can be partitioned into two edge-disjiont spanning trees. Which of the following is NOT true for G ? (A) For every subset of k vertices, the induced sub graph has a most 2k 2 edges. (B) The minimum cut in G has a least two edges (C) There are two edges-disjoint paths between every pair of vertices (D) There are two vertex-disjoint paths between every pair of vertices.
Question. 7

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into sub-lists each of which contains at least one-fifth of the elements. Let T (n) be the number of comparisons required to sort n elements. Then (A) T (n) # 2T (n/5) + n (B) T (n) # T (n/5) + T (4n/5) + n (C) T (n) # 2T (4n/5) + n (D) T (n) # 2T (n/2) + n

CS

2/31

2008
Question. 8

www.gatehelp.com

CS

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W ; determine whether there is aa subset of S whose elements sum to W . An algorithm Q Solves this problem in O (nW) time. Which of the following statements is false? (A) Q sloves the subset-sum problem unpolynomial time when the input unary is encoded in

(B) Q solves the subset-sum problem is polynominal time when the input is encoded in binary (C) The subset sum problem belongs to the class NP (D) The subset sum problem in NP-hard
Question. 9

Dijkstras single source shortest path algorithm when run from vertex a in the above graph, computes the corrects shortest path distance to

(A) only vertex a (C) only vertices,a, b, c, d

Question. 10

(B) only vertices a, e, f, g, h (D) all the vertices

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?

CS

3/31

2008 (A) (log n) (B) (n) (C) (n log n)

www.gatehelp.com

CS

(D) none of the above, as the tree cannot be uniquely determined.

Question. 11

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is (A) (log n) (C) (n log n) (B) (n) (D) (n2)

Common data for Questions 12 & 13:

Consider the following C functions: int f1 (int n) { If(n==0||n==1) return n; else return(2)f1(n-1)+3)f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[1]=1;Y[1]=2;Z[1]=3; for (i=2;i<=n;i++){ X[i]=Y[i-1]+Z[i-2]; Y[i]=2)X[i]; z[i]=3)X[i]; } return X[n]; }
Question. 12

The running time of f1 (n) and f2 (n) are CS 4/31

2008 (A) (n) and (n) (C) (n) and (2")

Question. 13

www.gatehelp.com (B) (2") and O (n) (D) (2") and (2")

CS

f1 (8) f2 (8) return the values (A) 1661 and 1640 (C) 1640 and 1640 (B) 59 and 59 (D) 1640 and 1661

Statement for Linked Answers Questions 14 & 15:

The subset-sum problem is defined as follows. Given set of n positive integers, S = {a1, a2, a3,....... an} and a positive integer W is there a subset S whose elements sum of W ? A dynamic program for solving this problem uses a 2-dimensiond Boolean array, X with n rows and W-1 columns X [i, j], 1 # i # W, is TRUE if and only if there is a subset of {a1, a2,...... ai} whose elements sum to j .
Question. 14

Which of the following is valid for 2 # i # n and a1 # j # W? (A) X [i, j] = X [i 1, j] 0 X [i, j ai] (B) X [i, j] = X [i 1, j] 0 X [i 1, j ai] (C) X [i, j] = X [i 1, j] / X [i, j ai] (D) X [i, j] = X [i 1, j] / X [i 1, j ai]
Question. 15

Which entry of the array X , if TRUE, implies that there is a subset whose elements sum to W? (A) X [1, W] (C) X [n, W] (B) X [n, 0] (D) X [n 1, n]

Statement for Linked Answers Questions 16 & 17:

CS 5/31

2008

www.gatehelp.com

CS

Consider the following C program that attempts to locate an element x in an array Y [ ] using binary search. The program is erroneous. 1. f (intY [10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5. k = (i + j) /2; 6. if (Y [K] < x) i = k; else j = k; 7. } while ((Y [k]! = x) && (i < j)), 8. if (Y [k] == x) print f ("x is in the array); 9. else printf ("x is not in the array); 10. }
Question. 16

On which of the following contents of Y and x does the program fail? (A) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10 (B) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1 (C) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2 (D) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
Question. 17

The correction needed in the program to make it work properly is (A) change line 6 to : if (Y [k]) < x) i = k + 1; else j = k - 1; (B) change line 6 to: if (Y [k] < x) i = k 1; else j = k + 1; (C) change line 6 to: if (Y [k] < x) i = k; else j = k; (D) change line 7 to : } while ((Y [k] == x)&&( i < j));
Question. 18

Which of the following describes a handle (as applicable to LR-parsing) appropriately? (A) It is the position in a sentential form where the next shift or reduce operation will occur (B) It is a non-terminal whose production will be used for reduction in the next step (C) It is a production that may be used for reduction in a future step along with a posiCS 6/31

2008

www.gatehelp.com tion in the sentential form where the next shift or reduce operation will occur.

CS

(D) 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
Question. 19

Some code optimizations are carried out on the intermediate code because (A) They enhance the portability of the complier to other target processors (B) Program analysis is name accurate on intermediate code than on machine code (C) The information from data flow analysis cannot otherwise be used for optimization (D) The information from the front end cannot otherwise be used for optimization
Question. 20

Which of the following are true? (i) A programming language option does not permit global variables of any king and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation (ii) Multi-level access link (or display) arrangement is needed to arrange activation records-only if the programming language being implemented has nesting of procedures/function (iii) Recursion in programming languages cannot be implemented with dynamic storage allocation (iv) Nesting of procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records (v) Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records (A) (ii) and (v) only (C) (i), (ii) and (v) (B) (i), (iii) and (iv) only (D) (ii), (iii) and (v) only

CS

7/31

2008
Question. 21

www.gatehelp.com

CS

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if (A) The SLR(1) parser for G has S-R conflicts (B) The LR(1) parser for G has S-R conflicts (C) The LR(0) parser for G has S-R conflicts (D) The LALR(1) parser for G has reduce-reduce conflicts
Question. 22

What is the maximum size of data that the application layer can pass on to the TCP layer below? (A) Any size (C) 216 bytes
Question. 23

(B) 216 bytes-size of TCP header (D) 1500 bytes

In the slow start phase of TCP congesting control algorithm, the size of the congestion window (A) Does not increase (B) Increases linearly (C) Increases quadratically (D) Increases exponentially
Question. 24

If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet? (A) 1022 (C) 2046 (B) 1023 (D) 2047

CS

8/31

2008
Question. 25

www.gatehelp.com

CS

A computer on a 10Mbps network is regulated by atoken bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits. What is the maximum duration for which the computer can transmit at the full 10Mbps? (A) 1.6 seconds (C) 5 seconds
Question. 26

(B) 2 seconds (D) 8 seconds

A client process P needs to make a TCP connection to a server Process S . Consider the following situation; the server process S executes a socket (), a bind() and a listen () system call in that order, following which it is preempted. Subsequently, the client Process P executes a socket () system call followed by connect () system call to connect to the server process S . The server process has not executed any accept() system call. Which one of the following events could take place? (A) connect ( ) system call returns successfully (B) connect ( ) system call blocks (C) connect ( ) system call returns an error (D) connect ( ) system call results in a core dump
Question. 27

For a magnetic disk with concentric circular track, the latency is not linearly proportional to the seek distance due to (A) non-uniform distribution of requests (B) arm starting and stopping inertia (C) higher capacity of tracks on the periphery of the platter (D) use of unfair arm scheduling policies.
Question. 28

Which of the following is/are true of the auto increment addressing mode? 1. 2. CS It is useful in creating self relocating code If it is included in an Instruction Set Architecture, then an additional ALU is required for 9/31

2008

www.gatehelp.com

CS

effective address calculation 3. The amount of increment depends on the size of the data item accessed. (A) 1 only (B) 2 only (C) 3 only
Question. 29

(D) 2 and 3 only

Which of the following must be true for the RFE (Return from Expectation) instruction on a general purpose processor. 1. 2. 3. (A) It must be a trap instruction It must be a privileged instruction An exception can not be allowed to occur during execution of an RFE instruction. 1 only (B) 2 only (D) 1, 2 and 3 only

(C) 1 and 2 only

Question. 30

For inclusion to hold between two cache level L1 and L2 in a multilevel cache hierarchy, which of the following are necessary? 1. 2. 3. 4. (A) L1 must be a write-through cache L2 must be write-through cache The associativity of L2 must be greater that of L1 The L2 cache must be at least as large as the L1 cache 4 only (B) 1 and 2 only (D) 1, 2, 3 and 4

(C) 1, 2 and 4 only

Question. 31

Which of the following are NOT true in a pipe lined processor? 1. 2. 3. (A) Bypassing can handle alll Raw hazards. Register renaming can eliminate all register carried WAR hazards. Control hazard penalties can be eliminated by dynamic branch prediction. 1 and 2 only (B) 1 and 3 only (D) 1,2 and 3

(C) 2 and 3 only

CS

10/31

2008
Question. 32

www.gatehelp.com

CS

The use of multiple register windows with overlap causes a reduction in the number of memory accesses for 1. Function locals and parameters 2. Register saves and restores 3. Instruction fetches (A) 1 only (C) 3 only
Question. 33

(B) 2 only (D) 1,2 and 3

In an instruction execution pipeline, the earliest that the data TLB (Translation Look aside Buffer) can be accessed is (A) before effective address calculation has started (B) during effective address calculation (C) after effective address calculation has completed (D) after data cache lookup has completed

Data for Q. 34, 35 & 36 are given below.

Consider a machine a 2-way set associative data cache of size 64 kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addressed and the page size is 4 kbytes. A program to be run on this machine begins as follows: Double APR[1024]]1024] int i , j ; /*Initalize array APR to 0.0*/ for (i = 0; i < 1024; i ++) for (j = 0; k < 1024; j ++) APR[i] [j] = 0.0; The size of double 8 bytes. Array APR is in memory stating at the beginning of virtual CS 11/31

2008

www.gatehelp.com

CS

page 0 # FF000 and stored in row major order. The cache is initially empty and no prefetching is done. The only data memory references made by the program are those to array APR.
Question. 34

The total size of the tags in the cache directory is (A) 32 kbits (C) 64 kbits
Question. 35

(B) 34 kbits (D) 68 kbits

Which of the following array elements has the same cache index as APR [0][0]? (A) APR[0][4] (C) APR[0][5]
Question. 36

(B) APR[4][0] (D) APR[5][0]

The cache hit ratio for this initialization loop is (A) 0% (C) 50% (B) 25% (D) 75%

Data for Q. 37 & 38 are given below.

Delayed branching can help in the handling of control hazardous
Question. 37

For all delayed conditional branch instruction, irrespective of weather the condition evato true or false, A (A) the instruction following the conditional branch instruction in memory is executed (B) the first instruction in the fall through path is executed (C) the first instruction in the taken path is executed CS 12/31

2008

www.gatehelp.com

CS

(D) the branch takes longer to execute that any other instruction
Question. 38

The following code is to run on a pipe lined processor with one branch delay slot 11: ADD R2 ! R7+R8 12: SUB R4 ! R5 R6 13: ADD R1 ! R2 + R3 14: STORE Memory [R4] ! R1 BRANCH to Label if R1==0 Which of the instruction 11,12,13 or 14 can legitimately occupy the delay slot without any other program modification? (A) 11 (C) 13
Question. 39

(B) 12 (D) 14

A clustering index is defined on the fields which are of type (A) Non-key and ordering (C) key and ordering
Question. 40

(B) Non-key and non-ordering (D) Key and non-ordering

Let R and S be two relations with the following schema R (P, Q, R1, R2, R3) S (P, Q, S1, S2) Where {P, Q} is the key for both schemes. Which of the following queries are equivalent? I II CS P (D S) P (R) D P (S) 13/31

2008 III IV P (P, Q (R) + P, Q (S))

www.gatehelp.com

CS

P (P, Q (R) (P, Q (R) P, Q (S))) (B) Only I and II (D) Only I, II and IV

(A) Only I and II (C) Only I, II and III

Question. 41

Consider the following relational schemes for a library database: Book (Title, Author, Catalog_no, Publisher, Year, price) Collection (Title, Author, Catalog_no) Which the following functional dependencies: I. II. III. Title Author " Catalog_no Catalog_no " Title Author Publisher Year Publisher Title Year " price

Assume {Author, Title} is the key for both schemes: which of the following statements is true? (A) Both Book and Collection are in BCNF (B) Both Book and Collection are in 3NF only (C) Book is in 2NF and Collection is in 3NF (D) Both Book and Collection are in 2NF only
Question. 42

Consider a file of 1684 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The CS 14/31

2008

www.gatehelp.com

CS

file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multi-level index scheme is used to store the secondary index, the number of first-level and second-level blocks in the multi-level index are respectively (A) 8 and 0 (C) 256 and 4 (B) 128 and 6 (D) 512 and 5

Data for Q. 43 & 44 are given below.

Solve the problems and choose the correct answers. Consider the following ER diagram

Question. 43

The minimum number of tables needed to represent M, N, P, R1, R2 is (A) 2 (C) 4

Question. 44

(B) 3 (D) 5

Which of the following is a correct attribute set for one of the tables for the correct answer to the above question? (A) {M1,M2,M3,P1} (C) {M1,P1,N1}
Question. 45

(B) {M1,P1,N1,N2} (D) {M1,P1}

In the IEEE floating point representation the hexadecimal value 0x00000000 corresponds to CS 15/31

2008 (A) the normalized value 2 127 (C) the normalized value + 0
Question. 46

www.gatehelp.com (B) the normalized value 2 126 (D) the special value + 0

CS

In the karnaugh map shown below, X denoted a dont care term. What is the nominal form of the function represented by the karnaugh map

(A) b.d + a.d

(B) a.b + b.d + a.b.d (D) a.b + b.d + a.d

(C) b.d + a.b.d

Question. 47

Let a denote number system radix. The only value(s) of r that satisfy the equation 121 + 11, is/are (A) decimal 10 (C) decimal 10 and 11
Question. 48

(B) decimal 11 (D) any value> 2

Give f1, f3 and f in canonical sum of products form (in decimal) for the circuit

f1 = /m (4, 5, 6, 7, 8) CS 16/31

2008 f3 = /m (1, 6, 15) f = /m (1, 6, 8, 15) Then f2 is (A) /m (4, 6) (C) /m (6, 8)
Question. 49

www.gatehelp.com

CS

(B) /m (4, 8) (D) /m (4,6,8)

If P , Q , R are Boolean variables, (P + Q) (P.Q + P.R) (P.R + Q)simplifies to (A) P.Q (C) P.Q + R
Question. 50

(B) P.R (D) P.R + Q

Which of the following tuple relational calculus expressions) is/are equivalent to 6t ! r (P (t)) 1. J7t ! r (P (t)) 3. J7t g r (JP (t)) (A) 1 only (C) 3 only
Question. 51

2. 7t g r (P (t)) 4. 7t g r (JP (t)) (B) 2 only (D) 3 and 4 only

If P, Q, R are subsets of the universal set U , then (P + Q + R) , (Pc + Q + R) , Qc , Rc is (A) Qc , Rc (C) Pc , Qc , Rc

Question. 52

(B) P , Qc , Rc (D) U

The following system of equations x1 + x2 + 2x 3 = 1 x1 + 2X 3 + 3X 3 = 2 X1 + 4X2 + ax 3 = 4 CS 17/31

2008

www.gatehelp.com

CS

has a unique solution. The only possible value (s) for a is/are (A) 0 (C) one of 0, 1 or 1
Question. 53

(B) either 0 or 1 (D) any real number other than 5

lim x sin x equals x + cos x (A) 1

x"3

(B) 1 (D) 3

(C) 3
Question. 54

Let fsa and pda be two predicates such that fsa(x) means x is a finite state automation, and pda(y) means, that y is a pushdown automation. Let equivalent be another predicate such that equivalent (a, b) means aa and b are equivalent. Which of the following first order logic statement represents the following: Each finite state automation has an equivalent pushdown automation. (A) (6x fsa (x)) & (7y pda(y) / equivalent(x, y)) (B) 6y fsa (x) & (7y pda(y) / equivalent(x, y)) (C) (6x7y (fsa( x) / pda (y)) / equivalent(x, y)) (D) (6x7y (fsa( x) / pda(x) / equivalent(x, y))
Question. 55

P and Q are two propositions. Which of the following logical expression are equivalent? 1. P 0 ~Q 2. ~(~ P / Q) 3. (P / Q) 0 (P / ~Q) 0 (~P / ~Q)

CS

18/31

2008 4. (P / Q) 0 (P / ~Q) 0 (~P / Q) (A) Only 1 and 2 (C) Only 1, 2 and 4

Question. 56

www.gatehelp.com

CS

(B) Only 1, 2 and 3 (D) All of 1, 2, 3, and 4

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? (A) 0.24 (C) 0.40
Question. 57

(B) 0.36 (D) 0.60

Let X be a random variable following normal distribution with mean + land variance 4. Let Y be another normal variable with mean 1 and variance unknown, If P (X # 1) = P (Y $ 2) the standard deviation of Y is (A) 3 (C) 2 (B) 2 (D) 1

Question. 58

Let

p=

/
1 # i # 2k i odd

i and Q =

/
1 # i # 2k i evene

i,

where k is positive integer. Then (A) P = Q k (C) P = Q (B) P = Q + k (D) P = Q + 2k

Data for Q. 59 & 60 are given below.

Solve the problems and choose the correct answers.

CS

19/31

2008

www.gatehelp.com

CS

Let xn denote the number of binary strings of length n that contain no consecutive so.
Question. 59

Which of the following recurrences does xn satisfy? (A) xn = 2xn 1 (C) xn = x[n/2] + n
Question. 60

(B) xn = x[n/2] + 1 (D) xn = xn 1 + xn 2

The value of x5 is (A) 5 (C) 8

Question. 61

(B) 7 (D) 16

Which of the following statements is true for every planar graph on n vertices (A) The graph is connected (B) The graph is Eulerian (C) The graph has a vertex-cover of size at most 3n/4 (D) The graph has an independent set of size at least n/3
Question. 62

How many of the following matrices have an eigenvalue 1? 1 0 0 1 11 1 0 G and = G = G.= G.= 00 00 1 1 11 (A) one (C) three (B) two (D) four

CS

20/31

2008
Question. 63

www.gatehelp.com

CS

The minimum Number of equal length subintervals needed to approximater

1

# xex dx

to an

accuracy of at least 1 # 10 6 using the trapezoidal rule is 3 (A) 1000e (B) 1000 (C) 100e
Question. 64

(D) 100

The Newton-Raphson iteration xn + 1 = 1 cxn + R m can be used to compute the 2 xn (B) reciprocal of R (A) square of R (C) square root of R
Question. 65

(D) logarithm of R

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 extreme for the curve 3x 4 16x3 24x2 + 37 is (A) 0 (C) 2
Question. 66

(B) 1 (D) 3

Which of the following system calls results in the sending of SYN packets? (A) socket (C) listen
Question. 67

(B) bind (D) connect

The data block of a very large file in the Unix file system are allocated using (A) Contiguous allocation (B) Linked allocation (C) indexed allocation CS 21/31

2008

www.gatehelp.com

CS

(D) an extension of indexed allocation

Question. 68

The P and V operations on counting semaphores, where s is a counting ewmaphore, are defined as follows: P (s); s = s 1; ifs < 0 then wait; V (s): s = s + 1; ifs <= 0 then wakeup a process waiting on s ; Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores Xb and Yb are used to implement the semaphore operations P (s) and V (s) as follows: P (s): Pb (X b); s = s - 1; if (s < 0) { Vb (X b); Pb (Yb); } else Vb (X b); P (s): Pb (X b); s = s + 1; if (s <= 0) { Vb (Yb); Vb (X b); The initial values of xb and yb are respectively (A) 0 and 0 (C) 1 and 0 (B) 0 and 1 (D) 1 and 1

CS

22/31

2008
Question. 69

www.gatehelp.com

CS

Which of the following statements about synchronous and asynchronous I/O is NOT true? (A) An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O (B) In both synchronous and asynchronous I/O an ISR (Interrupt Serive Routine) is invoked after completion of the I/O (C) A process making a synchronous I/O cal waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O (D) In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked afterr the completion of I/O
Question. 70

Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes? (A) In deadlock prevention, the request for resources is always granted if the resulting state is safe (B) In deadlock avoidance, the request for resources is always granted if the resulting state is safe (C) Deadlock avoidance is less restrictive than deadlock prevention (D) Deadlock avoidance requires knowledge of resource requirements a priori
Question. 71

A process executes the following code for(i = 0' i < n; i ++)fork(); The total number of child processes created is (A) n (C) 2n
Question. 72

(B) 2n 1 (D) 2n + 1 1

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual-to-physical address translation, where the virtual address is used as follows CS 23/31

2008

www.gatehelp.com

CS

: bits 30-31 are used to index into the first level page table, : bits 21-29 are used to index into second level page table : bits 12-20 are used to index into third level page table : bits 0-11 are used as offset within the page The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page table are respectively. (A) 20,20 and 20 (C) 24,24 and 20
Question. 73

(B) 24,24 and 24 (D) 25,25 and 24

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) (A) x = 3, y = 4, z = 2 (C) x = 6, y = 3, z = 5
Question. 74

(B) x = 6, y = 5, z = 3 (D) x = 5, y = 4, z = 5

What is printed by the following C program? int f(int x, int *py, int **ppz) void main() { { int y, z; int c, * b, ** a; ** ppz += 1; z = * ppz; c = 4; b = &c; a = &b; printf ("%d", f (c, b, a)); *py += 2; y = * py; x += 3; return x + y + z; (A) 18 (B) 19 (C) 21 (D) 22

CS

24/31

2008
Question. 75

www.gatehelp.com

CS

Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character. void reverse (void) { int c; if(?1) reverse(); ?2 } main () { printf(Enter Text); printf( "\n"); reverse(); printf( "\n"); } (A) ?1 is (getchar () ! = '\n') ?2 is getchar (c); (B) ?1 is (getchar ()) ! = '\n') ?2 is getchar (c); (C) ?1 is (c ! = '\n') ?2 is putchar (c); (D) ?1 is (( c = getchar ()) ! = '\n') ?2 is putchar (c);
Question. 76

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node { int value; struct node *next; } ; void rearrange (struct node *list) { struct node *p, *q; int temp; if (! list || ! list->next) return; p = list; q = list- > next; while (q) { CS 25/31

2008

www.gatehelp.com temp=p - > value;p_ >value = q - > value; q - > value = temp ; p = q - > next; q = p?p - > next : 0 ;

CS

} } (A) 1,2,3,4,5,6,7 (C) 1,3,2,5,4,7,6

Question. 77

(B) 2,1,4,3,6,5,7 (D) 2,3,4,5,6,7,1

Which of the following in true for the language{aP | P is a prime}? (A) It is not accepted by a Turning Machine (B) It is regular but not context-free (C) It is context-free but not regular (D) It is neither regular nor context-free, but accepted by a Turing machine
Question. 78

Which of the following are decidable? 1. 2. 3. 4. Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free (B) 1 and 4 (D) 2 and 4

(A) 1 and 2 (C) 2 and 3

Question. 79

If L and L are recursively enumerable then L is (A) regular (C) context-sensitive (B) context-free (D) recursive

CS

26/31

2008
Question. 80

www.gatehelp.com

CS

Which of the following statements is false? (A) Every NFA can be converted to an equivalent DFA (B) Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine (C) Every regular language is also a context-free language (D) Every subset of a recursively enumerable set is recursive
Question. 81

Given below are two finite state automata( " indicates the start and F indicates a final state) Y:
a 1 2 b 2 1

Z:
a 2 1 b 2 1

"
2F

"
2F

(A)
-P Q R(F) S a S R Q Q b R S P P

(B)
-P Q R(F) S a S R Q Q b Q S P P

(C)
-P Q R(F) S a Q R Q Q b S S P P

(D)
-P Q R(F) S a S S Q Q b Q R P P

CS

27/31

2008
Question. 82

www.gatehelp.com

CS

Which of the following statements are true ? 1. 2. 3. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa All -productions can be removed from any context-free grammar by suitable transformations The language generated by a context-free grammar all of whose production are of the form X " w or X " wY (where, w is a staring of terminals and Y is a non-terminal), is always regular The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees. (B) 2, 3 and 4 only (D) 1, 2 and 4 only

4.

(A) 1, 2, 3 and 4 (C) 1, 3 and 4 only

Question. 83

Match List-I with List-II and select the correct answer using the codes given below the lists: List-I A. Checking that identifiers are declared before their use B. Number of formal parameters in the declaration to a function agress with the number of actual parameters in a use of that function C. Arithmetic expressions with matched pairs of parentheses D. Palindromes List-II 1. 2. 3. 4. L = {a"b"c"d"| n # 1, m # 1} X " XbX | XcX | dXf | g L = {wcw | w ! (a | b)*} X " bXb | cXc |

Codes: A CS B C D 28/31

2008 (A) (B) (C) (D) 1 3 3 1 3 1 1 3 2 4 2 4 4 2 4 2

www.gatehelp.com

CS

Question. 84

Match List I with List II and select the correct answer using the codes given below the lists:

CS

29/31

2008

www.gatehelp.com

CS

Code: a (A) (B) (C) (D) 2 1 1 3 b 1 3 2 2 c 3 3 3 1 d 4 4 4 4

Question. 85

Which of the following are regular sets? 1. 2. CS {an b2m | n # 0, m # 0} {an bm | n = 2m} 30/31

2008 3. 4. {an bm | n ! m} {xcy | x, y ! {a, b}*}

www.gatehelp.com

CS

(A) 1 and 4 only (C) 1 only

(B) 1 and 3 only (D) 4 only

**********

CS

31/31