List of top Computer Science and IT Engineering Questions

The EX stage of a pipelined processor performs the memory read operations for
LOAD instructions, and the operations for the arithmetic and logic instructions. Let
𝑡𝐸𝑋 denote the time taken by the EX stage to perform the operation for an instruction.
For each instruction type, the values of 𝑡𝐸𝑋 and M (the number of instructions of that
type in a sequence of 100 instructions for a program P), are given in the table below.
The duration of the pipeline clock cycle is 1 nanosecond. Assume that the latch time
for the interstage buffers in the pipeline is negligible.
When program P is executed, the number of clock cycles for which the pipeline is
stalled due to structural hazards in the EX stage is ______. (answer in integer)
Instruction
𝑡𝐸𝑋 in
nanoseconds
𝑀
LOAD
1.8
15
IMUL
1.5
10
IDIV
2.5
5
FADD
1.7
10
FSUB
1.7
5
FMUL
2.8
15
FDIV
3.2
5
All other
instructions
Less than
1.0
35

Consider a hard disk with a rotational speed of 15000 rpm. The time to move the
read/write head from a track to its adjacent track is 1 millisecond. Initially, the head
is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes.
It is necessary to transfer data from 10 randomly located sectors in each of the
following tracks in the order: 5, 12 and 7.
The total time for the data transfer (in milliseconds) from the hard disk is _________.
(rounded off to one decimal place)

Consider a system that has a cache memory unit and a memory management unit
(MMU). The address input to the cache memory is a physical address. The MMU
has a translation lookaside buffer (TLB). Assume that when a page is evicted from
the main memory, the corresponding blocks in the cache are marked as invalid.
For a given memory reference, which of the following sequences of events can
NEVER happen?

Consider the following two syntax-directed definitions SDD1 and SDD2 for type
declarations.
𝐷 is the start symbol, and 𝑖𝑛𝑡, 𝑓𝑙𝑜𝑎𝑡 and 𝑖𝑑 are the three terminals. The non-terminal
𝑉1 is the same as 𝑉 and the non-terminal 𝐷1 is the same as 𝐷. Here, the subscript is
used to differentiate the grammar symbols on the two sides of a production. The
function 𝑝𝑢𝑡 updates the symbol table with the type information for an identifier.
Let P and Q be the languages specified by grammars G1 and G2, respectively.
Which of the following statements is/are true?
SDD1
Grammar
(G1)
Semantic Rules
𝐷 →𝑇 𝑉
𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑉. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑇 → 𝑖𝑛𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡
𝑇 → 𝑓𝑙𝑜𝑎𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡
𝑉→𝑉1 𝑖𝑑
𝑉1. 𝑡𝑦𝑝𝑒= 𝑉. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑉. 𝑡𝑦𝑝𝑒)
𝑉 → 𝑖𝑑
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑉. 𝑡𝑦𝑝𝑒)
SDD2
Grammar
(G2)
Semantic Rules
𝐷→𝐷1 𝑖𝑑
𝐷. 𝑡𝑦𝑝𝑒= 𝐷1. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝐷1. 𝑡𝑦𝑝𝑒)
𝐷 → 𝑇 𝑖𝑑
𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑇. 𝑡𝑦𝑝𝑒)
𝑇 →𝑖𝑛𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡
𝑇 → 𝑓𝑙𝑜𝑎𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡

An ISP having an address block 202.16.0.0/15 assigns a block of 6000 IP addresses
to a client, using the classless internet domain routing (CIDR) super-netting
approach. Which of the following address blocks can be assigned by the ISP?

Consider the following pseudocode for depth-first search (DFS) algorithm which
takes a directed graph 𝐺(𝑉, 𝐸) as input, where 𝑑[𝑣] and 𝑓[𝑣] are the discovery time
and finishing time, respectively, of the vertex 𝑣 ∈𝑉.
𝐷𝐹𝑆(𝐺):
𝑢𝑛𝑚𝑎𝑟𝑘 𝑎𝑙𝑙 𝑣∈𝑉
𝑡 ←0
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑣∈𝑉
𝑖𝑓 𝑣 𝑖𝑠 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑
𝑡←𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑣, 𝑡)
𝑒𝑛𝑑 𝑖𝑓
𝑒𝑛𝑑 𝑓𝑜𝑟
𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑣, 𝑡):
𝑚𝑎𝑟𝑘 𝑣
𝑡 ←𝑡+ 1
𝑑[𝑣] ←𝑡
𝑓𝑜𝑟 𝑒𝑎𝑐ℎ (𝑣, 𝑤) ∈𝐸
𝑖𝑓 𝑤 𝑖𝑠 𝑢𝑛𝑚𝑎𝑟𝑘𝑒𝑑
𝑡←𝐸𝑥𝑝𝑙𝑜𝑟𝑒(𝐺, 𝑤, 𝑡)
𝑒𝑛𝑑 𝑖𝑓
𝑒𝑛𝑑 𝑓𝑜𝑟
𝑡 ←𝑡 + 1
𝑓[𝑣] ←𝑡
𝑟𝑒𝑡𝑢𝑟𝑛 𝑡
Suppose that the input directed graph 𝐺(𝑉, 𝐸) is a directed acyclic graph (DAG).
For an edge (𝑢, 𝑣) ∈𝐸, which of the following options will NEVER be correct?

