GATE CS question library

Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$

Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$

Match the following: …

Which of the following statements is false?

We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is

You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to

The subset-sum problem is defined as follows: Given a set $S$ of $n$ positive integers and a positive integer $W$, determine whether there is a subset of $S$ whose elements sum to $W$. An algorithm $Q$ solves this problem in $O(nW)$ time. Which of the following statements is false?

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then

A B-tree of order $4$ is built from scratch by $10$ successive insertions. What is the maximum number of node splitting operations that may take place?

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

Consider the following functions: $f(n) = 2^n$ $g(n) = n!$ $h(n) = n^{\log n}$ Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and $h(n)$ is true?

In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is:

Which of the following are NOT true in a pipelined processor? Bypassing can handle all RAW hazards Register renaming can eliminate all register carried WAR hazards Control hazard penalties can be eliminated by dynamic branch prediction

The use of multiple register windows with overlap causes a reduction in the number of memory accesses for: Function locals and parameters Register saves and restores Instruction fetches

For inclusion to hold between two cache levels $L_1$ and $L_2$ in a multi-level cache hierarchy, which of the following are necessary? $L_1$ must be write-through cache $L_2$ must be a write-through cache The associativity of $L_2$ must be greater than that of $L_1$ The $L_2$ cache must be at least as large as the $L_1$ cache

Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor? It must be a trap instruction It must be a privileged instruction An exception cannot be allowed to occur during execution of an RFE instruction

Which of the following is/are true of the auto-increment addressing mode? It is useful in creating self-relocating code If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation The amount of increment depends on the size of the data item accessed

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to

$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent? $P ∨ \neg Q$ $\neg(\neg P ∧ Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$