ĐỀ THI GIỮA KÌ 2 TIN HỌC ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH 11 KẾT NỐI TRI THỨC ĐỀ 4

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. Mảng hai chiều là:

• A. A = [1, 2, 3, 4, 5].                                                    
• B. B = [7, 8, 9, “Tiếng Anh”].
• C. C = [“Tin học”, 10].                          
• D. D = [[“Ngữ Văn”, 8.5], [“Lịch Sử”, 9.5], [“Địa lí”, 9.0]].

Câu 2. Để bổ sung phần tử vào cuối danh sách trong Python, ta sử dụng lệnh:

• A.insert()
• B. append().
• C.add()
• D. extend()

Câu 3. Cấu trúc dữ liệu mảng một chiều trong Python có thể biểu diễn bằng kiểu dữ liệu:

• A. str.
• B. list.
• C. int.
• D. bool.

Câu 4. Chọn câu đúng.

• A. Sử dụng toán tử in và lệnh for … in để duyệt từng phần tử của mảng một chiều trong Python.                                 
• B. Phần tử nằm tại cột  và hàng  của ma trận kích thước m  n được kí hiệu là .
• C. Hàm clear dùng để xoá một phần tử bất kì của danh sách.
• D. Phần tử thứ 3 của mảng D = [8, 1, 9, 5, 6] là 5.

Câu 5. Ma trận vuông  bậc 3 dưới đây có thể khai báo trong Python như thế nào?

Câu 6. Để truy cập phần tử tại hàng 1 cột 3 của ma trận  ở câu 5, ta gõ lệnh:

• A.M[1][3]
• B.M[3][1]
• C.M[2][0]
• D.M[0][2]

Câu 7. Chọn câu sai.

• A. 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.                                                    
• B. Việc thiết kế thuật toán tìm kiếm sẽ phụ thuộc vào cấu trúc của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm kiếm.
• C. Tìm kiếm là một trong những bài toán quan trọng nhất của Tin học.                      
• 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 8. Cho dãy A = [21, 58, 0, 9, 36, 7, 100, 45, 82, 1]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 45 trong dãy?

• A. 6.
• B. 7.
• C. 8.
• D. 9.

Câu 9. Cho dãy A = [0, 2, 6, 14, 35, 47, 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 47 trong dãy?

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

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

Câu 11. Cách đơn giản nhất để ghi dữ liệu ra tệp văn bản là sử dụng lệnh:

• A.write()
• B.print()
• C. add().
• D.copy()

Câu 12. Để đọc toàn bộ dữ liệu tệp, đưa kết quả vào một danh sách (list), mỗi phần tử là một dòng, ta sử dụng lệnh:

• A.f.readlist()                                                        
• B.f.readall()
• C.f.readline()                                                           
• D.f.readlines()

Câu 13. Em đã được học mấy thuật toán sắp xếp đơn giản?

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

Câu 14. Ý tưởng của thuật toán sắp xếp nổi bọt là cho cho chỉ số j chạy từ:

• A. 0 đến n – 2.
• B. 1 đến n – 2.
• C. 0 đến n – 1.
• D. 1 đến n – 1.

Câu 15. Chọn câu 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. 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. 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.

Câu 16. Ý 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ử đầu tiên đến gần cuối dãy.                            
• B. Phần tử thứ hai đến gần cuối dãy.
• C. Phần tử đầu tiên đến cuối dãy.                                  
• D. Phần tử thứ hai đến cuối dãy.

Câu 17. Trong thuật toán sắp xếp chèn, vòng lặp for … in … được viết như thế nào?

• A.for i in range(1,n)
• B. for i in range (n,1)
• C. for i in range(0,n)
• D. for i in range(n)

Câu 18. Chọn câu đú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ử nhỏ nhất này với A[0].                         
• 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[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+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ử lớn 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[n-1].

Câu 19. Độ phức tạp tính toán phổ biến nhất có mấy loại?

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

Câu 20. Chọn câu sai.

• A. Kiểm thử làm tăng độ tin cậy của 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. Nếu với các bộ dữ liệu kiểm thử, dữ liệu đầu ra đều đúng thì kết luận ngay thuật toán và chương trình đúng.
• D. Các phương pháp kiểm thử không có tính năng chứng minh được tính đúng của một thuật toán.

Câu 21. Hiệu quả hay tính tối ưu của chương trình thường được xem xét trên cơ sở đánh giá:

• A. Độ phức tạp tính toán.
• B. Độ tin cậy của chương trình.                                    
• C. Tính đúng của thuật toán.                         
• D. Ý tưởng thực hiện thuật toán.

Câu 22. Chương trình kiểm tra số nguyên tố sau sai ở dòng thứ mấy?

• A. 4.
• B. 5.
• C. 6.
• D. 7.

Câu 23. Tính đúng của thuật toán cần được chứng minh bằng:

• A. Các bộ dữ liệu kiểm thử.    
• B. Thời gian thực hiện chương trình.                             
• C. Độ phức tạp của thuật toán.                      
• D. Lập luận toán học.

Câu 24. Chọn câu sai.

• A. Để đánh giá hiệu quả chương trình đôi khi người ta còn quan tâm tới các tiêu chí như tính dễ hiểu, rõ ràng, ngắn gọn, dễ cài đặt, dễ bảo trì, … của chương trình.
• 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 thời gian thường bị ảnh hưởng bởi 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.
• D. Độ phức tạp tính toán quan trọng nhất là độ phức tạp không gian.

B. PHẦN TỰ LUẬN (4,0 điểm)

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

a) Nêu cách thực hiện thuật toán tìm kiếm nhị phân.

b) Cho dãy số A = [8, 0, 5, 9, 2]. Hãy mô tả các bước của thuật toán tìm kiếm tuần tự để tìm kiếm phần tử có giá trị bằng 9.

Câu 2 (2,0 điểm) Cho dãy A = [38, 12, 57, 46, 90, 1, 88]. Viết chương trình sắp xếp dãy A theo thứ tự tăng dần theo thuật toán sắp xếp nổi bọt.

Hướng dẫn trả lời

A. PHẦN TRẮC NGHIỆM:

B. PHẦN TỰ LUẬN:

Câu 1:

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. Nếu giá trị của phần tử ở giữa bằng K thì thông báo tìm thấy. Nếu giá trị K nhỏ hơn giá trị của phần tử ở giữa thì thu hẹp phạm vi tìm kiếm là nửa đầu của dãy tăng A (ngược lại thì phạm vi tìm kiếm là nửa sau). Cứ tiếp tục thu hẹp phạm vi như vậy cho đến khi tìm thấy hoặc đã duyệt hết thì thông báo không tìm thấy.

b)

Bước 1: i = 0: A[0] = 8 không bằng 9.

Bước 1: i = 1: A[1] = 0 không bằng 9.

Bước 1: i = 2: A[2] = 5 không bằng 9.

Bước 1: i = 3: A[3] = 9 là phần tử cần tìm.

Câu 2: