GATE CS Applied Course

GATE Previous Year Wise Questions

GATE Previous Subject Wise Questions

Question 21
A processor can support a maximum memory of 4 GB, where the memory is word-addressable
(a word consists of two bytes). The size of the address bus of the processor is at least ___________ bits.

 
Submit
computer organization gate 2016 set 1
Question 22
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are
performed efficiently. Which one of the following statements is CORRECT (n refers to the
number of items in the queue)?
A
Both operations can be performed in O(1) time
B
At most one operation can be performed in O(1) time but the worst case time for
the other operation will be Ω(n)
C
The worst case time complexity for both operations will be Ω(n)
D
Worst case time complexity for both operations will be Ω(logn)
Data Structures gate 2016 set 1
Question 23
Submit
Data Structures gate 2016 set 1
Question 24
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
A
B
C
D
Algorithms gate 2016 set 1 Sorting
Question 25
Let G be a weighted connected undirected graph with distinct positive edge weights. If every
edge weight is increased by the same value, then which of the following statements is/are
TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
A
P only
B
Q only
C
Neither P nor Q
D
Both P and Q
Data Structures gate 2016 set 1 Graphs
Question 26
The size of the data count register of a DMA controller is 16 bits. The processor needs to
transfer a file of 29,154 kilobytes from disk to main memory. The memory is byte addressable.
The minimum number of times the DMA controller needs to get the control of the system bus
from the processor to transfer the file from the disk to main memory is _____________
Submit
computer organization gate 2016 set 1
Question 27
The stage delays in a 4-stage pipeline are 800, 500, 400 and 300 picoseconds. The first
stage (with delay 800 picoseconds) is replaced with a functionally equivalent design involving
two stages with respective delays 600 and 350 picoseconds. The throughput increase of the
pipeline is percent ______________ 
Submit
computer organization gate 2016 set 1
Question 28
An operator delete(i) for a binary heap data structure is to be designed to delete the item in
the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index
of the array. If the heap tree has depth d (number of edges on the path from the root to the
farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal
of the element?
A
B
C
D
Data Structures gate 2016 set 1
Question 29
Submit
Data Structures gate 2016 set 1 Graphs
Question 30
Submit
Algorithms gate 2016 set 1 Minimum-Spanning-Tree
Question 31
Submit
Data Structures gate 2016 set 1
Question 32
An IP datagram of size 1000 bytes arrives at a router. The router has to forward this packet on
a link whose MTU (maximum transmission unit) is 100 bytes. Assume that the size of the IP
header is 20 bytes.
The number of fragments that the IP datagram will be divided into for transmission is______________
Submit
Computer Networks gate 2016 set 1
Question 33
For a host machine that uses the token bucket algorithm for congestion control, the token
bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per second.
Tokens arrive at a rate to sustain output at a rate of 10 megabytes per second. The token bucket
is currently full and the machine needs to send 12 megabytes of data. The minimum time
required to transmit the data is ______________ seconds.
Submit
Computer Networks gate 2016 set 1
Question 34
A sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames
are of size 1000 bytes and the transmission rate at the sender is 80 Kbps (1Kbps = 1000
bits/second). Size of an acknowledgement is 100 bytes and the transmission rate at the receiver
is 8 Kbps. The one-way propagation delay is 100 milliseconds.
Assuming no frame is lost, the sender throughput is _______________ bytes/second.
Submit
Computer Networks gate 2016 set 1
Question 35
A processor has 40 distinct instructions and 24 general purpose registers. A 32-bit instruction
word has an opcode, two register operands and an immediate operand. The number of bits
available for the immediate operand field is ______________
Submit
computer organization gate 2016
Question 36
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is
a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the
maximum possible value of n is _____________
Submit
Data Structures gate 2016
Question 37
A
I and II only
B
I and III only
C
II and IV only
D
I and IV only
Algorithms gate 2016 Sorting
Question 38
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
A
Greedy paradigm.
B
Divide-and-Conquer paradigm.
C
Dynamic Programming paradigm.
D
neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
Algorithms gate 2016
Question 39
A
B
C
D
Data Structures gate 2016 Linked-List
Question 40
Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim
requires
A
Anarkali’s public key.
B
Salim’s public key.
C
Salim’s private key.
D
Anarkali’s private key.
Computer Networks gate 2016
© 2020 - All rights are reserved- AAIC Technologies pvt ltd