GATE CS-3

Kindly Submit Your Details, Then You Can Start Your Test !!

Name

Mobile No

City

State

Country

Course

1. The value of the dot product of the eigenvectors corresponding to any pair of different Eigen values of a 4- by-4 symmetric positive definite matrix is ___________.

A. -1

B. 1

C. 0

D. 2

2. A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________

A. 16383

B. 16391

C. 16387

D. 16385

3. Which one of the following statements is TRUE?

A. Compilation fails.

B. Execution results in a run-time error.

C. On execution, the value printed is 5 more than the address of variable i.

D. On execution, the value printed is 5 more than the integer value entered.

4. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

5. Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub trees having

A. 1

B. 11

C. 12

D. 21

6. Which one of the following is TRUE?

Consider the directed graph given below:

A. The graph does not have any topological ordering.

B. Both PQRS and SRQP are topological orderings.

C. Both PSRQ and SPRQ are topological orderings.

D. PSRQ is the only topological ordering.

7. Let P is a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

A. t1 = 5

B. t1 < t2

C. t1 > t2

D. t1 = t2

8. Which one of the following is FALSE?

A. A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.

B. Available expression analysis can be used for common sub expression elimination.

C. Live variable analysis can be used for dead code elimination.

D. x = 4 ∗ 5 ⇒ x = 20 is an example of common sub expression elimination.

9. Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.

A. 1

B. 3

C. 2

D. 4

10. Which one of the following is FALSE?

A. User level threads are not scheduled by the kernel.

B. When a user level thread is blocked, all other threads of its process are blocked.

C. Context switching between user level threads is faster than context switching between kernel level threads.

D. Kernel level threads cannot share the code segment.

11. Which one of the following statements is CORRECT?

Given the following statements:
S1: A foreign key declaration can always be replaced by
an equivalent check assertion in SQL.
S2: Given the table R (a, b, c) where a and b together
form the primary key, the following is a valid table
definition.
CREATE TABLE S (
a INTEGER,
d INTEGER,
e INTEGER,
PRIMARY KEY (d),
FOREIGN KEY (a) references R)

A. S1 is TRUE and S2 is FALSE.

B. Both S1 and S2 are TRUE.

C. S1 is FALSE and S2 is TRUE.

D. Both S1 and S2 are FALSE.

12. Which one of the following is correct about S1, S2, and S3?

Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links.
[S1] The computational overhead in link state protocols is higher than in distance vector protocols.
[S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol.
[S3] After a topology change, a link state protocol will converge faster than a distance vector protocol.

A. S1, S2, and S3 are all true.

B. S1, S2, and S3 are all false.

C. S1 and S2 are true, but S3 is false.

D. S1 and S3 are true, but S2 is false.

13. Which of the following are used to generate a message digest by the network security protocols? (P) RSA (Q) SHA-1 (R) DES (S) MD5

A. P and R only

B. Q and R only

C. Q and S only

D. R and S only

14. Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is 2 × 102 m/s and the token transmission time is ignored. If each station is allowed to hold the token for 2 μsec, the minimum time for which the monitoring station should wait (in μsec) before assuming that the token is lost is _______.

A. 28 to 30

B. 20 to 22

C. 30 to 32

D. 38 to 40

15. Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 m sec and the maximum segment size used is 2 KB. The time taken (in m sec) by the TCP connection to get back to 32 KB congestion window is _________.

A. 1100 to 1300

B. 800 to 1000

C. 1400 to 1600

D. 1500 to 1700

16. Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.

A. 3

B. 5

C. 4

D. 6

17. Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

A. r1(x); r2(x); w1(x); r3(x); w2(x)

B. r2(x); r1(x); w2(x); r3(x); w1(x)

C. r3(x); r2(x); r1(x); w2(x); w1(x)

D. r2(x); w2(x); r3(x); r1(x); w1(x)

18. Which one of the following is CORRECT?

Given the following two statements:
S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF.
S2: AB → C, D → E, E → C is a minimal cover for the set of functional dependencies
AB → C, D → E, AB → E, E → C.

A. S1 is TRUE and S2 is FALSE.

B. Both S1 and S2 are TRUE.

C. S1 is FALSE and S2 is TRUE.

D. Both S1 and S2 are FALSE.

19. Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in m sec) is ________.

Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.

A. 7.2

B. 8.2

C. 6

D. 9

20. Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.

A. 7

B. 6

C. 5

D. 4

21. A canonical set of items is given below

A. A shift-reduce conflict and a reduce-reduce conflict.

B. A shift-reduce conflict but not a reduce-reduce conflict.

C. A reduce-reduce conflict but not a shift-reduce conflict.

D. Neither a shift-reduce nor a reduce-reduce conflict.

22. There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is ___.

A. 13

B. 15

C. 12

D. 8

23. Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

24. The minimum number of comparisons required finding the minimum and the maximum of 100 numbers is _________________.

A. 147

B. 145

C. 146

D. 148

