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 n-1 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 n-1 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) | |
Θ(n2) | |
Θ(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/22, ‘for’ loop will run n/22 times.
⋮
For kth while loop iteration,
j=n/2k-1, for loop will run n/2k-1 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/22, ‘for’ loop will run n/22 times.
⋮
For kth while loop iteration,
j=n/2k-1, for loop will run n/2k-1 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?
n2 + n -1 | |
n2 + 2n -1 | |
n2 + 2
| |
n2 | |
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
= n2 - n + n + 1
= n2 + 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
= n2 - n + n + 1
= n2 + 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=bn | |
z=bn | |
b=zn | |
b=xn |
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 = zn = 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 = zn = 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 r1,r2,r3,....,rn, with a FIFO page replacement algorithm and that gives Ki
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
Ki < Kj | |
Ki = Kj | |
Ki > Kj | |
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
Ki < Ki
or Ki = Kj
or Ki > Kj
Hence we can say that when i
or Ki = Kj
or Ki > Kj
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,...i2 … 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 one-third 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 2AF16 is
65228 | |
62518 | |
65218 | |
65128 |
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
X2 - 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 36-bit floating-point 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
(226) x 2+255 . 2-256 | |
(1-226) x 2+255 . 2-256
| |
(1-2-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 ai b j ak where i+j=k | |
All palindromes over a and b | |
All strings with equal number of a’s and b’s
| |
All even-length 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 ai b j ak where i+j=k | |
All palindromes over a and b | |
All strings with equal number of a’s and b’s
| |
All even-length 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 end-point of a bidirectional inter-process communication flow across an Internet Protocol-based 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 33-34 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: Dx(y)=minv{c(x,v)+Dv(y)} for each node y in N
Consider the case when after an update Dx(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 33-34 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: Dx(y)=minv{c(x,v)+Dv(y)} for each node y in N
Consider the case when after an update Dx(y) has changed, then which of the following are correct:
1. The update helps to find a least-cost 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(N-1)/2 | |
L/R ((N-1))/2
| |
R(N-1)/2
| |
R/N ((N-1))/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 38-40 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 arm-chair 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 write-through 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 anbmambn, 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 non-increasing order of their costs and stored in a list. If there are n nodes in the input graph then will the first n-1 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 16-bit two’s complement representation for integers, and little-endian byte-ordering, 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.