Subject Revision Test-1 for GATE & PSU CS Exams

Question 1

Consider the following C-function:
int Rec (int n)
{

int i, j, k, p, q = 0;

for (i = n; i>1; i = i/2) {

p = 0;

for (j = 1; j < n; j++)

p = p + 1;

for (k = 1; k < p; k = k × 3)

q++;

} return q

}

Then time complexity of Rec in term of Θnotation is

Question 2

Solve the recurrence relation :
T(n) =

T(

) + n

Question 3

If in a given array atmost n inversions are there, then what will be the time complexity to sort this array by the best algorithm possible?

Question 4

Find the complexity T(n) for the following recurrence relation.

T(n) = T(n/5) + T(n/6) + T(n/8) + c

i) O(n^log₅³) ii) Ω(n^log₅³) iii) O(n^log₈³) iv) Ω(n^log₈³) v) O(n^log₆³)

Question 5

The worst case running time complexity to search for an element in a balanced binary search tree with elements n2ⁿ?

Question 6

A max heap is represented by array, what is the content of the array after performing two deletion operations on the following array.

{18, 12, 16, 8, 10, 13, 9}

Question 7

Which one of the following array represents is not Max heap?

Question 8

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

Question 9

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Question 10

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 has to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value

Question 11

If we use the Quicksort algorithm to sort the elements: 13,16,14,12,21,26,23 and 15 in ascending order, what is the output after the first pass of Quicksort? (Assume that pivot is chosen as n/4rth element from the array)

Question 12

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Question 13

An undirected graph consists of 50 vertices and 150 edges. Weight of the MST of this graph is 300. Each weight of each edges of this graph is incremented by 5, now what is the updated weight of the MST?

Question 14

The following function freelist( ) is used to free all the nodes of the linked list. The function free(x) is used to free all memory associated with the node x.
freelist (node ∗head)
{
while (head != NULL)
{
node ∗P = head → next;
X;
head = P;
}
}
What is the missing statement at X to implement the above functionality?

Question 15

Is the following statement a declaration or definition?

extern int i;

Question 16

Which of the following is true:

Question 17

The default return data type in function definition is:

Question 18

Consider the graph.

Which of the following is a valid topological ordering?

Question 19

Consider the following graph

What is the total number of spanning tree for the above graph?

Question 20

Consider the following traversals of binary search tree:
Post-order: 1, 3, 5, 4, 2, 6, 9, 11, 13, 12, 10, 8, 7
Inorder : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Find the number of nodes in the last level of binary search tree. Assume root is at first level.