GATE CS 2017 (Forenoon)

65 questions · 100 marks · 180 minutes

Take this paper as a timed test
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.

MATHEMATICAL FOUNDATIONS

  1. Q1The statement ( p) ( q) is logically equivalent to which of the statements below? I. p q II. q p III. ( q) p IV. ( p) qDiscrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  2. Q2Consider the first-order logic sentence F : x( y R(x, y)). Assuming non-empty logical domains, which of the sentences below are implied by F? I. y( x R(x, y)) II. y( x R(x, y)) II…Discrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 1 mark
  3. Q3Let c 1 c n be scalars, not all zero, such that i=1 n c i a i = 0 where a i are column vectors in R n. Consider the set of linear equations Ax = b where A = [a 1 a n] and b = i=1…Linear Algebra · Matrices, Determinants, & Linear Equation Systems · MCQ · 1 mark
  4. Q19Let X be a Gaussian random variable with mean 0 and variance 2. Let Y = (X, 0) where (a, b) is the maximum of a and b. The median of Y is .Probability & Statistics · Continuous/Discrete Distributions (Uniform, Normal, Exponential) · NAT · 1 mark
  5. Q20Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is .Discrete Mathematics · Graph Theory (Connectivity, Paths, Cycles, Trees) · NAT · 1 mark
  6. Q28The value of x 1 x 7 - 2x 5 + 1 x 3 - 3x 2 + 2Calculus · Limits, Continuity, and Differentiability · MCQ · 2 marks
  7. Q29Let p, q and r be propositions and the expression (p q) r be a contradiction. Then, the expression (r p) q isDiscrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 2 marks
  8. Q30Let u and v be two vectors in R 2 whose Euclidean norms satisfy u = 2 v . What is the value of such that w = u + v bisects the angle between u and v?Linear Algebra · Matrices, Determinants, & Linear Equation Systems · MCQ · 2 marks
  9. Q31Let A be n n real valued square symmetric matrix of rank 2 with i=1 n j=1 n A ij 2 = 50. Consider the following statements. I. One eigenvalue must be in [-5, 5] II. The eigenvalue…Linear Algebra · Eigenvalues and Eigenvectors · MCQ · 2 marks
  10. Q47The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is .Discrete Mathematics · Combinatorics (Counting Rules, Summation Formulas) · NAT · 2 marks

