List of top Computer Science and IT Engineering Questions

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)

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)

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)

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?

Consider the functions \(n^{1/3},\ \log_2 n,\ \log_2(n!),\ 2^{\log_2 n}\), where \(n\) is a positive integer.
Which option lists the functions in increasing asymptotic growth order?
Assume that the logarithm has base 2.

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: \(1\mathrm{M}=10^6\), \(1\mathrm{k}=10^3\)

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?

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?

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

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

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

Consider a relational database schema with a relation 𝑅(𝐴, 𝐵, 𝐶, 𝐷). If {𝐴, 𝐵} and
{𝐴, 𝐶} are the only two candidate keys of the relation 𝑅, then the number of superkeys
of relation 𝑅 is ______. (answer in integer)

Consider a CPU that has to execute two types of processes. The first type,
Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C),
requires a CPU burst of 8 seconds. A new process of type A arrives at time 𝑡 = 10,
20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time 𝑡 =
11, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First
Serve (FCFS). The first process of type A starts running at 𝑡 = 10 seconds. The
average waiting time (in seconds) for the 10 processes is ___________. (rounded off
to one decimal place)

Consider the following program snippet. Assume that the program compiles and runs
successfully. Further, assume that the fork() system call is always successful in
creating a process.
int main () {
int i;
for (i = 0; i < 3; i++){
if (fork() == 0){
continue;
}
break;
}
printf("Hello!");
return 0;
}
The total number of times that the printf statement gets executed is ________.
(answer in integer)

The following sequence corresponds to the preorder traversal of a binary search
tree 𝑇:
50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77
The position of the element 60 in the postorder traversal of 𝑇 is ______. (answer in
integer)
Note: The position begins with 1.

Consider the recursive functions represented by the following code segment:
int bar(int n){
if (n == 1) return 0;
else return 1 + bar(n/2);
}
int foo(int n){
if (n == 1) return 1;
else return 1 + foo(bar(n));
}
The smallest positive integer n for which foo(n) returns 5 is ______. (answer in
integer)
Note: Ignore syntax errors (if any) in the function.

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)

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 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. 𝑡𝑦𝑝𝑒)
𝐷 → 𝑇 𝑖𝑑
𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑇. 𝑡𝑦𝑝𝑒)
𝑇 →𝑖𝑛𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡
𝑇 → 𝑓𝑙𝑜𝑎𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡

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?