List of top Computer Science and IT Engineering Questions

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 17610. The
maximum possible size of the cache (in KB) for this configuration is ___________.
(answer in integer)
Note: 1K=210 and 1M=220

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: 1K=210 and 1M=220

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

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: 1K=210 and 1G=230

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?

A lexical analyzer uses the following token definitions
 𝑙𝑒𝑡𝑡𝑒𝑟→[𝐴−𝑍𝑎−𝑧]
 𝑑𝑖𝑔𝑖𝑡→[0 −9]
 𝑖𝑑→𝑙𝑒𝑡𝑡𝑒𝑟 (𝑙𝑒𝑡𝑡𝑒𝑟 | 𝑑𝑖𝑔𝑖𝑡)*
 𝑛𝑢𝑚𝑏𝑒𝑟→𝑑𝑖𝑔𝑖𝑡+
 𝑤𝑠→(𝑏𝑙𝑎𝑛𝑘 | 𝑡𝑎𝑏 | 𝑛𝑒𝑤𝑙𝑖𝑛𝑒)+
For the string given below,
𝑥1 23𝑚𝑚 78 𝑦 7𝑧 𝑧𝑧5 14𝐴 8𝐻 𝐴𝑎𝑌𝑐𝐷
the number of tokens (excluding 𝑤𝑠) that will be produced by the lexical analyzer
is __________. (answer in integer)

If an IP network uses a subnet mask of 255.255.240.0, the maximum number of IP
addresses that can be assigned to network interfaces is __________. (answer in
integer)

The 32-bit IEEE 754 single precision representation of a number is 0xC2710000.
The number in decimal representation is ________. (rounded off to two decimal
places)

Consider an array 𝐴= [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort
algorithm is executed on array 𝐴 to sort it in increasing order. The merge sort
algorithm will carry out a total of 7 merge operations.
A merge operation on sorted left array 𝐿 and sorted right array 𝑅 is said to be void
if the output of the merge operation is the elements of array 𝐿 followed by the
elements of array 𝑅.
The number of void merge operations among these 7 merge operations
is __________. (answer in integer)

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the
hash function ℎ(𝑘) = 𝑘 𝑚𝑜𝑑 9. The collisions are resolved by chaining. After all
the keys are inserted, the length of the longest chain is __________. (answer in
integer)

Which of the following grammars is/are ambiguous?

In a system, numbers are represented using 4-bit two’s complement form. Consider
four numbers 𝑁1 =1011, 𝑁2 =1101, 𝑁3 =1010 and 𝑁4 =1001 in the system.
Which of the following operations will result in arithmetic overflow?

Which one of the following protocols may need to broadcast some of its messages?

Consider the following functions, where 𝑛 is a positive integer.
𝑛1/3 , log(𝑛) , log(𝑛!), 2log(𝑛)
Which one of the following options lists the functions in increasing order of
asymptotic growth rate?
Note: Assume the base of log to be 2.

Which one of the following CPU scheduling algorithms cannot be preemptive?

In C runtime environment, which one of the following is stored in heap?

Consider a file of size 4 million bytes being transferred between two hosts
connected via a path consisting of three consecutive links of bandwidth 2 Mbps,
500 kbps, and 1 Mbps, respectively. All processing delays and propagation delays
are negligible. Assume that there is no other background traffic over the path and
no other additional overhead to transfer the file.
Which one of the following is the total time (in seconds) to transfer the file?
Note: 1M=106, 1k=103

Consider the following three ANSI-C programs, P1, P2, and P3.
P1
P2
P3
#include <stdio.h>
int a=5;
int main(){
int a=7;
return(0);
}
#include <stdio.h>
int main(){
int a=5;
int a=7;
return(0);
}
#include <stdio.h>
int main(){
int a=5;
float a=7;
return(0);
}
Which one of the following statements is true?

Consider the following two statements about interrupt handling mechanisms in a
CPU.
S1: In non-vectored interrupt mechanism, it usually takes more time to start the
Interrupt Service Routine (ISR) when compared to that in a vectored interrupt
mechanism.
S2: In daisy-chain interrupt mechanism, the CPU polls all the input devices
individually to determine the source of the interrupt.
Which one of the following options is correct with respect to S1 and S2 ?

Consider concurrent execution of two transactions 𝑇1 and 𝑇2 in a DBMS, both of
which access a data object 𝐴. For these two transactions to not conflict on 𝐴, which
one of the following statements must be true?

Which one of the following statements is equivalent to the following assertion?
Turing machine 𝑀 decides the language 𝐿⊆{0,1}∗

Which one of the following options is not a property of Boolean Algebra?
Note: + is OR operation, . is AND operation, and ′ is NOT operation

In the context of DBMS, consider the two sets T and S given below.
T
S
I: Logical schema
L: Views
II: Physical schema
M: File organization and indexes
III: External schema N: Relations
Which one of the following is the correct match from T to S ?

The set T represents various traversals over binary tree. The set S represents the
order of visiting nodes during a traversal.
T
S
I: Inorder
L: left subtree, node, right subtree
II: Preorder
M: node, left subtree, right subtree
III: Postorder N: left subtree, right subtree, node
Which one of the following is the correct match from T to S ?