CORE CS

  1. Q4Consider the following functions from positive integers to real numbers: 10, n , n, 2 n, 100 n The CORRECT arrangement of the above functions in increasing order of asymptotic com…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 1 mark
  2. Q5Consider the following table: Match the algorithms to the design paradigms they are based on.Algorithms · Greedy Approach & Divide-and-Conquer Designs · MCQ · 1 mark
  3. Q6Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: Note: The height of a tree with a single node is 0.Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 1 mark
  4. Q7The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n - f. The range of decimal values for X in this representation isDigital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 1 mark
  5. Q8Consider the C code fragment given below. c typedef struct node int data; node next; node; void join (node m, node n) node p = n; while (p -> next != NULL) p = p -> next; p -> nex…Data Structures · Linked Lists & Binary Trees · MCQ · 1 mark
  6. Q9When two 8-bit numbers A 7 A 0 and B 7 B 0 in 2's complement representation (with A 0 and B 0 as the least significant bits) are added using a ripple-carry adder, the sum bits obt…Digital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 1 mark
  7. Q10Consider the following context-free grammar over the alphabet = \ a, b, c\ with S as the start symbol: S abScT abcT T bT b Which one of the following represents the language gener…Theory of Computation (TOC) · Context-Free Grammars & Push-Down Automata · MCQ · 1 mark
  8. Q11Consider the C struct defined below: c struct data int marks [100]; char grade; int cnumber; ; struct data student; The base address of student is available in register R1. The fi…Computer Organization and Architecture (COA) · Machine Instructions & Addressing Modes · MCQ · 1 mark
  9. Q12Consider the following intermediate program in three address code p = a - b q = p c p = u v q = p + q Which one of the following corresponds to a static single assignment form of…Compiler Design · Intermediate Code Generation & Local Code Optimization · MCQ · 1 mark
  10. Q13Consider the following C code: c include <stdio.h> int assignval (int x, int val) x = val; return x; void main ( ) int x = malloc (sizeof(int)); if (NULL == x) return; x = assignv…Programming in C · Dynamic Memory Allocation & File Handling · MCQ · 1 mark
  11. Q14Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segment…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · MCQ · 1 mark
  12. Q15A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place.…Computer Networks (CN) · Application Layer (DNS, SMTP, HTTP, FTP, Email) & Security · MCQ · 1 mark
  13. Q16The following functional dependencies hold true for the relational schema R V, W, X, Y, Z : V W VW X Y VX Y Z Which of the following is irreducible equivalent for this set of func…Database Management Systems (DBMS) · Integrity Constraints & Functional Dependencies · MCQ · 1 mark
  14. Q17Consider the following grammar: P xQRS Q yz z R w S y What is FOLLOW (Q)?Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 1 mark
  15. Q18Threads of a process shareOperating Systems (OS) · System Calls, Processes, Threads, InterProcess Communication · MCQ · 1 mark
  16. Q21Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. Assume for all inputs (a, b, c, d), the respective complements ( a , b , c , d ) are…Digital Logic · Boolean Algebra, Minimization, K-Maps · NAT · 1 mark
  17. Q22Consider the language L given by the regular expression (a + b) b (a + b) over the alphabet \ a, b\ . The smallest number of states needed in a deterministic finite-state automato…Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · NAT · 1 mark
  18. Q23Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below: EMP sql SELECT AVG(EC.Num…Database Management Systems (DBMS) · SQL Queries (DDL/DML, Joins, Aggregations) · NAT · 1 mark
  19. Q24Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: If the pre-emptive shortest remaining time fir…Operating Systems (OS) · CPU and I/O Scheduling · NAT · 1 mark
  20. Q25Consider a two-level cache hierarchy with L 1 and L 2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L 1 cach…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 1 mark
  21. Q26Let 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 Tre…Algorithms · Minimum Spanning Trees (Prim/Kruskal Algorithms) · MCQ · 2 marks
  22. Q27A 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 p…Operating Systems (OS) · Concurrency & Synchronization (Semaphores, Mutex, Monitors, Locks) · MCQ · 2 marks
  23. Q32A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x 3 + x + 1 as the generator polynomial to generate the check bits. In t…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · MCQ · 2 marks
  24. Q33Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flop is connected to the input of the T flip-flop and the output of the T flip-flop…Digital Logic · Sequential Circuits (Flip-Flops, Registers, Counters) · MCQ · 2 marks
  25. Q34If G is a grammar with productions S SaS aSb bSa SS where S is the start variable, then which one of the following strings is not generated by G?Theory of Computation (TOC) · Context-Free Grammars & Push-Down Automata · MCQ · 2 marks
  26. Q35Consider the following two functions: c void fun1 (int n) if (n == 0) return; printf ("%d", n); fun2 (n - 2); printf ("%d", n); void fun2 (int n) if (n == 0) return; printf ("%d",…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · MCQ · 2 marks
  27. Q36Consider the C functions foo and bar given below: c int foo (int val) int x = 0; while (val > 0) x = x + foo (val --); return val; int bar (int val) int x = 0; while (val > 0) x =…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · MCQ · 2 marks
  28. Q37Consider the context-free grammars over the alphabet \ a, b, c\ given below. S and T are non-terminals. G 1 : S aSb T, T cT G 2 : S bSa T, T cT The language L(G 1) L(G 2) isTheory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
  29. Q38Consider the following languages over the alphabet = \ a, b, c\ . Let L 1 = \ a n b n c m m, n 0\ and L 2 = \ a m b n c n m, n 0\ . Which of the following are context-free languag…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
  30. Q39Let A and B be finite alphabets and let be a symbol outside both A and B. Let f be a total function from A to B . We say f is computable if there exists a Turing machine M which g…Theory of Computation (TOC) · Turing Machines & Undecidability · MCQ · 2 marks
  31. Q40Recall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements: S1: Random page replacem…Operating Systems (OS) · Memory Management and Virtual Memory · MCQ · 2 marks
  32. Q41Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId) and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Con…Database Management Systems (DBMS) · Relational Models, Relational Algebra, Tuple Calculus · MCQ · 2 marks
  33. Q42In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let TS(T 1) and TS(T 2) be the timestamps of transactions T 1 and T 2 respe…Database Management Systems (DBMS) · Transactions, Concurrency Control, Conflict Serializability · MCQ · 2 marks
  34. Q43Consider the following grammar: stmt if expr then expr else expr ; stmt 0 expr term relop term term term id number id a b c number [0-9] where relop is a relational operator (e.g.…Theory of Computation (TOC) · Context-Free Grammars & Push-Down Automata · NAT · 2 marks
  35. Q44In a RSA cryptosystem, a participant A uses two prime numbers p = 13 and q = 17 to generate her public and private keys. If the public key of A is 35, then the private key of A is…Computer Networks (CN) · Application Layer (DNS, SMTP, HTTP, FTP, Email) & Security · NAT · 2 marks
  36. Q45The values of parameters for the Stop-and-Wait ARQ protocol are as given below: Bit rate of the transmission channel = 1 Mbps. Propagation delay from sender to receiver = 0.75 ms.…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · NAT · 2 marks
  37. Q46Consider a database that has the relation schema CR( StudentName, CourseName). An instance of the schema CR is as given below: The following query is made on the database. T 1 Cou…Database Management Systems (DBMS) · Relational Models, Relational Algebra, Tuple Calculus · NAT · 2 marks
  38. Q48Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index i such that A[i] is 1 by probing the minim…Algorithms · Searching, Sorting, Hashing Mechanisms · NAT · 2 marks
  39. Q49Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified in…Computer Organization and Architecture (COA) · Machine Instructions & Addressing Modes · NAT · 2 marks
  40. Q50Instruction execution in a processor is divided into 5 stages. Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX) and Write Back (WB). These stages…Computer Organization and Architecture (COA) · Instruction Pipelining, Performance, Hazard Management · NAT · 2 marks
  41. Q51Consider a 2-way set associative cache with 256 blocks and uses LRU replacement. Initially the cache is empty. Conflict misses are those misses which occur due to contention of mu…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 2 marks
  42. Q52Consider the expression (a - 1) (((b + c)/3) + d). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a loa…Compiler Design · Intermediate Code Generation & Local Code Optimization · NAT · 2 marks
  43. Q53Consider the following C program. c include <stdio.h> include <string.h> void printlength (char s, char t) unsigned int c = 0; int len = ((strlen(s) - strlen(t)) > c) ? strlen(s):…Programming in C · Data Types, Syntax, Control Structures, Loops · NAT · 2 marks
  44. Q54A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If th…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 2 marks
  45. Q55The output of executing the following C program is . c include <stdio.h> int total (int v) static int count = 0; while (v) count += v & 1; v >>= 1; return count; void main ( ) sta…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 2 marks

GENERAL APTITUDE (GA)

  1. Q56After Rajendra Chola returned from his voyage to Indonesia, he to visit the temple in Thanjavur.Verbal Aptitude · Basic English Grammar (Tenses, Articles, Adjectives) · MCQ · 1 mark
  2. Q57Research in the workplace reveals that people work for many reasons .Verbal Aptitude · Grammar Rules (Prepositions, Conjunctions, Verb-Noun Agreement, Other Parts of Speech) · MCQ · 1 mark
  3. Q58Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul. Which of the following pairs a…Analytical Aptitude · Operational Puzzles and Systemic Reasoning · MCQ · 1 mark
  4. Q59Find the smallest number y such that that y 162 is a perfect cube.Quantitative Aptitude · Mathematical Operations (Powers, Exponents, Logarithms) · MCQ · 1 mark
  5. Q60The probability that a k-digit number does NOT contain the digits 0, 5 or 9 isQuantitative Aptitude · Elementary Statistics and Probability · MCQ · 1 mark
  6. Q61"The hold of the nationalist imagination on our colonial past is such that anything inadequately or improperly nationalist is just not history." Which of the following statements…Verbal Aptitude · Reading Comprehension · MCQ · 2 marks
  7. Q62Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her…Analytical Aptitude · Operational Puzzles and Systemic Reasoning · MCQ · 2 marks
  8. Q63The expression (x+y)- x-y 2 is equal toAnalytical Aptitude · Numerical Relations & Arithmetic Logic · MCQ · 2 marks
  9. Q64Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislike…Quantitative Aptitude · Combinatorics Core (Permutations, Combinations, Series) · MCQ · 2 marks
  10. Q65A contour line joins locations having the same height above the mean sea level. The following is a contour plot of a geographical region. Contour lines are shown at 25 m intervals…Quantitative Aptitude · Graphical Representations (2D and 3D Plots, Maps, Tables) · MCQ · 2 marks