MCQs
Total Questions : 65
| Page 2 of 7 pages
Question 11.
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.
What is the minimum number of page colours needed to guarantee that no two synonymsmap to
different sets in the processor cache of this computer?
Answer: Option C. -> 8
As the page size is `2^(13)`Bytes and page coloring is asked so we divide cache size by page
size and group 16 pages in one set.
Number of pages in cache = 1MB/8KB = 128 pages
Number of set in cache=128/16=8 sets
Take any page of LAS, it will be mapped with cache on any one of these 8 sets (set
association mapping).
For any two synonym to map with same set they should be colored with
same color of that respective set.
So minimum we need 8 colors for this mapping.
Question 12.
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.
F = {CH`rightarrow` G, A`rightarrow` BC, B`rightarrow` CFH, E`rightarrow` A,F`rightarrow` EG} is a set of functional dependencies
(FDs) so that `F^+` is exactly the set of FDs that hold for R
How many candidate keys does the relation R have?
Answer: Option B. -> 4
Candidate keys are AD, BD, ED and FD
Question 13.
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values.
F = {CH`rightarrow` G, A`rightarrow` BC, B`rightarrow` CFH, E`rightarrow` A,F`rightarrow` EG} is a set of functional dependencies (FDs) so that `F^+` is exactly the set of FDs that hold for R
The relation R is Answer: Option A. -> in INF, but not in 2NF
A`rightarrow` BC, B`rightarrow` CFH and F`rightarrow` EG are partial dependencies. Hence it is in
1NF but not in 2NF
Question 14.
The following code segment is executed on a processor which allows only register operands
in its instructions. Each instruction can have almost two source operands and one destination
operand. Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a {
y = a *a;
}
else {
d = d *d;
e = e*e;
}
What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation Answer: Option B. -> 4
c = a + b; `R_2` `leftarrow` `R_1` + `R_2`
d = c * a; `R_3` `leftarrow` `R_2` * `R_1`
e = c + a; `R_4` `leftarrow` `R_2` + `R_1`
x = c * c; `R_2` `leftarrow` `R_2` * `R_2`
if (x > a) CMP `R_2` `R_1`
{ y = a * a; } `R_1` `leftarrow` `R_1` * `R_1`
else {
d = d * d; `R_3` `leftarrow` `R_3` * `R_3`
e = e * e; `R_4` `leftarrow` `R_4` * `R_4`
}
In the above code minimum number of registers needed are = 4
Question 15.
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.
What is the size of a page in KB in this computer?
Answer: Option C. -> 8
Let the page size be `2^x` Bytes.
Then, the page offset = X bits
46 - x x
Now, we are using 3-level paging. First level page table is contained in one page. Each page
table entry is 32-bit.
The size of `T_3` is = `(2^(46) ast 2^2)/2^x` = `2^(46+2-x)` = [ `because` PTE = 32 bit = 4B `2^2`B]
The size of `T_2` is = `(2^(46+2-x) ast 2^2)/2^x` = `2^(46+4-2x)`
The size of `T_1` is = `(2^(46+4-x) ast 2^2)/2^x`= `2^(46+6-3x)` = `2^x` [`because` `T_1`occupies exactly one page]
`:.` 46 + 6 - 3x = x `Rightarrow` x = 13
So, page size = `2^(13)`B `2^3`kB = 8kB.
Question 16.
The following code segment is executed on a processor which allows only register operands
in
its instructions. Each instruction can have almost two source operands and one destination
operand.
Assume that all variables are dead after this code segment
c = a + b;
d = c * a;
e = c + a;
x = c *c;
if (x > a {
y = a *a;
}
else {
d = d *d;
e = e*e;
}
Suppose the instruction set architecture of the processor has only two registers. The only
allowed
compiler optimization is code motion, which moves statements from one place to
another while
preserving correctness. What is the minimum number of spills to memory in
the compiled code?
Answer: Option B. -> 1
After applying the code motion optimization the statement d = c*a; and e = c + a; can be moved
down to else block as d and e are not used anywhere before that and also value of a and c is
not changing.
c = a + b; `R_2` `leftarrow` `R_1` + `R_2`
x = c*c; `R_2` `leftarrow` `R_2` *`R_2` [spill c]
1 memory spill to store
the value of c in memory
if (x > a) CMP `R_2` `R_1`
{ y = a*a; } `R_2` `leftarrow` `R_1` *`R_1`
else{ `R_2` `leftarrow` [spill c]
`R_2` `leftarrow` `R_2`* `R_1`
d = c * a; `R_2` `leftarrow` `R_2`* `R_2`
d = d * d;
`R_2` `leftarrow` [spill c]
e = c + a; `R_2` `leftarrow` `R_2` + `R_1`
e = e* e; `R_2` `leftarrow` `R_2` * `R_2`
}
In the above code total number of spills to memory is 1
Question 17.
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] = = olde [j]) A[i] = newe [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"
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?
Answer: Option C. -> 3 and 4 only
Now for string "abcde" in array A, both test case (3) and (4) will be successful in finding the
flaw, as explained in above question
Answer: Option D. -> `not` `exists` x(F(x) ^ P(x))
"None of my friends are perfect."
= `forall` x F(x) `rightarrow` `not` P(x))
= `forall` x (`not` F(x) v `not` P(x))
= `not` `exists` x (F(x) ^ P(x))
Question 19.
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] = = olde [j]) A[i] = newe [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"
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?
Answer: Option B. -> Only two
Flaw in this given procedure is that one character of Array 'A' can be replaced by more than
one
character of newc array, which should not be so.Test case (3) and (4) identifies this flaw
as they
are containing 'oldc' and 'newc' array characters arranged in specific manner.
Following string
can reflect flaw, if tested by test case (3).
initially i = j = 0
A = `underline("b)`cda" oldc = `underline("b)` c a" newc = `underline("c)`da"
`uparrow` `uparrow` `uparrow`
i = 0 j = 0 j = 0
b = b so replaced by c
Next i = 0 & j = 1
A = `underline("c)`cda" oldc = "b`underline(c)`a" newc = "c`underline(d)`a"
`uparrow` `uparrow` `uparrow`
i = 0 j = 1 j = 1
c = c so replaced by d
Likewise single character 'b' in A is replaced by 'c' and then by 'd'.
Same way test case (4) can also catch the flaw
Question 20.
The line graph L(G) of a simple graph G is defined as follows:
- There is exactly one vertex v(e) in L(G) for each edge e in G.
- For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e
and e' are incident with the same vertex in G.
Which of the following statements is/are TRUE?
(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.
Answer: Option A. -> P only
P) The line graph of a cycle is a cycle
a V(`e_1`) b V(`e_1`)
V(`e_4`) G V(`e_2`) `Rightarrow` L(G) : V(`e_4 `) V(`e_2`)
d V(`e_3`) c V(`e_3`)
is also cycle graph
R) Line graph of planar graph need not be planar always. Consider the following example.
Consider
the following planar graph (star graph)
c
a d V(`e_1`)
V(`e_1`) `Rightarrow` L(G) :
V(`e_4`) V(`e_5`)
b V(`e_2`) V(`e_5`)
V(`e_3`) V(`e_2`)
e f V(`e_3`) V(`e_4`)
S) Hence line graph of planar graph need not be planar(Here we got `K_5` which is not planar).a V(`e_1`)
''''' `Rightarrow` L(G) :
b V(`e_3`) V(`e_2`)
V(`e_3`)
V(`e_2`)
c d
The line graph of a tree need not be tree.
Latest Videos
Latest Test Papers
Login With Google
Old way of Login
Login With Email