Free Printable Thuật toán và độ phức tạp

1.

What is the complexity of calculating the longest palindromic subsequence using dynamic programming?

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n^3)$

d)

All are incorrect

2.

In order to perform a binary search on array A, what condition must array A satisfy?

a)

The array must be sorted in ascending order

b)

The array does not need to be sorted

c)

The array must be sorted in descending order

d)

A or C are both correct

3.

What is the value of the variable k after executing the following code: int k=0, n=20; for(int i=1; i<=n; i++) { int j=i; while(j<=n) { k++; j=j*2; } } What is the value of k?

a)

400

b)

30

c)

40

d)

All are incorrect

4.

What is the time complexity of the binary search algorithm?

a)

$O(n)$

b)

$O(n\log n)$

c)

$O(\log n)$

d)

All are incorrect

5.

In order to perform binary search on array A, what condition must array A satisfy?

a)

The array must be sorted in ascending order

b)

The array does not need to be sorted

c)

The array must be sorted in descending order

d)

Either A or C is correct

6.

What is the complexity of the following code: int i=1; while(i<=n) { k++; i=i*2; } What is the complexity?

a)

$O(n)$

b)

$O(n\log n)$

c)

$O(\log n)$

d)

$O(1)$

7.

What is the best time complexity for the problem of finding the maximum sum of a contiguous subarray?

a)

$O(n^2)$

b)

$O(n^3)$

c)

$O(\log n)$

d)

$O(n)$

8.

Which of the following points does not belong to the exhaustive search method?

a)

No strategy in searching for solutions

b)

Trying all candidates for the solution

c)

Dividing a large problem into smaller subproblems

d)

Usually not used to solve problems with large data sizes

9.

How does the backtracking method solve problems?

a)

Depth-first search for solutions

b)

Breadth-first search for solutions

c)

Trying all possible acceptable options at the same time

d)

All are incorrect

10.

In the 8 queens problem, after placing a queen in the first row, what is the minimum number of possible placements for a queen in the second row?

a)

6

b)

5

c)

7

d)

All are incorrect

11.

In the 8 queens problem, after placing a queen in the first row and placing a queen in the second row, what is the minimum number of possibilities to place a queen in the third row?

a)

4

b)

5

c)

2

d)

3

12.

According to the divide-and-conquer method, how many multiplications are needed to calculate $x^{25}$ ?

a)

25

b)

5

c)

6

d)

7

13.

According to the Indian multiplication algorithm, when multiplying 13 by 17, what is the value of the variable S after the second iteration?

a)

0

b)

13

c)

39

d)

81

14.

In the helicopter patrol problem, suppose there are fuel tanks with values {3, 5, 1, 4} and the distance k=2, how many ways are there to arrange the fuel tanks for the patrol?

a)

2

b)

3

c)

4

d)

5

15.

What is the similarity between the divide and conquer method and dynamic programming?

a)

Used to solve optimization problems

b)

Divides a large problem into smaller subproblems

c)

Uses recursion to solve the problem

d)

All of the above

16.

In the problem of a mouse moving in a maze to reach the destination, a cell is called safe when it satisfies how many conditions?

a)

3

b)

4

c)

5

d)

2

17.

In the sudoku problem, how many conditions need to be checked when filling a number into a cell?

a)

2

b)

3

c)

4

d)

5

18.

Which of the following algorithms can produce incorrect results?

a)

Greedy method

b)

Divide and conquer method

c)

Exhaustive search method

d)

Probabilistic algorithm

19.

According to the greedy method, how many times do we need to read the file when merging 5 files with sizes {13, 10, 4, 8, 3} into one file?

a)

83

b)

123

c)

122

d)

38

20.

How many groups can probability algorithms be divided into?

a)

1

b)

2

c)

3

d)

4

21.

In the recursive definition of the ant problem, if we call C(5, 4), how many intermediate calls (calculations) of C(3,3) are needed?

a)

1

b)

2

c)

3

d)

4

22.

What is the complexity of calculating the longest palindromic subsequence using dynamic programming?

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n^3)$

d)

All are incorrect

23.

What condition must array A satisfy in order to perform binary search on it?

a)

A. The array is sorted in ascending order

b)

B. The array does not need to be sorted

c)

C. The array is sorted in descending order

d)

D. Both A and C are correct

24.

What is the value of the variable k after executing the following code: int k=0, n=20; for(int i=1; i<=n; i++) { int j=i; while(j<=n) { k++; j=j*2; } }

a)

400

b)

30

c)

40

d)

All are incorrect

25.

What is the time complexity of the following code: int i=1; while(i<=n) { k++; i=i*2; }

a)

$O(n)$

b)

$O(n\log n)$

c)

$O(\log n)$

d)

$O(1)$

26.

The best time complexity for the problem of finding the maximum sum of a contiguous subarray is

