wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Kiểm tra kiến thức về thuật toán

Total questions: 66

Worksheet time: 56mins

Name
Class
Date
1.
4 lines
2.

Tính toán độ phức tạp của bài toán là làm gì?

_______ được thực hiện trong mỗi lần thuật toán được khởi chạy dựa trên input đầu vào cua bài toán

4 lines
3.

Ký hiệu (a)   mô tả trường hợp tệ nhất của thuật toán thông qua một hàm của input đầu vào n

4.

Độ phức tạp của thuật toán càng nhỏ thì thuật toán chạy càng (a)  

5.

Thông qua ký hiệu Big O ta có thể mô tả độ phức tạp của thuật toán là (a)  

6.
4 lines
7.
4 lines
8.

Ký hiệu độ phức tạp thuật toán của các toán tử (Operation) và hàm scanf(), printf() là:____

a)

O(1)

b)

O(2)

c)

O(3)

d)

O(4)

9.
4 lines
10.
4 lines
11.
4 lines
12.
4 lines
13.
4 lines
14.

Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là đúng hay sai?

a)

Đúng

b)

Sai

15.

Thuật toán tối ưu là gì?

a)

  1. Sử dụng ít thời gian, ít bộ nhớ…

b)

  1. Sử dụng ít thời gian, ít bộ nhớ, ít phép toán…

c)

  1. Sử dụng ít thời gian, nhiều bộ nhớ, ít phép toán…

d)

  1. Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép toán…

16.

Chương trình nào chạy nhanh hơn?

a)

Chương trình 1

b)

Chương trình 2

17.

Tiêu chí lựa chọn hoặc thiết kế thuật toán là?

a)

  • Hiệu quả về thời gian

b)

  • Hiệu quả về không gian

c)

  • Khả thi khi cài đặt

d)

  • Tất cả đều đúng

18.

Tiêu chuẩn lựa chọn thuật toán là gì?

a)

  • Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép

b)

  • Độ phức tạp của thuật toán

c)

  • Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…

d)

  • Cả 3 ý đều đúng

19.

Khi nào thì thời gian chạy chương trình được tính bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp?

a)

Lệnh đơn

b)

Lệnh if

c)

Vòng lặp for hoặc while

d)

Các phép toán đơn giản và phép toán lôgic

20.

Khi nào thì thời gian chạy chương trình được tính bằng đơn vị thời gian lớn nhất của các lệnh nhánh?

a)

Lệnh đơn

b)

Lệnh if

c)

Vòng lặp for hoặc while

d)

Các phép toán đơn giản

21.

Sắp xếp các độ phức tạp của một số hàm chuẩn sau theo thứ tự độ phức tạp tăng dần:

O(n!), O(nlogn), O(logn)

a)

O(n!), O(nlogn), O(logn)

b)

O(logn), O(nlogn), O(n!)

c)

O(logn), O(n!), O(nlogn)

d)

O(n!), O(logn), O(nlogn)

22.

n càng lớn thì (a)   sẽ tăng lên nhưng với tốc độ khác nhau

23.

Hãy xác định độ phức tạp thời gian tính toán cho đoạn chương trình

a)

O(n)

b)

O(n+1)

c)

O(n^3)

d)

O(n+3)

24.

1. Một chương trình/thuật toán được coi là hiệu quả nếu độ phức tạp của nó:

a)

A.   cao.

b)

B.   thấp.

c)

C.   cả A và B đều đúng.

d)

D.   cả A và B đều sai.


25.

2. Thời gian chạy của thuật toán được kí hiệu là gì?

a)

A.   S(n)

b)

B.   M(n)

c)

C.   T(n)

d)

D.   P(n)


26.

3. Phép toán lấy thương nguyên và số dư được tính là mấy đơn vị thời gian?

a)

A.   một phần tám đơn vị thời gian.

b)

B.   một phần tư đơn vị thời gian.

c)

C.   một phần hai đơn vị thời gian.

d)

D.   một đơn vị thời gian.


27.

4. Vòng lặp for hoặc while sẽ được tính thời gian bằng:

a)

A.   tổng đơn vị thời gian thực hiện của mỗi bước lặp.

