PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 1

41 Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B*. We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let L_f denote the language {x ≠ f(x) | x ∈ A*}. Which of the following statements is true:

A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.

42 Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?

Shortest path from B to C are two B-A-C and B-C both of weight '3'

43 A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-re-entrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

Reentrant property is provided, so that a process who owns a lock, can acquire same lock multiple times. Here it is non-reentrant as given, process cant own same lock multiple times. So if a thread tries to acquire already owned lock, will get blocked, and this is a deadlock.
Hence correct answer is x=1, y=1.

44 A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x³ + x + 1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as

45 Let p, q, and r be propositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is

(p → q) → r is contradiction only when

P	q	r
T	T	F
F	T	F
F	F	F

And now for the above combination, the expression is always true when q is true. When q is false in the above combination (third one) will be false.

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 1

Follow Us :