DSBS-FN-31.01.2024

Which one of the following array elements represents a binary min heap?

• 12 10 8 25 14 17
• 8 10 12 25 14 17
• 25 17 14 12 10 8
• 14 17 25 10 12 8

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?

• 5 will be at root
• 5 will be at last level
• 5 will be at second level
• 5 can be anywhere in heap

Which of the following algorithms is the best approach for solving Huffman codes?

• greedy algorithm
• exhaustive search
• divide and conquer algorithm
• brute force algorithm

Fractional knapsack problem is solved most efficiently by which of the following algorithm?

• Backtracking
• Greedy algorithm
• Dynamic programming
• Divide and conquer

Fractional knapsack problem is also known as __________

• 0/1 knapsack problem
• Continuous knapsack problem
• Divisible knapsack problem
• Non continuous knapsack problem

What is the objective of the knapsack problem?

• To get maximum total value in the knapsack
• To get maximum weight in the knapsack
• To get minimum total value in the knapsack
• To get minimum weight in the knapsack

The main time taking step in fractional knapsack problem is ___________

• Breaking items into fraction
• Adding items into knapsack
• Sorting
• Looping through sorted items

Greedy Algorithms have following characteristic.

• Objective function
• Feasible solution
• Selection function
• All of these

Time Complexity of Recursive Fibonacci algorithm is

• O(n2)
• O(n3)
• O(n2 log(n) )
• O(Cn), where C is a constant

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:

• si≥fj
• sj≥fi
• si≥fj or sj≥fi
• si≥fj and sj≥fi