Consider the following context-free grammar 𝐺.
𝑆→𝑎𝑏𝑎𝐴𝐵𝐴𝑏𝑏𝑎
𝐴→𝑎𝑎𝐵𝐵𝐴𝑏 | 𝑏𝐵𝑎𝑏𝑎𝑎
𝐵→𝑎𝐵𝑏 | 𝑎𝑏
In the above grammar, 𝑆 is the start symbol, 𝑎 and 𝑏 are terminal symbols, and 𝐴 and
𝐵 are non-terminal symbols.
Let 𝐿(𝐺) be the language generated by the grammar 𝐺. For a string 𝑠∈𝐿(𝐺), let
𝑛1(𝑠) be the number of 𝑎’s in 𝑠 and 𝑛2(𝑠) be the number of 𝑏’s in 𝑠.
Which of the following statements is/are true?

Let 𝐿1 and 𝐿2 be two languages over a finite alphabet, such that 𝐿1 ∩𝐿2 and 𝐿2 are
regular languages.
Which of the following statements is/are always true?

Let 𝐺(𝑉, 𝐸) be a simple, undirected, edge-weighted graph with unique edge weights.
Which of the following statements about the minimum spanning trees (MST)
of 𝐺 is/are true?

Let 𝐺(𝑉, 𝐸) be a simple, undirected graph. A vertex cover of 𝐺 is a subset
𝑉′ ⊆𝑉 such that for every (𝑢, 𝑣) ∈𝐸, 𝑢∈𝑉′or 𝑣∈𝑉′. Let the size of the smallest
vertex cover in 𝐺 be 𝑘. Let 𝑆 be any vertex cover of size 𝑘.
For a vertex 𝑣∈𝑉, which of the following constraints will always ensure that
𝑣∈𝑆 ?

Consider a Boolean function F with the following minterm expression:
𝐹(𝑃, 𝑄, 𝑅, 𝑆) = ∑𝑚 (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)
Which of the following options is/are the minimal sum-of-products expression(s)
of F ?

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.

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 (1k = 103) and the one-way propagation delay
is 100 milliseconds. Assume that processing times at the sender and receiver are zero
and the transmission time of acknowledgements is also zero. Which one of the
following options gives the minimum size of 𝑊 (in number of frames) required to
achieve 100% link utilization?

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 𝐸 ?

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 𝑘 ≥0, 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 𝑘 ≥0 and 𝑢 ∈𝑉, 𝑑𝑘+1(𝑢) ≤𝑑𝑘(𝑢).
S2:
For every (𝑢, 𝑣) ∈𝐸, if (𝑢, 𝑣) is part of a shortest path (in terms of
weight) from 𝑠 to 𝑣, then for every 𝑘≥ 0, 𝑑𝑘(𝑢) ≤𝑑𝑘(𝑣).
Which one of the following options is correct?

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 10000 segments. Assume that the round-trip time is fixed at
1 millisecond. 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 milliseconds) at
which the transmission of segment number 2000 starts.
Which one of the following options is correct?

Consider the following code snippet in C language that computes the number of
nodes in a non-empty singly linked list pointed to by the pointer variable head.
struct node{
int elt;
struct node *next;
};
int getListSize (struct node *head)
{
if( E1 ) return 1;
return E2;
}
Which one of the following options gives the correct replacements for the
expressions E1 and E2?

The size of the physical address space of a processor is 232 bytes. The capacity of a
cache memory unit is 223 bytes. The cache block size is 128 bytes. The cache
memory unit can be built as a direct mapped cache or as a 𝐾-way set-associative
cache, where 𝐾= 2𝐿 and 𝐿∈{1, 2, 3}. Let the length of the TAG field be 𝑀 bits
for the direct mapped cache, and 𝑁 bits for the set-associative cache.
Which one of the following options is true?

Let 𝑃 be the set of all integers from 1 to 15. Consider any order of insertion of the
elements of 𝑃 into a binary search tree that creates a complete binary tree.
Which one of the following elements can NEVER be the third element that is
inserted?

Consider a 2-bit saturating up/down counter that performs the saturating up count
when the input P is 0, and the saturating down count when P is 1. The Next State
table of the counter is as shown. The counter is built as a synchronous sequential
circuit using D flip-flops.
Input
Current
State
Next
State
𝑃
𝑄1
𝑄0
𝑄1
+
𝑄0
+
0
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
Which one of the following options corresponds to the expressions for the inputs of
the D flip-flops, 𝐷1 and 𝐷0?

Consider the real valued variables X, Y and Z represented using the IEEE 754 single-
precision floating-point format. The binary representations of X and Y in hexadecimal
notation are as follows:
X: 35C00000 Y: 34A00000
Let 𝑍 = 𝑋+ 𝑌.
Which one of the following is the binary representation of 𝑍, in hexadecimal
notation?

Consider a system consisting of 𝑘 instances of a resource 𝑅, being shared by
5 processes. Assume that each process requires a maximum of two instances of
resource 𝑅 and a process can request or release only one instance at a time. Further,
a process can request the second instance of the resource only after acquiring the
first instance.
The minimum value of 𝑘 for the system to be deadlock-free is ________. (answer
in integer)

Consider the following program in C:
#include <stdio.h>
void func(int i, int j) {
if(i < j) {
int i = 0;
while (i < 10) {
j += 2;
i++;
}
}
printf("%d", i);
}
int main() {
int i = 9, j = 10;
func(i, j);
return 0;
}
The output of the program is _________. (answer in integer)
Note: Assume that the program compiles and runs successfully.

Let 𝑃, 𝑄, 𝑅 and 𝑆 be the attributes of a relation in a relational schema. Let 𝑋 ⟶𝑌
indicate functional dependency in the context of a relational database, where
𝑋, 𝑌 ⊆{𝑃, 𝑄, 𝑅, 𝑆}.
Which of the following options is/are always true?

With respect to deadlocks in an operating system, which of the following
statements is/are FALSE?