GATE CS question library

Suppose the adjacency relation of vertices in a graph is represented in a table Adj $(X,Y).$ Which of the following queries cannot be expressed by a relational algebra expression of constant length?

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

Which of the following statements is false?

Where does the swap space reside?

The process of assigning load addresses to the various parts of the program and adjusting the code and the data in the program to reflect the assigned addresses is called

Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct?

Consider any array representation of an $n$ element binary heap where the elements are stored from index $1$ to index $n$ of the array. For the element stored at index $i$ of the array $(i \leq n)$, the index of the parent is

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort?

A CPU has two modes -- privileged and non-privileged. In order to change the mode from privileged to non-privileged

Given the following karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map?

A processor needs software interrupt to

Suppose a processor does not have any stack pointer registers, which of the following statements is true?

A low memory can be connected to 8085 by using

Which of the following statements is false?

More than one word are put in one cache block to:

Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least

Which of the following statements is true?

Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct?

Consider two well-formed formulas in propositional logic $F_1: P \Rightarrow \neg P$ $F_2: (P \Rightarrow \neg P) \lor ( \neg P \Rightarrow P)$ Which one of the following statements is correct?

Consider the following relations: $R_1\:(a,b)$ iff $(a+b)$ is even over the set of integers $R_2 \:(a,b)$ iff $(a+b)$ is odd over the set of integers $R_3 \:(a,b)$ iff $a.b > 0$ over the set of non-zero rational numbers $R_4\:(a,b)$ iff $|a-b| \leq 2$ over the set of natural numbers Which of the following statements is correct?