25. Consider a hash table with 9 slots. The hash function is ℎ(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17 and 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

A. 3, 0, and 1

B. 3, 3, and 3

C. 4, 0, and 1

D. 3, 0, and 2

26. Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3

A. Half of the product of the 3 consecutive integers.

B. One-third of the product of the 3 consecutive integers.

C. One-sixth of the product of the 3 consecutive integers.

D. None of the above.

27. Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is __________.

A. 4

B. 8

C. 6

D. 7

28. An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associatively A ≥ k exercising least-recently-used replacement policy?

A. n/N

B. 1/N

C. 1/A

D. k/n

29. The function f(x) = x sin x satisfies the following equation: f"(x) + t cos x = 0. The value of t is _______

A. 2

B. -2

C. 1

D. -1

30. A function f(x) is continuous in the interval [0,2]. It is known that f(0) = f(2) = -1 and f(1) = 1. Which one of the following statements must be true?

A. There exists a y in the interval (0,1) such that f(y) = f(y+1)

B. For every y in the interval (0,1), f(y) = f(2-y)

C. The maximum value of the function in the interval (0,2) is 1

D. There exists a y in the interval (0,1) such that f(y) = -f(2-y)

31. Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is x/1296. The value of X is ________.

A. 10

B. 9

C. 8

D. 7

32. A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)} and the set of all 3- pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10-pennants is __________.

A. 87

B. 88

C. 89

D. 90

33. Let S denote the set of all functions f : {0,1}4 → {0,1}. Denote by N the number of functions from S to the set {0, 1}. The value of log2 log2 N is is ______.

A. 12

B. 13

C. 15

D. 16

34. Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a - c| ≤ 1 and |b - d| ≤ 1.The number of edges in this graph is

A. 500

B. 502

C. 506

D. 510

35. An ordered n-tuple (d1, d2, …,dn) with d1 ≥ d2 ≥ ⋯ ≥ dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, … , dn respectively. Which of the following 6-tuples is NOT graphic?

A. (1, 1, 1, 1, 1, 1)

B. (2, 2, 2, 2, 2, 2)

C. (3, 3, 3, 1, 0, 0)

D. (3, 2, 1, 1, 1, 0)

36. Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?

A. ((p ↔ q) ∧ r) ∨ (p ∧ q ∧ ∼ r)

B. (∼ (p ↔ q) ∧ r) ∨ (p ∧ q ∧ ∼ r)

C. ((p → q) ∧ r) ∨ (p ∧ q ∧ ∼ r)

D. (∼ (p ↔ q) ∧ r) ∧ (p ∧ q ∧ ∼ r)

37. Consider two processors P1 and P2 executing the same instruction set. Assume that under identical conditions, for the same input, a program running on P2 takes 25% less time but incurs 20% more CPI (clock cycles per instruction) as compared to the program running on P1. If the clock frequency of P1 is 1GHz, then the clock frequency of P2 (in GHz) is _________.

A. 1.2

B. 1.3

C. 1.5

D. 1.6

38. Choose the most appropriate phrase from the options given below to complete the following sentence. India is a post-colonial country because

A. It was a former British colony

B. Indian Information Technology professionals have colonized the world

C. India does not follow any colonial practices

D. India has helped other countries gain freedom

39. Who ___________ was coming to see us this evening?

A. you said

B. did you say

C. did you say that

D. had you said

40. Match the columns.

Column I
1) eradicate
2) distort
3) saturate
4) utilize
Column II
P) misrepresent
Q) soak completely
R) use
S) destroy utterly

A. 1:S, 2:P, 3:Q, 4:R

B. 1:P, 2:Q, 3:R, 4:S

C. 1:Q, 2:R, 3:S, 4:P

D. 1:S, 2:P, 3:R, 4:Q

41. What is the average of all multiples of 10 from 2 to 198?

A. 90

B. 100

C. 110

D. 120

42. The old city of Koenigsberg, which had a German majority population before World War 2, is now called Kaliningrad. After the events of the war, Kaliningrad is now a Russian territory and has a predominantly Russian population. It is bordered by the Baltic Sea on the north and the countries of Poland to the south and west and Lithuania to the east respectively. Which of the statements below can be inferred from this passage?

A. Kaliningrad was historically Russian in its ethnic make up

B. Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia

C. Koenigsberg was renamed Kaliningrad, as that was its original Russian name

D. Poland and Lithuania are on the route from Kaliningrad to the rest of Russia

43. The number of people diagnosed with dengue fever (contracted from the bite of a mosquito) in north India is twice the number diagnosed last year. Municipal authorities have concluded that measures to control the mosquito population have failed in this region. Which one of the following statements, if true, does not contradict this conclusion?

A. A high proportion of the affected population has returned from neighbouring countries where dengue is prevalent

B. More cases of dengue are now reported because of an increase in the Municipal Office’s administrative efficiency

C. Many more cases of dengue are being diagnosed this year since the introduction of a new and effective diagnostic test

D. The number of people with malarial fever (also contracted from mosquito bites) has increased this year

