Wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Understanding The Algorithms

Total questions: 65

Worksheet time: 3hrs 15mins

Name
Class
Date
1.

What is the time complexity of Bubble Sort in the worst case?

a)

O(2^n)

b)

O(n)

c)

O(n^2)

d)

O(n log n)

2.

How does Insertion Sort work on a nearly sorted array?

a)

Insertion Sort requires a complete array to function properly.

b)

Insertion Sort is efficient on nearly sorted arrays due to fewer necessary swaps and comparisons.

c)

Insertion Sort is only effective on completely unsorted arrays.

d)

Insertion Sort is slow on nearly sorted arrays due to many swaps.

3.

What is the main advantage of Selection Sort over other sorting algorithms?

a)

Its simplicity and in-place sorting capability.

b)

It requires additional memory for sorting.

c)

It is the fastest sorting algorithm available.

d)

It can sort linked lists more efficiently than other algorithms.

4.

What is the best-case time complexity of Insertion Sort?

a)

O(n^2)

b)

O(1)

c)

O(n log n)

d)

O(n)

5.

How many swaps does Bubble Sort perform in the worst case?

a)

O(n)

b)

O(n^2)

c)

O(log n)

d)

O(n^3)

6.

What is the average time complexity of Bubble Sort?

a)

O(n^2)

b)

O(n)

c)

O(n log n)

d)

O(log n)

7.

In which scenario is Insertion Sort most efficient?

a)

When the array is very large and complex.

b)

When the array is completely unsorted.

c)

When the array is nearly sorted or small in size.

d)

When the array contains duplicate elements only.

8.

How does the performance of Selection Sort compare to Insertion Sort?

a)

Selection Sort is faster than Insertion Sort.

b)

Insertion Sort is slower than Selection Sort.

c)

Insertion Sort is generally faster than Selection Sort.

d)

Both algorithms have the same performance.

9.

What is the primary disadvantage of Bubble Sort?

a)

Stable sorting algorithm

b)

In-place sorting with minimal memory usage

c)

Inefficiency for large datasets due to O(n^2) time complexity.

d)

Fast execution for small datasets

10.

What is the key operation performed in Insertion Sort?

a)

The key operation is inserting an element into its correct position in the sorted portion of the array.

b)

Removing duplicates from the array

c)

Finding the maximum element in the array

d)

Sorting the entire array at once

11.

How does the number of comparisons in Selection Sort relate to the size of the array?

a)

Selection Sort requires no comparisons regardless of array size.

b)

The number of comparisons in Selection Sort is O(n^2), where n is the size of the array.

c)

The number of comparisons in Selection Sort is O(n) for large arrays.

d)

The number of comparisons in Selection Sort is O(n log n).

12.

What sorting algorithm is this?

a)

Insertion Sort

b)

Sort of lame

c)

Selection Sort

d)

Bubble Sort

13.

What sorting algorithm is this?

a)

Insertion Sort

b)

Selection Sort

c)

Quicksort

d)

Bubble Sort

14.

What sorting algorithm is this?

a)

Bubble Sort

b)

Insertion Sort

c)

Selection Sort

d)

None of the above

15.
We are sorting the following list in ascending order:
 
1    4    2    9    3    8    5
 
What does the list look like after one pass of the bubble sort algorithm. 
a)
1 2 4 3 8 5 9
b)
1 4 2 5 3 8 9
c)
4 2 9 3 8 5 1
16.
We are sorting the following list in ascending order:
 
1    4    2    9    3    8    5
 
What does the list look like after one pass of the insertion sort algorithm. 
a)
1 4 2 9 3 8 5
b)
4 2 9 3 8 5 1
c)
4 1 2 9 3 8 5
17.

Which of the following case does not exist in complexity theory?

a)

Best case

b)

•Worst case

c)

•Average case

d)

Null case

18.

int fun(int n)

•{

•int count = 0;

•for (int i = 0; i < n; i++)

•for (int j = i; j > 0; j--)

count = count + 1;

•return count;

•}

a)

Theta (n)

b)

Theta (n^2)

c)

•Theta (n*Logn)

d)

•Theta (nLognLogn)

19.

•If for an algorithm time complexity is given by O(1) then complexity of it is:

a)

•constant

b)

•polynomial

c)

•exponential

d)

•none of the mentioned

20.

space complexity of algorithm means

a)

space it requires

