Free Printable DAA MCACCA2104

1.

In dynamic programming, the technique of storing the previously calculated values is called ___________

a)

Saving value property

b)

Storing value property

c)

Memorization

d)

Mapping

2.

What are 2 things required in order to successfully use the dynamic programming technique?

a)

Optimal sub structure and overlapping sub problems

b)

A problem that can’t be sub divided and is complex

c)

Non overlapping sub problems and intervals

d)

Recursion and a problem that is complex

3.

Dynamic Programming is often used for (choose all that apply):

a)

Optimization problems that involve making a choice that leave one or more subproblems to be solved.

b)

Problems previously solved using divide and conquer that have over lapping subproblems

c)

Non polynomial solution problems

d)

Subproblems where resources are shared

4.

The difference between Divide and Conquer and Dynamic Programming is:

a)

The division of problems and combination of subproblems

b)

Whether the sub problems overlap or not

c)

The way we solve the base case

d)

The depth of recurrence

5.

If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memorization

d)

Greedy

6.

Which of the following problems is NOT solved using dynamic programming?

a)

0/1 knapsack problem

b)

Matrix chain multiplication problem

c)

Edit distance problem

d)

Fractional knapsack problem

7.

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

a)

170

b)

200

c)

160

d)

90

8.

What is meant by the time complexity of an algorithm?

a)

The amount of time required to solve a particular problem

b)

How difficult a problem is to solve

c)

How many lines of code are required to solve a problem

d)

How quickly a solution can be developed

9.

What two pieces of information allow you to analyse an algorithm?

a)

Time Complexity

b)

Space Complexity

c)

Size Complexity

d)

Complex Complexity

e)

Simplicity Complex

10.

How do you measure of the time complexity?

a)

Big-O notation

b)

Big-N notation

c)

N notation

d)

Small-O notation

e)

Small-N notation

11.

What does the big-O notation show?

a)

The effectiveness of an algorithm

b)

The amount of time required to solve a particular problem

c)

How difficult a problem is to solve

d)

How many lines of code are required to solve a problem

e)

How quickly a solution can be developed

12.

What is the Big-O notation good for?

a)

It allows you to predict the amount of time taken to solve an algorithm given the number of items stored

b)

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

c)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

d)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

e)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

13.

What does a linear time complexity mean?

a)

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

b)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

c)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

d)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

e)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

14.

What does a constant time complexity mean?

a)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

b)

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

c)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

d)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

e)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

15.

What does a polynomial time complexity mean?

a)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

b)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

c)

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

d)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

e)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

16.

What does an exponential time complexity mean?

a)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

b)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

c)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

d)

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

e)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

17.

What does a logarithmic time complexity mean?

a)

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted.

b)

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted.

c)

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n

d)

The amount of time taken to complete an algorithm is independent to the number of inputted elements

e)

The amount of time taken to complete an algorithm is independent from the number of elements inputted.

18.

What is space complexity?

a)

The space complexity is the amount of storage space an algorithm takes up

b)

How many times a certain number (base) is multiplied together to reach another number.

c)

An algorithm is a series of steps that complete a task

19.

What is an algorithm?

a)

An algorithm is a series of steps that complete a task

b)

The space complexity is the amount of storage space an algorithm takes up

c)

How many times a certain number (base) is multiplied together to reach another number.

20.

How do you reduce the space complexity?

a)

Try to complete all of the operations on the same data set

b)

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

21.

How do you reduce the time complexity of an algorithm?

a)

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

b)

Try to complete all of the operations on the same data set

22.

What is the Big-O notation of a linear search algorithm?

a)

O(n)

b)

O(log(n))

c)

O(n2)

23.

What is the Big-O notation of a bubble sort algorithm?

a)

O(n2)

b)

O(log(n))

c)

O(n)

24.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Constant

25.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2ⁿ)

c)

O(log n)

d)

O(n²)

e)

O(1)

26.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

27.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

28.

What order of complexity does this graph represent?

a)

Exponential

b)

Polynomial

c)

Linear

d)

Logarithmic

29.

What is best case complexity of Insertion Sort?

a)

\Omega\left(n^2\right)

b)

$\Omega\left(n\right)$

c)

$\Omega\left(n\log_2n\right)$

d)

$\Omega\left(1\right)$

30.

What is the worst case complexity of Quick Sort?

a)

$O\left(n^2\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(n\right)$

d)

$O\left(1\right)$

31.

What is the worst case complexity of Merge Sort?

a)

$O\left(n^2\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(n\right)$

d)

$O\left(1\right)$

32.

What is the best case complexity of Bubble sort?

a)

$\Omega\left(n^2\right)$

b)

$\Omega\left(n\right)$

c)

$\Omega\left(n\log_2n\right)$

d)

$\Omega\left(n^2\log_2n\right)$

33.

What is the worst case complexity of selection sort?

a)

$O\left(n^2\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(n\right)$

d)

$O\left(1\right)$

34.

What will be the complexity of Quick sort while data is already sorted in increasing order?

a)

$O\left(1\right)$

b)

$O\left(n\right)$

