ĐỀ KIỂM TRA HỌC KÌ II

ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH 11 - KẾT NỐI TRI THỨC

NĂM HỌC: 2023 - 2024

Thời gian làm bài: … phút (Không kể thời gian phát đề)

A. PHẦN TRẮC NGHIỆM (6,0 điểm)

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng:

Câu 1. Thuật toán tìm kiếm tuần tự có độ phức tạp là:

A. O(n²).

B. O(n!).

C. O(n).

D. O(aⁿ).

Câu 2. Mỗi danh sách liên kết bao gồm mấy cấu trúc dữ liệu?

A. 1. B. 2. C. 3. D. 4.

Câu 3. Mảng một chiều là:

A. A = [1, 2, 3, “Hello”].

B. B = [“Monday”, “Tuesday”, “Wednesday”, 6].

C. C = [[“Henry”, 9.0], [“Anna”, 8.0], [“John”, 8.5]].

D. D = [5, 10, 15, 20, 25].

Câu 4. Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ:

A. Phần tử thứ hai đến phần tử cuối dãy.

B. Phần tử thứ nhất đến phần tử cuối dãy.

C. Phần tử thứ hai đến phần tử gần cuối dãy.

D. Phần tử thứ nhất đến phần tử gần cuối dãy.

Câu 5. Lệnh mở tệp để đọc là:

A. .

B. .

C. .

D. .

Câu 6. Phát biểu nào sau đây sai?

A. Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phần tử của dãy từ đầu đến cuối để tìm phần tử có giá trị bằng giá trị cần tìm.

B. Thuật toán tìm kiếm nhị phân được thực hiện bằng cách liên tục mở rộng phạm vi tìm kiếm.

C. Thuật toán tìm kiếm nhị phân được áp dụng cho các dãy được sắp xếp theo thứ tự xác định.

D. Thuật toán tìm kiếm tuần tự có thể duyệt từ đầu dãy hoặc từ cuối dãy.

Câu 7. Lệnh nào sau đây hỗ trợ duyệt từng phần tử của mảng?

A. …

B. … …

C. … …

D. … …

Câu 8. Hàm làm tròn xuống của thư viện là:

A. .

B. .

C. .

D. .

Câu 9. Cho dãy A = [1, 6, 10, 25, 37, 48, 99]. Thuật toán tìm kiếm nhị phân cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 48 trong dãy?

A. 6. B. 4. C. 3. D. 2.

Câu 10. Phát biểu nào sau đây sai khi nói về phương pháp thiết kế thuật toán và chương trình theo mô đun?

A. Phương pháp thiết kế thuật toán và chương trình theo mô đun sẽ tách bài toán lớn thành các bài toán nhỏ hơn, hay thành các mô đun, tương đối độc lập với nhau.

B. Đầu ra của mô đun trước không thể là đầu vào của mô đun sau.

C. Mỗi mô đun có thể là một số hàm hoặc thủ tục độc lập.

D. Chương trình chính là một bản ghép nối các hàm và thủ tục con.

Câu 11. Lệnh tạo một danh sách liên kết rỗng là:

A. .

B. .

C. .

D. .

Câu 12. Phát biểu nào sau đây đúng?

A. Sử dụng các bộ dữ liệu kiểm thử có thể làm tăng độ tin cậy của chương trình và chứng minh được tính đúng của thuật toán.

B. Một thuật toán nếu được thiết kế đúng thì với mọi bộ dữ liệu đầu vào sẽ nhận được bộ dữ liệu đầu ra đúng tương ứng.

C. Độ phức tạp tính toán quan trọng nhất là độ phức tạp không gian liên quan trực tiếp tới các câu lệnh được thực hiện trong chương trình/thuật toán.

D. Độ phức tạp thời gian phụ thuộc vào dung lượng bộ nhớ được sử dụng để thực hiện chương trình.

Câu 13. Phép toán tích cực trong chương trình dưới đây nằm ở dòng thứ mấy?

A. 3. B. 4. C. 5. D. 6.

Câu 14. Để bổ sung phần tử vào cuối danh sách trong Python, ta sử dụng lệnh:

A. . B. . C. . D. .

Câu 15. Khi tính thời gian thực hiện chương trình, lệnh nào không tính là 1 đơn vị thời gian?

A. Lệnh đọc dữ liệu.

B. Lệnh gán.

C. Lệnh in.

D. Lệnh if với nhiều trường hợp rẽ nhánh.

Câu 16. Phát biểu nào sau đây đúng?

A. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử nhỏ nhất nằm trong dãy A[i], A[i+1],…, A[n] và đổi chỗ phần tử nhỏ nhất này với A[i].

B. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử nhỏ nhất nằm trong dãy A[i], A[i+1],…, A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i].

C. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử nhỏ nhất nằm trong dãy A[i+1],…, A[n] và đổi chỗ phần tử nhỏ nhất này với A[i+1].

D. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử nhỏ nhất nằm trong dãy A[i+1],…, A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i+1].

Câu 17. Tính hiệu quả của chương trình/thuật toán được xem xét trên cơ sở đánh giá:

A. Tính đúng của thuật toán.

B. Ý tưởng thực hiện thuật toán.

C. Độ phức tạp tính toán.

D. Độ tin cậy của chương trình.

Câu 18. Hàm nào sau đây mô tả đúng thuật toán sắp xếp nổi bọt?

