Computer Science Gate 2020 Questions

Two straight lines are drawn perpendicular to each other in X−Y plane. If α and β are the acute angles the straight lines make with the X- axis, then α+β is ________ .

a) 60
b) 90
c) 120
d) 180

If P=3, R=27, T=243, then Q+S = ________ .

a) 40
b) 80
c) 90
d) 110

The dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN climate report estimates that without deep cuts to man-made emissions, at least 30% of the northern hemisphere’s surface permafrost could melt by the end of the century. Given this situation of imminent global exodus of billions of people displaced by rising seas, nation-states need to rethink their carbon footprint for political concerns, if not for environmental ones.

Which one of the following statements can be inferred from the given passage ?

a) Nation-states do not have environmental concerns.
b) Nation-states are responsible for providing fresh water to billions of people.
c) Billions of people are responsible for man-made emissions.
d) Billions of people are affected by melting glaciers.

Select the word that fits the analogy:
Cook : Cook :: Fly : _______

a) Flyer
b) Flying
c) Flew
d) Flighter

His knowledge of the subject was excellent but his classroom performance was _______ .

a) extremely poor
b) good
c) desirable
d) praiseworthy

Raman is confident of speaking English _______ six months as he has been practising regularly _______ the last three weeks.

a) during, for
b) for, since
c) for, in
d) within, for

Consider the following languages.

a) L1 is regular and L2 is context- free
b) L1 context- free but not regular and L2 is context-free
c) Neither L1 nor L2 is context- free
d) L1 context- free but L2 is not context-free

Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M.

L₁ = { ⟨M⟩ ∣ L(M)=∅ }
L₂ = { ⟨M,w,q⟩ ∣ M on input w reaches state q in exactly 100 steps }
L₃ = { ⟨M⟩ ∣ L(M) is not recursive }
L₄ = { ⟨M⟩ ∣ L(M) contains at least 21 members }

a) L₁, L₃, and L₄ only
b) L₁, and L₃ only
c) L₂, and L₃ only
d) L₂, L₃ and L₄ only

Consider the language L = { aⁿ ∣ n≥0 }∪{ aⁿbⁿ∣ n≥0 } and the following statements.
I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE ?

a) Ⅰ only
b) Ⅱ only
c) Ⅰ and Ⅲ only
d) Ⅲ only

Consider the following statements
I. If L1∪L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE ?

a) Ⅰ only
b) Ⅱ only
c) Both Ⅰ and Ⅱ
d) Neither Ⅰ nor Ⅱ

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1′s ?

a) ((0+1)*1(0+1)*1)*10*
b) (0*10*10*)*0*1
c) 10*(0*10*10*)*
d) None

Consider the following language.

Consider the following language.
L = { x∈{a,b}* ∣ number of a’s in x divisible by 2 but not divisible by 3 }
The minimum number of states in DFA that accepts L is _________ .

Consider the following C functions.

Consider the following C functions.

Consider the following C program.
#include <stdio.h>
int main () {
    int a[4][5] = {{1, 2, 3, 4, 5},
      {6, 7, 8, 9, 10},
      {11, 12, 13, 14, 15},
      {16, 17, 18, 19, 20}};
    printf("%dn", *(*(a+**a+2)+3));
    return(0);
}

The output of the program is _______

An organization requires a range of IP address to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space 202.61.0.0/17. The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. Which of the following address spaces are potential candidates from which the ISP can allot any one of the organization ?

I. 202.61.84.0 / 21
II. 202.61.104.0 / 21
III. 202.61.64.0 / 21
IV. 202.61.144.0 / 21

a) I and II only
b) II and III only
c) III and IV only
d) I and IV only

A computer system with a word length of 32 bits has a 16 MB byte- addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four physical addresses represented in hexadecimal notation.

a) A1 and A4 are mapped to different cache sets.
b) A2 and A3 are mapped to the same cache set.
c) A3 and A4 are mapped to the same cache set.
d) A1 and A3 are mapped to the same cache set.

