GATE CSE 2015 Set 1 Question Paper with Solutions & Answer Key

Engineering Mathematics and Programming and Data Structures together made up 30 of 84 marks, up 3 from GATE CSE 2014 Set 1. 19 of 55 questions were NAT, the most since 2014. Programming in C was the heaviest single topic with 7 marks across 4 questions. Programming and Data Structures moved the most against GATE CSE 2014 Set 1: up 8 marks.

1. Q1 · MCQ · 1 mark · Software EngineeringMatch the following: (P) Condition coverage (i) Black-box testing (Q) Equivalence class partitioning (ii) System testing (R) Volume testing (iii) White-box testing (S) A…
2. Q2 · MCQ · 1 mark · Asymptotic AnalysisWhich one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n (≥ 2) numbers? In the recurrence equati…
3. Q3 · MCQ · 1 mark · Turing Machines and UndecidabilityFor any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. L1 (c…
4. Q4 · MCQ · 1 mark · Calculuslimx → ∞ x1/x is
5. Q5 · MCQ · 1 mark · CalculusIf g(x) = 1-x and h(x) = (x)/(x-1), then (g(h(x)))/(h(g(x))) is:
6. Q6 · MCQ · 1 mark · Algorithm Design TechniquesMatch the following: (P) Prim's algorithm for minimum spanning tree (Q) Floyd-Warshall algorithm for all pairs shortest paths (R) Mergesort (S) Hamiltonian circuit (i) B…
7. Q7 · MCQ · 1 mark · SQLSELECT operation in SQL is equivalent to
8. Q8 · MCQ · 1 mark · Instruction Set and Addressing ModesFor computers based on three-address instruction formats, each address field can be used to specify which of the following: (S1) A memory operand (S2) A processor regist…
9. Q9 · NAT · 1 mark · Concurrency and SynchronizationThe following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently. P1 ( ) { C = B - 1; B = 2 * C; } P2 ( ) { D = 2 * B; B = D…
10. Q10 · MCQ · 1 mark · Binary Search TreesWhich of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25 III. 2, 7, 10, 8, 14,…
11. Q11 · NAT · 1 mark · Programming in CThe output of the following C program is … void f1(int a, int b) { int c; c=a; a=b; b=c; } void f2(int *a, int *b) { int c; c=*a; *a=*b; *b=c; } int main(){ int a=4, b=5…
12. Q12 · NAT · 1 mark · Memory Management and Virtual MemoryConsider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the…
13. Q13 · MCQ · 1 mark · Lexical Analysis, Parsing and SDTWhich one of the following is TRUE at any valid state in shift-reduce parsing?
14. Q14 · MCQ · 1 mark · Propositional and First-Order LogicWhich one of the following is NOT equivalent to p ↔ q?
15. Q15 · MCQ · 1 mark · DNS and HTTPWhich of the following statements is/are FALSE? I. XML overcomes the limitations in HTML to support a structured way of organizing content. II. XML specification is not…
16. Q16 · MCQ · 1 mark · Discrete MathematicsFor a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}}, which of the following options are TRUE? I. ∅ ∈ 2A II. ∅ ⊆ 2A III. {5, {6}} ∈ 2A IV. {5, {6}} ⊆ 2A
17. Q17 · MCQ · 1 mark · DNS and HTTPIn one of the pairs of protocols given below, both the protocols can use multiple TCP connections between the same client and the server. Which one is that?
18. Q18 · NAT · 1 mark · Linear AlgebraIn the LU decomposition of the matrix 2 & 2 4 & 9 , if the diagonal elements of U are both 1, then the lower diagonal entry l22 of L is …
19. Q19 · MCQ · 1 mark · TCP Flow and Congestion ControlSuppose two hosts use a TCP connection to transfer a large file. Which of the following statements is/are FALSE with respect to the TCP connection? I. If the sequence nu…
20. Q20 · MCQ · 1 mark · Combinational and Sequential CircuitsConsider a 4-bit Johnson counter with an initial value of 0000. The counting sequence of this counter is
21. Q21 · MCQ · 1 mark · Switching and Performance MetricsSuppose that everyone in a group of N people wants to communicate secretly with the N-1 others using symmetric key cryptographic system. The communication between any tw…
22. Q22 · MCQ · 1 mark · IPv4, CIDR and NATWhich one of the following fields of an IP header is NOT modified by a typical IP router?
23. Q23 · MCQ · 1 mark · Binary Search TreesWhat are the worst-case complexities of insertion and deletion of a key in a binary search tree?
24. Q24 · MCQ · 1 mark · File Organization and IndexingA file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index. Then that index is called
25. Q25 · MCQ · 1 mark · TreesThe height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
26. Q26 · NAT · 1 mark · CalculusΣx=199 (1)/(x(x+1)) = …
27. Q27 · NAT · 2 marks · SQLConsider the following relations: Consider the following SQL query. SELECT S.StudentName, sum(P.Marks) FROM Student S, Performance P WHERE S.RollNo = P.RollNo GROUP BY S…
28. Q28 · MCQ · 2 marks · Propositional and First-Order LogicThe binary operator ≠ is defined by the following truth table. Which one of the following is true about the binary operator ≠?
29. Q29 · NAT · 2 marks · Data Link LayerConsider a LAN with four nodes S1, S2, S3 and S4. Time is divided into fixed-size slots, and a node can begin its transmission only at the beginning of a slot. A collisi…
30. Q30 · NAT · 2 marks · CPU and I/O SchedulingSuppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of…
31. Q31 · MCQ · 2 marks · Asymptotic AnalysisConsider the following C function. int fun1(int n) { int i,j,k,p,q=0; for (i=1; i 1; j=j/2) ++p; for (k=1; k Which one of the following most closely approximates the ret…
32. Q32 · MCQ · 2 marks · Binary HeapsConsider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
33. Q33 · MCQ · 2 marks · Programming in CConsider the following pseudo code, where x and y are positive integers. begin q := 0 r := x while r >= y do begin r := r - y q := q + 1 end end The post condition that…
34. Q34 · MCQ · 2 marks · Discrete MathematicsSuppose L = {p, q, r, s, t} is a lattice represented by the following Hasse diagram: For any x, y ∈ L, not necessarily distinct, x y and x y are join and meet of x, y, r…
35. Q35 · MCQ · 2 marks · Programming in CWhat is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory. int main () { unsigned int x[…
36. Q36 · MCQ · 2 marks · Linear AlgebraConsider the following 2 × 2 matrix A where two elements are unknown and are marked by a and b. The eigenvalues of this matrix are -1 and 7. What are the values of a and…
37. Q37 · MCQ · 2 marks · Combinational and Sequential CircuitsA positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flip-flop as follows. The Q output of the D flip-flop is connected to both the J and K…
38. Q38 · NAT · 2 marks · Instruction PipeliningConsider a non-pipelined processor with a clock rate of 2.5 gigahertz and average cycles per instruction of four. The same processor is upgraded to a pipelined processor…
39. Q39 · MCQ · 2 marks · Boolean Algebra and MinimizationConsider the operations f(X,Y,Z) = X'YZ + XY' + Y'Z' and g(X,Y,Z) = X'YZ + X'YZ' + XY. Which one of the following is correct?
40. Q40 · MCQ · 2 marks · Searching, Sorting and HashingAn algorithm performs (log N)1/2 find operations, N insert operations, (log N)1/2 delete operations, and (log N)1/2 decrease-key operations on a set of data items with k…
41. Q41 · NAT · 2 marks · ER ModelConsider an Entity-Relationship (ER) model in which entity sets E1 and E2 are connected by an m:n relationship R12. E1 and E3 are connected by a 1:n (1 on the side of E1…
42. Q42 · NAT · 2 marks · Programming in CConsider the following C program segment. while(first last) notPresent = TRUE; The cyclomatic complexity of the program segment is …
43. Q43 · NAT · 2 marks · Graph Traversals, MSTs and Shortest PathsThe graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E…
44. Q44 · NAT · 2 marks · Calculus1/ 2/ (cos(1/x))/(x2) dx = …
45. Q45 · MCQ · 2 marks · Graph TraversalsLet G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ∈ V, let d(x) denote the shortest distance in G from s to x. A b…
46. Q46 · NAT · 2 marks · CPU and I/O SchedulingConsider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at…
47. Q47 · MCQ · 2 marks · Memory Management and Virtual MemoryConsider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is tr…
48. Q48 · NAT · 2 marks · File SystemsConsider a disk pack with a seek time of 4 milliseconds and rotational speed of 10000 rotations per minute (RPM). It has 600 sectors per track and each sector can store…
49. Q49 · MCQ · 2 marks · CombinatoricsLet an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?
50. Q50 · MCQ · 2 marks · Data Flow AnalysesA variable x is said to be live at a statement Si in a program if the following three conditions hold simultaneously: i. There exists a statement Sj that uses x ii. Ther…
51. Q51 · MCQ · 2 marks · Context-Free Grammars and PDAsConsider the NPDA (Q = {q0, q1, q2}, = {0, 1}, = {0, 1, }, , q0, , F = {q2}), where (as per usual convention) Q is the set of states, is the input alphabet, is the stack…
52. Q52 · NAT · 2 marks · Regular Expressions and Finite AutomataConsider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is …
53. Q53 · NAT · 2 marks · Data Link LayerSuppose that the stop-and-wait protocol is used on a link with a bit rate of 64 kilobits per second and 20 milliseconds propagation delay. Assume that the transmission t…
54. Q54 · NAT · 2 marks · Graph TheoryLet G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is …
55. Q55 · NAT · 2 marks · Intermediate Code GenerationThe least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r / 3 + s - t * 5 + u * v / w is …

How many questions were in GATE CSE 2015 Set 1?

GATE CSE 2015 Set 1 had 55 questions for 84 marks: 36 MCQ, 0 MSQ and 19 NAT.

Which subject carried the most marks in GATE CSE 2015 Set 1?

Engineering Mathematics carried the most marks (18 of 84). The top three were Engineering Mathematics (18), Programming and Data Structures (12), Algorithms (10).

Where can I find the GATE CSE 2015 Set 1 answer key?

The answer key table on this page lists the answer to every question of GATE CSE 2015 Set 1. Open any question for its full verified solution.

Is the GATE CSE 2015 Set 1 paper useful for GATE 2027 preparation?

Yes. Solving past GATE CSE papers shows how marks are spread across subjects and which topics repeat. Compare it with other GATE CSE question papers and the topic-wise GATE CSE PYQs.

• GATE CSE 2015 Set 2 question paper
• GATE CSE 2015 Set 3 question paper
• GATE CSE 2014 Set 1 question paper
• GATE CSE 2016 Set 1 question paper
• All GATE CSE papers →
• GATE CSE Engineering Mathematics PYQs
• GATE CSE Programming and Data Structures PYQs
• GATE CSE Algorithms PYQs