Exam Details
Computer Science & Information Technology (CS) 2020
Review the key details, then start the test when you are ready. You can also open the full package to see related papers.
Questions
65
Duration
180 mins
Package
GATE & PSU CS - Previous Year Papers
Paper pattern & analysis
Filter this paper by subject, topic or subtopic. Every graph updates from the selected questions.
Topic distribution
Subtopic distribution
Difficulty distribution
65questions
Medium
37
56.9%
Hard
25
38.5%
Easy
3
4.6%
Question type distribution
65questions
MCQ
42
64.6%
Fill in the blanks
23
35.4%
Syllabus
Sample
Practise paper questions
Choose your answer to check it. Log in to view the explanation. For a timed attempt and result, start the exam.
PYP
Computer Science & Information Technology (CS) 2020
There are multiple routes to reach from node 1 to node 2, as shown in the network.
The cost of the travel on an edge between nodes is given in rupees. Nodes ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ and ‘f’ are toll booths. The toll price at toll booths marked ‘a’ and ‘e’ is Rs. 200, Rs. 100 for the other toll booths. Which is the cheapest route from node 1 to 2?
The cost of the travel on an edge between nodes is given in rupees. Nodes ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ and ‘f’ are toll booths. The toll price at toll booths marked ‘a’ and ‘e’ is Rs. 200, Rs. 100 for the other toll booths. Which is the cheapest route from node 1 to 2?
PYP
Computer Science & Information Technology (CS) 2020
The total revenue of a company during 2014-2018 is shown in the graph. If the expenditure of the company in each year is 500 million rupees, then the aggregate profit loss (in percentage) on the total expenditure of the company during 2014-2018 is _______
PYP
Computer Science & Information Technology (CS) 2020
Select the words that fits the analogy:
Cook : Cook :: Fly : ______
Cook : Cook :: Fly : ______
PYP
Computer Science & Information Technology (CS) 2020
Raman is confident of speaking English _____ six months as he has been practicing regularly ______ the last three weeks.
PYP
Computer Science & Information Technology (CS) 2020
Goods and Services Tax (GST) is an indirect tax introduced in India in 2017 imposed on the supply of goods and services, and it subsumes all indirect taxes except few. It is a destination-based tax imposed on goods and services used, and it is not imposed the point of origin from where goods come. GST also has a few components specific to state governments, central government and Union Territories (UT’s).
Which one of the following statements can be inferred from the given passage?
Which one of the following statements can be inferred from the given passage?
PYP
Computer Science & Information Technology (CS) 2020
If P = 3, R = 27, T = 243, then Q + S = ______
PYP
Computer Science & Information Technology (CS) 2020
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 _____ .
PYP
Computer Science & Information Technology (CS) 2020
His knowledge of the subject was excellent, but his classroom performance was______.
PYP
Computer Science & Information Technology (CS) 2020
The dawn of the 21st century witnessed the melting glaciers oscillating between giving 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. Give situation of imminent global exodus of billions of people displaced by rising seas, nation-states need to rethink their cartoon footprint for political concerns, if not for environmental ones.
Which of the following statements can be inferred from the given passage?
Which of the following statements can be inferred from the given passage?
PYP
Computer Science & Information Technology (CS) 2020
The figure below shows an annular ring with outer and inner radii as b and a, respect. The annular space has been painted in the form of blue colour circles touching the and inner periphery of annular space. If maximum n number of circles can be painted, then the unpainted area available in annular space is _____.
PYP
Computer Science & Information Technology (CS) 2020
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 the 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.
Which of the above statements is/are TRUE?
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 the 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.
Which of the above statements is/are TRUE?
PYP
Computer Science & Information Technology (CS) 2020
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19 . Which one of the following is the post order traversal of the tree?
PYP
Computer Science & Information Technology (CS) 2020
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?
PYP
Computer Science & Information Technology (CS) 2020
Consider the functions
I. e–x
II. x2 – sin x
III. Which of the above functions is/are increasing everywhere in [0,1]?
I. e–x
II. x2 – sin x
III. Which of the above functions is/are increasing everywhere in [0,1]?
PYP
Computer Science & Information Technology (CS) 2020
Consider a double hashing scheme in which the primary hash function h1(k) = k mod 23, and the secondary hash function is h2(k) = 1 + (k mod19). 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 ________.
PYP
Computer Science & Information Technology (CS) 2020
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
PYP
Computer Science & Information Technology (CS) 2020
Consider the language 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?
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?
PYP
Computer Science & Information Technology (CS) 2020
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 ______.
PYP
Computer Science & Information Technology (CS) 2020
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 use’ are detected during syntax analysis.
Which of the above statements is/are TRUE?
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 use’ are detected during syntax analysis.
Which of the above statements is/are TRUE?
PYP
Computer Science & Information Technology (CS) 2020
For parameters a and b, both of which are T(n) = T(n1/a) + 1, and T(b)=1. Then T(n) is:
PYP
Computer Science & Information Technology (CS) 2020
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other G itself is ______.
PYP
Computer Science & Information Technology (CS) 2020
Consider the following data path diagram.
Consider an instruction: The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The Subscripts r and w indicate read and write operations, respectively.
1) R2r, TEMP1r, ALUadd, TEMP2w 2. R1r, TEMP1w
3) PCr, MARw, MEMr 4. TEMP2r, R0w
5) MDRr, IRw
Which one of the following is the correct order of execution of the above steps?
Consider an instruction: The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The Subscripts r and w indicate read and write operations, respectively.
1) R2r, TEMP1r, ALUadd, TEMP2w 2. R1r, TEMP1w
3) PCr, MARw, MEMr 4. TEMP2r, R0w
5) MDRr, IRw
Which one of the following is the correct order of execution of the above steps?
PYP
Computer Science & Information Technology (CS) 2020
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?
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?
PYP
Computer Science & Information Technology (CS) 2020
Let R be the set of all binary relations on the set {1, 2, 3}. Suppose a relation chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ________.
PYP
Computer Science & Information Technology (CS) 2020
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 _______.
PYP
Computer Science & Information Technology (CS) 2020
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?
PYP
Computer Science & Information Technology (CS) 2020
Consider a relational database containing the following schemas.
The primary key of each table is indicated by underlining the constituent fields
SELECT s.sno, s.sname
FROM Suppliers s, Catalogue c
WHERE s.sno = c.sno AND
Cost > (SELECT AVG (cost)
FROM Catalogue
WHERE pno = ‘P4’
GROUP BY pno);
The number of rows returned by the above SQL query is
The primary key of each table is indicated by underlining the constituent fields
SELECT s.sno, s.sname
FROM Suppliers s, Catalogue c
WHERE s.sno = c.sno AND
Cost > (SELECT AVG (cost)
FROM Catalogue
WHERE pno = ‘P4’
GROUP BY pno);
The number of rows returned by the above SQL query is
PYP
Computer Science & Information Technology (CS) 2020
Consider the following grammar.
The number of reduction steps taken by a bottom-up parser while accepting string aaadbbb is ______ .
The number of reduction steps taken by a bottom-up parser while accepting string aaadbbb is ______ .
PYP
Computer Science & Information Technology (CS) 2020
Consider the following statements about the functionality of an IP based router.
I. A router does not modify the 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 outing packet is larger than the size of the incoming IP packet.
Which of the above statements is/are TRUE?
I. A router does not modify the 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 outing packet is larger than the size of the incoming IP packet.
Which of the above statements is/are TRUE?
PYP
Computer Science & Information Technology (CS) 2020
If there are m input lines and n output for a decoder that is used to unique address a byte addressable 1 KB RAM, then the minimum value of m + n is _____
PYP
Computer Science & Information Technology (CS) 2020
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 of the existing holes. Which one of the following statements is TRUE?
PYP
Computer Science & Information Technology (CS) 2020
Consider the following sentences.
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?
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?
PYP
Computer Science & Information Technology (CS) 2020
What is the worst case time complexity of inserting n2 elements into an AVL Tree with n elements initially?
PYP
Computer Science & Information Technology (CS) 2020
A multiplexer is placed between a group of 32 register and an accumulator to regulate data movement such at that any given point in time the content of only one register will move to the accumulator. The minimum number of select lines needed for the multiplexer is ______ .
PYP
Computer Science & Information Technology (CS) 2020
Consider the following C program.
#include
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(“%d\n”, *(*(a+**a+2)+3));
return(0);
}
The output program is ______ .
#include
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(“%d\n”, *(*(a+**a+2)+3));
return(0);
}
The output program is ______ .
PYP
Computer Science & Information Technology (CS) 2020
Let G = (V, E) be a directed, weighted graph with weight function w: E ⇾ R. For some function f :V ⇾ R. for each edge 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, _____.
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, _____.
PYP
Computer Science & Information Technology (CS) 2020
Consider the following language.
number of a’s in x is divisible by 2 but not divisible by 3
The minimum number of states in a DFA that accepts L is ____.
number of a’s in x is divisible by 2 but not divisible by 3
The minimum number of states in a DFA that accepts L is ____.
PYP
Computer Science & Information Technology (CS) 2020
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
Note that W is a predicate formula without any free occurrence of x.
PYP
Computer Science & Information Technology (CS) 2020
Consider the Boolean function z(a, b, c).
Which one of the following minterm lists represents the circuit given above?
Which one of the following minterm lists represents the circuit given above?
PYP
Computer Science & Information Technology (CS) 2020
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 represent hexadecimal notation.
A1 = 0×42C8A4, A2 = 0×546888,
A3 = 0×6A289C, A4 = 0×5E4880
Which one of the following is TRUE?
A1 = 0×42C8A4, A2 = 0×546888,
A3 = 0×6A289C, A4 = 0×5E4880
Which one of the following is TRUE?
PYP
Computer Science & Information Technology (CS) 2020
A processor has 64 registers and uses 16-bit instruction format. It has two type instruction: 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 _____.
PYP
Computer Science & Information Technology (CS) 2020
Consider the production and Each of the five non-terminal A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.
Rule 1: P.i =i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i
Which one of the following is TRUE ?
Rule 1: P.i =i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i
Which one of the following is TRUE ?
PYP
Computer Science & Information Technology (CS) 2020
The number of permutations of the characters in LILAC so that no characters appears in its original position, if the two L’s are indistinguishable, is _______.
PYP
Computer Science & Information Technology (CS) 2020
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.
What does the code achieve?
What does the code achieve?
PYP
Computer Science & Information Technology (CS) 2020
Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) V × V is added to G. The worst case time complexity determining if T is still an MST of the resultant graph is
PYP
Computer Science & Information Technology (CS) 2020
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour is G______ .
PYP
Computer Science & Information Technology (CS) 2020
Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns. 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 required page is read in from disk. TLB update time is negligible. The average memory access time is ns (round off to 1 decimal places) is ______.
PYP
Computer Science & Information Technology (CS) 2020
Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj)|1ij100}, and weight of the edge (vi, vj) is |i – j|. The weight of the minimum spanning tree of G is _____.
PYP
Computer Science & Information Technology (CS) 2020
For n > 2, let be a non-zero vector. Suppose that x is chosenuniformly at random form (0,1)n. Then, the probability that is an number is _______ .
PYP
Computer Science & Information Technology (CS) 2020
Consider the array representation of a binary min-heap containing 1023 element. The minimum number of comparisons required to find the maximum in the heap is ______.
PYP
Computer Science & Information Technology (CS) 2020
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 pipeline processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instruction. 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-pipeline processor (round off to 2 decimal places) is ______.
PYP
Computer Science & Information Technology (CS) 2020
Consider the following languages.
L1 = {wxyx | w,x,y(0+1)+}
L2 = {xy | x,y(a + b)*,|x| = |y|, x y}
Which one of the following is TRUE?
L1 = {wxyx | w,x,y(0+1)+}
L2 = {xy | x,y(a + b)*,|x| = |y|, x y}
Which one of the following is TRUE?
PYP
Computer Science & Information Technology (CS) 2020
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.
(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)
Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.
Which one of the following statements is FALSE?
(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)
Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.
Which one of the following statements is FALSE?
PYP
Computer Science & Information Technology (CS) 2020
Consider the following C functions.
The value returned by pp(3, 4) is ______.
The value returned by pp(3, 4) is ______.
PYP
Computer Science & Information Technology (CS) 2020
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?
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?
PYP
Computer Science & Information Technology (CS) 2020
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.
PYP
Computer Science & Information Technology (CS) 2020
Consider the following C functions.
int fun1(int n) { static int i= 0; if (n > 0) { ++i; fun1(n-1); } return (i); } int fun2(int n) { static int i= 0; if (n>0) { i = i+ fun1 (n) ; fun2(n-1) ; } return (i); } The return value of fun2(5) is _______.
int fun1(int n) { static int i= 0; if (n > 0) { ++i; fun1(n-1); } return (i); } int fun2(int n) { static int i= 0; if (n>0) { i = i+ fun1 (n) ; fun2(n-1) ; } return (i); } The return value of fun2(5) is _______.
PYP
Computer Science & Information Technology (CS) 2020
Consider the following set of processes, assumed to have arrived at time Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1, P2, P3, P4.
If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off t0 2 decimal places) is …………….. .
If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off t0 2 decimal places) is …………….. .
PYP
Computer Science & Information Technology (CS) 2020
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) 0×42200000 and 0×C1200000, respectively.
If What is the value stored in R3?
If What is the value stored in R3?
PYP
Computer Science & Information Technology (CS) 2020
Consider a database implemented using B+ tree for file indexing and installed a disk drive with a block size of 4 KB. The size of the search key is 12 bytes, and the size of the 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 the 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 ______.
PYP
Computer Science & Information Technology (CS) 2020
Consider a schedule of transactions T1 and T2:
Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one following schedules is conflict equivalent to the above schedule?
Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one following schedules is conflict equivalent to the above schedule?
PYP
Computer Science & Information Technology (CS) 2020
Consider a relational table R that is in 3NF, but not in BCNF. Which one following statements is TRUE?
PYP
Computer Science & Information Technology (CS) 2020
An organization requires a range of IP addresses 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 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 to 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
I. 202.61.84.0/21
II. 202.61.104.0/21
III. 202.61.64.0/21
IV. 202.61.144.0/21
PYP
Computer Science & Information Technology (CS) 2020
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 advert window is 50 KB, slow-start threshold at the client is 32 KB, and the maximum segment size is 2 K
B. The connection is established at time t = 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 processed is _______.
B. The connection is established at time t = 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 processed is _______.
PYP
Computer Science & Information Technology (CS) 2020
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.
on input w reaches state q in exactly 100 steps}
is not recursive}
contains at least 21 members}
on input w reaches state q in exactly 100 steps}
is not recursive}
contains at least 21 members}
Showing 5 of 65 questions