GATE 2023 Computer Science and Information Technology (CS) PDF

Computer Science and Information Technology (CS) General Aptitude (GA) Q.1 – Q.5 Carry ONE mark Each Q.1 We reached the station late, and _______ missed the train. (A) near (B) nearly (C) utterly (D) mostly Q.2 Kind : _______ : : Often : Frequently (By word meaning) (A) Mean (B) Type (C) Cruel (D) Kindly Page 1 of 7 Organizing Institute: IIT Kanpur Computer Science and Information Technology (CS) Q.3 A series of natural numbers 𝐹1 , 𝐹2 , 𝐹3 , 𝐹4 , 𝐹5 , 𝐹6 , 𝐹7 , … obeys 𝐹𝑛+1 = 𝐹𝑛 + 𝐹𝑛−1 for all integers 𝑛 ≥ 2. If 𝐹6 = 37, and 𝐹7 = 60, then what is 𝐹1 ? (A) 4 (B) 5 (C) 8 (D) 9 Page 2 of 7 Organizing Institute: IIT Kanpur Computer Science and Information Technology (CS) Q.4 A survey for a certain year found that 90% of pregnant women received medical care at least once before giving birth. Of these women, 60% received medical care from doctors, while 40% received medical care from other healthcare providers. Given this information, which one of the following statements can be inferred with certainty? (A) More than half of the pregnant women received medical care at least once from a doctor. (B) Less than half of the pregnant women received medical care at least once from a doctor. (C) More than half of the pregnant women received medical care at most once from a doctor. (D) Less than half of the pregnant women received medical care at most once from a doctor. Q.5 Looking at the surface of a smooth 3-dimensional object from the outside, which one of the following options is TRUE? (A) The surface of the object must be concave everywhere. (B) The surface of the object must be convex everywhere. (C) The surface of the object may be concave in some places and convex in other places. (D) The object can have edges, but no corners. Page 3 of 7 Organizing Institute: IIT Kanpur Computer Science and Information Technology (CS) Q.6 – Q.10 Carry TWO marks Each Q.6 The country of Zombieland is in distress since more than 75% of its working population is suffering from serious health issues. Studies conducted by competent health experts concluded that a complete lack of physical exercise among its working population was one of the leading causes of their health issues. As one of the measures to address the problem, the Government of Zombieland has decided to provide monetary incentives to those who ride bicycles to work. Based only on the information provided above, which one of the following statements can be logically inferred with certainty? (A) All the working population of Zombieland will henceforth ride bicycles to work. (B) Riding bicycles will ensure that all of the working population of Zombieland is free of health issues. (C) The health experts suggested to the Government of Zombieland to declare riding bicycles as mandatory. (D) The Government of Zombieland believes that riding bicycles is a form of physical exercise. Page 4 of 7 Organizing Institute: IIT Kanpur Computer Science and Information Technology (CS) Q.7 Consider two functions of time (𝑡), 𝑓(𝑡) = 0.01 𝑡 2 𝑔(𝑡) = 4 𝑡 where 0 < 𝑡 < ∞. Now consider the following two statements: (i) For some 𝑡 > 0, 𝑔(𝑡) > 𝑓(𝑡). (ii) There exists a 𝑇, such that 𝑓(𝑡) > 𝑔(𝑡) for all 𝑡 > 𝑇. Which one of the following options is TRUE? (A) only (i) is correct (B) only (ii) is correct (C) both (i) and (ii) are correct (D) neither (i) nor (ii) is correct Page 5 of 7 Organizing Institute: IIT Kanpur Computer Science and Information Technology (CS) Q.8 Which one of the following sentence sequences creates a coherent narrative? (i) Once on the terrace, on her way to her small room in the corner, she notices the man right away. (ii) She begins to pant by the time she has climbed all the stairs. (iii) Mina has bought vegetables and rice at the market, so her bags are heavy. (iv) He was leaning against the parapet, watching the traffic below. (A) (i), (ii), (iv), (iii) (B) (ii), (iii), (i), (iv) (C) (iv), (ii), (i), (iii) (D) (iii), (ii), (i), (iv) Q.9 f ( x ) and g ( y ) are functions of x and y, respectively, and f ( x ) = g ( y ) for all real values of 𝑥 and 𝑦. Which one of the following options is necessarily TRUE for all x and y? (A) f ( x ) = 0 and g ( y ) = 0 (B) f ( x ) = g ( y ) = constant (C) f ( x )  constant and g ( y )  constant (D) f ( x) + g ( y ) = f ( x) − g ( y ) Page 6 of 7 Organizing Institute: IIT Kanpur Computer Science and Information Technology (CS) Q.10 Which one of the options best describes the transformation of the 2-dimensional figure P to Q, and then to R, as shown? (A) Operation 1: A clockwise rotation by 90º about an axis perpendicular to the plane of the figure Operation 2: A reflection along a horizontal line (B) Operation 1: A counter clockwise rotation by 90º about an axis perpendicular to the plane of the figure Operation 2: A reflection along a horizontal line (C) Operation 1: A clockwise rotation by 90º about an axis perpendicular to the plane of the figure Operation 2: A reflection along a vertical line (D) Operation 1: A counter clockwise rotation by 180º about an axis perpendicular to the plane of the figure Operation 2: A reflection along a vertical line Page 7 of 7 Organizing Institute: IIT Kanpur GATE 2023 Computer Science and Information Technology (CS) Q.11 – Q.35 Carry ONE mark each. Q.11 Consider the following statements regarding the front-end and back-end of a compiler. S1: The front-end includes phases that are independent of the target hardware. S2: The back-end includes phases that are speciﬁc to the target hardware. S3: The back-end includes phases that are speciﬁc to the programming language used in the source code. Identify the CORRECT option. (A) Only S1 is TRUE. (B) Only S1 and S2 are TRUE. (C) S1, S2, and S3 are all TRUE. (D) Only S1 and S3 are TRUE. CS Page 1 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.12 Which one of the following sequences when stored in an array at locations A,... , A forms a max-heap? (A) 23, 17, 10, 6, 13, 14, 1, 5, 7, 12 (B) 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 (C) 23, 17, 14, 6, 13, 10, 1, 5, 7, 15 (D) 23, 14, 17, 1, 10, 13, 16, 12, 7, 5 CS Page 2 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.13 Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel? (A) SLLdel is O(1) and DLLdel is O(n) (B) Both SLLdel and DLLdel are O(log(n)) (C) Both SLLdel and DLLdel are O(1) (D) SLLdel is O(n) and DLLdel is O(1) CS Page 3 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.14 Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s, p, q, r}, with s being the start state and p being the only ﬁnal state. 0 1 1 s p q 1 0 0 r 0,1 Which one of the following regular expressions correctly describes the language accepted by A? (A) 1(0∗ 11)∗ (B) 0(0 + 1)∗ (C) 1(0 + 11)∗ (D) 1(110∗ )∗ CS Page 4 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.15 The Lucas sequence Ln is deﬁned by the recurrence relation: Ln = Ln−1 + Ln−2 , for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE? √ n √ n 1+ 5 1− 5 (A) Ln = + 2 2 √ n √ n 1+ 5 1− 5 (B) Ln = − 2 3 √ n √ n 1+ 5 1− 5 (C) Ln = + 2 3 √ n √ n 1+ 5 1− 5 (D) Ln = − 2 2 CS Page 5 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.16 Which one of the options given below refers to the degree (or arity) of a relation in relational database systems? (A) Number of attributes of its relation schema. (B) Number of tuples stored in the relation. (C) Number of entries in the relation. (D) Number of distinct domains of its relation schema. CS Page 6 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.17 Suppose two hosts are connected by a point-to-point link and they are conﬁgured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest. (A) Longer link length and lower transmission rate (B) Longer link length and higher transmission rate (C) Shorter link length and lower transmission rate (D) Shorter link length and higher transmission rate CS Page 7 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.18 Let ⎡ ⎤ 1 2 3 4 ⎢4 1 2 3⎥ A=⎢ ⎣3 ⎥ 4 1 2⎦ 2 3 4 1 and ⎡ ⎤ 3 4 1 2 ⎢4 1 2 3⎥ B=⎢ ⎣1 ⎥. 2 3 4⎦ 2 3 4 1 Let det(A) and det(B) denote the determinants of the matrices A and B, respectively. Which one of the options given below is TRUE? (A) det(A) = det(B) (B) det(B) = −det(A) (C) det(A) = 0 (D) det(AB) = det(A) + det(B) CS Page 8 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.19 Consider the following deﬁnition of a lexical token id for an identiﬁer in a program- ming language, using extended regular expressions: letter → [A-Za-z] digit → [0-9] id → letter (letter | digit)∗ Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identiﬁers? (A double-circle denotes a ﬁnal state) letter letter digit (A) letter letter digit (B) letter letter digit (C) letter letter digit (D) CS Page 9 of 83 GATE 2023 Computer Science and Information Technology (CS) CS Page 10 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.20 An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k > m. Which one of the following is the best hashing strategy to counteract the adversary? (A) Division method, i.e., use the hash function h(k) = k mod m. (B) Multiplication method, i.e., use the hash function h(k) = m(kA − kA), where A is a carefully chosen constant. (C) Universal hashing method. (D) If k is a prime number, use Division method. Otherwise, use Multiplication method. CS Page 11 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.21 The output of a 2-input multiplexer is connected back to one of its inputs as shown in the ﬁgure. Multiplexer 0 Q 1 S Match the functional equivalence of this circuit to one of the following options. (A) D Flip-ﬂop (B) D Latch (C) Half-adder (D) Demultiplexer CS Page 12 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.22 Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process? (A) Page table base register (B) Stack pointer (C) Program counter (D) General purpose registers CS Page 13 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.23 Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode? (A) Function Call (B) malloc Call (C) Page Fault (D) System Call CS Page 14 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.24 Which of the following statements is/are CORRECT? (A) The intersection of two regular languages is regular. (B) The intersection of two context-free languages is context-free. (C) The intersection of two recursive languages is recursive. (D) The intersection of two recursively enumerable languages is recursively enumerable. CS Page 15 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.25 Which of the following statements is/are INCORRECT about the OSPF (Open Shortest Path First) routing protocol used in the Internet? (A) OSPF implements Bellman-Ford algorithm to ﬁnd shortest paths. (B) OSPF uses Dijkstra’s shortest path algorithm to implement least-cost path routing. (C) OSPF is used as an inter-domain routing protocol. (D) OSPF implements hierarchical routing. CS Page 16 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.26 Geetha has a conjecture about integers, which is of the form ∀x P (x) =⇒ ∃yQ(x, y) , where P is a statement about integers, and Q is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha’s conjecture? (A) ∃x P (x) ∧ ∀yQ(x, y) (B) ∀x∀yQ(x, y) (C) ∃y∀x P (x) =⇒ Q(x, y) (D) ∃x P (x) ∧ ∃yQ(x, y) CS Page 17 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.27 Which one or more of the following CPU scheduling algorithms can potentially cause starvation? (A) First-in First-Out (B) Round Robin (C) Priority Scheduling (D) Shortest Job First CS Page 18 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.28 Let f (x) = x3 + 15x2 − 33x − 36 be a real-valued function. Which of the following statements is/are TRUE? (A) f (x) does not have a local maximum. (B) f (x) has a local maximum. (C) f (x) does not have a local minimum. (D) f (x) has a local minimum. CS Page 19 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.29 Let f and g be functions of natural numbers given by f (n) = n and g(n) = n2. Which of the following statements is/are TRUE? (A) f ∈ O(g) (B) f ∈ Ω(g) (C) f ∈ o(g) (D) f ∈ Θ(g) CS Page 20 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.30 Let A be the adjacency matrix of the graph with vertices {1, 2, 3, 4, 5}. 3 5 2 1 4 Let λ1 , λ2 , λ3 , λ4 , and λ5 be the ﬁve eigenvalues of A. Note that these eigenvalues need not be distinct. The value of λ1 + λ2 + λ3 + λ4 + λ5 =. CS Page 21 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.31 The value of the deﬁnite integral 3 2 1 4x2 y − z 3 dz dy dx −3 −2 −1 is. (Rounded oﬀ to the nearest integer) CS Page 22 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.32 A particular number is written as 132 in radix-4 representation. The same number in radix-5 representation is. CS Page 23 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.33 Consider a 3-stage pipelined processor having a delay of 10 ns (nanoseconds), 20 ns, and 14 ns, for the ﬁrst, second, and the third stages, respectively. Assume that there is no other delay and the processor does not suﬀer from any pipeline hazards. Also assume that one instruction is fetched every cycle. The total execution time for executing 100 instructions on this processor is ns. CS Page 24 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.34 A keyboard connected to a computer is used at a rate of 1 keystroke per second. The computer system polls the keyboard every 10 ms (milli seconds) to check for a keystroke and consumes 100 μs (micro seconds) for each poll. If it is determined after polling that a key has been pressed, the system consumes an additional 200 μs to process the keystroke. Let T1 denote the fraction of a second spent in polling and processing a keystroke. In an alternative implementation, the system uses interrupts instead of polling. An interrupt is raised for every keystroke. It takes a total of 1 ms for servicing an interrupt and processing a keystroke. Let T2 denote the fraction of a second spent in servicing the interrupt and processing a keystroke. T1 The ratio is. (Rounded oﬀ to one decimal place) T2 CS Page 25 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.35 The integer value printed by the ANSI-C program given below is. #include int funcp(){ static int x = 1; x++; return x; } int main(){ int x,y; x = funcp(); y = funcp()+x; printf("%d\n", (x+y)); return 0; } CS Page 26 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.36 – Q.65 Carry TWO mark each. CS Page 27 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.36 Consider the following program: int main() int f1() int f2(int X) int f3() { { { { f1(); return(1); f3(); return(5); f2(2); } if (X==1) } f3(); return f1(); return(0); else } return (X*f2(X-1)); } Which one of the following options represents the activation tree corresponding to the main function? main f1 f2 f3 f3 f2 (A) f3 f1 main f1 f2 f3 (B) f3 f1 main f1 f2 (C) f3 f1 main f1 f2 f3 (D) f3 f2 f1 CS Page 28 of 83 GATE 2023 Computer Science and Information Technology (CS) CS Page 29 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.37 Consider the control ﬂow graph shown. ENTRY B1 i = m − 1 j = n a = 10 B2 i = i + 1 j = j − 1 B3 a = 20 B4 i = a + 1 EXIT Which one of the following choices correctly lists the set of live variables at the exit point of each basic block? (A) B1: {}, B2: {a}, B3: {a}, B4: {a} (B) B1: {i, j}, B2: {a}, B3: {a}, B4: {i} (C) B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a} (D) B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j} CS Page 30 of 83 GATE 2023 Computer Science and Information Technology (CS) CS Page 31 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.38 Consider the two functions incr and decr shown below. incr(){ decr(){ wait(s); wait(s); X = X+1; X = X-1; signal(s); signal(s); } } There are 5 threads each invoking incr once, and 3 threads each invoking decr once, on the same shared variable X. The initial value of X is 10. Suppose there are two implementations of the semaphore s, as follows: I-1: s is a binary semaphore initialized to 1. I-2: s is a counting semaphore initialized to 2. Let V1, V2 be the values of X at the end of execution of all the threads with implementations I-1, I-2, respectively. Which one of the following choices corresponds to the minimum possible values of V1, V2, respectively? (A) 15, 7 (B) 7, 7 (C) 12, 7 (D) 12, 8 CS Page 32 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.39 Consider the context-free grammar G below S → aSb | X X → aX | Xb | a | b , where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of the following statements is CORRECT? (A) The language generated by G is (a + b)∗ (B) The language generated by G is a∗ (a + b)b∗ (C) The language generated by G is a∗ b∗ (a + b) (D) The language generated by G is not a regular language CS Page 33 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.40 Consider the pushdown automaton (PDA) P below, which runs on the input alpha- bet {a, b}, has stack alphabet {⊥, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/γ, where c is an input symbol or , X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v. In the initial conﬁguration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack. a/⊥/A⊥ a/A/AA b/A/ b/A/ s p /A/ /A/ q /A/ /⊥/ Which one of the following options correctly describes the language accepted by P ? (A) {am bn | 1 ≤ m and n < m} (B) {am bn | 0 ≤ n ≤ m} (C) {am bn | 0 ≤ m and 0 ≤ n} (D) {am | 0 ≤ m} ∪ {bn | 0 ≤ n} CS Page 34 of 83 GATE 2023 Computer Science and Information Technology (CS) Q.41 Consider the given C-code and its corresponding assembly code, with a few operands U1–U4 being unknown. Some useful information as well as the semantics of each unique assembly instruction is annotated as inline comments in the code. The memory is byte-addressable. //C-code ;assembly-code (; indicates comments) ;r1-r5 are 32-bit integer registers ;initialize r1=0, r2=10 ;initialize r3, r4 with base address of a, b int a, b, i; L01: jeq r1, r2, end ;if(r1==r2) goto end // int is 32-bit L02: lw r5, 0(r4) ;r5

GATE 2023 Computer Science and Information Technology (CS) PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue