List of practice Questions

Which one of the following statements is TRUE for all positive functions $ f(n) $?

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Which one of the following statements is TRUE?

In a relational data model, which one of the following statements is TRUE?

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

The reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in $ O(1) $ space?

Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_1$ and $h_2$. Further suppose our hashing scheme uses $h_1$ for the odd keys and $h_2$ for the even keys. What is the expected number of keys in a slot?

Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

Let R1 and R2 be two 4-bit registers that store numbers in 2's complement form. For the operation R1 + R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

Consider the following two statements with respect to the matrices $A_{m \times n}$, $B_{n \times m}$, $C_{n \times n}$ and $D_{n \times n}$.

Statement 1: $tr(AB) = tr(BA)$
Statement 2: $tr(CD) = tr(DC)$

where $tr()$ represents the trace of a matrix. Which one of the following holds?

Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below.

What is the number of subnets inside the enterprise network?

Which of the following statements is/are TRUE?

Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

Consider the following three relations in a relational database.

Employee($eId$, Name), Brand($bId$, bName), Own($eId$, $bId$)

Which of the following relational algebra expressions return the set of $eId$'s who own all the brands?

Which of the following statements is/are TRUE with respect to deadlocks?

Which of the following statements is/are TRUE for a group $ G $?

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index $\underline{\hspace{1cm}}$.

Consider the augmented grammar with $\{+,* , (, ), id\}$ as the set of terminals. \[ S' \rightarrow S \] \[ S \rightarrow S + R \mid R \] \[ R \rightarrow R^{\,*} P \mid P \] \[ P \rightarrow (S) \mid id \] If $I_0$ is the set of two LR(0) items $\{[S' \rightarrow S.], [S \rightarrow S. + R]\}$, then $goto(\text{closure}(I_0), +)$ contains exactly $\underline{\hspace{1cm}}$ items.

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is

Consider a relation $R(A, B, C, D, E)$ with the following three functional dependencies: \[ AB \rightarrow C, BC \rightarrow D, C \rightarrow E \] The number of superkeys in the relation is

The number of arrangements of six identical balls in three identical bins is

A cache memory that has a hit rate of 0.8 has an access latency of 10 ns and a miss penalty of 100 ns. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is $\underline{\hspace{1cm}}$.

The value of the following limit is $\underline{\hspace{1cm}}$. \[ \lim_{x \to 0^+} \frac{\sqrt{x}}{1 - e^{2\sqrt{x}}} \]

Consider the resolution of the domain name www.gate.org.in by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that the iterative query mechanism is used in the resolution. The number of DNS query-response pairs involved in completely resolving the domain name is $\underline{\hspace{1cm}}$.

Which one of the following is the closed form for the generating function of the sequence $ \{ a_n \}_{n \geq 0} $ defined below?
\[ a_n = \begin{cases} n+1, & \text{if } n \text{ is odd} \\ 1, & \text{otherwise} \end{cases} \]