a)

$O(n^2)$

b)

$O(n^3)$

c)

$O(\log n)$

d)

$O(n)$

27.

Which of the following points does not belong to the exhaustive search method?

a)

No strategy in searching for solutions

b)

Trying all candidates for the solution

c)

Dividing a large problem into smaller subproblems

d)

Usually not used to solve problems with large data sizes

28.

How does the backtracking method solve problems?

a)

Search for solutions in depth

b)

Search for solutions in breadth

c)

Try all possible acceptable options at the same time

d)

All are incorrect

29.

In the 8 queens problem, after placing a queen in the first row, what is the minimum number of possibilities to place a queen in the second row?

a)

6

b)

5

c)

7

d)

9

30.

In the 8 queens problem, after placing a queen in the first row and placing a queen in the second row, what is the minimum number of possible placements for a queen in the third row?

a)

4

b)

5

c)

2

d)

3

31.

According to the Indian multiplication algorithm, when multiplying 13 by 17, what is the value of variable S after the second iteration?

a)

0

b)

13

c)

39

d)

81

32.

In the helicopter patrol problem, suppose there are fuel tanks with values {3, 5, 1, 4} and the distance k=2, how many ways are there to arrange the fuel tanks for the patrol?

a)

2

b)

3

c)

4

d)

5

33.

The similarity between the divide and conquer method and the dynamic programming method is

a)

Used to solve optimization problems

b)

Divides a large problem into smaller subproblems

c)

Uses recursion to solve the problem

d)

All of the above are correct

34.

In the problem of a mouse moving in a maze to reach the destination, a cell is called safe when it satisfies how many conditions

a)

3

b)

4

c)

5

d)

2

35.

Which of the following algorithms can produce incorrect results?

a)

Greedy method

b)

Divide and conquer method

c)

Exhaustive search method

d)

Probabilistic algorithm

36.

According to the greedy method, how many times do we need to read the file when merging 5 files with sizes {13, 10, 4, 8, 3} into one file?

a)

83

b)

123

c)

122

d)

38

37.

How many groups can probability algorithms be divided into?

a)

1

b)

2

c)

3

d)

4

38.

Which algorithm design method describes solving a problem by listing all candidate solutions and checking each candidate to select the solution?

a)

Randomized Algorithm

b)

Dynamic Programming

c)

Exhaustive Search

d)

Greedy Algorithms

39.

Which algorithm design method describes solving the problem of finding the contiguous subsequence with the largest sum by listing all possible subsequences and calculating the sum of each subsequence to select the one with the largest sum?

a)

Greedy Algorithms

b)

Exhaustive Search

c)

Randomized Algorithm

d)

Divide and Conquer

40.

The algorithm design method that describes how a robot can take 2 types of steps with lengths of 1 m and 2 m by listing all possible ways to walk and checking in each way if there is a way that does not take more than 2 steps of 1 m

a)

Dynamic Programming

b)

Randomized Algorithm

c)

Greedy Algorithms

d)

Exhaustive Search

41.

Which algorithm design method describes the solution to the problem of a robot that can take 2 types of steps with lengths of 1 m and 2 m by using state variables to analyze how to cover the distance?

a)

Greedy Algorithms

b)

Exhaustive Search

c)

Randomized Algorithm

d)

Dynamic Programming

42.

Which algorithm design method describes solving the problem of a patrol aircraft by organizing a program that uses arrays to store information about fuel tanks and results?

a)

Exhaustive Search

b)

Dynamic Programming

c)

Divide and Conquer

d)

Backtracking

43.

Which algorithm design method describes solving the Sudoku puzzle by assigning the numbers from 1 to 9 to the empty cells so that each row, column, and 3x3 region contains each number from 1 to 9 exactly once

a)

Exhaustive Search

b)

Backtracking

c)

Dynamic Programming

d)

Divide and Conquer

44.

Which algorithm design method describes the process of solving the problem of counting how many ways to choose numbers to sum up to k from n different integers?

a)

Randomized Algorithm

b)

Dynamic Programming

c)

Greedy Algorithms

d)

Exhaustive Search

45.

Which algorithm design method describes the enumeration of permutations of characters in the string S?

a)

Dynamic Programming

b)

Backtracking

c)

Greedy Algorithms

d)

Exhaustive Search

46.

Which algorithm design method describes the solution to the problem of breaking down the number n into the sum of 3 numbers and counting how many ways it can be done?

a)

Exhaustive Search

b)

Greedy Algorithms

c)

Randomized Algorithm

d)

Dynamic Programming

47.

Which algorithm design method describes the enumeration of binary sequences of length n such that no two adjacent bits are 1?

a)

Dynamic Programming

b)

Backtracking

c)

Greedy Algorithms

d)

Exhaustive Search

48.

