Đề kiểm tra, đề thi cuối kì 2 tin học 11 định hướng khoa học máy tính kết nối tri thức (đề số 5)

ĐỀ 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. Hàm dùng để làm tròn của thư viện math là

A. floor().

B. round().

C. sqrt().

D. ceil().

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. Danh sách liên kết đúng cấu trúc dữ liệu là:

A. 

B. 

C. 

D. 

Câu 4. Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất?

A. Khi giá trị cần tìm trùng với số đầu tiên của dãy.

B. Khi không tìm thấy.

C. Khi dãy số không được sắp xếp theo thứ tự xác định.

D. Khi giá trị cần tìm trùng với số chính giữa dãy.

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

A. Trong Tin học, dữ liệu mảng một chiều thường được gọi là cấu trúc dữ liệu tuyến tính.

B. Phần tử nằm tại hàng i và cột j của ma trận A được kí hiệu là aij.

C. Khái niệm mạng của khoa học máy tính được đồng nhất với kiểu dữ liệu list trong Python.

D. Trong Python, cấu trúc dữ liệu hai chiều có thể được biểu diễn bằng mô hình danh sách trong danh sách.

Câu 6. Toán tử kiểm tra một đối tượng có nằm trong mảng hay không là

A. on. B. in. C. check. D. while.

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

A. remove(). B. cut(). C. clear(). D. delete().

Câu 8. Cho dãy A = [5, 8, 12, 36, 79, 81, 90]. 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 8 trong dãy?

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

Câu 9. Độ phức tạp không gian (space complexity) là gì?

A.Là độ phức tạp tính toán quan trọng nhất 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.

B. Là thời gian thực hiện chương trình/thuật toán.

C. Là tài nguyên của máy tính trong đó có phần bộ nhớ được sử dụng để thực hiện chương trình.

D. Là số lần thực hiện các phép toán/câu lệnh có trong chương trình/thuật toán.

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.

B. Mỗi bài toán nhỏ được viết thành một mô đun con của chương trình.

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

D. Các mô đun tương đối độc lập với nhau.

Câu 11. “Thực hiện một vòng lặp với chỉ số chạy từ phần tử đầu tiên đến phần tử gần cuối” là ý tưởng của thuật toán sắp xếp nào?

A. Thuật toán sắp xếp chèn.

B. Thuật toán sắp xếp nhị phân.

C. Thuật toán sắp xếp nổi bọt.

D. Thuật toán sắp xếp chọn.

Câu 12. Lệnh mở tệp để ghi tiếp dữ liệu là

A. f=open(, “a”, encoding = “UTF-8”).

B. f=open(, “r”, encoding = “UTF-8”).

C. f=open(, “o”, encoding = “UTF-8”).

D. f=open(, “w”, encoding = “UTF-8”).

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

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

C. 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 đó.

D. Ở 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.

Câu 14. Vòng lặp thứ hai của thuật toán sắp xếp nổi bọt cần thực hiện bao nhiêu bước lặp?

A. n – i.

B. n – 1.

C. n + 1 – i.

D. n – 1 – i.

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

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

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

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

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

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

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

A. O(an). B. O(n!). C. O(n). D. O(n2).

Câu 18. Cho ma trận M=4 1 8 9 3 2 0 8 6 . Phát biểu nào sau đây sai?

A. Ma trận M là ma trận vuông bậc 3.

B. M02=M21=8.

C. M20=0.

D. Ma trận M có thể khai báo trong Python như sau: M=4, 9, 0, 1, 3, 8, 8, 2, 6 .

Câu 19. 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 if với nhiều trường hợp rẽ nhánh.

D. Lệnh in.

Câu 20. 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 21. Hàm insert(L, k) sẽ bổ sung node với khoá k vào vị trí nào của danh sách?

A. Vị trí đầu của danh sách.

B. Vị trí cuối của danh sách.

C. Vị trí chính giữa của danh sách.

D. Vị trí bất kì của danh sách.

Câu 22. 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. Dễ dàng nâng cấp, thay đổi, chỉnh sửa chương trình.

B. Các mô đun được thiết lập một lần và sử dụng nhiều lần.

C. Khó bổ sung các mô đun mới.

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

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

A. L= LL().

B. LL=L().

C. L=().

D. LL=().

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

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

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