A. B.

C. D.

Câu 19. Phát biểu nào sau đây sai?

A. Cấu trúc node mô tả các phần tử độc lập của danh sách liên kết.

B. Để đưa toàn bộ thư viện math vào bộ nhớ, sử dụng lệnh: import * from math.

C. Hàm delete_first(L) sẽ xoá node đầu tiên của danh sách L (nếu danh sách không rỗng).

D. Cấu trúc head là đầu của mỗi danh sách liên kết.

Câu 20. Phát biểu nào sau đây sai khi nói về phương pháp làm mịn dần trong thiết kế chương trình?

A. Ở bước cuối cùng, các hành động tương ứng với các câu lệnh của ngôn ngữ lập trình để viết chương trình hoàn chỉnh.

B. Phương pháp làm mịn dần chia việc thiết kế thành từng bước và thực hiện lần lượt các bước.

C. Mỗi bước lớn có thể được chia thành nhiều bước nhỏ hơn để giải quyết độc lập.

D. Phương pháp làm mịn dần tiếp cận bài toán từ tổng quan đến chi tiết, mỗi bước tiếp theo sẽ phải là thiết kế đơn giản hơn bước trước đó.

Câu 21. Thuật toán tìm kiếm nhị phân được thực hiện như sau:

- Thiết lập các giá trị left, right là chỉ số phần tử đầu và cuối của dãy A có n phần tử. Như vậy cần tìm K trong dãy A[left…right]. Ban đầu đặt left = 0, right = n – 1.

- So sánh K với phần tử giữa dãy A[mid], với mid là phần nguyên của phép chia
(left + right) cho 2. Nếu K < A[mid] thì giá trị left, right được cập nhật như thế nào?

A. Giá trị right = mid – 1, giữ nguyên giá trị left.

B. Giữ nguyên giá trị right, giá trị left = 1.

C. Giữ nguyên giá trị right, giá trị left = mid – 1.

D. Giá trị right = mid + 1, giữ nguyên giá trị left.

Câu 22. Ma trận vuông có:

A. . B. .

C. . D. .

Câu 23. Quy tắc cộng để tính độ phức tạp thời gian thuật toán là:

A. O(f(n) + g(n)) = f(n) + g(n).

B. O(f(n) + g(n)) = O(max(f(n), g(n))).

C. O(f(n) + g(n)) = O(f(n)) + O(g(n)).

D. O(f(n) + g(n)) = O(min(f(n), g(n))).

Câu 24. Danh sách liên kết đúng cấu trúc dữ liệu là:

A.

B.

C.

D.

PHẦN TỰ LUẬN (4,0 điểm)

Câu 1 (1,5 điểm) Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = n³ – 2n + 9.

b) T(n) = 4n⁵ + n²logn + 7n + 10.

Câu 2 (1,5 điểm) Ưu điểm của việc thiết kế thuật toán và chương trình theo mô đun là gì?

Câu 3 (1,0 điểm) Viết hàm delete_last(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L.

BÀI LÀM:

………………………………………………………………………………………....

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

………………………………………………………………………………………....

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

………………………………………………………………………………………....

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

…………………………………………………………………………………………

TRƯỜNG THPT ........

HƯỚNG DẪN CHẤM KIỂM TRA HỌC KÌ II (2023 - 2024)

MÔN: ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH 11 - KẾT NỐI TRI THỨC

A. PHẦN TRẮC NGHIỆM: (6,0 điểm)

Mỗi câu trả lời đúng được 0,25 điểm.

B. PHẦN TỰ LUẬN: (4,0 điểm)

Câu	Nội dung đáp án	Biểu điểm
Câu 1 (1,5 điểm)	a) Chọn c = 3, n0 = 2. Khi đó với n n0, ta có: T(n) = n3 – 2n + 5 < n3 + n3 + n03 n3 + n3 + n3 = 3n3 = c.n3. Do đó T(n) = O(n3).	0,75 điểm
	b) T(n) = 4n5 + n2logn + 7n + 10 = O(max(4n5, n2logn, 7n, 10)) = O(4n5) = O(n5).	0,75 điểm
Câu 2 (1,5 điểm)	Thiết kế thuật toán và chương trình theo mô đun có các ưu điểm sau: - Chương trình ngắn gọn, sáng sủa, dễ hiểu. - Các mô đun được thiết lập một lần và sử dụng nhiều lần. - Dễ dàng nâng cấp, thay đổi, chỉnh sửa mà không mất công sửa lại toàn bộ chương trình. - Dễ dàng bổ sung các mô đun mới. - Có thể chia sẻ trong môi trường làm việc nhóm, ví dụ phân công mỗi người một công việc độc lập.	0,3 điểm 0,3 điểm 0,3 điểm 0,3 điểm 0,3 điểm
Câu 3 (1,0 điểm)		0,5 điểm 0,5 điểm

TRƯỜNG THPT .........

MA TRẬN ĐỀ KIỂM TRA HỌC KÌ II (2023 - 2024)

MÔN: ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH 11 - KẾT NỐI TRI THỨC

TRƯỜNG THPT .........

BẢN ĐẶC TẢ KĨ THUẬT ĐỀ KIỂM TRA HỌC KÌ II (2023 - 2024)

MÔN: ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH 11 - KẾT NỐI TRI THỨC