List of top Computer Science and IT Engineering Questions

Let $ S $ be an NP-complete problem and $ Q $ and $ R $ be two other problems not known to be in NP. $ Q $ is polynomial-time reducible to $ S $ and $ S $ is polynomial-time reducible to $ R $. Which one of the following statements is true?

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

The Lucas sequence $L_n$ is defined by the recurrence relation: \[ L_n = L_{n-1} + L_{n-2}, \text{for } n \geq 3, \] with $L_1 = 1$ and $L_2 = 3$. Which one of the options given is TRUE?

Let \[ A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{bmatrix} \] Let det(A) and det(B) denote the determinants of the matrices A and B, respectively.
Which one of the options given below is TRUE?

Let $A$ be a priority queue implemented using a max-heap.
Extract-Max(A) deletes and returns the maximum element;
Insert(A, key) inserts a new element. The max-heap property is preserved after each operation.
When $A$ has $n$ elements, which statement about the worst-case running times is TRUE?

Consider the syntax-directed translation with non-terminals N, I, F, B and the rules:

\[ \begin{aligned} N &\to I\ \#\ F \qquad && N.val = I.val + F.val \\ I &\to I_1\ B \qquad && I.val = 2 \times I_1.val + B.val \\ I &\to B \qquad && I.val = B.val \\ F &\to B\ F_1 \qquad && F.val = \tfrac12 \big(B.val + F_1.val\big) \\ F &\to B \qquad && F.val = \tfrac12 B.val \\ B &\to 0 \qquad && B.val = 0 \\ B &\to 1 \qquad && B.val = 1 \end{aligned} \] Find the value computed for the input string 10#011 (rounded to three decimals).

Consider the language $L$ over the alphabet $\{0,1\}$: \[ L = \{\, w \in \{0,1\}^* \;\mid\; \text{$w$ does not contain three or more consecutive $1$'s}\,\}. \] The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is ________.

A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of $b$ blocks needs $\lceil \log_2 b \rceil$ block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.

The forwarding table of a router is shown below. A packet addressed to a destination address 200.150.68.118 arrives at the router. It will be forwarded to the interface with ID

A Boolean digital circuit is composed using two 4-input multiplexers (M1 and M2) and one 2-input multiplexer (M3) as shown in the figure. X0–X7 are the inputs of M1 and M2 and can be set to 0 or 1. The select lines of M1 and M2 are $(A,C)$, and the select line of M3 is $B$. The output of M3 is the final circuit output.
Which one of the following sets of values of $(X0,X1,X2,X3,X4,X5,X6,X7)$ will realise the Boolean function \[ F(A,B,C) = \overline{A} + \overline{A}C + ABC \; ? \]

Consider the C function foo and the binary tree shown. When foo is called with a pointer to the root node of the given binary tree, what will it print?

typedef struct node {
    int val;
    struct node *left, *right;
} node;

int foo(node *p) {
    int retval;
    if (p == NULL)
        return 0;
    else {
        retval = p→val + foo(p→left) + foo(p→right);
        printf("%d ", retval);
        return retval;
    }
}

Binary tree structure:

Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown. At the beginning, $Q_1=0$, $Q_2=1$, $Q_3=1$. Which one of the given values of $(Q_1,Q_2,Q_3)$ can NEVER be obtained with this circuit?

A 4 KB byte-addressable memory is built using four 1 KB memory blocks. IA4 and IA3 feed a decoder that drives the active-high CS of the four blocks; the remaining ten address lines (all except IA4, IA3) go to the Addr inputs of each block. For each block, let $X_1,X_2,X_3,X_4$ be the input memory address (IA11–IA0), in decimal, of its starting location (Addr $=0$). Which option is correct?

Consider the given C-code and its corresponding assembly code, with a few operands U1–U4 being unknown. Some useful information as well as the semantics of each unique assembly instruction is annotated as inline comments in the code. The memory is byte-addressable.

Consider the pushdown automaton (PDA) $P$ over input alphabet $\{a,b\}$ and stack alphabet $\{\perp, A\}$ with start state $s$ and acceptance by empty stack.
The transition sketch shows:
- In $s$ on each $a$ it pushes one $A$ (i.e., $a/\perp \to A\perp$ and $a/A \to AA$).
- On the first $b$ it goes to $p$ with $b/A \to \epsilon$ and stays in $p$ popping one $A$ per $b$ ($b/A \to \epsilon$).
- From $p$ it may go to $q$ by $\epsilon/A \to \epsilon$, and in $q$ it can keep popping $A$’s and finally pop $\perp$ by $\epsilon/\perp \to \epsilon$.
Question: Which option describes $L(P)$? IMAGE8

Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block?

Consider the following program:

int main() {
    f1();
    f2(2);
    f3();
    return(0);
}

int f1() {
    f1();
    return(1);
}

int f2(int X) {
    f3();
    if (X==1)
        return f1();
    else
        return (X * f2(X-1));
}

int f3() {
    return(5);
}

Which one of the following options represents the activation tree corresponding to the main function?

Let $A$ be the adjacency matrix of the given graph with vertices $\{1,2,3,4,5\}$.

Let $\lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5$ be the eigenvalues of $A$ (not necessarily distinct). Find: \[ \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_5 \;=\; \_\_\_\_\_\_ . \]