CHỦ ĐỀ 6: KĨ THUẬT LẬP TRÌNH

BÀI 24: ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

A. TRẮC NGHIỆM

1. NHẬN BIẾT

Câu 1: Các bước giải bài toán trên máy tính được tiến hành theo thứ tự nào sau đây:

1. Xác định bài toán – Lựa chọn thuật toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu
2. Xác định bài toán – Viết chương trình – Lựa chọn thuật toán – Viết tài liệu
3. Lựa chọn thuật toán – Xác định bài toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu
4. Viết chương trình – Hiệu chỉnh – Viết tài liệu

Câu 2: Mỗi bài toán được đặc tả bởi mấy thành phần:

1. 4
2. 3
3. 2
4. 1

Câu 3: Viết chương trình là?

1. Biểu diễn thuật toán
2. Dùng ngôn ngữ lập trình để diễn đạt bài toán
3. Dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả thuật toán
4. Tất cả đều đúng

Câu 4: Tiêu chuẩn lựa chọn thuật toán:

1. Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép
2. Độ phức tạp của thuật toán
3. Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…
4. Cả 3 ý trên đều đúng

Câu 5: Giải bài toán trên máy tính được tiến hành qua mấy bước?

1. 3
2. 4
3. 5
4. 6

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

1. Hiệu quả về thời gian
2. Hiệu quả về không gian
3. Khả thi khi cài đặt
4. Tất cả đều đúng

Câu 7: Bước quan trọng nhất để giải một bài toán trên máy tính là

1. Lựa chọn hoặc thiết kế thuật toán
2. Viết chương trình
3. Xác định bài toán
4. Hiệu chỉnh

2. THÔNG HIỂU

Câu 1: 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?

1. Sai
2. Đúng
3. Ý kiến khác
4. Chưa đủ dữ kiện

Câu 2: Mục đích của việc hiệu chỉnh là:

1. Xác định lại Input và Output của bài toán
2. Phát hiện và sửa sai sót
3. Mô tả chi tiết bài toán
4. Để tạo ra một chương trình mới

Câu 3: Thuật toán tối ưu là?

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

Câu 4: Các bước cần phải có khi giải bài toán trên máy tính là:

1. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, diễn tả thuật toán, hiệu chỉnh, viết tài liệu
2. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, viết tài liệu
3. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh, viết tài liệu
4. Xác định bài toán, viết thuật chọn, viết chương trình, viết tài liệu

3. VẬN DỤNG

Câu 1: Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?

1. 3 đơn vị thời gian
2. 1 đơn vị thời gian
3. 2 đơn vị thời gian
4. 5 đơn vị thời gian

Câu 2: Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?

1. 3 đơn vị thời gian
2. 1 đơn vị thời gian
3. 2 đơn vị thời gian
4. 5 đơn vị thời gian

Câu 3: Tính độ phức tạp của các hàm thời gian sau:

Tính = 2n(n - 2) + 4.

1. O(n) - tuyến tính
2. O(n^{3}) - lũy thừa
3. O(n^{1}) - lũy thừa
4. O(n^{5}) - lũy thừa

Câu 4: Tính độ phức tạp của các hàm thời gian sau:

Tính = n³ + 5n - 3.

1. O(n) - tuyến tính
2. O(n^{3}) - lũy thừa
3. O(n^{1}) - lũy thừa
4. O(n^{5}) - lũy thừa

Câu 5: Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:

Tính = n3 + nlogn + 2n + 1.

1. O(n³ ) + 1.
2. 3O(n⁴ ) + 10.
3. O(n² ) + 1.
4. O(n⁴ ) + 10.

Câu 6: Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:

Tính = 3n⁴ + 2n²logn + 10.

1. O(n³ ) + 1.
2. 3O(n⁴ ) + 10.
3. O(n² ) + 1.
4. O(n⁴ ) + 10.

4. VẬN DỤNG CAO

Câu 1: Xác định độ phức tạp thời gian cho chương trình sau:

n = 1000

s = 0

for i in range (n);

S = S + i(i+1)

Print (S)

1. 2 đơn vị thời gian
2. 5 đơn vị thời gian
3. 1 đơn vị thời gian
4. 3 đơn vị thời gian

 --------------- Còn tiếp ---------------