b)

B.   hiệu đơn vị thời gian thực hiện giữa mỗi bước lặp.

c)

C.   tích đơn vị thời gian thực hiện của mỗi bước lặp.

d)

D.   cả A, B, C đều sai.


28.

5. Độ phức tạp thời gian có thể coi là một hàm số T(n) với n là:

a)

A.   số thực.

b)

B.   số hữu tỉ.

c)

C.   số nguyên.

d)

D.   số tự nhiên.


29.

6. Định nghĩa nào được dùng để so sánh và phân tích bậc của hàm thời gian T(n) khi n tăng lên vô cùng?

a)

A.   M-lớn.

b)

B.   N-lớn.

c)

C.   O-lớn.

d)

D.   P-lớn.


30.

7. Nếu thực hiện thuật toán với các độ phức tạp sau đây, trường hợp nào sẽ là bất lợi nhất?

a)

A.   O(1)

b)

B.   O(logn)

c)

C.   O(nlogn)

d)

D.   O(n)


31.

8. Tính độ phức tạp của hàm thời gian T(n) = 2n(n – 2) + 4.

a)

A.   T(n) = O(n)

b)

B.   T(n) = O(n2)

c)

C.   T(n) = O(n – 2)

d)

D.   T(n) = O(1)


32.

9. Tính độ phức tạp của hàm thời gian T(n) = 3n4 + 2n2logn + 10.

a)

A.   T(n) = O(1)

b)

B.   T(n) = O(logn)

c)

C.   T(n) = O(n2)

d)

D.   T(n) = O(n4)


33.

10. Xác định độ phức tạp thời gian tính toán cho chương trình sau:

a)

A.   T(n) = O(logn)

b)

B.   T(n) = O(n)

c)

C.   T(n) = O(n2)

d)

D.   T(n) = O(2n)


34.

What is the time complexity of the following code?

for (int i = 1; i < n; i *= 2)

for (int j = 0; j < n; j++)

cout << i << j;

a)

O(n log n)

b)

O(n^2)

c)

O(log n)

d)

O(n)

35.

Which sorting algorithm has the best worst-case time complexity?

a)

Bubble Sort

b)

Quick Sort

c)

Merge Sort

d)

Insertion Sort

36.

Choose the correct Big-O for this recursive function:
void recurse(int n) {
  if (n <= 1) return;
  recurse(n / 2);
recurse(n / 2);
}

a)

O(n^2)

b)

O(n log n)

c)

O(log n)

d)

O(n)

37.

Time complexity of calculating Fibonacci(n) with naive recursion?

a)

O(n^2)

b)

O(n log n)

c)

O(2^n)

d)

O(n)

38.

Given a graph with V vertices and E edges, what is the time complexity of DFS?

a)

O(V^2)

b)

O(V log V)

c)

O(E log V)

d)

O(V + E)

39.

Giả sử đây có 9 phần tử trong thuật toán Quick Sort, pivot luôn được chọn là phần tử chính giữa. Bao nhiêu lời gọi đệ quy tối đa sẽ diễn ra nếu chia đều dãy mỗi lần?

a)

1

b)

3

c)

4

d)

8

40.

Để cài đặt Stack ta có thể dùng phương pháp nào sau đây:

a)

Chỉ bằng con trỏ.

b)

Chỉ bằng mảng.

c)

Bằng con trỏ và bằng mảng.

d)

Các phương án khác đều sai.

41.

Tư tưởng của giải thuật tìm kiếm tuần tự:

a)

So sánh X lần lượt với các phần tử của dãy cho đến khi gặp phần tử có khóa cần tìm.

b)

Tìm kiếm dựa vào cây nhị phân tìm kiếm.

c)

Tại mỗi bước so sánh X với phần tử ở giữa của dãy...

d)

Lần lượt chia dãy thành hai...

42.

Tư tưởng của giải thuật tìm kiếm nhị phân:

a)

So sánh X lần lượt với từng phần tử...

b)

Lần lượt chia dãy thành hai dãy con dựa vào phần tử khóa...

c)

