Company: iGATE Global Solutions Limited

Gate Model Exam Paper(CS)

1. Find the Fourier sine transform off f(x), where

(c) (1-cos as)                                   (d) None of these

1. Nullity of the matrix is

(a) 1(b) 2

(c) 3(d) 4

1. The proposition n of  is

(a) A tautology

(c) Logically equivalent to

(d) None of the above

1. If A and B be sets and Ac and Bc denote the complements of the sets, A and B, then set (A-B) (B-A)  (A B) Is equal to

(a) A B                                            (b) Ac Bc

(c) A B                                            (d) Ac Bc

1. Let   G=G(V,E)  has five vertices, then what is the maximum number of m of edges in E, if G  is a multi graph?

(a) 5(b) 2

(c) 10(d) Finite or infinite

1. How many straight lines can be drawn through 10 points on a circle?

(a) 10(b) 20

(c) 45(d) infinite

1. Which of these does not over run the server when the number of clients rises?

1. CGI2. JSP

(a) 1 only (b) 2 only

(c) Both (a) and (b) (d) None of these

1. Which of these does not require closing?

(a) <h1>(b) <br>

(c) <body> (d) <html>

1. The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right  hand side

(a) 30(b) 31

(c) 33(d) 28

1. Which of these is not a software process model?

(a) RAD(b) WINWIN spiral

(c) Prototyping(d) Recurrent

1. The building blocks of CASE are

1. CASE tools

2. Hardware platform

3. Operating system

4. Environment architecture

5. Integration framework

6. Portability services

(a) 1,2,3,4,5,6 (b) 1,3,4,2,5,6

(c) 1,2,5,6,3,4(d) 4,2,3,6,5,1

1. A cohesive module performs a single task within a software procedure, requiring little interaction with other procedures.

The correct order from least required cohesion to most required cohesion from these cohesion types is

1. Coincidentally

2. Temporal

3. Logically

4. Communicational

(a)1,2,3,4 (b) 1,3,2,4

(C) 3,2,1,4(d)4,2,1,3

1. What does the following program print?
2.

