GATE CS question library

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.

Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE? The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph. The cyclomatic complexity of a module is the number of decisions in the module plus one, where a decision …

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$, …

Let $G(x)$ be the generator polynomial used for CRC checking. What is the condition that should be satisfied by $G(x)$ to detect odd number of bits in error?

In the RSA public key cryptosystem, the private and public keys are $(e, n)$ and $(d, n)$ respectively, where $n=p \times q$ and $p$ and $q$ are large primes. Besides, $n$ is public and $p$ and $q$ are private. Let $M$ be an integer such that $0<M<n$ and $\phi(n) = (p-1)(q-1)$. Now consider the following equations. …

While opening a $TCP$ connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order $32$ bits of the counter of the ToD clock is to be used for the initial sequence numbers. The clock counter increments once per milliseconds. The maximum packet lifetime is given to be …

Consider two transactions $T_1$ and $T_2$, and four schedules $S_1, S_2, S_3, S_4$, of $T_1$ and $T_2$ as given below: $T_1: R_1[x]W_1[x]W_1[y]$ $T_2: R_2[x]R_2[y]W_2[y]$ $S_1: R_1[x]R_2[x]R_2[y] W_1[x] W_1[y] W_2[y]$ $S_2: R_1[x]R_2[x]R_2[y] W_1[x] W_2[y] W_1[y]$ $S_3: R_1[x]W_1[x]R_2[x] W_1[y] R_2[y] W_2[y]$ …

The following key values are inserted into a $B^+$ - tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The $B^+$ - …

Let $R$ and $S$ be relational schemes such that $R=\{a,b,c\}$ and $S=\{c\}.$ Now consider the following queries on the database: $\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$ …

Which of the following statements are TRUE? There exist parsing algorithms for some programming languages whose complexities are less than $\Theta(n^3)$ A programming language which allows recursion can be implemented with static storage allocation. No L-attributed definition can be evaluated in the framework of bottom-up parsing. Code improving …

The above DFA accepts the set of all strings over $\{0,1\}$ that