WorksheetsAOA Quiz Exp1-5
Total questions: 33
Worksheet time: 16mins
Name
Class
Date
1.
Your Full Name
4 lines
2.
Your SE Division:
a)
3
b)
4
3.
Your Roll Number: (2 Digit only)
4 lines
4.
In the following scenarios, when will you use selection sort?
a)
The input is already sorted
b)
A large file has to be sorted
c)
Large Values need to be sorted with small keys
d)
Small values need to be sorted with large keys
5.
What is the worst case complexity of selection sort?
a)
O(nlogn)
b)
O(logn)
c)
O(n)
d)
O(n^2)
6.
What is the disadvantage of selection sort?
a)
It requires auxiliary memory
b)
It is not scalable
c)
It can be used for small keys
d)
It takes linear time to sort the elements
7.
How many passes does an insertion sort algorithm consist of?
a)
N
b)
N-1
c)
N+1
d)
N^2
8.
What will be the number of passes to sort the elements using insertion sort?<br />14, 12,16, 6, 3, 10
a)
6
b)
5
c)
7
d)
1
9.
Which of the following methods is the most effective for picking the pivot element?
a)
first element
b)
last element
c)
median-of-three partitioning
d)
random element
10.
Find the pivot element from the given input using median-of-three partitioning method.<br />8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
a)
8
b)
7
c)
9
d)
6
11.
What is the average running time of a quick sort algorithm?
a)
O(N^2)
b)
O(N)
c)
O(N log N)
d)
O(log N)
12.
What is the average case time complexity of merge sort?
a)
O(n log n)
b)
O(n^2)
c)
O(n^2 log n)
d)
O(n log (n^2))
13.
Choose the incorrect statement about merge sort from the following?
a)
it is a comparison based sort
b)
it is an adaptive algorithm
c)
it is not an in place algorithm
d)
it is stable algorithm
14.
Fractional knapsack problem is also known as __________
a)
0/1 knapsack
b)
continuous knapsack
c)
divisible knapsack
d)
non-continuous knapsack
15.
Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
a)
In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
b)
Both are the same
c)
0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming
d)
In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
16.
Time complexity of fractional knapsack problem is ____________
a)
O(n log n)
b)
O(n)
c)
O(n^2)
d)
O(nW)
17.
Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.
a)
60
b)
80
c)
100
d)
40
18.
The main time taking step in fractional knapsack problem is ___________
a)
Breaking items into fraction
b)
Adding items into knapsack
c)
Sorting
d)
Looping through sorted items
19.
Every graph has only one minimum spanning tree.
a)
true
b)
false
20.
Prim's algorithm is a ------
a)
Divide and conquer algorithm
b)
Greedy algorithm
c)
Dynamic Programming
d)
Approximation algorithm
21.
The algorithm that generates the minimum cost spanning tree starting from the root vertex is known as ------
a)
Kruskal's algorithm
b)
Prim's algorithm
c)
Dijkstra's algorithm
d)
Bellman Ford algorithm
22.
The algorithm that generates the minimum cost spanning tree starting from the least weighted edge is known as ------
a)
Kruskal's algorithm
b)
Prim's algorithm
c)
Dijkstra's algorithm
d)
Bellman Ford algorithm
23.
Which of the following is false about the Kruskal's algorithm?
a)
It is a greedy algorithm.
b)
It constructs MST by selecting edges in increasing order of their weights.
c)
It can accept cycles in the MST.
d)
It uses union-find data structure.
24.
Bellman Ford algorithm provides solution for ---- problems.
a)
All pairs shortest path
b)
Single source shortest path
c)
Sorting
d)
Minimum cost spanning tree
25.
Bellman Ford algorithm is used to indicate whether the graph has negative weight cycles or not.
a)
true
b)
false
26.
What is the running time of Bellman Ford algorithm?
a)
O(V)
b)
O(V2)
c)
O(ElogV)
d)
O(VE)
27.
Bellman Ford algorithm can be applied for ----
a)
Undirected and unweighted graphs
b)
Undirected and weighted graphs
c)
Directed and weighted graphs
d)
All directed graphs
28.
Bellman Ford algorithm is an example for
a)
Greedy algorithms
b)
Dynamic Programming
c)
Backtracking
d)
Branch-and-Bound
29.
Which of the following is the Longest Common Subsequence between the strings 'ABCDEFGHIJK' and 'ABHISHEK'?
a)
ABHISHEK
b)
ABHIEK
c)
ABHIK
d)
ABHEK
30.
Given two sequences X=(x1x2…xm) and Y=(y1y2…yn). If i,j > 0 and Xi = Yj then length of LCS(Xi,Yj) is given by
a)
c[i , j] = c[i-1 , j-1]+1
b)
c[i , j] = max(c[i , j-1], c[i-1 , j])
c)
c[i , j] = 0
d)
c[i , j] = c[i , j]+1
31.
In the construction of Longest Common Subsequence, which arrow symbols are stored in table b[i,j]?
a)
↖
b)
←
c)
↑
d)
All of the above
32.
Consider the strings "ABCDEFGHIJK" and "AABDFFIK". What is the length of the longest common subsequence?
a)
7
b)
8
c)
6
d)
11
33.
Which of the following methods can be used to solve the longest common subsequence problem?
a)
Recursion
b)
Dynamic programming
c)
Both recursion and dynamic programming
d)
Greedy algorithm
100 %