C. Nếu với các bộ dữ liệu kiểm thử, dữ liệu đầu ra đều đúng thì điều đó chứng minh thuật toán hay chương trình đúng.

D. Độ 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.

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) Tn=7n6 -n3 +4.

b) Tn=n4 +9n +2nlog n  +n!.

Câu 2 (1,5 điểm) 

a) Kiểm thử có vai trò như thế nào?

b) Độ phức tạp thời gian thường bị ảnh hưởng bởi điều gì?

Câu 3 (1,0 điểm) Cho dãy số A = [9, 5, 0, 1, 4, 0, 8, 1, 1]. Em hãy viết chương trình tính số lần lặp của một giá trị bất kì trong dãy A. 

✄

BÀI LÀ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

 - Biết cách thiết lập và làm việc với cấu trúc dữ liệu mảng một chiều và hai chiều. - Hiểu được mô hình biểu diễn mảng một chiều và mảng hai chiều. - Thực hiện được lệnh và chương trình làm việc đơn giản với mảng như khởi tạo mảng, tính toán đơn giản trên mảng một chiều và hai chiều. - Sử dụng được mảng một chiều và hai chiều trong lập trình.- Ứng dụng kiểu dữ liệu list để thể hiện mảng một và hai chiều trong các bài toán cụ thể.- Viết được các câu lệnh để khai báo mảng một chiều và hai chiều, thực hiện một số thao tác cơ bản với mảng như thêm và duyệt phần tử, tính độ dài của mảng. - Biết được ý nghĩa của bài toán tìm kiếm trên thực tế.- Biết được chương trình tìm kiếm tuần tự và tìm kiếm nhị phân. - Thực hiện được các chương trình tìm kiếm tuần tự và tìm kiếm nhị phân trên một mảng dữ liệu tuyến tính. - Biết được cách đọc dữ liệu từ tệp dữ liệu trong máy tính. - Áp dụng được thuật toán tìm kiếm trong một vài bài toán cụ thể.- Thực hiện được việc đọc và ghi dữ liệu vào tệp dữ liệu trong máy tính, có thể sử dụng thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân để tìm kiếm một phần tử trong mảng. - Biết được một số thuật toán sắp xếp đơn giản. - Hiểu được ý tưởng của một số thuật toán sắp xếp đơn giản. - Thực hiện được các thuật toán và chương trình sắp xếp đơn giản như sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt. - Hiểu được hai thuật toán sắp xếp là sắp xếp chèn và sắp xếp chọn. - Thực hiện được hai thuật toán sắp xếp là sắp xếp chèn và sắp xếp chọn, có thể áp dụng hai thuật toán trên để sắp xếp dãy số theo thứ tự tăng hoặc giảm dần. - Biết được vai trò của kiểm thử là làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của chương trình.- Biết được các tiêu chí đánh giá hiệu quả và tính đúng của chương trình. - Trình bày được những tiêu chí đánh giá tính hiệu quả của chương trình. - Thực hiện được lập trình tính thời gian chạy của chương trình. - Nhận biết được phép toán tích cực trong chương trình.- Biết cách phân tích độ phức tạp thời gian thuật toán.- Biết được cách tính toán độ phức tạp thời gian của một số thuật toán đã biết. - Hiểu được ý nghĩa của các hàm thời gian. - Thực hiện được tính toán độ phức tạp thời gian của một số thuật toán đã biết. - Thực hành xác định độ phức tạp (O-lớn) của hàm thời gian. - Biết được phương pháp làm mịn dần trong lập trình. - Giải thích được phương pháp làm mịn dần trong lập trình. - Vận dụng được phương pháp làm mịn dần để thiết kế chương trình. - Thực hành thiết kế chương trình theo phương pháp làm mịn dần. - Nhận biết được lợi ích của phương pháp thiết kế chương trình theo mô đun. - Hiểu được cách thiết kế chương trình theo mô đun. - Vận dụng được cách thiết kế chương trình theo mô đun cho một số bài toán cụ thể. - Thực hành thiết kế một số chương trình hoàn chỉnh theo mô đun. - Nhận biết một số hàm của thư viện math. - Hiểu được việc thiết lập thư viện cho chương trình.- Trình bày được cấu trúc danh sách liên kết. - Tạo được một thư viện nhỏ của người lập trình. - Viết được chương trình vận dụng những kiến thức tích hợp liên môn để giải quyết vấn đề.