Tại mỗi bước so sánh X với phần tử giữa, quyết định tìm ở nửa trên hoặc nửa dưới.

d)

Tìm kiếm dựa vào cây nhị tìm kiếm.

43.

Sắp xếp nhanh thuộc loại thuật toán nào?

a)

Sắp xếp trực tiếp (In-place) và đệ quy.

b)

Dùng thêm bộ nhớ ngoài.

c)

Không đệ quy.

d)

Không thể áp dụng cho dữ liệu lớn.

44.

Trường hợp nào khiến sắp xếp nhanh có độ phức tạp xấu nhất?

a)

Dãy đã được sắp tăng (hoặc giảm) và luôn chọn phần tử đầu làm pivot.

b)

Chọn pivot là phần tử giữa.

c)

Dãy chứa các phần tử bằng nhau.

d)

Dãy chỉ có 1 phần tử.

45.

Độ phức tạp trung bình của thuật toán sắp xếp nhanh là:

a)

O(n)

b)

O(nlogn)

c)

O(n^2)

d)

O(logn)

46.

Cơ chế nào dưới đây được cài đặt cho Stack:

a)

LIFO

b)

Tuần tự

c)

Round Robin

d)

FIFO

47.

Một cây nhị phân được gọi là đúng nếu:

a)

Node gốc và các node trung gian đều có 2 node con.

b)

Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên phải.

c)

Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên trái

d)

Node gốc và các node trung gian đều có 2 node con và các node lá có mức bằng nhau.

48.

Trong các cấu trúc dữ liệu sau, đâu là dữ liệu trừu tượng:

a)

Cấu trúc dữ liệu dạng cây (TREE).

b)

Cấu trúc dữ liệu dạng danh sách (LIST).

c)

Tất cả cấu trúc đã nêu.

d)

Cấu trúc dữ liệu kiểu hàng đợi (QUEUE).

49.

Định nghĩa cấu trúc dữ liệu hàng đợi (QUEUE):

a)

Thêm và loại bỏ đều ở cùng một đầu.

b)

Thêm và loại bỏ ở đầu hoặc cuối.

c)

Thêm ở cuối (Rear), loại bỏ ở đầu (Front).

d)

Thêm ở đầu (Front), loại bỏ ở cuối (Rear).

50.

Định nghĩa cấu trúc dữ liệu Stack:

a)

Stack là danh sách kết nối.

b)

Stack là danh sách đặc biệt, thêm ở một đầu, loại bỏ ở đầu kia.

c)

Stack là danh sách đặc biệt, thêm và loại bỏ ở cùng một đầu gọi là đỉnh (Top).

d)

Stack là cấu trúc dữ liệu cài đặt bằng con trỏ.

51.

Khi chèn phần tử vào danh sách, nếu độ dài danh sách bằng độ dài mảng thì thông báo:

a)

Danh sách rỗng.

b)

Danh sách không tồn tại.

c)

Danh sách chưa khai báo.

d)

Danh sách đầy.

52.

Giá trị nào thường được chọn làm pivot trong Quick Sort đơn giản:

a)

Giá trị lớn nhất.

b)

Giá trị nhỏ nhất.

c)

Giá trị trung bình.

d)

Một phần tử bất kỳ (thường đầu, cuối hoặc giữa).

53.

Định nghĩa cấu trúc dữ liệu dạng Danh sách (LIST)

a)

Danh sách là kiểu con trỏ.

b)

Danh sách là tập hợp các phần tử khác kiểu.

c)

Danh sách là kiểu dữ liệu mảng.

d)

Danh sách là một tập hợp các phần tử có cùng kiểu (ElementType).

54.

Độ phức tạp tốt nhất của thuật toán sắp xếp nổi bọt là:

a)

O(log n)

b)

O(n)

c)

O(n log n)

d)

O(n^2)

55.

Trong thuật toán tìm kiếm nhị phân, điều kiện nào là cần thiết để áp dụng?

a)

Dãy phải là dãy số nguyên.

b)

Dãy phải được sắp xếp.

c)

Dãy có ít nhất 2 phần tử.

d)

Dãy không chứa phần tử trùng lặp.

56.

