## 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) | |

Θ(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

⋮

For kth while loop iteration,

j=n/2

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

^{k-1}, for loop will run n/2^{k-1}timesQuestion 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

= n

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}+ 1Question 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

x = 2

Not correct.

B)

z = n

z = 2

Correct.

C)

b = z

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}= 8Not correct.

B)

z = n

^{n}z = 2

^{3}= 8Correct.

C)

b = z

^{n}= 8^{3 Not correct. D) b = xn = 16 3 Not correct.}