In the Merge Sort algorithm, what is the time complexity of the "merge" step?

a)

$O(1)$

b)

$O(\log N)$

c)

$O(N)$

d)

$O(N^2)$

49.

What is another name for a Queue?

a)

Last In First Out (LIFO)

b)

First In Last Out (FILO)

c)

Last In Last Out (LILO)

d)

First In First Out (FIFO)

50.

What is the time complexity of the Bubble Sort algorithm when sorting an already sorted array?

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n\log n)$

d)

All are incorrect

51.

Use Radix Sort to sort the array: 47, 891, 3, 11, 27, 69, 26, 8; after step 1 (sorting by the unit place), the resulting array is:

a)

3, 8, 11, 26, 27, 47, 69, 891

b)

891, 11, 3, 26, 27, 47, 8, 69

c)

891, 11, 3, 26, 47, 27, 8, 69

d)

3, 8, 11, 26, 47, 27, 69, 891

52.

The complexity of the Quick Sort algorithm is

a)

$O(n)$

b)

$O(n^2)$

c)

$O(n\log n)$

d)

$O(n^3)$

53.

For the binary search algorithm to work, the array (list) must be

a)

Unordered

b)

Ordered (Sorted)

c)

Heap format

d)

Removed from the stack

54.

Find an element in a matrix of size $m \times n$ with what complexity?

a)

$O(n^2)$

b)

$O(m^2)$

c)

$O(m\times n)$

d)

All are incorrect

55.

What is the minimum number of comparisons needed when searching in a sorted array of 256 elements (using binary search)?

a)

1

b)

10

c)

256

d)

8

56.

The postfix form of the expression $A/X + B*C^F$ is:

a)

A X + B C * F + ^

b)

A X / B C F ^ * +

c)

A X + B C * F ^ +

d)

A X B + / C * F ^ +

57.

What is the process of handling each element in a list called?

a)

sorting

b)

merging

c)

inserting

d)

traversal

58.

How many fields must each node in a singly linked list contain at a minimum?

a)

Three fields

b)

Two fields

c)

Four fields

d)

Five fields

59.

How many pointers does a doubly linked list have at each node?

a)

0

b)

1

c)

2

d)

3

60.

The correct order to swap the second and third nodes in a list l with more than 3 elements using the steps: (1) p=head; (2) head.next=q; (3) q=p.next; (4) p.next=q.next; (5) q.next=p; is:

a)

(1), (5), (3), (4), (2)

b)

(2), (3), (4), (5), (1)

c)

(1), (3), (5), (4), (2)

d)

(1), (3), (4), (5), (2)

61.

The postfix form of the expression (M + N)*(C*D − E)*F / G is:

a)

