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

ĐỀ 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. Lệnh nào dùng để bổ sung phần tử vào vị trí bất kì của danh sách trong Python?

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

Câu 2. Kí hiệu O-lớn dùng để làm gì?

• A. Đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu vào của bài toán giảm xuống vô cùng.

• B. Đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu ra của bài toán tăng lên vô cùng.

• C. Đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu ra của bài toán giảm xuống vô cùng.

• D. Đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu vào của bài toán tăng lên vô cùng.

Câu 3. Thuật toán sắp xếp chèn có độ phức tạp là

• A. O(n!).                      B. O(n).                   C. O(n²).                                   D. O(aⁿ).

Câu 4. Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

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

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

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

• D. Khi dãy số đã được sắp xếp theo thứ tự xác định.

Câu 5. 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 6. 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 7. 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. Chương trình chính là một bản ghép nối các hàm và thủ tục con.

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

Câu 8. 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 9. Lệnh duyệt từng phần tử của mảng là

• A.  …  …                                               

• B.  …  …                   

• C. …  …                                                     

• D.  …

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

• A. A = [“Math”, 10, 8.5].                                             

• B. B = [[“abc”, 6], 12].

• C. C = [[“one”, 1], [“two”, 2], [“three”, 3]].                    

• D. D = [1, 0, 7, 9, 1].

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

• A. .          

• B. .          

• C. .          

• D. .

Câu 12. Việc tìm kiếm phần tử có khoá  trong danh sách  bắt đầu từ vị trí nào?

• A. Từ node bất kì của danh sách.

• B. Từ node cuối cùng của danh sách.

• C. Từ node đầu tiên của danh sách.

• D. Từ node chính giữa danh sách.

Câu 13. Hàm tính giá trị tuyệt đối của một số trong thư viện  là

• A. .                                                     B. .                       

• C. .                                                      D. .

Câu 14. Cho dãy A = [1, 2, 10, 25, 36, 81, 100]. 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 81 trong dãy?

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

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

Câu 16. 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. 2.                         C. 3.                                          D. 4.

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

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

• D. 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âu 18. Nếu không có tham số encoding trong lệnh mở tệp văn bản thì chỉ đọc được văn bản có mã gì?

• A. Unicode.

• B. VISCII.

• C. ASCII.

• D. TCVN3.

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

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

• 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 21. Phương án nào sau đây không phải là tiêu chí đánh giá hiệu quả và tính đúng của chương trình?

• A. Tính dễ hiểu.          

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

• C. Tính dễ cài đặt.               

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

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

• A. .                                                               

• B. .

• C. .                                                                  

• D. L.

Câu 23. Ý 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ứ nhất đến cuối dãy.                                                             

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

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

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

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

b) .

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

Câu 3 (1,0 điểm) Em hãy thiết lập một thư viện bao gồm hàm nhập dữ liệu và hàm sắp xếp chọn.

✄

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