ECIL GET 2018 : Subject revision Test-1 (Algo, PDS) for GATE & PSU CS Exams

Question 1

Two main measures for the efficiency of an algorithm are :

Question 2

What is the solution to the recurrence T(n)=T(n/2) +n ?

Question 3

The concept of order Big O is important because :

Question 4

0/1 - Knapsack is a well known problem where, it is desired to get the maximum total profit by placing n times (each item is having some weight and associated profit) into a knapsack of capacity W. The table given below shows the weights and associated profits for 5 items, where one unit of each item is available to you. It is also given that the knapsack capacity W is 8. If the given 0/1 knapsack problem is solved using Dynamic Programming, which one of the following will be maximum earned profit by placing the items into the knapsack of capacity 8.

Question 5

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are

Question 6

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Question 7

Suppose T(n) = 2T(n/2) + n, T(0) = T(1) =1 which one of the following is false?

Question 8

The time complexity of Quicksort algorithm depends heavily on the selection of :

Question 9

The following program is to be tested for statement coverage:
begin
if (a==b) {S1; exit;}
else if (c==d){S2;]
else (S3; exit;)
S4;
end
The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the valued of variables a, b, c and d. The exact values are not given.
T1 : a, b, c and d are all equal
T2 : a, b, c and d are all distinct
T3 : a = b and c |= d
T4 : a |= b and c = d
Which of the test suits given below ensures coverage of statements S1, S2, S3 and S4?

Question 10

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 11

Which one of the following is a key factor for preferring B+-trees to binary search trees for indexing database relations?

Question 12

In a complete K-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

Question 13

Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S to do processing
void fun(int n)
{
Stack S; // Say it creates an empty stack S
while (n > 0)
{
// This line pushes the value of n%2 to stack S
Push(&S, n%2);
N = n/2
}
// Run while Stack S is not empty
while (lisEmpty(&S))
printf(“%d”, pop(&S)); //pop an element from S and print it
}
What does the above function do in general?

Question 14

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represented using adjacency matrix.

Question 15

What will be output if you will compile and execute the following c code ?
void main ()
printf(“%d”,sizeof(5.2));