GATE CS question library

Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation. employee (empId, empName, empAge) dependent (depId, eId, depName, depAge) Consider the following relational algebra query: …

Consider the transactions $T1, T2, \:\text{and} \:T3$ and the schedules $S1 \:\text{and} \:S2$ given below. $T1: r1(X); r1(Z); w1(X); w1(Z)$ $T2: r2(Y); r2(Z); w2(Z)$ $T3: r3(Y); r3(X); w3(Y)$ $S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)$ $S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)$ …

An $IP$ router with a $\text{Maximum Transmission Unit (MTU)}$ of $1500$ bytes has received an $IP$ packet of size $4404\text{ bytes}$ with an $IP$ header of length $20\text{ bytes}$. The values of the relevant fields in the header of the third $IP$ fragment generated by the router for this packet are:

Every host in an $\textsf{IPv4}$ network has a $1\text{-second}$ resolution real-time clock with battery backup. Each host needs to generate up to $1000$ unique identifiers per second. Assume that each host has a globally unique $\textsf{IPv4}$ address. Design a $50\text{-bit}$ globally unique ID for this purpose. After what period (in seconds) …

An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address $131.23.151.76$. The router's routing table has the following entries: …

Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP v4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D? TTL Checksum Fragment Offset

A bit-stuffing based framing protocol uses an $\text{8-bit}$ delimiter pattern of $01111110.$ If the output bit-string after stuffing is $01111100101,$ then the input bit-string is:

In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

A prime attribute of a relation scheme $R$ is an attribute that appears

What is the optimized version of the relation algebra expression $\pi_{A1}(\pi_{A2}(\sigma_{F1}(\sigma_{F2}(r))))$, where $A1, A2$ are sets of attributes in $r$ with $A1 \subset A2$ and $F1,F2$ are Boolean expressions based on the attributes in $r$?

A system uses $3$ page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? $\text{4, 7, 6, 1, 7, 6, 1, 2, 7, 2}$

In the context of modular software design, which one of the following combinations is desirable?

One of the purposes of using intermediate code in compilers is to

Which of the following statements are CORRECT? Static allocation of all data areas by a compiler makes it impossible to implement recursion. Automatic garbage collection is essential to implement recursion. Dynamic allocation of activation records is essential to implement recursion. Both heap and stack are essential to implement recursion.

Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$. Which one of the following is TRUE?

The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______. $$a^*b^*(ba)^*a^*$$

You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

Consider the following rooted tree with the vertex labeled $P$ as the root: The order in which the nodes are visited during an in-order traversal of the tree is

The minimum number of arithmetic operations required to evaluate the polynomial $P(X) = X^5+4X^3+6X+5$ for a given value of $X$, using only one temporary variable is ______.