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
A
bubble sort
B
Shell sort
C
Merge Sort
D
Selection sort
       Algorithms       Sorting
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
A
Hamiltonian and Euclidean
B
Euclidean but not Hamiltonian
C
hamiltonian but not Euclidean
D
neither hamiltonian nor Euclidean
Question 3
Which of the following is in correct LEXICOGRAPHIC order when using ASCII code?
A
a, an, OR, AND
B
1,5,15,125
C
AND, OR, a, an
D
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.
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;

}
A
Θ(log n)
B
Θ(n)
C
Θ(n2)
D
Θ(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

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?
A
bubble sort
B
Selection sort
C
insertion sort
D
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:
A
binary tree
B
linear Chain
C
complete graph
D
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.
Question 7
The postfix expression ABC+*DE*/is equivalent to which of the following prefix expression?
A
*/*A+BCDE
B
/*A+BC*DE
C
/+*ABC*DE
D
*/+*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
Question 8
Algorithm for finding strongly connected components in linear time makes use of
A
BFS
B
DFS
C
Shortest path
D
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?
A
n2 + n -1
B
n2 + 2n -1
C
n2 + 2
D
n2
E
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
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)
A
z*y/x+c
B
z/y*x+c
C
z+c/y*x
D
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
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)
A
5
B
8
C
9
D
12
E
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?
A
x=bn
B
z=bn
C
b=zn
D
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.
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?
A
0
B
1
C
2
D
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
A
(2), (3) and (4)
B
(1), (3) and (4)
C
(1) and (2)
D
(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?
A
When the time for migration is infinite
B
When the priority is same for all processes
C
When time slice is same
D
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
A
Ki < Kj
B
Ki = Kj
C
Ki > Kj
D
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
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?
A
129024
B
120924
C
131072
D
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
A
(2) only
B
(1) and (2) only
C
(1) and (3) only
D
(2) and (3) only
Question 19
In the context of databases, entity integrity constraint states that
A
Primary key value can not be NULL
B
Foreign key value can not be NULL
C
Every relation has at least one superkey
D
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?
A
All buckets will receive approximately the same number of entries
B
All entries will go into particular bucket
C
Three of the buckets will each get approximately one-third of the entries, and the fourth bucket will remain empty
D
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
A
(p V q) ⋀ (p V r)
B
(p V q) ⋀ r
C
(p V q) ⋀ (p ⋀ r)
D
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.
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
A
25200
B
1120
C
7! / 2!
D
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
A
q
B
R
C
P ⋀ r
D
P V q
E
None of the given option is correct
Question 23 Explanation: 
⋀ also means ‘∙’
⋁ also means ‘+’
‘~’ also means ‘×’
So,

Question 24
In octal, the twelve- bit two’s complement of the hexadecimal number 2AF16 is
A
65228
B
62518
C
65218
D
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?
A
10
B
11
C
13
D
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
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
A
(226) x 2+255 . 2-256
B
(1-226) x 2+255 . 2-256
C
(1-2-26) x 2+255 . 2+256
D
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
A
CD + ABC + ABD
B
ACD + BCD + ABC + ABD
C
ABC’D + ABC + CD
D
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?
A
S ⊂ R
B
R ⊂ S
C
T ⊂ S
D
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.
A
(1) only
B
(3) only
C
(1) and (3) only
D
(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.
A
(2) only
B
(3) Only
C
(1) and (3) only
D
(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.
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?
A
All strings of the form ai b j ak where i+j=k
B
All palindromes over a and b
C
All strings with equal number of a’s and b’s
D
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?
A
All strings of the form ai b j ak where i+j=k
B
All palindromes over a and b
C
All strings with equal number of a’s and b’s
D
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
A http URL and an IP address
B
An IP address and a port number
C
An IP address and a proxy address
D
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
A
The algorithm is unstable
B
A path better than a previous estimate is found
C
The algorithm has converged
D
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.
A
(1) only
B
(2) and (3) only
C
(3) only
D
(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
A
0
B
1
C
Infinity times since TTL is NULL
D
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
A
L(N-1)/2
B
L/R ((N-1))/2
C
R(N-1)/2
D
R/N ((N-1))/2
Question 38
UDP checksum for two 16 bit numbers: 1110011001100110, 1101010101010101 is
A
0100010001000011
B
1011101110111100
C
0011010111110100
D
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
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?
A
Alice, March Hare and the Hatter
B
March hare, the Hatter and the Dormouse
C
March Hare, Dormouse and Alice
D
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?
A
There’s no room at the table
B
Dormouse is talking in its sleep
C
You don’t feel uncomfortable sleeping at a table
D
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?
A
March Hare, the Hatter and the Dormouse wanted Alice to join them at the table
B
March Hare and the hatter are sitting next to one another
C
There are only three chairs at the table
D
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?
A
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?
A
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?
A
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.
A
Descriptive solution
Question 46
Prove
A
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.
A
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.
A
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?
A
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]);
A
Descriptive solution
There are 50 questions to complete.