Time Left - 15:00 mins
ECIL GET 2018 : Subject revision Test-1 (Algo, PDS)
Attempt now to get your rank among 345 students!
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?
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?
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));
- 345 attempts
- 5 upvotes
- 10 comments
Tags :
GATE & PSU CSMock TestsJun 16GATE & PSU CS