void f(int *p, int* g){

•
•
•

int i=1, j=0;

int main(){

f(&i, &j);

printf(“%d %dn”, i, j);

return 0;

•

(a) 2 2(b) 2 1(c) 0 1(d) 1 2

1. Which of these correct in C?
2.
3.
4.
5.

(a) P1 (b) P2(c) P3(d) P4

1. How to remove security concerns caused by dynamic linking?

(a) By incorporating cryptographic procedures in C

(b) By using secure linking

(c) By making security static

(d) By making search path for libraries known somehow at runtime

1. What is the value of j and k after the execution of following code fragment?

j =0

k=j++ + ++j+ ++ j + j++ + ++j+ j++

(a) 4, 12(b) 4, 15

(c) 3, 15(d) 4, 18

1. How many keywords are there in the following code fragment   printf(“i=%d” ,i)?

(a) 12(b) 10

(c) 8(d) 7

1. What is the height of the binary tree

45, 12, 15, 34, 56, 70, 54?

(a) 3(b) 2

(c) 4(d) 5

1. In SQL, relations can contain null values and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pair is equivalent?

(a) x=5; not (not (x=5)

(b) x=5; x>4, where x is an integer

(c) x≠5; not (x=5)

(d) None of the above

1. From the following instance of a relation schema R(A, B, C), we can conclude that

(a) A functionally determine B and B functionally determine C

(b) A functionally determine B and B does not functionally determine C

(c) B does not functionally determine C

(d) A does not functionally determine b and B does not functionally determine C

1. In the index allocation scheme of blocks to a life, the maximum possible size of the file does not depend on

(a) The size of the blocks

(b) The number of blocks used for the index

(c) The size of the address of the blocks

(d) The level of indices

1. Which of these are error correcting codes?

1. Parity2. Hamming code

3. CRC code

(a) 1, 2, 3(b) 1, 2

(c) 1, 3(d) 2, 3

1. Which of these fields doesn’t come in FDDI frame format?

(a) Preamble(b) Destination address

(c) Source address(d) Access control

1. The following functional dependencies hold for relations R(A, B, C) and S(B, D, E)
2.
3.

The relation R contains 300 tuples and the relation S contains 100 tuples. What is the maximum number of tuples possible in the natural join RS?

(a) 100(b) 200

(c) 300(d0 3000

1. Binary trees are preferred to B+ trees in databases

(a) when data is transferred in blocks

(b) when data is transferred in individual blocks

(c) when disk capacities are more than memory capacities

(d) when disks are more reliable than memory

1. With regard to the expressive power of the formal relational query languages, which of the following statements is false?

(a) Relational algebra is less powerful than relational calculus

(b) Relational algebra doesn’t have the same power as relational calculus

(c) Relational algebra doesn’t have the same power as safe relational calculus

(d) None of the above

2 marks Questions

1. Given  P(A )=  and P(A B)=   then P(B) is

(a) 2/3(b) 1/5

(c) 1/3(d) 4/5

1. If  u+iv is an analytic function, then v+iu will be

(a) always analytic’

(b) Analytic only ifu= constant

(c) Analytic only ifv= constant

(d) Analytic only if both u and v are constants

1. If product of matrix

A=  and

B=

is a null matrix, then  and  differ  by an

(a) Odd multiple of

(b) Even multiple of

(c) Odd multiple of

(d) Even multiple of

1. The value of  in the mean value theorm of

F(b)-f(a)=(b-a)f’(

For f(x) A=x2 + Bx + Cin (a,b) is

(a) b+a(b) b-a

(c)                                      (d)

1. If , then a constant k, k equals

(a) 1(b) 0

(c) f(k)-f(0)(d) f(x+k)-f(x)

1. Complementary function of

is

(a) c1x+c2(b) c1=x2 +c3

(c) c1x-1+c2x-2(d) c1x2 +c1x

1. The maximum slope of the curve
2.

(a) 14(b) 16

(c) 19(d) -13

1. The solution of the differential equation

is given by

(a)

(b)

(c) =x2c

(d)

1. Consider the following code fragment:

If (fork( ) = =0)

{a=a+5;printf(“%d, %d/n”, a and a);}

else {a-5;printf(“%d,%d/n”, a, & a);}

let u, v be the values printed by the parent process, and x, y be the values printed by the child process,which one of the following is true?

(a) u=x+10 and v=y

(b) u=x=10 and v≠y

(c) u+10=x and v=y

(d) u+10=x and v≠y

1. Consider the following C function

int f(int n)

{static int i=1;

If (n>=5) return n:

n= n+i;

•

return f(n);

•

The value returned by f(1) is

(a) 5(b) 6

(c) 7(d) 8

1. Consider the grammar :
2.

Let the number of states in SLR (1), LR(1), and LALR(1) parses for the grammar be n1, n2, and n3 respectively, which of the following holds good?

(a) n1 < n2 < n3(b) n1 = n3 <n2

(c) n1 =n2 =n3(d) n1 ≥ n3 ≥ n2

1. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.6µs.The maximum frame size is

(a) 94(b) 416

(c) 464(d) 512

1. Which of the following layers doesn’t come in TCP/IP model?

(a) Application(b) Transport

(c) Internet(d) Data link

1. 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

1. Consider the following program segment for a hypothetical CPU having three user register R1, R2,and  R3:

 Instruction size(in words) MOV R1, 5000 ; R1           Memory [5000] MOV R2, (R1) ; R2           Memory [(R1)] ADD R2, R3 : R2         R2 +R3 MOV 6000, R2 : Memory[6000]R2 : Machine halts

Consider that the memory is byte addressable with size 32 bit and program has been loaded starting from memory location 1000(decimal). If an interrupt occurs while the CPU has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be

(a) 1007(b) 1020

(c) 1024(d) 1028

1. In a M×N matrix such that all non-zero entries are covered in row a and b columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

(a) ≤ a+b(b)≤ MAX{A,B}

(c) ≤ min {M –a, N –b}(d)≤ min {a, b}

1. Suppose T(n) =2t(n/2) +nT (0) =T(1) =1

Which one of the following is false?

(a) T(n) = O(n2)                         (b) T(n) = (n log n)

(c) T(n) = (n2)                         (d) T(n) = O(n log n)

1. The goal of structured programming is to

(a) have well indented programs

(b) be able to infer the flow of control from the compiled code

(c) be able to infer the flow of control from the program text

(d) avoid the use of GOTO statements

1. The tightest lower bound on the number of comparisons, in the worst ease, for comparison-based sorting is of the order of

(a) n(b) n2

(c) n log n(d) n log2 n

1. Consider a relation schema R = (A, B, C, D, E, H) on which the following functional dependences hold:

(A->B, BC-> D, E->C, D->A), what are the candidate keys of R?

(a) AE,BE(b) AE, BE, DE

(c) AEH, BEH, BCH (d) AEH, BEH, DEH

1. If 73x( in base-x number system)nis equal to 54y( in base-y number system), the possible values of x and y are

(a) 8, 16(b) 10, 12

(c) 9, 13(d) 8, 11

1. Consider the languages:

L1=(wwR|w  {0, 1}*}

L2={w#wR|w  {0,1}*}where # is a special symbol

L3= {ww| w {0,1}*}

Which one of the following is true?

(a) L1 is a deterministic CFL

(b) L2 is a deterministic CFL

•

(d) L3 is a deterministic CFL

1. Consider the Grammar:

E       E+n| E n| n

For a sentence n + n  n, the handles in the right sensential form of the reduction are

(a) n, E+ n and E+ n  n

(b) n, E+ n and E+ E  n

(c) n, E+ n and n+ n  n

(d) n, E+ n and E  n

1. Consider the grammar with the following translation rules and E as the start symbol

2.
3.
4.
5.

Fnum {F.value=num.value}

Compute E.value for the root of the parser tree for the expression: 2# 3 & 5 # 6 & 4.

(a) 200(b) 180

(c) 160(d) 40

1. Let A be a sequence of distinct integers sorted in ascending order. How many distinct pairs of sequences B and C there such that (1) each sorted in ascending order (2) B has 5 and C has 3 elements, (3) the result of merging B and C gives A?

(a) 2(b) 30

(c) 56(d) 256

1. The problem 3-SAT and 2-Sat are

(a) Both in P

(b) Both NP-complete

(c) NP-complete and in P respectively

(d) undecidable and NP-complete respectively

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

(a) Abstraction and encapsulation

(b) strictly-typedness

(c)Type-safe properly coupled with sub-type rule

(d) Polymorphism in the pressure of inheritance

1. Assume the following C variable declaration

Int *A[10], B[10][10];

Of the following expressions

1. A[2] 2. A[2][3]3. B[1]4. B[2][3]

Which will not give compile-time errors is used as left hand sides of assignment statements in a C program?

(a) 1, 2 and 4(b) 2, 3 and 4

(c) 2 and 4(d) 4 only

1. Given the following input (4322 1334,1471,9679, 1989, 6171, 6173, 4199) and the hash function xmod 10, Which of the following statements are true?

1. 9679, 1989, 4199 hash to the same value

2. 1471, 6171, hash to the same value

3. all elements hash to the same value

4. Each element hashes to a different value

(a) 1 only(b) 2 only

(c) 1 and 2 (d) 3 or 4

1. Let f:B        C and g:A        B be two functions and let h=fog. Given that h is an onto function. Which one of the following is true?

(a) f and g should both be onto functions

(b) f should be onto and g needs not be onto

(c) g should be onto and f needs not be onto

(d) both f and g need not be onto

1. In a population of N families,50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?

(a) 3/23(b) 6/23

(c) 3/10(d) 3/5

1. Which one of the following is not shared by the threads of the same process?

(a) Stack(b) Address space

(c) File descriptor table(d) Message queue

1. A subnet has been assigned a subnet mask of 255.255.255.192. What is the maximum number of hosts that can belong to this subnet?

(a) 14(b) 30

(c) 62(d) 126

1. A software organization has been assessed at SEI CMM level 4.Which of the following does the organization need to practice beside process Change management and Technology Change Management in order to achieve level 5

(a) Defect detection(b) Defect prevention

(c) Defect isolation(d) Defect propagation

1. Suppose two parties A and B wish to setup a common secret key (D-H key) between themselves using the Diffle-Hellman key exchange technique. They agree on 7 as the modulus and 3 as the primitive root. Party A chooses 2 and party B chooses 5 as their respective secrets. Their D-H key is

(a) 3(b) 4

(c) 5(d) 6

1. We have two designs D1 and D2 for a synchronous pipeline processor. D1 has 5 pipeline stage with execution times of 3ns, 2ns, and 3,ns while the design D2 has 8 pipeline stages each with 2ns execution time. How much time can be saved using design D2 over design D1 for execution 100 instructions?

(a) 214ns(b) 202ns

(c) 86ns(d) -200ns

1. Which of the following statements is false regarding a bridge?

(a) Bridge is a layer 2 device

(b) Bridge reduces collision domain

(c) Bridge is used to connect two or more LAN segments

(d) Bridge reduces broadcast domain

1. What is the availability of software with the following reliability figures?

Mean Time Between Failure (MTBF) = 25 days

Mean Time To Repair (MTTR) = 6 h

(a) 1% (b) 24%

(c) 99%(d) 99.009%

1. Ina particular Unix OS, each data block is of size 1024 byte, each node has 10 direct data block addresses and three additional addresses-one for single indirect block, one for double indirect block and one for triple indirect block. Also each block can contain addresses for 128 blocks. Which one of the following is approximately the maximum size of a file in the file system?

(a) 512Mbyte(b) 2 Gbyte

(c) 8 Gbyte(d) 16 Gbyte

1. On a TCP connection, current congestion window size is congestion Window =4kbyte. The window size advertised by the receiver is Advertise Window=6 Kbyte. The last byte sent by the sender is last byte sent =10240 and the last byte acknowledged by the receiver is last byte asked =8192. The current window size at the sender is

(a) 2048 byte(b) 4096 byte

(c) 6144 byte(d) 8192 byte

1. How many pulses are needed to change the content of a 8-bit up counter from 10101100 to 00100111 (rightmost bit is the LSB)?

(a) 134(b) 133

(c) 124(d) 123

1. Which of these is worst routing algorithm in case of congestion?

(a) Flooding(b) Distance vector

(c) Link state(d) Flow based

1. What is the size of checksum in byte in token ring MAC sub layer protocol

(a) 1(b) 2

(c) 3(d) 4

1. What is in-order traversal of the tree which is shown as pre-order traversal here 10, 70, 50, 60, 30, 40, 90, 20, 80?

(a) 10, 20. 30. 40. 50. 60. 70. 80. 90

(b) 20, 30, 50, 60, 90, 10, 40, 80, 70

(c) 20, 50, 80, 90, 10, 30, 60, 40, 70

(d) 70, 50, 90, 30, 10, 20, 40, 60, 80

1. A hash table of length 10 uses open addressing with hash function  h(k)=k mod 10 and linear probing. After inserting 5 values into a empty hash table, the table is as shown below

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

(a) 12, 24, 54, 35, 10(b) 54, 35, 24, 10, 12

(c) 12, 10, 35, 54, 24(d) 10, 12, 35, 24, 54

1. Match List 1 with list 2 and select the correct answer using the codes given below the lists

 List 1 List 2 A. Token bus B. DQDB C. Ethernet D. Token ring 1. 802.3 2. 802.4 3. 802.5 4. 802.6

(a) A-(2), B-(3), C-(4), D-(1)

(b) A-(3), B-(1), C-(4), D-(2)

(c) A-(1), B-(2), C-(3), D-(4)

(d) A-(4), B-(3), C-(1), D-(2)

General Aptitude

1. Which of the following options is closest in meaning to the word given below?

2.

(a) Unrefined(b) Tasteless

(c) Inelegant(d) Graceful

1. The question below consists of a pair of related words followed by four pair of words. Select the pair which best expresses the relation in the original pair

Die : Dice

(a) data : Datas(b) Mouse : Mice

(c) Monkey : Monkies(d) Dates : Datum

1. Choose the most appropriate word for the options given below to complete the following sentence.

Congress is having great difficulty developing a consensus on energy policy, primarily because the policy objectives of various members of Congress rest on such……… assumptions

(a) common place(b) trivial

(c) explicit(d) divergent

1. Choose the most appropriate word for the options given below to complete the following sentence.

Because folk art is neither completely rejected nor accepted as an art form by art historians, their final evaluations of it necessarily remain ………

(a) Arbitrary(b) equivocal

(c) Orthodox(d) unspoken

1. The price per kg of rice increases by 20 %. By what percentage should the consumption be decreased such that expenditure remains the same?

(a) 20% (b) 16.67%

(c) 25%(d) 16.33%

1. One state adds 7% sales tax to the price of most purchased within its jurisdiction. This tax therefore, if viewed as tax on income, has the reverse effect of the federal income tax, the lower the income, the higher the annual percentage rate at which the income is taxed

The conclusion above would be properly drawn if which of the following were assumed as a premise?

(a) The amount of money citizens spend on products subject to the state tax tends to be equal across income levels

(b) The federal income tax favours citizens with high incomes, whereas the state sales

tax favours citizens with low incomes.

(c) Citizens with low annual incomes can afford to pay a relatively higher percentage

of their incomes in state sales tax, since their federal income tax is relatively low

(d) The lower a state’s sales tax, the income it will tend to redistribute income from

the more affluent citizens to the rest of the society

1. A man invests a certain amount of money at 6 % pa simple interest and another sum at 7% pa simple interest. His income from interest after 2 year was Rs354. One fourth of the first sum is equal to One-fifth of the second sum. The total sum invested was

(a) Rs 2600(b) Rs 2700

(c) Rs 2880(d) Rs 2900

1. Mr Rachel buys some apples at 5 per rupee from one trader, and a similar quantity at 7 per rupee from a different trader. He mixes both the varieties and sells the entire lot at 6 per rupee. What is the profit or loss % that he makes

(a) 2 %                                (b) 3 %

(c) 3 %                            (d) 2 %

1. A man starts from B to k, another man starts from K to B at the same time. After passing each either they complete their journey in 3  and 4  h respectively. Find the speed of the second man if the speed of the first is 12km/h

(a) 8 km/h(b) 10km/h

(c) 15 km/h(d) 24 km/h

1. A and B working separately can do a piece of work in 9 and 12 days respectively. If they work for a day alternatively. A beginning, in how many days the work will be completed

(a) 7 days                                 (b) 9  days

(c) 10  days                              (d) 12  days

•

1. (c)2. (b)3. (b)4. (c)5. (d)6. (c)

7. (a)8. (b)9. (d) 10. (d)11. (d)12. (b)

13. (d)14. (a)15. (a)16. (d)17. (a)18. (a)

19. (a)20. (a)21. (d)22. (b)23. (d)24. (a)

25. (a)26. (c)27. (c)28. (d)29. (c)30. (c)

31. (b)32. (c)33. (a)34. (b)35. (b)36. (c)

37. (b)38. (c)39. (d)40. (a)41. (a)42. (a)

43. (b)44. (c)45. (b)46. (d)47. (d)48. (b)

49. (d)50. (c)51. (d)52. (c)53. (b)54. (d)

55. (c)56. (b)57. (b)58. (a)59. (c)60. (b)

61. (c)62. (a)63. (d)64. (b)65. (d)66. (b)

67. (b)68. (a) 69. (d)70. (a)71. (a)72. (b)

73. (d)74. (b)75. (d)76. (b)77. (b)78. (a)

79. (b)80. (a)81. (b)82. (c)