Đề thi cuối kì 2 khoa học máy tính 11 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. Ma trận vuông  có:

• A. .          

• B. .          

• C. .          

• D. .

Câu 2. 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 3. 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ử 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].

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

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

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

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

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

• A. .                                                                  

• B. L.

• C. .                                                               

• D. .

Câu 8. 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 9. Thuật toán sắp xếp chọn có độ phức tạp là:

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

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

• A. A = [“Math”, 2, 3.8].                                               

• B. B = [0, 1, 0, 0, 1].

• C. C = [[“abc”, 10], [“bcd”, 20], [“cde”, 30]].                 

• D. D = [4, 5, 6, “July”].

Câu 11. 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 12. 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 13. 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 14. Cho dãy A = [0, 1, 4, 9, 12, 30, 56]. 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 30 trong dãy?

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

Câu 15. Hàm tính căn bậc hai của thư viện  là:

• A. .                                                     B. .                       

• C. .                                                      D. .

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

• A.  

• B.  

• C.  

• D.  

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

• 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. Ở 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 18. Lệnh mở tệp để ghi tiếp dữ liệu là:

• A. .

• B. .

• C. .

• D. .

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

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

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

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

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

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

Câu 21. 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ưởng thực hiện thuật toán.                 

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

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

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

Câu 22. 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 gán.

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

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

• D. Lệnh in.

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

• A. 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 ba vòng lặp lồng nhau.                           
• 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. 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.             
• D. Ý 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ử cạnh nhau nếu chúng chưa được sắp thứ tự đúng.

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. Một chương trình/thuật toán là hiệu quả nếu độ phức tạp của thuật toán này là thấp.

• 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. Độ 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) T(n) = n5 – 7n2 + 4.

b) T(n) = n3logn + n! + 6n.

Câu 2 (1,5 điểm) Em hãy trình bày cấu trúc dữ liệu của danh sách liên kết.

Câu 3 (1,0 điểm) Em hãy sử dụng thư viện math để viết hàm prime(n) kiểm tra số tự nhiên n có là số nguyên tố hay không.

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