List of top Computer Science and IT Engineering Questions

Let 𝑛 be an odd number greater than 100. Consider a binary minheap with
𝑛 elements stored in an array 𝑃 whose index starts from 1.
Which of the following indices of 𝑃 do/does NOT correspond to any leaf node of
the minheap?

It is necessary to design a link-layer protocol between two hosts that are directly
connected over a lossless link of length 3000 kilometers. Assume that the link
bandwidth is \(10^8\) bits per second and that the propagation delay in the link is 5
nanoseconds per meter. Every transmitted data byte is assigned a unique sequence
number.
Let 𝑁 be the minimum number of bits needed for the sequence number field in the
protocol header such that
i.
the sequence numbers do not wrap around before 60 seconds, and
ii.
the maximum utilization of the link is achieved.
The value of 𝑁 is ______. (answer in integer)

Consider the following ANSI-C function.
int func(int start, int end){
int length=end+1-start;
if((length<1)||(start<0)||(end<0)){ return(0); }
if(length%3==0){
return(func(start+1, end));
} else if(length%3==1){
return(1+func(start, end-1));
} else {
return(func(start+2, end));
}
}
The maximum possible value that can be returned from this function is
____________. (answer in integer)
Note: Ignore syntax errors (if any) in the function.

Consider the following ANSI-C program.
#include <stdio.h>
int main(){
int *ptr, a, b, c;
a=5; b=11; c=20;
ptr=&a; *ptr=c; ptr=&c;
a=*(&b); c=*ptr-a;
printf("%d",c);
return(0);
}
The output of this program is ____________. (answer in integer)
Note: Assume that the program compiles and runs successfully.

Consider the digital circuit shown below with two input lines A and B, two select
lines S0 and S1, and an output line Y. The blocks Q and M represent active high
2:4 decoder and 4-to-1 multiplexer, respectively. Out of 16 possible input
combinations, the number of combinations that produce Y=1 is ____________.
(answer in integer)
Note: One input combination is an instance of [A B S1 S0].

Consider a new TCP connection between a sender and a receiver. The receiver
advertised window is constant at 48 KB, the maximum segment size (MSS) is
2 KB, and the slow start threshold for TCP congestion control is 16 KB. Assume
that there are no timeouts or duplicate acknowledgements. The number of rounds
of transmission required for the congestion control algorithm of the TCP connection
to reach the congestion avoidance phase is ___________. (answer in integer)
Note: \(1\mathrm{K}=2^{10}\)

A non-pipelined instruction execution unit that operates at 1.6 GHz clock takes an
average of 5 clock cycles to complete the execution of an instruction. To improve
the performance, the system was pipelined with a goal of achieving an average
throughput of one instruction per clock cycle. However, it could operate only at
1.2 GHz due to pipeline overheads. While executing a program in the pipelined
design, 30% of instructions encountered a stall of 2 cycles due to pipeline hazards.
The speed-up obtained by the pipelined design over the non-pipelined one for this
program is ___________. (rounded off to two decimal places)
Note: \(1\mathrm{G}=10^9\)

Consider a system with 1 MB physical memory and a word length of 1 byte. The
system uses a direct mapped cache, with block numbers starting from 0. The word
with physical address 0xA2C28 is mapped to the cache block number \(176_{10}\). The
maximum possible size of the cache (in KB) for this configuration is ___________.
(answer in integer)
Note: \(1\mathrm{K}=2^{10}\) and \(1\mathrm{M}=2^{20}\)

Consider contiguous allocation of physical memory to processes using variable
partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB,
25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are
adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order,
and they are allocated memory using the best-fit technique. After allocating space
to P1 and P2, the number of holes of size less than 8 KB is ____________. (answer
in integer)
Note: \(1\mathrm{K}=2^{10}\)

A system has a Translation Lookaside Buffer (TLB) that has a reach of 1 MB. TLB
reach is defined as the total amount of physical memory that can be accessed
through the TLB entries. The paging system uses pages of size 4 KB. The virtual
address space is 64 GB and physical address space is 1 GB. If each TLB entry stores
a 4-bit process id, page number, frame number, and a 2-bit control field, then the
size of the TLB (in bytes) is ___________. (answer in integer)
Note: \(1\mathrm{K}=2^{10}\), \(1\mathrm{M}=2^{20}\), \(1\mathrm{G}=2^{30}\)

To keep track of free blocks in a file system, one of the two approaches is generally
used - using bitmaps (bit vectors) or using linked lists. Consider that the linked list
approach is used to keep track of free blocks in a file system. Assume that the disk
size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single
pointer of size 4 bytes is used in each block of the list to point to the next block of
the list. The number of blocks required to hold the free disk block numbers is
____________. (answer in integer)
Note: \(1\mathrm{K}=2^{10}\) and \(1\mathrm{G}=2^{30}\)

Consider a system with a processor and a 4 KB direct mapped cache with block size
of 16 bytes. The system has a 16 MB physical memory. Four words P, Q, R, and S
are accessed by the processor in the same order 10 times. That is, there are a total
of 40 memory references in the sequence P, Q, R, S, P, Q, R, S,…
Assume that the cache memory is initially empty. The physical addresses of the
words are given below (1 word =1 byte).
P: 0x845B32, Q: 0x845B26, R: 0x845B36, S: 0x846B32
Which of the following statements is/are true?
Note: \(1\mathrm{K}=2^{10}\) and \(1\mathrm{M}=2^{20}\)