b)

time it requires

c)

hardware it requires

d)

all of the above

21.

This picture represents

a)

big theta noataion

b)

big oh notation

c)

big omega notation

d)

none of the above

22.

big O represents

a)

best case scenario

b)

worst case scenario

c)

average case scenario

d)

none of the above

23.

•What is the time complexity of following code:

•int a = 0, b = 0;

•for (i = 0; i < N; i++) {

•a = a + rand();

•}

•for (j = 0; j < M; j++) {

•b = b + rand();

•}

a)

•O(N * M) time,

b)

•O(N + M) time,

c)

None of these

24.

Big

Ω\Omega defines

a)

lower bound

b)

upper bound

c)

middle bound

d)

none of the above

25.

Which of the following case does not exist in complexity theory?

a)

Best case

b)

•Worst case

c)

•Average case

d)

Null case

26.

Which of the following functions has the largest growth rate? *

a)

n^(1/2)

b)

n^100

c)

2^(n/2)

d)

2^(n!)

27.

Which of the following shows the correct relationship among some of the more common computing times on algorithms

a)

. O(log n) < O(n) < O( n* log n) < O(2n ) < O(n2)

b)

O(log n) < O(n) < O( n* log n) < O(n2) < O(2n )

c)

O(n) < O(log n) < O( n* log n) < O(n2) < O(2n )  

d)

O(n) < O(log n) < O( n* log n) < O(2n ) < O(n2)

28.

•The worst case complexity for insertion sort is _________

•

a)

O(n)

•

b)

O(log n)

c)

•O(n2)

d)

•O(n log n)

29.

•If for an algorithm time complexity is given by O(1) then complexity of it is:

a)

•constant

b)

•polynomial

c)

•exponential

d)

•none of the mentioned

30.

Find the slowest time complexity

a)

O (n)

b)

O (n^2)

c)

O (n!)

d)

O (2^n)

31.

Which Asymptotic notation is used to represent the Best time complexity

a)

Big Oh

b)

Omega

c)

Theta

d)

Small Omega

32.

Which Asymptotic notation is used to represent the average time complexity

a)

Big Oh

b)

Omega

c)

Theta

d)

Small Onega

33.

asymptotic notations represents

a)

space complexity of algo

b)

time complexity of algo

c)

both a and b

d)

none of the above

34.

...................................are the characteristics of an algorithm

a)

Input

b)

infiniteness

c)

Effectiveness

d)

output

e)

finiteness

35.

____, if there are positive constants n0 and c such that at and to the right of n0, the value of f(n) always lies on or below cg(n).

a)

f(n) = Ω(g(n))

b)

f(n) = O(g(n))

c)

f(n) = Θ(g(n))

36.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2n)

c)

O(log n)

d)

O(n2)

e)

O(1)

37.

What is the time complexity of this algorithm?

a)

O(n)

b)

O(2n)

c)

O(log n)

d)

O(n2)

e)

O(1)

38.

Which of the following is the time complexity of insertion sort?

a)

O(n2)O(n^2)

b)

O(log⁡n)O(\log n)

c)

O(n)O(n)

d)

O(nlog⁡n)O(n\log n)

39.

The mechanism of finding an element /key in a given set of elements is known as ________________

a)

sorting

b)

searching

c)

both

d)

none

40.

Which greedy algorithm is used to solve the Huffman coding problem?

a)

Kruskal's algorithm

b)

Huffman algorithm

c)

Dijkstra's algorithm

d)

Prim's algorithm

41.

In Prim’s algorithm, how do we decide which edge to add next to the growing Minimum Spanning Tree (MST)?

a)

The edge with the minimum weight that connects a new vertex to the MST

b)

The edge with the maximum weight that connects a new vertex to the MST

c)

Any random edge from the graph

d)

The edge that forms a cycle in the MST

42.

Prim’s algorithm starts with:

a)

The edge with the lowest weight

b)

The highest weighted edge

c)

Any arbitrary vertex

d)

A randomly chosen edge

43.

Which is optimal value in the case of job sequence problem Item : 1 2 3 4 5..

Profit : 20 15 10 5 1

Deadline : 2 2 3 3 3

a)

1,3,4

b)

1,2,4

c)

4,2,3

d)

1,5,2

44.

The correct encoding of the letter C in this tree is...

a)

11

b)

10

c)

01

d)

00