Consider three registers R1, R2, and R3 that store numbers in IEEE−754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200000, respectively.

If R3 = ^R1/ _R2, what is the value stored in R3 ?

a) 0x40800000
b) 0xC0800000
c) 0x83400000
d) 0xC8500000

Consider the following statements.
I. Daisy chaining is used to assign priorities in attending interrupts.
II. When a device raises a vectored interrupt, the CPU does polling to identify the source of interrupt.
III. In polling,the CPU periodically checks the status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA controller can be bus masters at the same time.

a) Ⅰ and Ⅱ only
b) Ⅰ and Ⅳ onlyⅠ and Ⅲ onlya
c) Ⅰ and Ⅲ only
d) Ⅲ only

A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a 4-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are 8 distinct I-type opcodes, then the maximum number of distinct R-type opcodes is _______ .

Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5- stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to 2 decimal places) is __________ .

A direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the first word of a block from the main memory, while each subsequent word takes 5 ns. The word size is 64 bits. The average memory access time in ns (round off to 1 decimal place) is ________ .

A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The number of select lines needed for the multiplexer is _________

Consider the productions A → PQ and A → XY. Each of the five non-terminals A,P,Q,X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.

a) Both Rule 1 and Rule 2 are L-attributed
b) Only Rule 1 is L-attributed
c) Only Rule 2 is L-attributed
d) Neither Rule 1 nor Rule 2 is L-attributed

Consider the following statements.
I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.
Which of the above statements is/are TRUE ?

a) I only
b) I and III only
c) Ⅱ only
d) None of Ⅰ, Ⅱ and Ⅲ

Consider the following grammar.

Consider the following statements about the functionality of an IP based router.

I. A router does not modify the IP packets during forwarding.
II. It is not necessary for a router to implement any routing protocol.
III. A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet.

Which of the above statements is/are TRUE ?

a) I and II only
b) I only
c) II and III only
d) II only

Consider a TCP connection between a client and a server with the following specifications; the round trip time is 6 ms, the size of the receiver advertised window is 50 KB, slow-start threshold at the client is 32 KB, and the maximum segment size is 2 KB. The connection is established at time t=0. Assume that there are no timeouts and errors during transmission. Then the size of the congestion window (in KB) at time t+60 ms after all acknowledgements are processed is _________ .

Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persistent mode. The web page contains text and five very small images. The minimum number of TCP connections required to display the web page completely in your browser is ________ .

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order ?

a) Θ(n)
b) Θ(nlogn)
c) Θ(n²)
d) Θ(1)

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially ?

a) Θ(n⁴)
b) Θ(n²)
c) Θ(n²log(n))
d) Θ(n³)

For parameters a and b, both of which are ω(1), T(n)=T(n^1/a)+1, and T(b)=1. Then T(n) is

a) Θ(log_alog_bn)
b) Θ(log_abn)
c) Θ(log_blog_an)
d) Θ(log₂log₂n)

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ________ .

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b] ? Assume that the number of reported elements is k.

a) Θ(log n)
b) Θ(log(n)+k)
c) Θ(k log n)
d) Θ(n log k)

Let G = (V, G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u, v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

a) Θ(∣E∣ + ∣V∣)
b) Θ(∣E∣.∣V∣)
c) Θ(E∣ log ∣V∣)
d) Θ(∣V∣)

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree ?

a) 10, 11, 12, 15, 16, 18, 19, 20
b) 11, 12, 10, 16, 19, 18, 20, 15
c) 20, 19, 18, 16, 15, 12, 11, 10
d) 19, 16, 18, 20, 11, 12, 10, 15

Let G=(V,E) be a directed, weighted graph with weight function w:E→R.
For some function f:V→R, for each edge (u,v)∈E, define w′(u,v) as w(u,v)+f(u)−f(v).
Which one of the options completes the following sentence so that it is TRUE ? “The shortest paths in G under w are shortest paths under w′ too, _________”.

