35. Consider the following relational schema.
Students(rollno: integer, sname: string)
Courses(courseno: integer, cname: string)
Registration(rollno: integer, courseno: integer, percent: real)
Which of the following queries are equivalent to this query in English?
$“$Find the distinct names of all students who score more than 90% in the course numbered $107”$
(I) SELECT DISTINCT S.sname
FROM Students as S, Registration as R
WHERE R.rollno=S.rollno AND R.courseno=107 AND R.percent >90
(II)$ ∏_{\text{sname}}(σ_{\text{courseno=107} ∧ \text{percent>90}} ($Registration $⋈$ Students$)) $
(III)$ \{T | ∃S∈Students, ∃R∈Registration $$( S.rollno=R.rollno ∧ R.courseno=107 ∧ R.percent>90 ∧T.sname=S.sname)\} $
(IV) $ \{<S_N> | ∃S_R∃R_P ( <S_R, S_N>∈\text{Students} ∧ <S_R, 107, R_P>∈\text{Registration} ∧ R_P>\text{90})\}$
37. In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and
the fragment offset value is 300. The position of the datagram, the sequence numbers of the first
and the last bytes of the payload, respectively are
43. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which
one of the following is the postorder traversal sequence of the same tree?
(A) 10, 20, 15, 23, 25, 35, 42, 39, 30
(B) 15, 10, 25, 23, 20, 42, 35, 39, 30
(C) 15, 20, 10, 23, 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30
Unmarked
45. Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction
(FI), Decode Instruction ($DI$), Fetch Operand ($FO$), Execute Instruction ($EI$) and Write Operand
($WO$). The stage delays for $FI$, $DI$, $FO$, $EI$ and $WO$ are 5 ns, 7 ns, 10 ns, 8 ns and 6 ns, respectively.
There are intermediate storage buffers after each stage and the delay of each buffer is 1 ns. A
program consisting of 12 instructions $I1$, $I2$, $I3$, …, $I12$ is executed in this pipelined processor.
Instruction $I4$ is the only branch instruction and its branch target is $I9$. If the branch is taken during
the execution of this program, the time (in ns) needed to complete the program is
The procedure given below is required to find and replace certain characters inside an input character string supplied in array $A$.
The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc.
Array $A$ has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed.
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}
The procedure is tested with the following four test cases.
(1) oldc = $“abc”$, newc = $“dab”$
(2) oldc = $“cde”$, newc = $“bcd”$
(3) oldc = $“bca”$, newc = $“cda”$
(4) oldc = $“abc”$, newc = $“bac”$
50. The tester now tests the program on all input strings of length five consisting of characters $`aʼ$,
$ʻbʼ$, $ʻcʼ$, $ʻdʼ$ and $ʻeʼ$ with duplicates allowed. If the tester carries out this testing with the four
test cases given above, how many test cases will be able to capture the flaw?
51. If array $A$ is made to hold the string $“abcde”$, which of the above four test cases will be successful
in exposing the flaw in this procedure?
A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table
organization. The page table base register stores the base address of the first-level table ($T_1$), which
occupies exactly one page. Each entry of $T_1$ stores the base address of a page of the second-level table ($T_2$).
Each entry of $T_2$ stores the base address of a page of the third-level table ($T_3$). Each entry of $T_3$ stores a page
table entry ($PTE$). The $PTE$ is 32 bits in size. The processor used in the computer has a 1 $MB$ 16-way set
associative virtually indexed physically tagged cache. The cache block size is 64 bytes.
52. What is the size of a page in $KB$ in this computer?
53. What is the minimum number of page colours needed to guarantee that no two synonyms map to
different sets in the processor cache of this computer?
Relation $R$ has eight attributes $ABCDEFGH$. Fields of $R$ contain only atomic values.
$F={CH→G, A→BC, B→CFH, E→A, F→EG}$ is a set of functional dependencies ($FD$s) so that $F^+$ is exactly the set of FDs that hold for $R$.
54. How many candidate keys does the relation $R$ have?
56. Which one of the following options is the closest in meaning to the word given below?
Nadir
57. Complete the sentence:
Universalism is to particularism as diffuseness is to _______________.
58. What will be the maximum sum of 44, 42, 40, ...... ?
59. Were you a bird, you ___________________ in the sky.
60. Choose the grammatically INCORRECT sentence:
61. Find the sum of the expression
$\frac{1}{\sqrt{1}+\sqrt{2}}+\frac{1}{\sqrt{2}+\sqrt{3}}+\frac{1}{\sqrt{3}+\sqrt{4}}+............+\frac{1}{\sqrt{80}+\sqrt{81}}$
62. Out of all the 2-digit integers between 1 and 100, a 2-digit number has to be selected at random.
What is the probability that the selected number is not divisible by 7?
63. After several defeats in wars, Robert Bruce went in exile and wanted to commit suicide. Just before
committing suicide, he came across a spider attempting tirelessly to have its net. Time and again,
the spider failed but that did not deter it to refrain from making attempts. Such attempts by the
spider made Bruce curious. Thus, Bruce started observing the near-impossible goal of the spider to
have the net. Ultimately, the spider succeeded in having its net despite several failures. Such act of
the spider encouraged Bruce not to commit suicide. And then, Bruce went back again and won
many a battle, and the rest is history.
Which one of the following assertions is best supported by the above information?
64. A tourist covers half of his journey by train at 60 km/h, half of the remainder by bus at 30 km/h and
the rest by cycle at 10 km/h. The average speed of the tourist in km/h during his entire journey is
65. The current erection cost of a structure is Rs. 13,200. If the labour wages per day increase by 1/5 of
the current wages and the working hours decrease by 1/24 of the current period, then the new cost
of erection in Rs. is
GATECSE