45.

How do you move through a Huffman tree?

a)

0 = right 1= left

b)

1 = left 2 = right

c)

0 = left 1 = right

d)

0 = middle 1 = back

46.

The output of Kruskal and Prims algorithm is ________________

a)

Maximum spanning tree

b)

Spanning tree

c)

Minimum spanning tree

d)

None

47.

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

48.
In the given graph, identify the shortest path having minimum cost to reach vertex E if A is the source vertex.
a)
a-b-e
b)
a-c-e
c)
a-c-d-e
d)
a-c-d-b-e
49.

Consider a job scheduling problem with 4 jobs J1, J2, J3, J4 and with corresponding deadlines: ( d1, d2, d3, d4) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job schedule?

a)

J2, J4, J1, J3

b)

J4, J1, J2, J3

c)

J4, J2, J1, J3

d)

J4, J2, J3, J1

50.

From the following given tree, what is the code word for the character ‘a’?

a)

011

b)

010

c)

100

d)

101

51.

Fractional knapsack solution maximizes:

a)

Weight in knapsack

b)

Number of items

c)

Total value of knapsack

d)

Number of distinct items

52.

Dijkstra's algorithm is based on which paradigm?

a)

Greedy paradigm

b)

Backtracking paradigm

c)

Dynamic Programming paradigm

d)

Divide and Conquer paradigm

53.

Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?

a)

20

b)

12

c)

6

d)

5

54.

Consider the given graph. What is the weight of the minimum spanning tree using the Prim’s algorithm, starting from vertex a?

a)

23

b)

28

c)

27

d)

11

55.

Consider the graph shown below. Which of the following edges form the MST of the given graph using Prim’a algorithm, starting from vertex 4.

a)

(4-3)(5-3)(2-3)(1-2)

b)

(4-3)(3-5)(5-1)(1-2)

c)

(4-3)(3-5)(5-2)(1-5)

d)

(4-3)(3-2)(2-1)(1-5)

56.
Kruskal’s algorithm uses ___________ and prim’s algorithm uses _________ in determining the MST
a)
vertex, edges
b)
vertex, vertex
c)
edges, edges
d)
edges, vertex
57.
Kruskal’s algorithm is used to ______
a)
find single source shortest path
b)
find minimum spanning tree
c)
find all pair shortest path algorithm
d)
traverse the graph
58.

Big

Ω\Omega defines

a)

lower bound

b)

upper bound

c)

middle bound

d)

none of the above

59.

Using Kruskal’s algorithm, which edge should you choose fourth?

a)

AB

b)

BC

c)

BD

d)

DE

60.

Using Kruskal’s algorithm, which edge should you choose second?

a)

AE

b)

BD

c)

DE

d)

AB

61.

Create a minimal spanning tree, then find the minimum total cost.

a)

30

b)

39

c)

47

d)

50

62.
What is the weight of the Minimum Spanning tree?
a)
12
b)
17
c)
14
d)
15
63.
What is the weight of the Minimum Spanning tree?
a)
1
b)
44
c)
17
d)
22
64.
What is the weight of the Minimum Spanning tree?
a)
17
b)
16
c)
15
d)
14
65.

Which Algorithm is used for finding single-source shortest path

a)

Kruskal's Algorithm

b)

Dijkstra's Algorithm

c)

Prims Algorithm

d)

Huffman's Algorithm

Similar Resources on Wayground

PPS - Chapter 7,8,9,10

60 questions

PPS - Chapter 7,8,9,10

quiz

Worksheet

•

University

PYTHON PROGRAMMING FINALS

69 questions

PYTHON PROGRAMMING FINALS

quiz

Worksheet

•

University

2-Term-MT-OOP

70 questions

2-Term-MT-OOP

quiz

Worksheet

•

University

U23CS381 - ADD QUIZ Assessment

60 questions

U23CS381 - ADD QUIZ Assessment

quiz

Worksheet

•

University

2023-2024 Living in IT Era Midterm Exam

60 questions

2023-2024 Living in IT Era Midterm Exam

quiz

Worksheet

•

University

SQL-Quiz

66 questions

SQL-Quiz

quiz

Worksheet

•

University

2 Facts 1 Lie

60 questions

2 Facts 1 Lie

quiz

Worksheet

•

University

HTML & CSS

60 questions

HTML & CSS

quiz

Worksheet

•

University