List of top Computer Science and IT Engineering Questions

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?

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?

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 ?

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

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

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.

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?

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?

The size of the physical address space of a processor is \(2^{32}\) bytes.
The capacity of a cache memory unit is \(2^{23}\) bytes and the cache block size is 128 bytes.
The cache can be direct-mapped or \(K\)-way set-associative, where \(K=2^L\) and \(L\in\{1,2,3\}\).
Let the TAG field contain \(M\) bits for the direct-mapped cache and \(N\) bits for the set-associative cache.
Which one of the following options is true?

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.

The height of a binary tree is the number of edges in the longest path from the root
to a leaf in the tree. The maximum possible height of a full binary tree with
23 nodes is _________. (answer in integer)

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?

Which of the following statements is/are true?

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite
alphabet.
Which of the following options CANNOT be the number of states in the minimal
deterministic finite automaton (DFA) that is equivalent to 𝑀 ?

Consider the following grammar where 𝑆 is the start symbol, and 𝑎 and 𝑏 are
terminal symbols.
𝑆 →𝑎𝑆𝑏𝑆 ∣ 𝑏𝑆 ∣ ϵ
Which of the following statements is/are true?

Consider a hash table 𝑃[0, 1, … , 10] that is initially empty. The hash table is
maintained using open addressing with linear probing. The hash function used is
ℎ(𝑥) = (𝑥+ 7) mod 11.
Consider the following sequence of insertions performed on 𝑃:
1, 13, 22, 15, 11, 24
Which of the following positions in the hash table is/are empty after these insertions
are performed?

Consider the 8-bit signed integers 𝑋, 𝑌 and 𝑍 represented using the sign-magnitude
form. The binary representations of 𝑋 and 𝑌 are as follows:
𝑋: 10110100 𝑌: 01001100
Which of the following operations to compute 𝑍 result(s) in an arithmetic
overflow?

Consider the following Boolean expression of a function F :
𝐹(𝑃, 𝑄) = (𝑃̅ + 𝑄) ⊕(𝑃̅𝑄)
Which of the following expressions is/are equivalent to F ?

Which one of the following dependencies among the register operands of different
instructions can cause a data hazard in a pipelined processor?

Consider a processor P whose instruction set architecture is the load-store
architecture. The instruction format is such that the first operand of any instruction
is the destination operand.
Which one of the following sequences of instructions corresponds to the high-level
language statement Z = X + Y ?
Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.