GATE CS question library

The minterm expansion of $f(P,Q,R) = PQ +Q \bar{R}+P\bar{R}$ is

Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$. Which one of the statements below expresses best the meaning of the formula, $\qquad∀x∃y∃t(¬F(x,y,t))$

Consider the following matrix $$A = \left[\begin{array}{cc}2 & 3\\x & y \end{array}\right]$$ If the eigenvalues of A are $4$ and $8$, then

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$

What is the probability that divisor of $10^{99}$ is a multiple of $10^{96}$?

Consider a company that assembles computers. The probability of a faulty assembly of any computer is $p$. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of $q$. What is the probability of a computer being declared faulty?

What is the value of $\displaystyle\lim_{n \to \infty}\left(1 - \frac{1}{n}\right)^{2n}$ ?

Consider the set $S = \{1, ω, ω^2\}$, where $ω$ and $ω^2$ are cube roots of unity. If $*$ denotes the multiplication operation, the structure $(S, *)$ forms

What is the possible number of reflexive relations on a set of $5$ elements?

Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with $\xi(S) = \xi(T)$, then

A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the 0$^{th}$ sector is addresses as $\langle 0, 0, 0 \rangle$, …

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common sub-sequence (LCS) of $X[m]$ and $Y[n]$ as …

Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ $\text{Catalog}(\underline {\text{sid:integer, pid:integer}}, \text{cost:real})$ Assume that, in the suppliers relation above, …

Frames of $1000\text{ bits}$ are sent over a $10^6$ bps duplex link between two hosts. The propagation time is $25ms$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). Let $I$ be the minimum number of bits $(I)$ that will be required to represent the sequence numbers distinctly assuming that no time …

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

Consider a binary max-heap implemented using an array. What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$

Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). What is the minimum number of bits $(I)$ that will be required to represent the sequence numbers distinctly? Assume …

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences $X[m]$ and $Y[n]$ of lengths $m$ and $n$, respectively with indexes of $X$ and $Y$ starting from $0$. We wish to find the length of the longest common sub-sequence (LCS) of $X[m]$ and $Y[n]$ as …

Consider the following relational schema: $\text{Suppliers}(\underline{\text{sid:integer}},\text{ sname:string, city:string, street:string})$ $\text{Parts}(\underline{\text{pid:integer}}, \text{ pname:string, color:string})$ $\text{Catalog}(\underline {\text{sid:integer, pid:integer}}, \text{cost:real})$ Consider the following relational query on the …

Which of the following statements are TRUE? The context diagram should depict the system as a single bubble. External entities should be identified clearly at all levels of DFDs. Control information should not be represented in a DFD. A data store can be connected wither to another data store or to an external entity.