GATE CS question library

Consider the following statements regarding the front-end and back-end of a compiler. S1: The front-end includes phases that are independent of the target hardware. S2: The back-end includes phases that are specific to the target hardware. S3: The back-end includes phases that are specific to the programming language used in the source code. Identify the …

Which one of the following sequences when stored in an array at locations $A[1], \ldots, A[10]$ forms a max-heap?

Let $\textsf{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 $\textsf{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 …

Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state. Which one of the following regular expressions correctly describes the language accepted by …

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

Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?

Suppose two hosts are connected by a point-to-point link and they are configured to use $\textsf{Stop-and-Wait}$ protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.

Let $$A=\left[\begin{array}{llll} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{array}\right]$$ and $$B=\left[\begin{array}{llll} 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{array}\right]$$ Let …

Consider the following definition of a lexical token $\textbf{id}$ for an identifier in a programming language, using extended regular expressions: …

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k>m$. Which one of the following is the best hashing strategy to counteract the adversary?

The output of a $2$-input multiplexer is connected back to one of its inputs as shown in the figure. Match the functional equivalence of this circuit to one of the following options.

Which one or more of the following need to be saved on a context switch from one thread $\text{(T1)}$ of a process to another thread $\text{(T2)}$ of the same process?

Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?

Which of the following statements is/are $\text{CORRECT}?$

Which of the following statements is/are $\text{INCORRECT}$ about the $\textsf{OSPF (Open Shortest Path First)}$ routing protocol used in the Internet?

Geetha has a conjecture about integers, which is of the form $$\forall x(P(x) \Longrightarrow \exists y Q(x, y)),$$ where $P$ is a statement about integers, and $Q$ is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

Which one or more of the following $\text{CPU}$ scheduling algorithms can potentially cause starvation?

Let $$\qquad f(x)=x^{3}+15 x^{2}-33 x-36$$ be a real-valued function. Which of the following statements is/are $\text{TRUE}?$

Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^{2}.$ Which of the following statements is/are $\text{TRUE}?$

Let $A$ be the adjacency matrix of the graph with vertices $\{1,2,3,4,5\}.$ Let $\lambda_{1}, \lambda_{2}, \lambda_{3}, \lambda_{4}$, and $\lambda_{5}$ be the five eigenvalues of $A$. Note that these eigenvalues need not be distinct. The value of $\lambda_{1}+\lambda_{2}+\lambda_{3}+\lambda_{4}+\lambda_{5}=$____________