NEW
Font size
S
M
L
XL
WorksheetsDSBS-FN-31.01.2024
Total questions: 15
Worksheet time: 30mins
Name
Class
Date
1.
Which one of the following array elements represents a binary min heap?
a)
12 10 8 25 14 17
b)
8 10 12 25 14 17
c)
25 17 14 12 10 8
d)
14 17 25 10 12 8
2.
What will be the position of 5, when a max heap is constructed on the input elements 5, 70, 45, 7, 12, 15, 13, 65, 30, 25?
a)
5 will be at root
b)
5 will be at last level
c)
5 will be at second level
d)
5 can be anywhere in heap
3.
Which of the following algorithms is the best approach for solving Huffman codes?
a)
greedy algorithm
b)
exhaustive search
c)
divide and conquer algorithm
d)
brute force algorithm
4.
Fractional knapsack problem is solved most efficiently by which of the following algorithm?
a)
Backtracking
b)
Greedy algorithm
c)
Dynamic programming
d)
Divide and conquer
5.
Fractional knapsack problem is also known as __________
a)
0/1 knapsack problem
b)
Continuous knapsack problem
c)
Divisible knapsack problem
d)
Non continuous knapsack problem
6.
What is the objective of the knapsack problem?
a)
To get maximum total value in the knapsack
b)
To get maximum weight in the knapsack
c)
To get minimum total value in the knapsack
d)
To get minimum weight in the knapsack
7.
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
8.
Greedy Algorithms have following characteristic.
a)
Objective function
b)
Feasible solution
c)
Selection function
d)
All of these
9.
Time Complexity of Recursive Fibonacci algorithm is
a)
O(n2)
b)
O(n3)
c)
O(n2 log(n) )
d)
O(Cn), where C is a constant
10.
In Activity-Selection problem, each activity i has a start time si and a finish time fi where si≤fi. Activities i and j are compatible if:
a)
si≥fj
b)
sj≥fi
c)
si≥fj or sj≥fi
d)
si≥fj and sj≥fi
11.
The minimum num of colors with which we can guarantee that no two adjacent nodes will have the same color if we want to coloue the node of any cycle are:
a)
2
b)
3
c)
4
d)
N+2
12.
Consider a person wants to make change for Rs.1874 and he has infinite supply of denomination i.e. 1, 2, 5, 10, 20, 50, 100, 500, 1000 valued coins. What is the minimum number of coins needed to make the change ?
a)
5
b)
9
c)
2
d)
100
13.
If Jobs J =(J1, J2, J3, J4) are given their processing time Ti = (1,1,2,3) and deadlines are Di = (3,4,2,3) maximum how many jobs can be done?
a)
1
b)
2
c)
3
d)
all
14.
Which of the following problem cannot be solved using greedy approch?
a)
Huffman code
b)
Minimum spanning tree
c)
0 -1 knapsack
d)
Job scheduling
15.
Matching the pairs
(i) 0/1 Knapsack
(ii) Multiply numbers
(iii) Minimum weight
(iv) Connected Components
(1) Greedy
(2) Depth-first search
(3) Dynamic programming
(4) Divide and conquer
a)
i-2 , ii-4 , iii-1, iv-3
b)
i-3 , ii-4 , iii-l , iv-2
c)
i-3 , ii-4 , iii-2 , iv-1
d)
i-4 , ii-1 , iii-2 , iv-3
Reset