c)

$O\left(n\log_2n\right)$

d)

$O\left(n^2\right)$

35.

What will be the worst case complexity of Merge Sort while data is already sorted in increasing order?

a)

$O\left(1\right)$

b)

$O\left(n\right)$

c)

$O\left(n\log_2n\right)$

d)

$O\left(n^2\right)$

36.

Which one of the following sorting algorithm uses divide and conquer approach?

a)

Selection Sort

b)

Insertion Sort

c)

Merge Sort

d)

Bubble Sort

37.

What is best case complexity of Insertion Sort?

a)

\Omega\left(n^2\right)

b)

$\Omega\left(n\right)$

c)

$\Omega\left(n\log_2n\right)$

d)

$\Omega\left(1\right)$

38.

What is the worst case complexity of Quick Sort?

a)

$O\left(n^2\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(n\right)$

d)

$O\left(1\right)$

39.

What is the worst case complexity of Merge Sort?

a)

$O\left(n^2\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(n\right)$

d)

$O\left(1\right)$

40.

What is the best case complexity of Bubble sort?

a)

$\Omega\left(n^2\right)$

b)

$\Omega\left(n\right)$

c)

$\Omega\left(n\log_2n\right)$

d)

$\Omega\left(n^2\log_2n\right)$

41.

What is the worst case complexity of selection sort?

a)

$O\left(n^2\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(n\right)$

d)

$O\left(1\right)$

42.

What will be the complexity of Quick sort while data is already sorted in increasing order?

a)

$O\left(1\right)$

b)

$O\left(n\right)$

c)

$O\left(n\log_2n\right)$

d)

$O\left(n^2\right)$

43.

What will be the worst case complexity of Merge Sort while data is already sorted in increasing order?

a)

$O\left(1\right)$

b)

$O\left(n\right)$

c)

$O\left(n\log_2n\right)$

d)

$O\left(n^2\right)$

44.

Which one of the following sorting algorithm uses divide and conquer approach?

a)

Selection Sort

b)

Insertion Sort

c)

Merge Sort

d)

Bubble Sort

45.

Which one of the following sorting algorithm always divides its data into almost two equal half ?

a)

Selection Sort

b)

Quick Sort

c)

Merge Sort

d)

Bubble Sort

46.

Which one of the following uses divide, conquer and combine approach?

a)

Quick Sort

b)

Merge Sort

c)

Selection

d)

Counting Sort

47.

What is the space complexity of Insertion sort?

a)

O\left(1\right)

b)

$O\left(n\right)$

c)

$O\left(n\log_2n\right)$

d)

$O\left(n^2\right)$

48.

What is the space complexity of Bubble sort?

a)

$O\left(n\right)$

b)

$O\left(n\log_2n\right)$

c)

$O\left(1\right)$

d)

$O\left(n^2\right)$

49.

What is space complexity of Merge Sort?

a)

$O\left(1\right)$

b)

$O\left(n\right)$

c)

$O\left(n^2\right)$

d)

$O\left(n\log_2n\right)$

50.

Which one of the following is linear sorting algorithm?

a)

Selection sort

b)

Merge sort

c)

Counting sort

d)

Bubble sort

51.

Which one of the following is not stable sort?

a)

Counting sort

b)

Radix sort

c)

Merge sort

d)

Quick sort

52.

Which one of the following is not a comparable sort?

a)

Selection sort

b)

Insertion sort

c)

Radix sort

d)

Quick sort

53.

What is the complexity of counting sort?

a)

O\left(n\right)

b)

$O\left(n\cdot k\right)$

c)

$O\left(n+k\right)$

d)

$O\left(n^2\right)$

e)

$O\left(n\log_2n+k\right)$

54.

What is the space complexity of counting sort?

a)

$O\left(1\right)$

b)

$O\left(n\right)$

c)

$O\left(k\right)$

d)

$O\left(n+k\right)$

55.

Which one of the following sorting algorithm cannot sort negative numbers?

a)

Merge sort

b)

Quick sort

c)

Counting sort

d)

Selection

56.

Which one of the sorting algorithm picks the smallest element of the array and place it in beginning positions in every iteration?

a)

Quick sort

b)

Insertion sort

c)

Selection sort

d)

Bubble sort

57.

Which one of the following uses divide, conquer and combine approach?

a)

Quick Sort

b)

Merge Sort

c)

Selection

d)

Counting Sort

58.

What is the space complexity of Insertion sort?

a)

O\left(1\right)

b)

$O\left(n\right)$

c)

$O\left(n\log_2n\right)$

d)

$O\left(n^2\right)$

59.

A binary search is to be performed on the list:
3 5 9 10 23
How many comparisons would it take to find number 9?

a)

0-1

b)

2-3

c)

4-5

d)

I can't find the number 9

60.

It consists of a finite set of elements called nodes and a finite set of directed lines called branches.

a)

Graph Data Structure

b)

Tree Data Structure

c)

Linked List Data Structure

d)

Array

DAA MCACCA2104

Total questions: 60

Worksheet time: 32mins

Similar Resources on Wayground