Độ phức tạp thời gian của thuật toán sắp xếp trộn là:

a)

O(n log n)

b)

O(log n)

c)

O(n^2)

d)

O(n)

57.

1. Một chương trình/thuật toán được coi là hiệu quả nếu độ phức tạp của nó:

a)

A.   cao.

b)

B.   thấp.

c)

C.   cả A và B đều đúng.

d)

D.   cả A và B đều sai.


58.

2. Thời gian chạy của thuật toán được kí hiệu là gì?

a)

A.   S(n)

b)

B.   M(n)

c)

C.   T(n)

d)

D.   P(n)


59.

3. Phép toán lấy thương nguyên và số dư được tính là mấy đơn vị thời gian?

a)

A.   một phần tám đơn vị thời gian.

b)

B.   một phần tư đơn vị thời gian.

c)

C.   một phần hai đơn vị thời gian.

d)

D.   một đơn vị thời gian.


60.

4. Vòng lặp for hoặc while sẽ được tính thời gian bằng:

a)

A.   tổng đơn vị thời gian thực hiện của mỗi bước lặp.

b)

B.   hiệu đơn vị thời gian thực hiện giữa mỗi bước lặp.

c)

C.   tích đơn vị thời gian thực hiện của mỗi bước lặp.

d)

D.   cả A, B, C đều sai.


61.

5. Độ phức tạp thời gian có thể coi là một hàm số T(n) với n là:

a)

A.   số thực.

b)

B.   số hữu tỉ.

c)

C.   số nguyên.

d)

D.   số tự nhiên.


62.

6. Định nghĩa nào được dùng để so sánh và phân tích bậc của hàm thời gian T(n) khi n tăng lên vô cùng?

a)

A.   M-lớn.

b)

B.   N-lớn.

c)

C.   O-lớn.

d)

D.   P-lớn.


63.

7. Nếu thực hiện thuật toán với các độ phức tạp sau đây, trường hợp nào sẽ là bất lợi nhất?

a)

A.   O(1)

b)

B.   O(logn)

c)

C.   O(nlogn)

d)

D.   O(n)


64.

8. Tính độ phức tạp của hàm thời gian T(n) = 2n(n – 2) + 4.

a)

A.   T(n) = O(n)

b)

B.   T(n) = O(n2)

c)

C.   T(n) = O(n – 2)

d)

D.   T(n) = O(1)


65.

9. Tính độ phức tạp của hàm thời gian T(n) = 3n4 + 2n2logn + 10.

a)

A.   T(n) = O(1)

b)

B.   T(n) = O(logn)

c)

C.   T(n) = O(n2)

d)

D.   T(n) = O(n4)


66.

10. Xác định độ phức tạp thời gian tính toán cho chương trình sau:

a)

A.   T(n) = O(logn)

b)

B.   T(n) = O(n)

c)

C.   T(n) = O(n2)

d)

D.   T(n) = O(2n)


Similar Resources on Wayground

MS office Revision

61 questions

MS office Revision

quiz

Worksheet

•

8th - 10th Grade

KIỂM TRA GIỮA HỌC KY 1 TIN HỌC 8

68 questions

KIỂM TRA GIỮA HỌC KY 1 TIN HỌC 8

quiz

Worksheet

•

8th Grade

5º-INSTRUMENTOS Y FAMILIAS (2021)

65 questions

5º-INSTRUMENTOS Y FAMILIAS (2021)

quiz

Worksheet

•

6th Grade

Tin 7-Ôn tập GK2

65 questions

Tin 7-Ôn tập GK2

quiz

Worksheet

•

7th Grade

ÔN THI CK2 TIN 3 KNTT

70 questions

ÔN THI CK2 TIN 3 KNTT

quiz

Worksheet

•

3rd Grade - University

ICDL-TIN HỌC-CHƯƠNG I

65 questions

ICDL-TIN HỌC-CHƯƠNG I

quiz

Worksheet

•

6th Grade

Windows 10

62 questions

Windows 10

quiz

Worksheet

•

1st - 6th Grade

Ôn tập Tin 7

70 questions

Ôn tập Tin 7

quiz

Worksheet

•

7th Grade