List of top Computer Science and IT Engineering Questions

Consider a table 𝑇, where the elements 𝑇[𝑖][𝑗], 0 ≤𝑖, 𝑗≤𝑛, represent the cost of
the optimal solutions of different subproblems of a problem that is being solved
using a dynamic programming algorithm. The recursive formulation to compute the
table entries is as follows:
𝑇[0][𝑘] = 𝑇[𝑘][0] = 1 for 𝑘= 0,1,2, … , 𝑛
𝑇[𝑖][𝑗] = 2𝑇[𝑖−1][𝑗] + 3𝑇[𝑖][𝑗−1] for 1 ≤𝑖, 𝑗≤𝑛
Consider the following two algorithms to compute entries of 𝑇. Assume that for
both the algorithms, for all 0 ≤𝑖, 𝑗≤𝑛, 𝑇[𝑖][𝑗] has been initialized to 1.

Algorithm B1:
For i = 1, 2, ..., n
  For j = 1, 2, ..., n
    T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm B2:
For s = 2, 3, ..., 2n
  For i = 1, 2, ..., n
    For j = 1, 2, ..., n
      If (i + j == s)
        T[i][j] = 2T[i-1][j] + 3T[i][j-1]

Algorithm 𝐵𝑘, 𝑘∈{1,2} is said to be correct if and only if it calculates the correct
values of 𝑇[𝑖][𝑗], for all 0 ≤𝑖, 𝑗≤𝑛, (as per the recursive formulation) at the end
of the execution of the algorithm 𝐵𝑘.
Which one of the following statements is true?

Consider the control flow graph given below.
Which one of the following options is the set of live variables at the exit point of
each basic block?

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

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

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 ?

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 ?

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?

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?

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

In the context of relational database normalization, which of the following
statements is/are true?

Consider the following C statements:
char *str1 = "Hello; /* Statement S1 */
char *str2 = "Hello;"; /* Statement S2 */
int *str3 = "Hello"; /* Statement S3 */
Which of the following options is/are correct?

With respect to a TCP connection between a client and a server, which one of the
following statements is true?

Which of the following statements is/are true with respect to the interaction of a
web browser with a web server using HTTP 1.1?

Match each addressing mode in List I with a data element or an element of a data
structure (in a high-level language) in List II:
List I
List II
P. Immediate
1. Element of an array
Q. Indirect
2. Pointer
R. Base with index
3. Element of a record
S. Base with offset/displacement 4. Constant