Consider the two cascaded 2-to-1 multiplexers as shown in the figure. [figure] The minimal sum of products form of the output X is:

(D) \overline{Q}\overline{R}+PQR

(A) \overline{P}\overline{Q}+PQR

(C) PQ+\overline{P}Q\overline{R}

GATE 2016 CS (Set 1) question paper PDF and answer key

The official GATE 2016 Computer Science & Information Technology (Set 1) paper, organised by IISc Bengaluru: 65 questions for 100 marks in 3 hours. Download the official question paper and answer key as PDFs. Below is how the marks were split by topic, the complete official answer key and 5 questions solved step by step.

Take this paper as a timed test Try the free demo

Question paper (PDF)Official answer key (PDF)

Source: the official paper and answer key published by IISc Bengaluru for GATE 2016. Spotted a mistake? Email team@lemyte.com.

General Aptitude: 10 · 15 marks
Computer Science & Information Technology: 55 · 85 marks
MCQ / MSQ / NAT: 39 / 0 / 26
Marks to all: None

Not in 2027 2 questions (Q 18, 25) are on topics removed from the GATE 2027 syllabus. They are marked in the answer key below. What changed for CS

Where the marks were

GATE 2016 CS (Set 1) topic-wise marks

Computer Science & Information Technology questions only; General Aptitude adds 15 marks on top. The top three topics carried 29 of the 85 subject marks.

Topic	Questions	Marks
Computer Networks	6	10
Programming and Data Structures	6	10
Theory of Computation	6	9
Algorithms	6	9
Operating System	5	9
Discrete Mathematics	5	8
Compiler Design	5	8
Computer Organization and Architecture	4	6
Digital Logic	4	6
Databases	4	5
Probability and Statistics	2	3
Calculus	1	1
Linear Algebra	1	1

Free solved questions

5 solved questions from GATE 2016 CS (Set 1)

Question text and figures as in the official paper, the answer from the official key, and a worked solution. The other 60 solutions are in your report after you take the paper.

Q7 · General Aptitude · MCQ · 2 marks

f(x)=2x^7+3x-5,

which of the following is a factor of $f(x)$ ?

(A)
$(x^3+8)$
(B)
$(x-1)$
(C)
$(2x-5)$
(D)
$(x+1)$

Answer (official key): B

Solution

Use the factor theorem.

If $(x-1)$ is a factor, then:

f(1)=0.

Now,

f(1)=2(1)^7+3(1)-5 = 2+3-5 = 0.

Therefore, $(x-1)$ is a factor of $f(x)$ .

The correct answer is Option B.

Q8 · General Aptitude · MCQ · 2 marks

A shaving set company sells 4 different types of razors: Elegance, Smooth, Soft and Executive.

Elegance sells at Rs. 48, Smooth at Rs. 63, Soft at Rs. 78 and Executive at Rs. 173 per piece.

The table below shows the numbers of each razor sold in each quarter of a year.

Quarter	Elegance	Smooth	Soft	Executive
Q1	27300	20009	17602	9999
Q2	25222	19392	18445	8942
Q3	28976	22429	19544	10234
Q4	21012	18229	16595	10109

Which product contributes the greatest fraction to the revenue of the company in that year?

(A)
Elegance
(B)
Executive
(C)
Smooth
(D)
Soft

Answer (official key): B

Solution

Compute yearly revenue for each product.

Elegance:

(27300+25222+28976+21012)\times48 = 102510\times48 = 4920480.

Smooth:

(20009+19392+22429+18229)\times63 = 80059\times63 = 5043717.

Soft:

(17602+18445+19544+16595)\times78 = 72186\times78 = 5630508.

Executive:

(9999+8942+10234+10109)\times173 = 39284\times173 = 6796132.

Executive contributes the greatest revenue.

Therefore, the correct answer is Option B.

Q30 · Operating System · MCQ · 1 mark

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system.

Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