a) for every f:V→R
b) if and only if ∀u∈V, f(u) is positive
c) if and only if ∀u∈V, f(u) is negative
d) if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is ___________ .

Graph G is obtained by adding vertex s to K_3,4 and making s adjacent to every vertex of K_3,4 . The minimum number of colours required to edge-colour G is _________ .

Consider a graph G=(V, E), where V = { v₁,v₂,…,v₁₀₀ }, E={ (v_i, v_j) ∣ 1<=i<j<=100 is ∣ i–j ∣ . The weight of minimum spanning tree of G is ________ .

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _________

Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(k) = 1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________

Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE ?

a) R has a nontrivial functional dependency X→A, where X is not a superkey and A is a prime attribute.
b) R has a nontrivial functional dependency X→A, where X is not a superkey and A is a non-prime attribute and X is not a proper subset of any key.
c) R has a nontrivial functional dependency X→A, where X is not a superkey and A is a non-prime attribute and X is a proper subset of some key.
d) A cell in R holds a set instead of an atomic value.

Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram ?

a) Diamonds with double/bold border
b) Rectangles with double/bold border
c) Ovals with double/bold border
d) Ovals that contain underlined identifiers

If there are m input lines n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m+n is ________ .

Which one of the following predicate formulae is NOT logically valid ? Note that W is a predicate formula without any free occurrence of x.

a) ∀x(p(x) ∨ W) ≡ ∀x(px) ∨ W
b) ∃x(p(x) ∧ W) ≡ ∃xp(x) ∧ W
c) ∀x(p(x) → W) ≡ ∀xp(x) → W
d) ∃x(p(x) → W) ≡ ∀xp(x) → W

Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ________ .

Let R be the set of all binary relations on the set {1, 2, 3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ________ .

Let A and B be two n×n matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements.

I. rank(AB) = rank(A)*rank (B)
II. det(AB) = det(A)*det(B)
III. rank(A+B) ≤ rank(A) + rank(B)
IV. det(A+B) ≤ det(A) + det(B)

Which of the above statements are TRUE ?

a) I and II only
b) I and IV only
c) II and III only
d) III and IV only

Consider the functions

I. e^-x
II. x² - sin x
III. √x^3+1

Which of the above functions is/are increasing everywhere in [0, 1] ?

a) Ⅲ only
b) Ⅱ only
c) Ⅱ and Ⅲ only
d) Ⅰ and Ⅲ only

For n>2, let a∈{0, 1}ⁿ be a non-zero vector. Suppose that x is chosen uniformly at random from {0,1}ⁿ. Then, the probability that Σⁱ⁼¹_i=n a_ix_i is an odd number is _________

Consider the following five disk five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.

a) T is serviced before P.
b) Q is serviced after S, but before T.
c) The head reverses its direction of movement between servicing of Q and P.
d) R is serviced before P.

Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.

CODE SECTION P
wait(a); count=count+1;
if (count==n) signal (b);
signal (a): wait (b) ; signal (b);
CODE SECTION Q

What does the code achieve ?

a) It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
b) It ensures that two processes are in CODE SECTION Q at any time.
c) It ensures that all processes execute CODE SECTION P mutually exclusively.
d) It ensures that at most n−1 processes are in CODE SECTION P at any time.

Consider the following statements about process state transitions for a system using preemptive scheduling.

I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.
Which of the above statements are TRUE ?

a) I, II, and III only
b) II and III only
c) I, II, and IV only
d) I, II, III and IV only

Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statement is TRUE ?

a) The hole created by first fit is always larger than the hole created by next fit.
b) The hole created by worst fit is always larger than the hole created by first fit.
c) The hole created by best fit is never larger than the hole created by first fit.
d) The hole created by next fit is never larger than the hole created by best fit.

Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ___________ .