List of practice Questions

Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic.
\[ S_1 : (\neg p \wedge (p \vee q)) \rightarrow q \] \[ S_2 : q \rightarrow (\neg p \wedge (p \vee q)) \] Which one of the following choices is correct?

Consider the following two statements.
\[ S_1 : \text{Destination MAC address of an ARP reply is a broadcast address.} \] \[ S_2 : \text{Destination MAC address of an ARP request is a broadcast address.} \] Which one of the following choices is correct?

Consider the following array:
\[ 23 32 45 69 72 73 89 97 \] Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A binary search tree $ T $ contains $ n $ distinct elements. What is the time complexity of picking an element in $ T $ that is smaller than the maximum element in $ T $?

In the context of operating systems, which of the following statements is/are correct with respect to paging?

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are NOT recursive?

Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct?

Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory \texttt{foo. Which of the following operations will necessarily require a full scan of \texttt{foo} for successful completion?}

In an undirected connected planar graph $ G $, there are eight vertices and five faces. The number of edges in $ G $ is $\underline{\hspace{2cm}}$.

Consider the following undirected graph with edge weights as shown. The number of minimum-weight spanning trees of the graph is $\underline{\hspace{2cm}}$.

The lifetime of a component is exponentially distributed with parameter 2. The probability that its lifetime exceeds the expected lifetime (rounded to 2 decimal places) is $\underline{\hspace{2cm}}$.

There are 6 jobs with distinct difficulty levels and 3 computers with distinct processing speeds. The fastest computer gets the toughest job and the slowest computer gets the easiest job. Every computer gets at least one job. The number of ways in which this can be done is $\underline{\hspace{2cm}}$.

Consider the following expression.
\[ \lim_{x \to -3} \frac{\sqrt{2x + 22} - 4}{x + 3} \] The value of the above expression (rounded to 2 decimal places) is $\underline{\hspace{2cm}}$.

Consider the following sequence of operations on an empty stack and an empty queue.
Stack:
push(54); push(52); pop(); push(55); push(62); s = pop();
Queue:
enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
The value of $ s + q $ is $\underline{\hspace{2cm}}$.

Consider a computer system with a byte-addressable primary memory of size $2^{32}$ bytes.
Assume a direct-mapped cache of size 32 KB and cache block size of 64 bytes. The size of the tag field is $\underline{\hspace{2cm}}$ bits.

A relation $ r(A,B) $ has 1200 tuples.
Attribute $ A $ ranges from 6 to 20 and attribute $ B $ ranges from 1 to 20. Assume independent uniform distribution. The estimated number of tuples in $ \sigma_{(A>10)\vee(B=18)}(r) $ is $\underline{\hspace{2cm}}$.

Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127.
\[ S : 1 E : 10000001 F : 11110000000000000000000 \] Here $ S $, $ E $, and $ F $ denote the sign, exponent, and fraction components of the floating-point representation.
The decimal value corresponding to the above representation (rounded to 2 decimal places) is $\underline{\hspace{2cm}}$.

Three processes arrive at time zero with CPU bursts of 16, 20, and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is $\underline{\hspace{2cm}}$ milliseconds.

Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:

P → D* E*
D → int ID {record that ID.lexeme is of type int}
D → bool ID {record that ID.lexeme is of type bool}
E → E₁ + E₂ {check that E₁.type = E₂.type = int; set E.type := int}
E → !E₁ {check that E₁.type = bool; set E.type := bool}
E → ID {set E.type := int}

With respect to the above grammar, which one of the following choices is correct?

The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key:
\[ empAge(empNo, age) \] Consider the following relational algebra expression:
\[ \Pi_{empNo}\big( empAge \;\Join_{age > age_1}\; \rho_{empNo_1,\,age_1}(empAge) \big) \] What does the above expression generate?

Consider a 3-bit counter, designed using T flip-flops, as shown below. Assuming the initial state of the counter given by $PQR$ as $000$, what are the next three states?

Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is $d_8 d_7 d_6 d_5 c_8 d_4 d_3 d_2 c_4 d_1 c_2 c_1$, where the data bits and the check bits are given in the following tables. Which one of the following choices gives the correct values of $x$ and $y$?

Consider the following recurrence relation.
\[ T(n) = \begin{cases} T(n/2) + T(2n/5) + 7n, & \text{if } n > 0 \\ 1, & \text{if } n = 0 \end{cases} \] Which one of the following options is correct?

Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$:
\[ S \rightarrow daT \mid Rf \] \[ T \rightarrow aS \mid baT \mid \epsilon \] \[ R \rightarrow caTR \mid \epsilon \] The following is a partially-filled LL(1) parsing table.

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?