(A)
Shortest remaining time first
(B)
Round-robin with time quantum less than the shortest CPU burst
(C)
Uniform random
(D)
Highest priority first with priority proportional to CPU burst length

Answer (official key): A

Solution

When all processes arrive at the same time and CPU burst lengths are known, executing the shortest job first minimizes average waiting time.

Shortest Remaining Time First is the preemptive version of Shortest Job First. Since all processes are submitted at the same time, it behaves like shortest-job-first ordering.

Therefore, it minimizes the average waiting time.

The correct answer is Option A.

Q31 · Digital Logic · Numerical · 1 mark

We want to design a synchronous counter that counts the sequence:

0-1-0-2-0-3

and then repeats.

The minimum number of J-K flip-flops required to implement this counter is __________.

Answer (official key): 3 to 4

Solution

The output sequence is:

0,1,0,2,0,3

and then it repeats.

Although only the values 0, 1, 2 and 3 appear, the state corresponding to output 0 must occur in different positions of the cycle because it is followed by different next outputs: 1, 2 and 3.

So the counter requires 6 distinct states in the cycle.

The number of flip-flops required for 6 states is:

\lceil \log_2 6 \rceil = 3.

Therefore, the minimum required number of J-K flip-flops is 3.

The official accepted range is 3 to 4.

Q50 · Digital Logic · MCQ · 2 marks

Consider the two cascaded 2-to-1 multiplexers as shown in the figure.

Cascaded 2-to-1 multiplexers for Q30

The minimal sum of products form of the output $X$ is:

(A)
$\overline{P}\overline{Q}+PQR$
(B)
$P\overline{Q}+QR$
(C)
$PQ+\overline{P}Q\overline{R}$
(D)
$\overline{Q}\overline{R}+PQR$

Answer (official key): D

Solution

Trace the two multiplexers from the given figure.

The output is 1 in the following cases:

$Q=0$ and $R=0$ , giving the term:

\overline{Q}\overline{R}

$P=1$ , $Q=1$ , and $R=1$ , giving the term:

PQR.

Therefore, the minimal sum of products form is:

X=\overline{Q}\overline{R}+PQR.

The correct answer is Option D.

The other 60 questions are solved in your report when you take GATE 2016 CS (Set 1) as a 3-hour test.

Take GATE 2016 CS (Set 1) as a test

Official answer key

GATE 2016 CS (Set 1) answer key

All 65 answers from the official key. Numerical answers are ranges; “or” means the key accepts either answer.

Download the official GATE 2016 CS (Set 1) answer key (PDF)

