In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is True?

Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)

A bridge cannot be part of a simple cycle

Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)

A graph with bridges cannot have a cycle

Consider a simple checkpointing protocol and the following set of operations in the log. (start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7); (checkpoint); (start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3); (write, T3, z, 7, 2); If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list

Undo: none; Redo: T2, T4, T3; T1

Suppose you are provided with the following function declaration in the C programming language. int partition (int a[], int n); The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n int kth_smallest (int a[], int n, int k) { int left_end = partition (a, n); if (left_end+1==k) { return a [left_end]; } if (left_end+1 > k) { return kth_smallest (____________________); } else { return kth_smallest (____________________); } } The missing argument lists are respectively

(a, left_end, k) and (a, n–left_end–1, k–left_end–1)

(a, left_end, k) and (a+left_end+1, n–left_end–1, k–left_end–1

(a, left_end, k) and (a, n–left_end–1, k–left_end–1)

(a, left_end+1, N–left_end–1, K–left_end–1) and(a, left_end, k

(a, n–left_end–1, k–left_end–1) and (a, left_end, k

The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates xa and xb for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is the solution. The procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to be put in place of? So that it follows all steps of the secant method? Secant Initialize: xa, xb, ε, N // ε = convergence indicator fb = f(xb) i = 0 while (i ε) do i = i + 1 // update counter xt = ? // missing expression for // intermediate value xa = xb // reset xa xb = xt // reset xb fb = f(xb) // function value at new xb end while if |fb| > ε then // loop is terminated with i = N write “Non-convergence” else write “return xb” end if

xb – (fb– f(xa)) fb/ (xb – xa

xa– (fa– f(xa)) fa/ (xb – xa)

xb – (fb – xa) fb/ (xb – fb(xa)

xa – (xb – xa) fa/ (fb – f(xa))

Consider two relations R1(A, B) with the tuples (1, 5), (3, 7) and R1(A, C) = (1, 7), (4, 9). Assume that R(A,B,C) is the full natural outer join of R1 and R2. Consider the following tuples of the form (A,B,C) a = (1, 5, null), b = (1, null, 7), c = (3, null, 9), d = (4, 7, null), e = (1, 5, 7), f = (3, 7, null), g = (4, null, 9). Which one of the following statements is correct?

R contains a, b, e, f, g but not c, d

R contains e, f, g but not a, b

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is

Congruent to 0 mod 4, or 1 mod 4

Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is True?

R is symmetric and reflexive but not transitive

R is reflexive but not symmetric and not transitive

R is transitive but not reflexive and not symmetric

R is symmetric but not reflexive and not transitive

Which one of the following statements is NOT correct about HTTP cookies?

A cookie gains entry to the user’s work area through an HTTP header

A cookies is a piece of code that has the potential to compromise the security of an Internet user

A cookie gains entry to the user’s work area through an HTTP header

A cookie has an expiry date and time

Cookies can be used to track the browsing pattern of a user at a particular site

Consider the basic COCOMO model where E is the effort applied in person-months, D is the development time in chronological months, KLOC is the estimated number of delivered lines of code (in thousands) and ab, bb, cb, db have their usual meanings. The basic COCOMO equations are of the form.

D = ab(KLOC) exp(bb), E = cb(D) exp(db)

E = ab(KLOC) exp(bb), D = cb(E) exp(db)

D = ab(KLOC) exp(bb), E = cb(D) exp(db)

E = ab exp(bb), D = cb(KLOC) exp(db)

E = ab exp(db), D = cb(KLOC) exp(bb)

Consider the following two statements. S1: If a candidate is known to be corrupt, then he will not be elected. S2: If a candidate is kind, he will be elected. Which one of the following statements follows from S1 and S2 as per sound inference rules of logic

If a person is not kind, he is not known to be corrup

If a person is known to be corrupt, he is kind

If a person is not known to be corrupt, he is not kind

If a person is kind, he is not known to be corrupt

If a person is not kind, he is not known to be corrup

56 + Mcqs in GATE- CS-2015(SET 2) Page 1 McqOptions

1.	Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote the set of all possible functions defined from X and Y. Let f be randomly chosen from F. The probability of f being one-to-one is _________
A.	0.95
B.	0.80
C.	0.75
D.	0.70
Answer» B. 0.80

Discussion

2.	The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________
A.	2
B.	3
C.	4
D.	5
Answer» C. 4

Discussion

3.	Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN. Ethernet frames may carry data up to 1500 bytes (i.e. MTU = 1500 bytes). Size of UDP header is 8 bytes and size of IP header is 20 bytes. There is no option field in IP header. How may total number of IP fragments will be transmitted and what will be the contents of offset field in the last fragment?
A.	6 and 925
B.	6 and 7400
C.	7 and 1110
D.	7 and 8880
Answer» D. 7 and 8880

Discussion

4.	Which of the following languages is/are regular? L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w L2: {anbm ⎪m ≠ n and m, n≥0 L3: {apbqcr ⎪ p, q, r ≥ 0}
A.	L1 and L3 only
B.	L2 only
C.	L2 and L3 only
D.	L3 only
Answer» B. L2 only

Discussion

5.	In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is True?
A.	A tree has no bridge
B.	A bridge cannot be part of a simple cycle
C.	Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)
D.	A graph with bridges cannot have a cycle
Answer» C. Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)

Discussion

6.	A Computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is _______________ bits
A.	36
B.	32
C.	28
D.	40
Answer» B. 32

Discussion

7.	Consider a simple checkpointing protocol and the following set of operations in the log. (start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7); (checkpoint); (start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3); (write, T3, z, 7, 2); If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list
A.	Undo: T3, T1; Redo: T2
B.	Undo: T3, T1; Redo: T2, T4
C.	Undo: none; Redo: T2, T4, T3; T1
D.	Undo: T3, T1, T4; Redo: T2
Answer» B. Undo: T3, T1; Redo: T2, T4

Discussion

8.	Suppose you are provided with the following function declaration in the C programming language. int partition (int a[], int n); The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n int kth_smallest (int a[], int n, int k) { int left_end = partition (a, n); if (left_end+1==k) { return a [left_end]; } if (left_end+1 > k) { return kth_smallest (____________________); } else { return kth_smallest (____________________); } } The missing argument lists are respectively
A.	(a, left_end, k) and (a+left_end+1, n–left_end–1, k–left_end–1
B.	(a, left_end, k) and (a, n–left_end–1, k–left_end–1)
C.	(a, left_end+1, N–left_end–1, K–left_end–1) and(a, left_end, k
D.	(a, n–left_end–1, k–left_end–1) and (a, left_end, k
Answer» B. (a, left_end, k) and (a, n–left_end–1, k–left_end–1)

Discussion

9.	Consider the sequence of machine instructions given below: MUL R5, R0, R1 DIV R6, R2, R3 ADD R7, R5, R6 SUB R8, R7, R4 In the above sequence, R0 to R8 are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following 4 stages: (1) Instruction Fetch and Decode (IF), (2) Operand Fetch (OF), (3) Perform Operation (PO) and (4) Write back the Result (WB). The IF, OF and WB stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD or SUB instruction, 3 clock cycles for MUL instruction and 5 clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instructions is ___________
A.	11
B.	12
C.	13
D.	14
Answer» D. 14

Discussion

10.	Consider a processor with byte-addressable memory. Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes. A stack in the main memory is implemented from memory location (0100)16 and it grows upward. The stack pointer (SP) points to the top element of the stack. The current value of SP is (016E)16. The CALL instruction is of two words, the first word is the op-code and the second word is the starting address of the subroutine (one word = 2 bytes). The CALL instruction is implemented as follows: • Store the current value of PC in the stack. • Store the value of PSW register in the stack. • Load the starting address of the subroutine in PC. The content of PC just before the fetch of a CALL instruction is (5FA0)16. After execution of the CALL instruction, the value of the stack pointer is
A.	(016A)16
B.	(016C)16
C.	(0170)16
D.	(0172)16
Answer» E.

Discussion

11.	Consider the following routing table at an IP router Q51 For each IP address in Group-I identify the correct choice of the next hop from Group-II using the entries from the routing table above. List-I List-II A. 128.96.171.92 1. Interface 0 B. 128.96.167.151 2. Interface 1 C. 128.96.163.121 3. R2 D. 128.96.165.121 4. R3 5. R4 Codes: A B C D (a) 1 3 5 4 (b) 1 4 2 5 (c) 2 3 4 5 (d) 2 3 5 4
A.	a
B.	b
C.	c
D.	d
Answer» B. b

Discussion

12.	The number of onto functions (surjective functions) from set X = {1, 2, 3, 4} to set Y = {a, b, c} is
A.	36
B.	64
C.	81
D.	72
Answer» B. 64

Discussion

13.	The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates xa and xb for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is the solution. The procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to be put in place of? So that it follows all steps of the secant method? Secant Initialize: xa, xb, ε, N // ε = convergence indicator fb = f(xb) i = 0 while (i < N and \|fb\| > ε) do i = i + 1 // update counter xt = ? // missing expression for // intermediate value xa = xb // reset xa xb = xt // reset xb fb = f(xb) // function value at new xb end while if \|fb\| > ε then // loop is terminated with i = N write “Non-convergence” else write “return xb” end if
A.	xb – (fb– f(xa)) fb/ (xb – xa
B.	xa– (fa– f(xa)) fa/ (xb – xa)
C.	xb – (fb – xa) fb/ (xb – fb(xa)
D.	xa – (xb – xa) fa/ (fb – f(xa))
Answer» E.

Discussion

14.	Consider the C program below. #include int *A, stkTop; int stkFunc (int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case -1: size = val; break; case 0: if (stkTop < size ) A[stkTop++]=val; break; default: if (stkTop) return A[--stkTop]; } return -1; } int main() { int B[20]; A=B; stkTop = -1; stkFunc (-1, 10); stkFunc (0, 5); stkFunc (0, 10); printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0)); } The value printed by the above program is ___________
A.	9
B.	10
C.	15
D.	17
Answer» D. 17

Discussion

15.	The number of min-terms after minimizing the following Boolean expression is _________. [D′ + AB′ + A′C + AC′D + A′C′D]′
A.	1
B.	2
C.	3
D.	4
Answer» B. 2

Discussion

16.	Given below are some algorithms, and some algorithm design paradigms. List-I A. Dijkstra’s Shortest Path B. Floyd-Warshall algorithm to compute all pairs shortest path C. Binary search on a sorted array D. Backtracking search on a graph List-II 1. Divide and Conquer 2. Dynamic Programming 3. Greedy design 4. Depth-first search 5. Breadth-first search Match the above algorithms on the left to the corresponding design paradigm they follow Codes: A B C D (a) 1 3 1 5 (b) 3 3 1 5 (c) 3 2 1 4 (d) 3 2 1 5
A.	a
B.	b
C.	c
D.	d
Answer» D. d

Discussion

17.	Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows: X0 = 1 X1 X1 = 0 X1 + 1 X2 X2 = 0 X1 + {λ} Which one of the following choices precisely represents the strings in X0?
A.	10 (0* + (10)*)1
B.	10 (0* + (10))1
C.	1(0* + 10)*1
D.	10 (0 + 10)1 + 110 (0 + 10)1
Answer» D. 10 (0 + 10)1 + 110 (0 + 10)1

Discussion

18.	Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let α be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size with window scale option. Then the values of α and β are.
A.	63 milliseconds 65535 × 214
B.	63 milliseconds 65535 × 216
C.	500 milliseconds 65535 × 214
D.	500 milliseconds 65535 × 216
Answer» D. 500 milliseconds 65535 × 216

Discussion

19.	Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
A.	h(i) =i2 mod 10
B.	h(i) =i3 mod 10
C.	h(i) = (11 ∗ i2) mod 10
D.	h(i) = (12 ∗ i) mod 10
Answer» C. h(i) = (11 ∗ i2) mod 10

Discussion

20.	Consider two relations R1(A, B) with the tuples (1, 5), (3, 7) and R1(A, C) = (1, 7), (4, 9). Assume that R(A,B,C) is the full natural outer join of R1 and R2. Consider the following tuples of the form (A,B,C) a = (1, 5, null), b = (1, null, 7), c = (3, null, 9), d = (4, 7, null), e = (1, 5, 7), f = (3, 7, null), g = (4, null, 9). Which one of the following statements is correct?
A.	R contains a, b, e, f, g but not c, d
B.	R contains a, b, c, d, e, f, g
C.	R contains e, f, g but not a, b
D.	R contains e but not f, g
Answer» D. R contains e but not f, g

Discussion

21.	A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries. 1 2 5 14 3 4 6 23 10 12 18 25 31 ∞ ∞ ∞ When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is ____________
A.	2
B.	5
C.	6
D.	18
Answer» C. 6

Discussion

22.	Consider six memory partitions of size 200 KB, 400 KB, 600 KB, 500 KB, 300 KB, and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?
A.	200 KB and 300 KB
B.	200 KB and 250 KB
C.	250 KB and 300 KB
D.	300 KB and 400 KB
Answer» B. 200 KB and 250 KB

Discussion

23.	Consider the intermediate code given below: 1. i = 1 2. j = 1 3. t1 = 5 * i 4. t2 = t1 + j 5. t3 = 4 * t2 6. t4 = t3 7. a[t4] = –1 8. j = j + 1 9. if j <= 5 goto(3) 10. i = i + 1 11. if i < 5 goto(2) The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are
A.	5 and 7
B.	6 and 7
C.	5 and 5
D.	7 and 8
Answer» C. 5 and 5

Discussion

24.	A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is
A.	A multiple of 4A multiple of 4
B.	Even
C.	Odd
D.	Congruent to 0 mod 4, or 1 mod 4
Answer» E.

Discussion

25.	Perform the following operations on the matrix ⎡ 3 4 45⎤ ⎢ 7 8 105⎥ ⎣13 2 195⎦ Add the third row to the second row. Subtract the third column from the first column. The determinant of the resultant matrix is _____________.
A.	0
B.	1
C.	50
D.	100
Answer» B. 1

Discussion

26.	Let f(x) = x –(1/3) and A denote the area of the region bounded by f(x) and the X-axis, when x varies from –1 to 1. Which of the following statements is/are True? 1. f is continuous in [–1, 1] 2. f is not bounded in [–1, 1] 3. A is nonzero and finite
A.	2 only
B.	3 only
C.	2 and 3 only
D.	1, 2 and 3
Answer» D. 1, 2 and 3

Discussion

27.	A computer system implements a 40 bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _________
A.	20
B.	10
C.	11
D.	22
Answer» E.

Discussion

28.	Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the processor’s read requests result in a cache hit. The average read access time in nanoseconds is____________.
A.	10
B.	12
C.	13
D.	14
Answer» E.

Discussion

29.	A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?
A.	1
B.	2
C.	3
D.	4
Answer» E.

Discussion

30.	An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
A.	Θ(nlogn]
B.	Θ(n)
C.	Θ(logn)
D.	Θ(1)
Answer» E.

Discussion

31.	Consider the following statements: 1. The complement of every Turning decidable language is Turning decidable 2. There exists some language which is in NP but is not Turing decidable 3. If L is a language in NP, L is Turing decidable Which of the above statements is/are True?
A.	Only 2
B.	Only 3
C.	Only 1 and 2
D.	Only 1 and 3
Answer» E.

Discussion

32.	Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIX socket API.
A.	listen, accept, bind recv
B.	bind, listen, accept, recv
C.	bind, accept, listen, recv
D.	accept, listen, bind, recv
Answer» C. bind, accept, listen, recv

Discussion

33.	Match the following: List-I List-II A. Lexical analysis 1. Graph coloring B. Parsing 2. DFA minimization C. Register allocation 3. Post-order traversal D. Expression evaluation 4. Production tree Codes: A B C D (a) 2 3 1 4 (b) 2 1 4 3 (c) 2 4 1 3 (d) 2 3 4 1
A.	a
B.	b
C.	c
D.	d
Answer» D. d

Discussion

34.	The cardinality of the power set of {0, 1, 2 . . ., 10} is _________.
A.	1024
B.	1023
C.	2048
D.	2043
Answer» D. 2043

Discussion

35.	Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
A.	Ω(logn)
B.	Ω(n)
C.	Ω(nlogn)
D.	Ω(n2)
Answer» B. Ω(n)

Discussion

36.	Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is True?
A.	R is symmetric and reflexive but not transitive
B.	R is reflexive but not symmetric and not transitive
C.	R is transitive but not reflexive and not symmetric
D.	R is symmetric but not reflexive and not transitive
Answer» E.

Discussion

37.	Consider the following function written in the C programming language. The output of the above function on input “ABCD EFGH” is void foo (char a) { if (a && a != ` `) { foo(a+1); putchar(a); } }
A.	ABCD EFGH
B.	ABCD
C.	HGFE DCBA
D.	DCBA
Answer» E.

Discussion

38.	Which one of the following statements is NOT correct about HTTP cookies?
A.	A cookies is a piece of code that has the potential to compromise the security of an Internet user
B.	A cookie gains entry to the user’s work area through an HTTP header
C.	A cookie has an expiry date and time
D.	Cookies can be used to track the browsing pattern of a user at a particular site
Answer» B. A cookie gains entry to the user’s work area through an HTTP header

Discussion

39.	Consider the basic COCOMO model where E is the effort applied in person-months, D is the development time in chronological months, KLOC is the estimated number of delivered lines of code (in thousands) and ab, bb, cb, db have their usual meanings. The basic COCOMO equations are of the form.
A.	E = ab(KLOC) exp(bb), D = cb(E) exp(db)
B.	D = ab(KLOC) exp(bb), E = cb(D) exp(db)
C.	E = ab exp(bb), D = cb(KLOC) exp(db)
D.	E = ab exp(db), D = cb(KLOC) exp(bb)
Answer» B. D = ab(KLOC) exp(bb), E = cb(D) exp(db)

Discussion

40.	Consider the following C function. int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k
A.	0
B.	26
C.	51
D.	71
Answer» D. 71

Discussion

41.	A binary tree T has 20 leaves. The number of nodes in T having two children is
A.	18
B.	19
C.	17
D.	Any number between 10 and 20
Answer» C. 17

Discussion

42.	The number of divisors of 2100 is _________.
A.	42
B.	36
C.	78
D.	72
Answer» C. 78

Discussion

43.	A link has a transmission speed of 106 bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgment has negligible transmission delay, and that its propagation delay is the same as the data propagation delay. Also assume that the processing delays at nodes are negligible. The efficiency of the stop-and-wait protocol in this setup is exactly 25%. The value of the one-way propagation delay (in milliseconds) is ___________.
A.	4
B.	8
C.	12
D.	16
Answer» D. 16

Discussion

44.	The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0,...) is ________
A.	0
B.	1
C.	2
D.	3
Answer» E.

Discussion

45.	The larger of the two eigenvalues of the matrix ⎡ 4 5 ⎤ ⎣ 2 1 ⎦ is ____
A.	5
B.	6
C.	7
D.	8
Answer» C. 7

Discussion

46.	Consider the following two statements. S1: If a candidate is known to be corrupt, then he will not be elected. S2: If a candidate is kind, he will be elected. Which one of the following statements follows from S1 and S2 as per sound inference rules of logic
A.	If a person is known to be corrupt, he is kind
B.	If a person is not known to be corrupt, he is not kind
C.	If a person is kind, he is not known to be corrupt
D.	If a person is not kind, he is not known to be corrup
Answer» D. If a person is not kind, he is not known to be corrup

Discussion

47.	Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?
A.	Q1 is in NP, Q2 is NP hard
B.	Q2 is in NP, Q1 is NP hard
C.	Both Q1 and Q2 are in NP
D.	Both Q1 and Q2 are in NP hard
Answer» B. Q2 is in NP, Q1 is NP hard

Discussion

48.	Consider the following transaction involving two bank accounts x and y. read(x); x := x – 50; write(x); read(y); y := y + 50; write(y) The constraint that the sum of the accounts x and y should remain constant is that of
A.	Atomicity
B.	Consistency
C.	Isolation
D.	Durability
Answer» C. Isolation

Discussion

49.	If p, q, r, s are distinct integers such that: f(p, q, r, s) = max (p, q, r, s) g(p, q, r, s) = min (p, q, r, s) h(p, q, r, s) = remainder of (p × q) / (r × s) if (p × q) > (r × s) OR remainder of (r × s) / (p × q) if (r × s) > (p × q) Also a function fgh (p, q, r, s) = f(p, q, r, s) × g(p, q, r, s) × h(p, q, r, s). Also the same operation are valid with two variable functions of the form f(p, q). What is the value of fg(h(2, 5, 7, 3), 4, 6, 8)?
A.	6
B.	7
C.	8
D.	9
Answer» D. 9

Discussion

50.	Four branches of a company are located at M, N, O and P. M is north of N at a distance of 4 km; P is south of O at a distance of 2 km; N is southeast of O by 1 km. What is the distance between M and P in km?
A.	5.34
B.	6.74
C.	28.5
D.	45.49
Answer» B. 6.74

Discussion

Explore topic-wise MCQs in Computer Science.

Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote the set of all possible functions defined from X and Y. Let f be randomly chosen from F. The probability of f being one-to-one is _________

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________

Which of the following languages is/are regular? L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w L2: {anbm ⎪m ≠ n and m, n≥0 L3: {apbqcr ⎪ p, q, r ≥ 0}

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is True?

The number of onto functions (surjective functions) from set X = {1, 2, 3, 4} to set Y = {a, b, c} is

The number of min-terms after minimizing the following Boolean expression is _________. [D′ + AB′ + A′C + AC′D + A′C′D]′

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, n is

Perform the following operations on the matrix ⎡ 3 4 45⎤ ⎢ 7 8 105⎥ ⎣13 2 195⎦ Add the third row to the second row. Subtract the third column from the first column. The determinant of the resultant matrix is _____________.

Let f(x) = x –(1/3) and A denote the area of the region bounded by f(x) and the X-axis, when x varies from –1 to 1. Which of the following statements is/are True? 1. f is continuous in [–1, 1] 2. f is not bounded in [–1, 1] 3. A is nonzero and finite

A computer system implements a 40 bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _________

Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the processor’s read requests result in a cache hit. The average read access time in nanoseconds is____________.

A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?

An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Consider the following statements: 1. The complement of every Turning decidable language is Turning decidable 2. There exists some language which is in NP but is not Turing decidable 3. If L is a language in NP, L is Turing decidable Which of the above statements is/are True?

Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIX socket API.

Match the following: List-I List-II A. Lexical analysis 1. Graph coloring B. Parsing 2. DFA minimization C. Register allocation 3. Post-order traversal D. Expression evaluation 4. Production tree Codes: A B C D (a) 2 3 1 4 (b) 2 1 4 3 (c) 2 4 1 3 (d) 2 3 4 1

The cardinality of the power set of {0, 1, 2 . . ., 10} is _________.

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is True?

Consider the following function written in the C programming language. The output of the above function on input “ABCD EFGH” is void foo (char *a) { if (*a && *a != ` `) { foo(a+1); putchar(*a); } }

Which one of the following statements is NOT correct about HTTP cookies?

Consider the basic COCOMO model where E is the effort applied in person-months, D is the development time in chronological months, KLOC is the estimated number of delivered lines of code (in thousands) and ab, bb, cb, db have their usual meanings. The basic COCOMO equations are of the form.

Consider the following C function. int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k

A binary tree T has 20 leaves. The number of nodes in T having two children is

The number of divisors of 2100 is _________.

The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0,...) is ________

The larger of the two eigenvalues of the matrix ⎡ 4 5 ⎤ ⎣ 2 1 ⎦ is ____

Consider the following two statements. S1: If a candidate is known to be corrupt, then he will not be elected. S2: If a candidate is kind, he will be elected. Which one of the following statements follows from S1 and S2 as per sound inference rules of logic

Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?

Consider the following transaction involving two bank accounts x and y. read(x); x := x – 50; write(x); read(y); y := y + 50; write(y) The constraint that the sum of the accounts x and y should remain constant is that of

Four branches of a company are located at M, N, O and P. M is north of N at a distance of 4 km; P is south of O at a distance of 2 km; N is southeast of O by 1 km. What is the distance between M and P in km?

Consider the following function written in the C programming language. The output of the above function on input “ABCD EFGH” is void foo (char a) { if (a && a != ` `) { foo(a+1); putchar(a); } }