Đề 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ố 1)

ĐỀ 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 nào sau đây mô tả đúng thuật toán sắp xếp chèn?

• A.               B. 

• C.               D. 

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

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

Câu 3. Cách tốt nhất để chứng minh tính đúng của một thuật toán là gì?

• A. Suy luận logic.       

• B. Ước lượng thời gian thực hiện các bước trong thuật toán.                                    

• C. Lập luận toán học.          

• D. Sử dụng các bộ dữ liệu kiểm thử.

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

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

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

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

• D. Thuật toán sắp xếp ngược.

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

• A. 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.                            

• B. Ma trận kích thước  sẽ bao gồm  phần tử, có cấu trúc bao gồm  hàng, mỗi hàng có  cột.

• C. Có thể truy cập từng phần tử của mảng một chiều theo chỉ số.                                          

• D. Mảng trong Python được đánh chỉ số từ 1.

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

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

• B. Thuật toán tìm kiếm nhị phân đượ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. Thuật toán tìm kiếm nhị phân không được áp dụng cho các dãy chưa được sắp xếp theo thứ tự xác định.                                                                            

• D. Thuật toán tìm kiếm tuần tự cần nhiều bước nhất khi giá trị cần tìm trùng với số đầu tiên của dãy.

Câu 7. Hàm  sẽ bổ sung node với khoá  vào vị trí nào của danh sách?

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

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

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

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

Câu 8. Cho dãy A = [81, 60, 45, 32, 19, 7, 0]. 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 7 trong dãy?

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

Câu 9. 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(min(f(n), g(n))).                         

• C. O(f(n) + g(n)) = O(max(f(n), g(n))).                        

• D. O(f(n) + g(n)) = O(f(n)) + O(g(n)).

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

• A. 

• B. 

• C. 

• D. 

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. Ma trận vuông  có

• A. .                                           B. .               

• C. .                                           D. .

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. Lệnh nào sau đây dùng để bổ sung phần tử vào cuối danh sách trong Python?

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

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

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

Câu 16. 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. Chương trình ngắn gọn, sáng sủa, dễ hiểu.

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

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

• D. 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âu 17. 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(n).                                               

• D. O(aⁿ).

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

• A. Độ 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.

• B. Khi sử dụng các bộ dữ liệu kiểm thử để kiểm tra tính đúng của chương trình, nếu phát hiện lỗi không chính xác của dữ liệu đầu ra thì kết luận ngay thuật toán và chương trình không đúng.

• C. Độ 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.                              

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

Câu 19. 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 20. Hàm làm tròn lên của thư viện  là

• A. .

• B. .

• C. .

• D. .

Câu 21. Để đưa toàn bộ thư viện math vào bộ nhớ, sử dụng lệnh

• A. from math.

• B. import * from math.

• C. import math.

• D. from math import *.

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], 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[0].

• 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[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].

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

• B. Lệnh gán.

• C. Lệnh in.                                                  

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

Câu 24. Tham số encoding dùng khi mở tệp văn bản có mã gì?

• A. Mã TCVN3.

• B. Mã ASCII.

• C. Mã Unicode.

• D. Mã VNI.

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

b) .

Câu 2 (1,5 điểm) Độ phức tạp thời gian trong trường hợp tổng quát là gì?

Câu 3 (1,0 điểm) Em hãy viết hàm xoá phần tử có khoá k trong danh sách liên kết L.

✄

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