ĐỀ 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. Phát biểu nào sau đây đúng?

A. Các phương pháp kiểm thử có tính năng chứng minh được tính đúng của một thuật toán.

B. Độ phức tạp tính toán quan trọng nhất là độ phức tạp thời gian liên quan trực tiếp tới dung lượng bộ nhớ được sử dụng để thực hiện chương trình.

C. Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học.

D. Độ phức tạp không gian phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình/thuật toán.

Câu 2. 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(f(n)) + O(g(n)).

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

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

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

A. .

B. .

C. .

D. L.

Câu 4. Hàm nào sau đây mô tả đúng thuật toán sắp xếp chèn?

A. B.

C. D.

Câu 5. Thuật toán sắp xếp nổi bọt có độ phức tạp là:

A. O(n).

B. O(n!).

C. O(aⁿ).

D. O(n²).

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

A. A = [[“Kate”, 8.0], [“Louis”, 8.5], [“Mary”, 8.5]].

B. B = [0, 1, 0, “Computer”].

C. C = [“Java”, “Ruby”, “PHP”, “Python”, “Perl”].

D. D = [“Black”, “White”, “Red”, 5.2].

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

A. Ý tưởng của thuật toán sắp xếp nổi bọt là liên tục đổi chỗ hai phần tử bất kì nếu chúng chưa được sắp thứ tự đúng.

B. Thuật toán sắp xếp nổi bọt kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ.

C. Có nhiều cách thể hiện thuật toán sắp xếp nổi bọt, nhưng cách thường dùng là sử dụng hai vòng lặp lồng nhau.

D. Thuật toán sắp xếp nổi bọt lấy ý tưởng từ hiện tượng “nổi bọt” của không khí dưới nước.

Câu 8. 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 9. Phát biểu nào sau đây sai khi nói về ưu điểm của việc thiết kế thuật toán và chương trình theo mô đun?

A. Có thể chia sẻ trong môi trường làm việc nhóm.

B. 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.

C. Các mô đun chỉ được sử dụng một lần.

D. Chương trình ngắn gọn, sáng sủa, dễ hiểu.

Câu 10. 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 11. 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. Mỗi mô đun có thể là một số hàm hoặc thủ tục độc lập.

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

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 12. Cho dãy A = [0, 3, 7, 21, 26, 54, 80]. 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 3 trong dãy?

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

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

A. Thuật toán tìm kiếm nhị phân được thực hiện bằng cách liên tục thu hẹp phạm vi tìm kiếm.

B. Thuật toán tìm kiếm tuần tự không được áp dụng cho các dãy được sắp xếp theo thứ tự xác định.

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ự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.

Câu 14. Hàm làm tròn lên của thư viện là:

A. . B. .

C. . D. .

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

A.

B.

C.

D.

Câu 16. Lệnh mở tệp để ghi dữ liệu từ đầu là:

A. .

B. .

C. .

D. .

Câu 17. Để xoá một phần tử của danh sách trong Python, ta sử dụng lệnh:

A. . B. clear. C. . D. pop.

Câu 18. 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. Độ tin cậy của chương trình.

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

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

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

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

A. .

B. .

C. .

D. .

Câu 20. 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. 5. C. 6. D. 4.

Câu 21. 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 in.

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

C. Lệnh gán.

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

Câu 22. 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+1],…, A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i+1].

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+1],…, A[n] và đổi chỗ phần tử nhỏ nhất này với A[i+1].

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], A[i+1],…, A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i].

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], A[i+1],…, A[n] và đổi chỗ phần tử nhỏ nhất này với A[i].

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

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

B. Có thể thiết lập hàm chỉnh sửa thông tin trên danh sách liên kết.

C. Mỗi danh sách liên kết bao gồm hai cấu trúc dữ liệu là cấu trúc linked list và cấu trúc head.

D. Hàm delete(L) sẽ xoá node bất kì của danh sách L (nếu danh sách không rỗng).

Câu 24. 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ị left = mid + 1, giữ nguyên giá trị right.

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

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

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

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⁴ + n³ + 18.

b) T(n) = 9ⁿ + 5nlogn + n² + 1.

Câu 2 (1,5 điểm) Phương pháp làm mịn dần trong thiết kế chương trình phải tuân thủ các quy trình và nguyên tắc gì?

Câu 3 (1,0 điểm) Cho trước một danh sách liên kết L. Viết một hàm đếm số lượng phần tử của danh sách liên kết này.

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 = 3. Khi đó với n n0, ta có: T(n) = n4 + n3 + 18 < n4 + n4 + n04 n4 + n4 + n4 = 3n4 = c.n4. Do đó T(n) = O(n4).	0,75 điểm
	b) T(n) = 9n + 5nlogn + n2 + 1 = O(max(9n, 5nlogn, n2, 1)) = O(9n).	0,75 điểm
Câu 2 (1,5 điểm)	Phương pháp làm mịn dần trong thiết kế chương trình phải tuân thủ các quy trình và nguyên tắc sau: - 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. - 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. - 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ế chi tiết hơn bước trước đó. Quá trình như vậy sẽ tiếp tục cho đến khi viết xong toàn bộ các câu lệnh của chương trình giải bài toán đã cho.	0,5 điểm 0,5 điểm 0,5 đ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