Consider three processes P1, P2, and P3 running identical code, as shown in the
pseudocode below. A and B are two binary semaphores initialized to 1 and 0,
respectively. X is a shared variable initialized to 0. Each line in the pseudocode is
executed atomically.
Pseudocode of P1, P2, and P3
Wait(A);
Print(*);
X = X+1;
If (X == 2)
{
Print($);
Signal(B);
}
Signal(A);
Wait(B);
Print(#);
Signal(B);
Assume that any of the three processes can start to execute first and context
switching can happen between these processes at any arbitrary time and in any
arbitrary order.
Which of the following patterns is/are possible to be generated as an outcome of the
execution of these three processes?

Consider a stack 𝑆 and a queue 𝑄. Both of them are initially empty and have the
capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one,
in that order. When an element arrives, it is assigned either to 𝑆 (pushed on 𝑆 ) or
to 𝑄 (enqueued to 𝑄). Once all the five elements are stored, the output is generated
in two steps. First, stack S is emptied by popping all elements. Then queue 𝑄 is
emptied by dequeueing all elements. The output obtained by following this process
is 4 3 1 2 5 .
Given the output, the objective is to predict whether an element was assigned to 𝑆
or 𝑄.
Which of the following options is/are possible valid assignment(s) of the
elements?
Note: In the options, the notation 𝑥𝑆 denotes that element 𝑥 was assigned to 𝑆 and
𝑦𝑄 denotes that element 𝑦 was assigned to 𝑄.

Consider a binary search tree (BST) with 𝑛 leaf nodes (𝑛> 0). Given any node 𝑉,
the key present in the node is denoted as 𝑉𝑎𝑙(𝑉). All the keys present in the given
BST are distinct. The keys belong to the set of real numbers.
For a node 𝑉, let 𝑆𝑢𝑐(𝑉) denote the node that is its inorder successor. If a node 𝑉
does not have an inorder successor, then 𝑆𝑢𝑐(𝑉) is 𝑁𝑈𝐿𝐿. As there are no
duplicates, if 𝑆𝑢𝑐(𝑉) is not 𝑁𝑈𝐿𝐿, then 𝑉𝑎𝑙(𝑉) < 𝑉𝑎𝑙(𝑆𝑢𝑐(𝑉)).
Corresponding to every leaf node 𝐿𝑖 that has a non-NULL 𝑆𝑢𝑐(𝐿𝑖), a new key 𝑘𝑖
with the following property is to be inserted into the BST.
𝑉𝑎𝑙(𝐿𝑖) < 𝑘𝑖< 𝑉𝑎𝑙(𝑆𝑢𝑐(𝐿𝑖))
Let 𝐾 represent the list of all such new keys to be inserted into the BST.
Which of the following statements is/are true?

Let \(\Sigma=\{a,b,c,d\}\) and \(L=\{a^i b^j c^k d^{\ell}\mid i,j,k,\ell\geq0\}\).
Which of the following constraints ensure(s) that the language \(L\) is context-free?

Consider the following two finite automata 𝐷1 and 𝐷2.
Which of the following statements is/are true?

An index in a DBMS is said to be dense if an index entry appears for every
search-key value in the indexed file. Otherwise it is called a sparse index. Consider
the following two statements.
S1: A hash index must be a dense index
S2: A 𝐵+ tree index can be a sparse index
Which one of the following options is correct?

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?

Consider the transmission of data bits 110001011 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?

In the context of schema normalization in relational DBMS, consider a set F of
functional dependencies. The set of all functional dependencies implied by F is
called the closure of F. To compute the closure of F, 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 Z
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 ?

Consider the canonical 𝐿𝑅(0) 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 𝐿𝑅(0) ACTION table?

Consider the following 4-variable Boolean function
𝐹(𝐴, 𝐵, 𝐶, 𝐷) = Σ𝑚(0, 1, 2, 3, 8, 9, 10, 11)
Consider 𝐴 as MSB, 𝐷 as LSB. Which one of the following options represents the
minimal sum of products form for the above function?
Note: + is OR operation, . is AND operation, ′ is NOT operation

Consider an array 𝐴 of integers of size 𝑛. The indices of 𝐴 run from 1 to 𝑛. An
algorithm is to be designed to check whether 𝐴 satisfies the condition given below.
∀𝑖, 𝑗∈{1, … , 𝑛−1} such that 𝑖> 𝑗, (𝐴[𝑖+ 1] −𝐴[𝑖]) > (𝐴[𝑗+ 1] −𝐴[𝑗])
Which one of the following gives the worst case time complexity of the fastest
algorithm that can be designed for the problem?

Let 𝐺 be a weighted directed acyclic graph with 𝑚 edges and 𝑛 vertices. Given 𝐺
and a source vertex 𝑠 in 𝐺, which one of the following options gives the worst case
time complexity of the fastest algorithm to find the lengths of shortest paths from 𝑠
to all vertices that are reachable from 𝑠 in 𝐺?