HCU PHD CS MAY 2011
Question 1 
Heap sort algorithm is the same as which of the following algorithms, except for the fact that is uses the heap data structure
bubble sort  
Shell sort  
Merge Sort
 
Selection sort 
Question 1 Explanation:
Heap sort algorithm is same as selection sort algorithm ,because in selection sort we find the min element from the array and then swap that selected min element with first element of the list and then continue with the remaining n1 elements, similarly in heap sort we find the min or max element and then we swap the selected element with the last element of the list and then continue with the remaining n1 elements.
Question 2 
Consider the graph G given below:
Th graph G is
Hamiltonian and Euclidean  
Euclidean but not Hamiltonian  
hamiltonian but not Euclidean  
neither hamiltonian nor Euclidean 
Question 3 
Which of the following is in correct LEXICOGRAPHIC order when using ASCII code?
a, an, OR, AND  
1,5,15,125  
AND, OR, a, an  
1, 15,125,5 
Question 3 Explanation:
Option A is wrong since ascii value of ‘a’ is 97 and ascii value of ‘O’ is 79 and ascii value of A is 65 so the correct lexographic order in this option will be AND,OR,a,an.
Option B is wrong since ascii since ascii value of 5’’ is 101 and of ‘1’ is 97,so the correct lexographic order for the sequence given in this option is 1,125,15,5.
Option C is correct as it can be seen in Option A explaination.
Option D is wrong as it can be seen in explaination of Option B.
Option B is wrong since ascii since ascii value of 5’’ is 101 and of ‘1’ is 97,so the correct lexographic order for the sequence given in this option is 1,125,15,5.
Option C is correct as it can be seen in Option A explaination.
Option D is wrong as it can be seen in explaination of Option B.
Question 4 
The number of times the statement "x=x+1" is executed in the following program fragment using Theta notation in terms of n is
j=n;
while(j>=1)
{
for(i=1; i<=j; ++i)
x=x+1;
j=j/2;
}
Θ(log n)  
Θ(n)  
Θ(n^{2})  
Θ(n log n) 
Question 4 Explanation:
* For first while loop iteration,
j=n, ‘for’ loop will run n times.
* For second while loop iteration,
j=n/2, ‘for’ loop will run n/2 times.
* For third while loop iteration,
j=n/2^{2}, ‘for’ loop will run n/22 times.
⋮
For kth while loop iteration,
j=n/2^{k1}, for loop will run n/2^{k1} times
j=n, ‘for’ loop will run n times.
* For second while loop iteration,
j=n/2, ‘for’ loop will run n/2 times.
* For third while loop iteration,
j=n/2^{2}, ‘for’ loop will run n/22 times.
⋮
For kth while loop iteration,
j=n/2^{k1}, for loop will run n/2^{k1} times
Question 5 
A list of integers is almost sorted with only the largest number being out of place. if this information is not known to the algorithm, then which of the following algorithms sort the list the fastest?
bubble sort  
Selection sort  
insertion sort  
Shell sort 
Question 5 Explanation:
Whenever the list is almost sorted then insertion sort will always take O(n) time .But for some sequences even the list is almost sorted then also bubble sort might take O(n^2).And Selection sort will always take O(n^2) time.
Question 6 
The Depth First and Breadth First traversal Algorithms visit the nodes in exactly the same order in which of the following type of graphs:
binary tree  
linear Chain  
complete graph  
none of the above 
Question 6 Explanation:
Depth first traversal algorithm visits the node depth wise and breadth first traversal algorithm visits the node level wise. So among the given options only in linear chain both Depth first traversal algorithm and
Breadth first traversal algorithm visits the node in the exactly same order because in linear chain nodes either we visit them level wise or depth wise the order of visiting will be same.
Breadth first traversal algorithm visits the node in the exactly same order because in linear chain nodes either we visit them level wise or depth wise the order of visiting will be same.
Question 7 
The postfix expression ABC+*DE*/is equivalent to which of the following prefix expression?
*/*A+BCDE  
/*A+BC*DE  
/+*ABC*DE  
*/+*ABCDE 
Question 7 Explanation:
The given postfix expression is,
ABC+*DE*/
So the binary tree for above given postfix expression is,
No the prefix expression for above binary tree is nothing but the preorder traversal sequence of above binary tree. So the preorder sequence of above binary tree is,
/*A+BC*DE
ABC+*DE*/
So the binary tree for above given postfix expression is,
No the prefix expression for above binary tree is nothing but the preorder traversal sequence of above binary tree. So the preorder sequence of above binary tree is,
/*A+BC*DE
Question 8 
Algorithm for finding strongly connected components in linear time makes use of
BFS  
DFS  
Shortest path
 
None of the above 
Question 8 Explanation:
Both BFS and DFS can be used to find strongly connected components in linear time O(V+E).
Question 9 
What is the value of the C language expression n*n + 1*n++ + 1?
n^{2} + n 1  
n^{2} + 2n 1  
n^{2} + 2
 
n^{2}  
None of the given answer is correct .The correct answer is (n^2)+1. 
Question 9 Explanation:
Since key points before solving this question,
Unary operators have higher precedence than arithmetic operators.
If ‘’ or ‘++’ unary operator is before n then that will be considered in the current equation and not the ‘’ or ‘++’ which is after n, since it will be calculated after calculating the current equation.
So,
n*n+1*n+++1
= (n  1) * n + 1 * n + 1
= n^{2}  n + n + 1
= n^{2} + 1
Unary operators have higher precedence than arithmetic operators.
If ‘’ or ‘++’ unary operator is before n then that will be considered in the current equation and not the ‘’ or ‘++’ which is after n, since it will be calculated after calculating the current equation.
So,
n*n+1*n+++1
= (n  1) * n + 1 * n + 1
= n^{2}  n + n + 1
= n^{2} + 1
Question 10 
Which of the following results in the maximum value if their declarations are
int x=5, y=4;
double z=10.0;
char c=’a’;
(Assume the ASCII value of ‘a’ is 97)
z*y/x+c  
z/y*x+c  
z+c/y*x  
z/c+y*x 
Question 10 Explanation:
Whenever a float is calculated with integer we get float value.But when integer is calculated with integer value we will get integer value as a result even if the original value comes as float.
Let’s check option wise,
A)
z * y/x + c
= 10.0 ⅘ + 97
= 40.0/5 + 97
= 8.0 + 97
= 105
B)
z/y * x + c
= 10.0/4 * 5 + 97
= 2.5 * 5 + 97
= 12.5 + 97
= 109.5
C)
z + c/y * x
= 10.0 + 97/4 * 5
= 10.0 + 24 * 5
= 10.0 + 120
= 130
D)
z/c + y * x
= 10.0/97 + 4 * 5
= 0.1031 + 20
= 20.1031
Let’s check option wise,
A)
z * y/x + c
= 10.0 ⅘ + 97
= 40.0/5 + 97
= 8.0 + 97
= 105
B)
z/y * x + c
= 10.0/4 * 5 + 97
= 2.5 * 5 + 97
= 12.5 + 97
= 109.5
C)
z + c/y * x
= 10.0 + 97/4 * 5
= 10.0 + 24 * 5
= 10.0 + 120
= 130
D)
z/c + y * x
= 10.0/97 + 4 * 5
= 0.1031 + 20
= 20.1031
Question 11 
Consider the following function:
double power(double base, unsigned int exponent)
{
if (exponent == 0)
return 1.0;
else if (even (exponent))
return power(base*base, exponent/2);
else
return power(base*base, exponent/2)*base;
}
How many multiplications are executed as a result of the call power(5.0, 12)? (Do not include divisions in this total)
5  
8  
9  
12  
None of the given options is correct.Correct answer is 6. 
Question 11 Explanation:
Question 12 
Consider the following program segment:
x=b; k=n; z=1;
while(k!=0)
{
If (odd(k))
z=z*x;
x=x*x;
k=k/2;
}
When the loop terminates. Which of the following must be true?
x=b^{n}  
z=b^{n}  
b=z^{n}  
b=x^{n} 
Question 12 Explanation:
Let’s take example,
x=b=2
k=n=3
z=1
Now,
k!=0 and k is odd, so
z= 1 x 2 = 2
x = 2 x 2 = 4
k = (3/2)=1
Again, k!=0 and k is odd, so
z= 2 x 4 = 8
x= 4 x 4= 16
k = (½) = 0
Since k=0, so while loop will be terminated.
So, finally the values are,
z=8
x=16
k=0
b=2
n=3
Now, let’s check option wise,
A)
x = b ^{n}
x = 2 ^{3} = 8
Not correct.
B)
z = n ^{n}
z = 2 ^{3} = 8
Correct.
C)
b = z^{n} = 8 ^{3 Not correct. D) b = xn = 16 3 Not correct.}
x=b=2
k=n=3
z=1
Now,
k!=0 and k is odd, so
z= 1 x 2 = 2
x = 2 x 2 = 4
k = (3/2)=1
Again, k!=0 and k is odd, so
z= 2 x 4 = 8
x= 4 x 4= 16
k = (½) = 0
Since k=0, so while loop will be terminated.
So, finally the values are,
z=8
x=16
k=0
b=2
n=3
Now, let’s check option wise,
A)
x = b ^{n}
x = 2 ^{3} = 8
Not correct.
B)
z = n ^{n}
z = 2 ^{3} = 8
Correct.
C)
b = z^{n} = 8 ^{3 Not correct. D) b = xn = 16 3 Not correct.}
Question 13 
Consider the following code:
#include
main()
{
float sum=0.0, j=1.0, i=2.0;
while(i/j > 0.001)
{
j=j+j;
sum=sum+i/j;
printf(“%f \n”, sum);
}
When this code is executed, which of the following integers best approximates the last number that is printed?
0  
1  
2  
3 
Question 14 
Thrashing problem in operating systems can not be solved by
1. Increasing the degree of multiprogramming
2. Increasing the clock speed of the processor
3. Decreasing the degree of multiprogramming
4. Increasing the memory
(2), (3) and (4)  
(1), (3) and (4)  
(1) and (2)  
(1) and (4) 
Question 14 Explanation:
In virtual storage system thrashing is the situation in which excessive pagefault takes place.Thrashing can be reduced by either decreasing degree of multiprogramming or increasing the memory size.But thrashing cannot be solved by either increasing degree of multiprogramming or increasing the clock speed of the processor.
Question 15 
In operating systems when does multilevel feedback scheduling become FCFS?
When the time for migration is infinite  
When the priority is same for all processes  
When time slice is same  
Quantum of time needed by each process is same 
Question 16 
Consider a reference sequence r_{1},r_{2},r_{3},....,r_{n}, with a FIFO page replacement algorithm and that gives K_{i}
Page faults with i page frames allocated. When the number of page frames is j, then for Kj and Ki which of the following is always TRUE when i
K_{i} < K_{j}  
K_{i} = K_{j}  
K_{i} > K_{j}  
None of the above 
Question 16 Explanation:
Generally when no. of page frames increases then no. of page faults decreases or remain equals but does not increases .But in FIFO when the no. of page frames increases then no. of page faults might get increased also due to Belady's anomaly.
Hence we can say that when i
K_{i} < K_{i}
or K_{i} = K_{j}
or K_{i} > K_{j}
Hence we can say that when i
or K_{i} = K_{j}
or K_{i} > K_{j}
Question 17 
If a system has 1 GB RAM with a page size of 8KB and the operating system occupies 16 MB of RAM, how many page frames does the system have for user processes?
129024  
120924  
131072  
119864 
Question 17 Explanation:
Question 18 
In databases, spurious may occur due to
1. Bad normalization
2. Theta joins
3. Updating tables from joins other than theta joins
(2) only  
(1) and (2) only
 
(1) and (3) only  
(2) and (3) only 
Question 19 
In the context of databases, entity integrity constraint states that
Primary key value can not be NULL  
Foreign key value can not be NULL  
Every relation has at least one superkey
 
Superkey of smallest size should be chosen as primary key 
Question 19 Explanation:
The entity integrity constraint states that primary key value can't be null. This is because the primary key value is used to identify individual rows in relation and if the primary key has a null value, then we can't identify those rows. A table can contain a null value other than the primary key field.
Question 20 
Suppose there is an open(external) hash table with four buckets, numbered 0,1,2,3. Suppose integers are hashed into these buckets using hash function h(x)=r mod 4. If the sequence of perfect squares 1,4,9,...i^{2} … is hashed into the table, then as the total number of entries in the table grows, what will happen?
All buckets will receive approximately the same number of entries  
All entries will go into particular bucket  
Three of the buckets will each get approximately onethird of the entries, and the fourth bucket will remain empty  
Two of the buckets will get approximately half the entries, and the other two will remain almost empty 
Question 20 Explanation:
Now let’s enter the elements in the hash table using hash function,
h(x) = r mod 4
And the collision will be resolved using chaining, since the table is an open hash table.
⟶ Insert 1,
h(x) = 1 mod 4 = 1
⟶ Insert 4,
h(x) = 4 mod 4 = 0
⟶ Insert 9,
h(x) = 9 mod 4 = 1
⟶ Insert 16,
h(x) = 16 mod 4 = 0
⟶ Insert 25,
h(x) = 25 mod 4 = 1
⟶ Insert 36,
h(x) = 36 mod 4 = 0
⟶ Insert 49,
h(x) = 49 mod 4 = 1
⟶ Insert 64,
h(x) = 64 mod 4 = 0
⟶ Insert 81,
h(x) = 81 mod 4 = 1
⟶ Insert 100,
h(x) = 100 mod 4 = 0
Question 21 
The truth table for (p V q) V (p ⋀ r) is the same as truth table for
(p V q) ⋀ (p V r)  
(p V q) ⋀ r  
(p V q) ⋀ (p ⋀ r)
 
p V q 
Question 21 Explanation:
The given expression in question is,
(p ⋁ q) ⋁ (p ⋀ r)
Note that ‘⋁’ also means ‘+’ and ‘⋀’ also means ‘∙’
So, above expression can also be written as,
(p +q) + (pr)
= p + q + pr
= p(1 + r) + q
= p + q (∵ 1+n = 1)
Now let’s check option wise,
A)
(p ⋁ q) ⋀ (p ⋁ r)
= (p +q) ∙ (p+r)
= p + qr
which is not equal to p+q
B)
(p⋁q) ⋀ r
= (p + q) ∙ r
= pr + qr
which is not equal to p+q
C)
(p⋁q) ⋀ (p⋀r)
= (p + q) ∙ (pr)
= pr + pqr
= pr (1 + q)
= pr (∵ 1+n = 1)
which is not equal to p+q
D)
p ⋁ q
= p + q
which is equal to p+q. Hence answer.
(p ⋁ q) ⋁ (p ⋀ r)
Note that ‘⋁’ also means ‘+’ and ‘⋀’ also means ‘∙’
So, above expression can also be written as,
(p +q) + (pr)
= p + q + pr
= p(1 + r) + q
= p + q (∵ 1+n = 1)
Now let’s check option wise,
A)
(p ⋁ q) ⋀ (p ⋁ r)
= (p +q) ∙ (p+r)
= p + qr
which is not equal to p+q
B)
(p⋁q) ⋀ r
= (p + q) ∙ r
= pr + qr
which is not equal to p+q
C)
(p⋁q) ⋀ (p⋀r)
= (p + q) ∙ (pr)
= pr + pqr
= pr (1 + q)
= pr (∵ 1+n = 1)
which is not equal to p+q
D)
p ⋁ q
= p + q
which is equal to p+q. Hence answer.
Question 22 
The number of distinct regular binary trees that can be constructed with 7 nodes named as a, b, c, d, e, f, g is
25200
 
1120  
7! / 2!  
None of the above 
Question 22 Explanation:
Question 23 
The boolean function that is equivalent to the boolean function
(~(~p ⋀ q) ⋀ ~(~p⋀~q)) V (p ⋀ r) is
q
 
R  
P ⋀ r
 
P V q  
None of the given option is correct 
Question 23 Explanation:
⋀ also means ‘∙’
⋁ also means ‘+’
‘~’ also means ‘×’
So,
⋁ also means ‘+’
‘~’ also means ‘×’
So,
Question 24 
In octal, the twelve bit two’s complement of the hexadecimal number 2AF_{16} is
6522_{8}  
6251_{8}  
6521_{8}  
6512_{8} 
Question 24 Explanation:
Let’s first convert (2AF)_{16} into binary no.,
Question 25 
What is the radix of the numbers if the solutions to the quadratic equation
X^{2}  10x + 31 = 0 is x=5 and x=8?
10  
11  
13  
None of the above 
Question 25 Explanation:
Let the radix of the numbers be ‘b’.
Now we know that product of roots of quadratic equation
Now we know that product of roots of quadratic equation
Question 26 
A 36bit floatingpoint binary number has eight bits plus sign bit for the exponent and 26 bits plus sign bit for mantissa. The mantissa is a normalized fraction. Number in the mantissa and exponent are in signed magnitude representation. The largest and smallest positive quantities that can be represented excluding zero are
(2^{26}) x 2^{+255} . 2^{256}  
(12^{26}) x 2^{+255 }. 2^{256}
 
(12^{26}) x 2^{+255} . 2^{+256}
 
None of the above 
Question 27 
Using karnaugh map. Four variable boolean function F(A,B,C,D)=Σ(3,7,11,13,14,15) can be simplified to
CD + ABC + ABD
 
ACD + BCD + ABC + ABD
 
ABC’D + ABC + CD  
None of the above

Question 27 Explanation:
Question 28 
Let r=1(1+0)*, s=11*0 and t=1*0 be three regular expressions respectively corresponding to three regular sets R, S and T, then which one of the following is TRUE?
S ⊂ R  
R ⊂ S  
T ⊂ S  
None of the above

Question 28 Explanation:
S ⊂ R because every string that is generated by s will also be generated by r ,but there are some strings that is generated by r but not generated by s like “1”
Question 29 
Which of the following is (are) FALSE about Context free Languages?
1. Context free languages are closed under intersection
2. Context free languages are closed under concatenation
3. Context free languages are closed under Kleene’s closure.
(1) only  
(3) only  
(1) and (3) only  
(2) and (3) only

Question 29 Explanation:
Context free language closed under concatenation and kleene closure but not intersection.
Question 30 
Which of the following is (are) undecidable problem(s)?
1. Determination of ambiguity of context free grammar(s)?
2. Given two context free grammars G1 and G2 determining whether they generate exactly the same language.
3. Determining whether the language accepted by a Turing machine is finite or infinite.
(2) only  
(3) Only  
(1) and (3) only
 
(2) and (3) only 
Question 30 Explanation:
None of the given option is correct. The correct answer is All three are undecidable problems.
Ambiguity problem of context free grammar is undecidable.
Determining L1 = L2 is undecidable , where L1 and L2 are context free language.
It is undecidable to determine whether a given Turing machine accepts a finite or infinite number of inputs.
Ambiguity problem of context free grammar is undecidable.
Determining L1 = L2 is undecidable , where L1 and L2 are context free language.
It is undecidable to determine whether a given Turing machine accepts a finite or infinite number of inputs.
Question 31 
Consider the following grammar where λ denote the null string
S→ aSb
S→ bSa
S→ SS
S→ λ
Which of the following best characterizes the language generated by the above grammar?
All strings of the form a^{i} b^{ j} a^{k} where i+j=k  
All palindromes over a and b  
All strings with equal number of a’s and b’s
 
All evenlength strings of a’s and b’s 
Question 31 Explanation:
The given grammar generates all strings with equal no. of a’s and b’s.
Question 32 
Consider the following grammar where λ denote the null string
S→ aSb
S→ bSa
S→ SS
S→ λ
Which of the following best characterizes the language generated by the above grammar?
All strings of the form a^{i} b^{ j} a^{k} where i+j=k  
All palindromes over a and b  
All strings with equal number of a’s and b’s
 
All evenlength strings of a’s and b’s 
Question 32 Explanation:
The given grammar generates all strings with equal no. of a’s and b’s.
Question 33 
In computer networking, an Internet socket or network socket is an endpoint of a bidirectional interprocess communication flow across an Internet Protocolbased computer network. A socket address combines which of the following?
A http URL and an IP address  
An IP address and a port number
 
An IP address and a proxy address  
An IP address and a PID (process identifier) 
Question 33 Explanation:
A socket address is a combination of IP address and a port number.
Question 34 
Questions 3334 are based on the following:
In a Distance Vector (DV) routing algorithm each node x maintains a distance vector Dx where costs paths from node x to any other node y in the network with N nodes are estimated. Each node then updates its DV based on the DV update from its neighbour v as: D_{x}(y)=min_{v}{c(x,v)+D_{v}(y)} for each node y in N
Consider the case when after an update D_{x}(y) does not change, then it implies that
The algorithm is unstable  
A path better than a previous estimate is found
 
The algorithm has converged  
There is necessarily n count to infinity problem.

Question 35 
Questions 3334 are based on the following:
In a Distance Vector (DV) routing algorithm each node x maintains a distance vector Dx where costs paths from node x to any other node y in the network with N nodes are estimated. Each node then updates its DV based on the DV update from its neighbour v as: D_{x}(y)=min_{v}{c(x,v)+D_{v}(y)} for each node y in N
Consider the case when after an update D_{x}(y) has changed, then which of the following are correct:
1. The update helps to find a leastcost path from node x to y
2. The update needs to be communicated to x’s neighbours in an asynchronous fashion.
3. There is necessarily a count to infinity problem.
(1) only  
(2) and (3) only
 
(3) only  
(1) and (2) only

Question 36 
A router software had a bug that set TTL field values to NULL when forwarding IP packets, irrespective of the actual TTL value. How many hops further will these IP packets be forwarded
0  
1  
Infinity times since TTL is NULL
 
TTL field does not really matter for this 
Question 36 Explanation:
We know that whenever router decreases te TTL velue and if it becomes 0 then router discards that packet.And since the router has bug and it is making the TTL value to NULL so this router will discard the packet and no further forwarding is done.
Question 37 
Consider the queuing delay in a router buffer(preceding an outbound link). Suppose all packets are L bits, the transmission rate is R bps and that N packets arrive the buffer every LN/R seconds. The average queuing delay of a packet is
L(N1)/2  
L/R ((N1))/2
 
R(N1)/2
 
R/N ((N1))/2

Question 38 
UDP checksum for two 16 bit numbers: 1110011001100110, 1101010101010101 is
0100010001000011  
1011101110111100  
0011010111110100  
1011101110111111 
Question 38 Explanation:
To find the checksum we will add the two given binary nos. and if we get carry then we will add that to the result and then we will take 1’s complement of the final result.
Now let’s take 1’s complement of the final result. 0100010001000011
∴ Final answer will be,
0100010001000011
Now let’s take 1’s complement of the final result. 0100010001000011
∴ Final answer will be,
0100010001000011
Question 39 
After reading the following passage carefully, answer questions 3840 on the basis of what is stated or implied in the passage.
There was a table set out under a tree in front of the house, and the March Hare and the hatter were having tea at it: a Dormouse was sitting between them, fast asleep, and the other two were using it as a cushion, resting their elbows on it, and talking over its head. “Very uncomfortable for the Dormouse,”thought Alice; “only as its asleep, I suppose it doesn’t mind.”
The table was a large one, but the three were all crowded together at one corner of it. “No room!” they cried out when they saw Alice coming. “There’s plenty of room! Said Alice indignantly, and she sat down in a large armchair at one end of the table.
Who were “the three” sitting at one corner of the table?
Alice, March Hare and the Hatter  
March hare, the Hatter and the Dormouse
 
March Hare, Dormouse and Alice  
Dormouse the Hatter and Alice 
Question 39 Explanation:
By reading the passage we can clearly conclude that March hare, the Hatter and the Dormouse
were the three who were sitting at one corner of the table.
Question 40 
According to Alice, which of the following is TRUE?
There’s no room at the table  
Dormouse is talking in its sleep  
You don’t feel uncomfortable sleeping at a table  
You feel uncomfortable only if you are awake 
Question 40 Explanation:
From the line “as its asleep, I suppose it doesn’t mind” ,alice says that you feel uncomfortable only if you are awake.
Question 41 
Which of the following is TRUE from the above passage?
March Hare, the Hatter and the Dormouse wanted Alice to join them at the table
 
March Hare and the hatter are sitting next to one another  
There are only three chairs at the table  
There are only three chairs at one end of the table

Question 41 Explanation:
From the line “No room!” they cried out when they saw Alice coming.”, it is clear that, the end in which the three were sitting ,there was no extra chairs ,thats why they said there was no room!
Question 42 
A digital computer has a common bus system for 16 registers of 32 bits each. The bus is constructed with multiplexers.
a. How many selection inputs are there in each multiplexer?
b. What size of multiplexers are needed?
c. How many multiplexers are there in the bus?
Descriptive solution 
Question 43 
The access time of a cache memory is 100ns and that of main memory is 100ns. It is estimated that 80% of the memory requests are for read and the remaining 20% for write. The hit ratio for read accessed only is 0.9. A writethrough procedure is used.
a. What is the average access time of the system considering only memory read cycles?
b. What is the average access time of the system considering both the read and write requests?
c. What is the hit ratio talking into consideration the write cycles?
Descriptive solution 
Question 44 
The size of a file is 16MB in a file system that uses 2KB as the block size. How many index blocks are needed to store this file in indexed allocation? Assuming the inode structure, how many levels of indexing is needed? How many disk blocks, other than the inode, need to be read to access the 300th block?
Descriptive solution 
Question 45 
Design Push Down Automaton for the language consisting of all words of the form a^{n}b^{m}a^{m}b^{n}, where m,n > 0 over the alphabet Σ={a,b}. Also provide a context free grammar that generates this language.
Descriptive solution 
Question 46 
Prove
Descriptive solution 
Question 47 
Write an algorithm to find a maximum cost spanning tree, i.e., the spanning tree with highest possible cost. Suppose the edges are sorted according to nonincreasing order of their costs and stored in a list. If there are n nodes in the input graph then will the first n1 edges of this list will always be part of the maximum spanning tree? Justify your answer.
Descriptive solution 
Question 47 Explanation:
Suppose that G is a connected planar graph with less than 12 regions and such that each vertex of G has degree ≥ 3. Then prove that Ghas a region of degree ≤ 4.
Question 48 
Consider the following relation STUDY and functional dependencies F1, F2, F3, F4 and F5.
Relation
STUDY [ Stid, Name, birthdate, Coursecode, Title, Credits, Dept, Dname, Location, Semester, marks, grade]
Functional Dependencies:
F1: {Stid} → { Name, Birthdate}
F2: {coursecode} → {Title, Credits, Dept}
F3: {Dept} → {Dname, Location}
F4: {Stid, coursecode} → {Semester, Marks, Grade}
F5: {Marks} → {Grade}
A. Find all candidate keys for relation STUDY
B. What is the highest normal form of relation STUDY?
C. Decompose you make, identify the normal form of the original and the resulting relations? Give brief justification for each normalization step.
Descriptive solution 
Question 49 
In C language, how do you declare and define a two dimensional array D of integers with r rows and c columsdunalically In C language, a two dimensional array M with 4 rows and 6 columns may be declared as a formal parameter to a function as M[][6], but not as M[4][]. Why?
Descriptive solution 
Question 50 
A machine uses a 16bit two’s complement representation for integers, and littleendian byteordering, this means that the least significant byte of an integer is stored at the lower address. Determine what the following program fragment will print:
int x; /* 16 bit signed integer */
char *p=(char *) &x;
x=0x0013;
printf(“x is %d\n”,x);
printf(“%d %d\n”,p[0],p[1]);
Descriptive solution 
There are 50 questions to complete.