Q	Topic	Type	Marks	Answer
1	Verbal Aptitude	MCQ	1	A
2	Spatial Aptitude	MCQ	1	D
3	Verbal Aptitude	MCQ	1	A
4	Analytical Aptitude	MCQ	1	A
5	Verbal Aptitude	MCQ	1	D
6	Quantitative Aptitude	MCQ	2	B
7	Quantitative Aptitude	MCQ	2	B
8	Quantitative Aptitude	MCQ	2	B
9	Analytical Aptitude	MCQ	2	D
10	Verbal Aptitude	MCQ	2	D
11	Databases	MCQ	1	B
12	Theory of Computation	MCQ	1	D
13	Databases	MCQ	1	B
14	Algorithms	MCQ	1	D
15	Algorithms	MCQ	1	A
16	Discrete Mathematics	MCQ	1	B
17	Theory of Computation	MCQ	1	C
18	Computer NetworksNot in GATE 2027 syllabus: SMTP, FTP and e-mail protocols	MCQ	1	C
19	Calculus	Numerical	1	1
20	Theory of Computation	MCQ	1	B
21	Algorithms	Numerical	1	6
22	Computer Organization and Architecture	Numerical	1	-11
23	Programming and Data Structures	Numerical	1	2016
24	Digital Logic	MCQ	1	A
25	Computer NetworksNot in GATE 2027 syllabus: ARP, DHCP and ICMP	MCQ	1	C
26	Compiler Design	MCQ	1	D
27	Compiler Design	Numerical	1	10
28	Computer Organization and Architecture	Numerical	1	31
29	Linear Algebra	Numerical	1	15
30	Operating System	MCQ	1	A
31	Digital Logic	Numerical	1	3 to 4
32	Programming and Data Structures	MCQ	1	A
33	Discrete Mathematics	Numerical	1	11
34	Probability and Statistics	Numerical	1	0.5
35	Databases	MCQ	1	D
36	Programming and Data Structures	MCQ	2	D
37	Digital Logic	MCQ	2	B
38	Compiler Design	MCQ	2	D
39	Programming and Data Structures	Numerical	2	256
40	Discrete Mathematics	Numerical	2	10
41	Computer Organization and Architecture	Numerical	2	33 to 34
42	Probability and Statistics	Numerical	2	0.33 to 0.34
43	Computer Organization and Architecture	Numerical	2	456
44	Discrete Mathematics	Numerical	2	197.9 to 198.1
45	Algorithms	Numerical	2	12
46	Discrete Mathematics	Numerical	2	2
47	Algorithms	Numerical	2	7
48	Theory of Computation	MCQ	2	D
49	Algorithms	MCQ	2	B
50	Digital Logic	MCQ	2	D
51	Programming and Data Structures	MCQ	2	B
52	Programming and Data Structures	MCQ	2	A
53	Databases	MCQ	2	A
54	Operating System	Numerical	2	1
55	Theory of Computation	MCQ	2	C
56	Compiler Design	Numerical	2	9
57	Computer Networks	Numerical	2	2500
58	Computer Networks	MCQ	2	B
59	Computer Networks	Numerical	2	13
60	Computer Networks	Numerical	2	1.1
61	Theory of Computation	MCQ	2	D
62	Operating System	MCQ	2	A
63	Compiler Design	MCQ	2	C
64	Operating System	Numerical	2	346
65	Operating System	Numerical	2	384

Questions about GATE 2016 CS (Set 1)

How many questions are in the GATE 2016 CS (Set 1) paper?

65 questions for 100 marks: 10 General Aptitude questions worth 15 marks and 55 Computer Science & Information Technology questions worth 85 marks. By type, there were 39 MCQs, 26 numerical answer (NAT) questions. The paper lasted 3 hours.

Is there negative marking in GATE 2016 CS (Set 1)?

Yes, for MCQs only. A wrong MCQ answer costs one-third of its marks (−⅓ for a 1-mark question, −⅔ for a 2-mark question). MSQ and numerical (NAT) questions have no negative marking, and an MSQ earns marks only when every correct option is chosen.

Which topics carried the most marks in GATE 2016 CS (Set 1)?

Outside General Aptitude, the biggest topics were Computer Networks (10 marks), Programming and Data Structures (10 marks), Theory of Computation (9 marks). The full topic-wise split is in the table on this page.

Were any GATE 2016 CS (Set 1) questions awarded marks to all?

No. Every question was graded with the answer in the official key.

Where does this GATE 2016 CS (Set 1) answer key come from?

From the official answer key published by IISc Bengaluru, which organised GATE 2016. Range answers for numerical questions and questions with more than one accepted answer are kept exactly as the key gives them.

GATE 2016 CS (Set 1) question paper PDF and answer key

GATE 2016 CS (Set 1) topic-wise marks

5 solved questions from GATE 2016 CS (Set 1)

GATE 2016 CS (Set 1) answer key

Questions about GATE 2016 CS (Set 1)

How many questions are in the GATE 2016 CS (Set 1) paper?

Is there negative marking in GATE 2016 CS (Set 1)?

Which topics carried the most marks in GATE 2016 CS (Set 1)?

Were any GATE 2016 CS (Set 1) questions awarded marks to all?

Where does this GATE 2016 CS (Set 1) answer key come from?

More GATE papers