44. If x is real and |x2 – 2x + 3| = 11, then possible values of |- x3 + x2 - x| include

A. 2, 4

B. 2, 14

C. 4, 52

D. 14, 52

45. The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students doubled in 2009, by what percent did the number of male students increase in 2009?

A. 120

B. 140

C. 160

D. 180

46. At what time between 6 a.m and 7 a.m Will the minute hand and hour hand of a clock make an angle closest to 60°?

A. 6: 22 a. m

B. 6: 27 a. m

C. 6: 38 a. m

D. 6: 45 a. m

47.Which one of the following about L, M, and N is CORRECT?

Consider the following statements:
P : Good mobile phones are not cheap
Q : Cheap mobile phones are not good
L : P implies Q
M : Q implies P
N : P is equivalent to Q

A. Only L is TRUE.

B. Only M is TRUE.

C. Only N is TRUE.

D. L, M and N are TRUE.

48. Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4. The size of L is __________.

A. 3

B. 5

C. 7

D. 9

49. Which one of the following statements is TRUE about every n × n matrix with only real eigenvalues?

A. If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative.

B. If the trace of the matrix is positive, all its eigenvalues are positive.

C. If the determinant of the matrix is positive, all its eigenvalues are positive.

D. If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive

50. If V1 and V2 are 4-dimensional subspaces of a 6- dimensional vector space V, then the smallest possible dimension of V1 ∩ V2 is ______.

A. 1

B. 2

C. 3

D. 4

51. Which one of the following Digital Logicblocks is the most suitable for implementing this function?

Consider the following combinational function block
involving four Boolean variables x, y, a, b where x, a, b
are inputs and y is the output.
f (x, y, a, b)
{
if (x is 1) y = a;
else y = b; }

A. Full adder

B. Priority encoder

C. Multiplexor

D. Flip-flop

52. Which processor has the highest peak clock frequency?

Consider the following processors (ns stands for
nanoseconds). Assume that the pipeline registers have
zero latency.
P1 : Four-stage pipeline with stage latencies 1 ns, 2 ns, 2
ns, 1 ns.
P2 : Four-stage pipeline with stage latencies 1 ns, 1.5 ns,
1.5 ns, 1.5 ns.
P3 : Five-stage pipeline with stage latencies 0.5 ns, 1 ns,
1 ns, 0.6 ns, 1 ns.
P4 : Five-stage pipeline with stage latencies 0.5 ns, 0.5
ns, 1 ns, 1 ns, 1.1 ns.

A. P1

B. P2

C. P3

D. P4

53. The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4 X3 + 6X + 5 for a given value of X, using only one temporary variable is _______.

A. 6

B. 7

C. 8

D. 9

54. The order in which the nodes are visited during an in-order traversal of the tree is

Consider the following rooted tree with the vertex labeled P as the root:

A. SQPTRWUV

B. SQPTUWRV

C. SQPTWUVR

D. SQPTRUWV

55. Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

A. 17

B. 18

C. 19

D. 20

56. You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

A. O(n2)

B. O(n log n)

C. Θ(n log n)

D. O(n3)

57. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.

a∗b∗(ba)∗a∗

A. 2

B. 3

C. 4

D. 5

58. Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE?

A. Both 2Σ* and Σ* are countable

B. 2Σ* is countable and Σ* is uncountable

C. 2Σ* is uncountable and Σ* is countable

D. Both 2Σ* and Σ* are uncountable

59. One of the purposes of using intermediate code in compilers is to

Add description here!

A. Make parsing and semantic analysis simpler.

B. Improve error recovery and error reporting.

C. Increase the chances of reusing the machineindependent code optimizer in other compilers.

D. Improve the register allocation.

60. Which of the following statements are CORRECT?

1) Static allocation of all data areas by a compiler makes
it impossible to implement recursion.
2) Automatic garbage collection is essential to implement
recursion.
3) Dynamic allocation of activation records is essential to
implement recursion.
4) Both heap and stack are essential to implement
recursion.

A. 1 and 2 only

B. 2 and 3 only

C. 3 and 4 only

D. 1 and 3 only

61. A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? 4, 7, 6, 1, 7, 6, 1, 2, 7, 2

A. 4

B. 5

C. 6

D. 7

62. A prime attribute of a relation scheme R is an attribute that appears

A. In all candidate keys of R.

B. In some candidate key of R.

C. In a foreign key of R.

D. Only in the primary key of R.

63. In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

A. Network layer and Routing

B. Data Link Layer and Bit synchronization

C. Transport layer and End-to-end process communication

D. Medium Access Control sub-layer and Channel sharing

64. A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

A. 0111110100

B. 0111110101

C. 0111111101

D. 0111111111

65. Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a 50-bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?

A. 128

B. 64

C. 256

D. 512

Warning: Undefined array key "correct_answer_logic" in /home/kaling/public_html/kalingaplus/wp-content/plugins/quiz-master-next/php/classes/class-qmn-quiz-manager.php on line 451