MN+ CD*E− FG /**

b)

MN+ CD* E− F **G /

c)

MN + CD* E − *F *G /

d)

MN + CDE * − * F *G /

62.

What does the following function do for a linked list with the head node as head? void fun1(Node head) { if(head == null) return; System.out.print(head.data + " "); fun1(head.next); }

a)

Prints all nodes of the linked list

b)

Prints all nodes in reverse order

c)

Prints alternate nodes of the linked list

d)

Prints alternate nodes in reverse order

63.

What is the output of the function when start points to the head of the list: 1->2->3->4->5->6? void fun(Node start) { if(start == NULL) return; System.out.print (start.data + " "); if(start.next.next != null ) fun(start.next.next); System.out.print (start.data + " "); }

a)

1 4 6 6 4 1

b)

1 3 5 1 3 5

c)

1 3 5

d)

1 3 5 5 3 1

64.

Which algorithmic model involves systematically listing all candidates for a solution and checking whether each candidate satisfies the problem statement or not?

a)

Divide and Conquer

b)

Dynamic Programming

c)

Greedy

d)

Brute Force

65.

The appropriate algorithm to solve the Knight Tour problem is:

a)

Divide and Conquer

b)

Dynamic Programming

c)

Backtracking

d)

Brute Force

66.

The appropriate algorithm to solve the problem of merging n files into 1 file is:

a)

Divide and Conquer

b)

Greedy

c)

Backtracking

d)

Brute Force

67.

What technique is the Merge Sort algorithm an example of?

a)

Divide and Conquer

b)

Dynamic Programming

c)

Backtracking

d)

Brute Force

68.

In the Travelling Salesman problem, if using the Brute Force technique and the number of cities is 30, how many trials are needed to find the result?

a)

$30!$

b)

$29!$

c)

$30^2$

d)

$29^2$

69.

In the function to remove a node from a linked list, what is the correct order of the 3 commands: p->next = t (1); q = p (2); delete q (3);?

a)

(1), (2), (3)

b)

(3), (1), (2)

c)

(2), (3), (1)

d)

(2), (1), (3)

70.

What is the command used in the function to calculate the sum of all nodes in a linked list?

a)

p = NULL;

b)

k = k + p->data;

c)

p->next->next != NULL;

d)

k = k + 1;

71.

What is the command used in the function to calculate the height of a binary tree?

a)

return 1 + max(height(T->left), height(T->right));

b)

return max(height(T->left), height(T->right));

c)

return 1 + height(T->left) + height(T->right);

d)

All of the above are correct

72.

In the Fibonacci sequence, what is F(6)?

a)

5

b)

8

c)

13

d)

1

73.

Where is the maximum value located in a Binary Search Tree?

a)

the leftmost branch

b)

the rightmost branch

c)

the root

d)

There is no correct answer

74.

What operation reduces the size of the stack?

a)

popS()

b)

pushS()

c)

Both A and B are correct

d)

All are incorrect

75.

What operation increases the size of the queue?

a)

addQ()

b)

removeQ()

c)

Both A and B are correct

d)

All are incorrect

76.

Let LCS(Xi, Yj) be the length of the longest common subsequence. What is the formula for calculating LCS(Xi, Yj) if X[i] ≠ Y[j]?

a)

$LCS(X_i,Y_j)=LCS(X_{i-1},Y_{j-1})$

b)

$LCS(X_i,Y_j)=LCS(X_{i-1},Y_{j-1})+1$

c)

$LCS(X_i,Y_j)=\max\big(LCS(X_i,Y_{j-1}),\;LCS(X_{i-1},Y_j)\big)$

d)

$LCS(X_i,Y_j)=\max\big(LCS(X_{i-1},Y_{j-1}),\;LCS(X_{i-2},Y_{j-2})\big)$

77.

Consider the following pseudocode with a queue: void fun(int n) { queue q; q.push(0); q.push(1); for (int i = 0; i <= n; i++) int a = q.front(); q.pop(); int b = q.front(); q.pop(); q.push(b); q.push(a + b); cout<

a)

Prints the numbers from 0 to n-1

b)

Prints the numbers from n-1 to 0

c)

Prints the first n Fibonacci numbers

d)

Prints the first n Fibonacci numbers in reverse order

78.

The Karatsuba algorithm for multiplying two numbers with n digits requires a number of operations that scales according to which complexity?

a)

$O(n^2)$

b)

$O(n^3)$

c)

$O(n^{\log 3})$

d)

$O(n^{\log n})$

79.

Choose the C pseudocode of the function that takes a queue Q and uses a stack S to process it: void fun(Queue *Q) { Stack S; while (!isEmpty(Q)) { deQueue an element from Q and push that element into S; } while (!isEmpty(&S)) { Pop an element from S and enQueue (add) that element into Q; } } What does the above function generally do?

a)

Remove the last element of Q

b)

Keep Q unchanged as before calling

c)

Make Q empty

d)

Reverse the order of Q

80.

To find two numbers with the largest product in an array of n integers using the brute force technique, how many pairs need to be checked?

a)

$n\times n$

b)

$n(n-1)$

c)

$\dfrac{n(n-1)}{2}$

d)

$\dfrac{n\times n}{2}$

81.

To retrieve information from an AVL tree in descending order, what order should be traversed?

a)

left, root, right

b)

root, left, right

c)

right, root, left

d)

No correct answer

82.

How much time is needed to insert a node x into a doubly linked list with n nodes?

a)

$O(n)$

b)

$O(\log n)$

c)

$O(1)$

d)

$O(n\log n)$

83.

Choose the C pseudocode of the function that takes a number n and uses stack S to process: void fun(int n) { Stack S; while (n > 0) { push(&S, n % 2); n = n/2; } while (!isEmpty(&S)) printf("%d ", pop(&S)); } What does the above function generally print?

a)

Prints the binary representation of n in reverse order

b)

Prints the value of log n

c)

Prints the value of log n in reverse order

d)

Prints the binary representation of n

84.

Assuming p points to the head of the linked list: 3->2->5->7->6->9->NULL. What is the result of the statement cout << p->next->next->next->data?

a)

6

b)

2

c)

7

d)

All are incorrect

85.

Matrix A of size $4\times5$ and matrix B of size $5\times7$ . How many multiplications are needed to compute $A\times B$ ?

a)

20

b)

35

c)

150

d)

All are incorrect

86.

Which of the following algorithms can produce incorrect results?

a)

Greedy method

b)

Divide and conquer method

c)

Exhaustive search method

d)

Probabilistic algorithm

87.

What is the similarity between the divide and conquer method and the dynamic programming method?

a)

Used to solve optimization problems

b)

Divides a large problem into smaller subproblems

c)

Uses techniques to solve the problem

d)

All of the above are correct

Thuật toán và độ phức tạp – Bài tập trắc nghiệm

Total questions: 87

Worksheet time: 44mins

Similar Resources on Wayground