Computer Science and Information Technology
GATE CSE topic:computing PYQs
Build your understanding with focused practice from past exam papers.
Questions 81–90 of 975. Imported answers require independent review unless marked reviewed.
Question 41
Open questionCSMCQ2 marksNeeds review
Let
be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.Let
be a vertex in
. For every
and for every
, let
denote the weight of a shortest path (in terms of weight) from
to
of length at most
. If there is no path from
to
of length at most
, then
.Consider the statements:
S1: For every
and
,
.S2: For every
, if
is part of a shortest path (in terms of weight) from
to
, then for every
,
.Which one of the following options is correct?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 41
Open questionCS2MCQ2 marksNeeds review
Consider the canonical
parsing of the grammar below using terminals
and non-terminals
with
as the start symbol.
Which one of the following options gives the number of shift-reduce conflicts that will occur in the
ACTION table?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 42
Open questionCSMCQ2 marksNeeds review
Consider the control flow graph shown in the figure.
Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?
Note: All the variables are integers.
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 42
Open questionCS2MCQ2 marksNeeds review
In the context of schema normalization in relational DBMS, consider a set
of functional dependencies. The set of all functional dependencies implied by
is called the closure of
. To compute the closure of
, Armstrong’s axioms can be applied. Consider
,
, and
as sets of attributes over a relational schema. The three rules of Armstrong’s Axioms are described as follows.Reflexivity: If
, then
Augmentation: If
, then
for any
Transitivity: If
and
, then
The additional rule of Union is defined as follows.
Union: If
and
, then
It can be proved that the additional rule of Union is also implied by the three rules of Armstrong’s Axioms. Listed below are four combinations of these three rules. Which one of these combinations is both necessary and sufficient for the proof?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 43
Open questionCSMCQ2 marksNeeds review
Consider a relational database schema with two relations
and
. Let
be a tuple relational calculus expression. Which one of the following relational algebraic expressions is equivalent to
?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 43
Open questionCS2MCQ2 marksNeeds review
Consider the transmission of data bits 1100101 over a link that uses Cyclic Redundancy Check (CRC) code for error detection. If the generator bit pattern is given to be 1001, which one of the following options shows the remainder bit pattern appended to the data bits before transmission?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 44
Open questionCSMCQ2 marksNeeds review
A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism’s slow-start threshold is set to 1000 segments. Assume that the round-trip time is fixed at 1 milisecond. Assume that the sender always has data to send, the segments are numbered from 1, and no segment is lost. Let
denote the time (in miliseconds) at which the transmission of segment number 2000 starts. Which one of the following options is correct?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 44
Open questionCS2MCQ2 marksNeeds review
Consider a processor that has 16 general purpose registers and it uses 2-byte instruction format for all its instructions. Variable-sized opcodes are permitted. There are three different types of instructions; M-type, R-type, and C-type. Each M-type instruction has 2 register operands and a 6-bit immediate operand. Each R-type instruction has 3 register operands. Each C-type instruction has a register operand and a 6-bit offset value. If there are 2 unique M-type opcodes and 7 unique R-type opcodes, which one of the following options gives the maximum number of unique opcodes possible for C-type instructions?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 45
Open questionCSMCQ2 marksNeeds review
Consider the implementation of sliding window protocol over a lossless link, with a window size of
frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (
) and the one-way propagation delay is 100 miliseconds. Assume that processing times at the sender and receiver are zero and the transmission time of acknowledgments is also zero. Which one of the following options gives the minimum size of
(in number of frames) required to achieve 100% link utilization?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 45
Open questionCS2MCQ2 marksNeeds review
Consider the control flow graph given below.
Which one of the following options is the set of live variables at the exit point of each basic block?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer