ĐỀ THI CUỐI HỌC KÌ 2 MÔN KHOA HỌC MÁY TÍNH 11

CÁNH DIỀU ĐỀ SỐ 2

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. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân là:

• • A. 0($n^2$)                                                                  B.0($log_{2}n$).          
  • C. 0($C^n$)                                                           D. 0(n)

Câu 2. Từkhoá để quy định: Nếu kết quả có nhiều dòng giống nhau thì chỉ một dòng được đưa vào kết quả là:

• • A. UNIQUE                                                          
  • B. SEPARATE                                           
  • C. DISTINCT                                                 
  • D. ONLY     

Câu 3. Danh sách liên kết nào sau đây đúng cấu trúc dữ liệu?

Câu 4. Mảng một chiều được khai báo như một danh sách Python là:

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

• A. Lỗi cú pháp là lỗi hay xảy ra trong quá trình soạn thảo chương trình.
• B. Lỗi thời gian chạy là chương trình đã biên dịch, chạy thử thành công một vài lần vẫn có thể đột ngột dừng giữa chừng hoặc chạy mãi không dừng.
• C. Người lập trình chỉ cần hiểu rõ ngôn ngữ lập trình mình sử dụng là có thể dễ dàng sửa lỗi thời gian chạy.
• D. Việc phát hiện chương trình còn lỗi và sửa lỗi sẽ không phân biệt đó là lỗi chương trình thực hiện thuật toán hay lỗi của bản thân thuật toán.

Câu 6. Kết quả của hàm round(189.267,1)  là:

• A.189.2                                                                B. 189.27
• C.189.3                                                                 D. 189.26

Câu 7. Ma trận  có:

Câu 8. Để sử dụng  như một thư viện cần khai báo như thế nào?

• • A. import lib from* from lib import*  from*import lib*                                             
  • B. from lib import*
  • C. import* from lib                                                       
  • D. from* import lib 

Câu 9. Trong Python, hàm nào với tham biến  dùng để sắp xếp danh sách các cặp hay các bộ nhiều thành phần, theo giá trị của một thành phần bất kì trong bộ?

• • A. sorted()                                                               
  • B. sort()    
  • C. arrange()                                                       
  • D. ordered()

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

• A. Một nút của danh sách liên kết có hai thành phần: phần Data chứa địa chỉ của nút liền kề, phần liên kết gọi là Next.              
• B. Các nút danh sách liên kết được lưu trữ thành một khối liên tục liền kề và không tách rời nhau trong bộ nhớ.
• C. Có thể thêm nút vào đầu, cuối và giữa danh sách liên kết.
• D. Các nút trong danh sách liên kết có chỉ số giống như các phần tử của danh sách mảng.

Câu 11. Phương án nào không phải là biện pháp bảo mật thông tin trong CSDL?

• A. Sao lưu dự phòng và duy trì biên bản hệ thống.
• B. Giám sát hiệu suất CSDL.
• C. Nén dữ liệu.
• D. Mã hoá dữ liệu.

Câu 12. Phương thức nào trong Python thực hiện tìm kiếm phần tử trong một dãy tuần tự (xâu kí tự, mảng hoặc danh sách) và trả về vị trí của phần tử đó?

• • A. index() search()                                                            B. find()               
  • C. search()                                                           D. position() 

Câu 13. Phương thức nào trong Python dùng để xoá các phần tử bắt đầu từ vị trí  đến hết danh sách (ds )?

• A. ds.delete(i)
• B. ds.cut(i)
• C. ds.remove(i)
• D. ds.clear(i)

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

• A. Thuật toán sắp xếp nhanh được thiết kế theo chiến lược “chia để trị”.
• B. Thuật toán sắp xếp nhanh có thể áp dụng một trong hai lược đồ phân đoạn: theo Lomuto hoặc theo Hoare.
• C. Lược đồ Lomuto thực hiện phân đoạn bằng cách kiểm tra theo một chiều từ phải sang trái, đổi chỗ và dịch chuyển dần vị trí phân tách hai dãy con cho đến khi thoả mãn yêu cầu phân đoạn.
• D. Lược đồ Hoare thực hiện phân đoạn bằng cách kiểm tra theo hai chiều, từ hai đầu dãy số tiến dần vào giữa, đổi chỗ để thoả mãn yêu cầu phân đoạn; kết thúc khi gặp nhau.

Câu 15. Trong thuật toán Lomuto, pivot là phần tử ở vị trí nào của dãy số?

• A. Vị trí đầu dãy số.                                                
• B. Vị trí cuối dãy số.
• C. Vị trí bất kì.                                                        
• D. Vị trí chính giữa dãy số.

Câu 16. Kết quả của đoạn chương trình dưới đây là:

• A. a = [2, 7, 1, 9, 0, 8, 4].                                        
• B. a = [7, 1, 9, 0, 8, 4].
• C. a = [2, 7, 1, 9, 0, 8].                                             
• D. a = [7, 1, 9, 0, 8, 4, 5].

Câu 17. Hệ CSDL phân tán không phù hợp với:

• A. Hệ thống quản lí học sinh của trường em.
• B. Các hệ thống dịch vụ dựa trên web.
• C. Hệ thống thương mại điện tử.
• D. Hệ thống tìm kiếm của Google.

Câu 18. Thao tác gỡ bỏ nút đầu hay cuối danh sách có thời gian thực hiện là:

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

• A. Lời gọi các hàm toán học sơ cấp với đầu vào là giá trị cụ thể không phụ thuộc  có độ phức tạp thời gian là 0(1).
• B. Độ phức tạp thời gian của thuật toán tìm giá trị cực tiểu một dãy số a1, a2, a3...an  là 0(n) .
• C. Lời gọi các hàm thư viện có độ phức tạp thời gian là T(n)=0(n)
• D. Độ phức tạp thời gian của cấu trúc rẽ nhánh là độ phức tạp thời gian lớn nhất trong các độ phức tạp thời gian của các nhánh.

Câu 20. Quy ước nào đúng khi viết mã giả?

• A.  x=6 nghĩa là gán x nhận giá trị bằng 6.             
• B. Số lần lặp chưa biết trước: Phỏng theo mẫu lệnh  của Python.
• C. Số lần lặp biết trước: Phỏng theo mẫu lệnh  của Python.             
• D. Lời chú thích bắt đầu bằng dấu “#” cho đến hết dòng.

Câu 21. Phương án nào không phải là ưu điểm của lập trình theo phương pháp mô đun hoá?

• A. Chương trình dễ hiểu hơn.                                  
• B. Phối hợp cùng lập trình viên.
• C. Ít mắc phải lỗi logic khi viết chương trình.          
• D. Dễ kiểm thử và sửa lỗi hơn.

Câu 22. Vòng lặp 2 của thuật toán sắp xếp nổi bọt cần rà soát nghịch thế và đổi chỗ đến vị trí nào của dãy?

• A. n-1 với n là độ dài của dãy.      
• B. n-2 với n  là độ dài của dãy.                             
• C. n+1 với n là độ dài của dãy.                                
• D.  n với n là độ dài của dãy.

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

• • A. Nếu i>j  mà $a_{i}$>$a_{j}$ thì cặp hai phần tử ($a_{i}$ ,$a_{j}$ ) gọi là một nghịch thế.
  • B. Nếu i<j  mà $a_{i}$<$a_{j}$ thì cặp hai phần tử ($a_{i}$ , $a_{j}$ ) gọi là một nghịch thế.         
  • C. Nếu i>j  mà $a_{i}$<$a_{j}$ thì cặp hai phần tử ($a_{i}$ , $a_{j}$ ) gọi là một nghịch thế.         
  • D. Nếu i<j  mà $a_{i}$>$a_{j}$ thì cặp hai phần tử ($a_{i}$ , $a_{j}$ ) gọi là một nghịch thế.

Câu 24. Nhà quản trị CSDL cần thường xuyên cập nhật xu thế phát triển CSDL để:

• A. Đề xuất mở rộng, nâng cấp các khả năng đáp ứng trong CSDL.                     
• B. Có những dự báo tương lai về: không gian lưu trữ của CSDL, công suất sử dụng CSDL.
• C. Phán đoán sự cố, nhanh chóng khắc phục các sự cố về CSDL.                       
• D. Kiểm soát và đảm bảo tính toàn vẹn an toàn cho dữ liệu.

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

Câu 1 (2,0 điểm): Em hãy nêu một số gợi ý các ca kiểm thử để phát hiện lỗi chương trình.

Câu 2 (2,0 điểm): Em hãy viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính. 

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

 A. PHẦN TRẮC NGHIỆM: (6,0 điểm)

        Mỗi câu trả lời đúng được 0,25 điểm.  

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

Câu 1:

- Kiểm tra các câu lệnh rẽ nhánh với đầu vào tương ứng cho đủ các trường hợp. 

- Kiểm tra các câu lệnh lặp với đầu vào khiến số lần lặp là 0 lần, 1 lần, nhiều lần. 

  - Kiểm tra với các giá trị ở các đầu mút trái, phải của một biểu thức điều kiện. Ví dụ, với điều kiện a $\leq $ x $\leq $ b , hãy thử với các giá trị  và . Các hạn chế “không là số dương”, “không là số âm”, … hãy thử với đầu vào bằng 0.

- Cần thận trọng với điều kiện “bằng nhau” khi so sánh hai biến kiểu số thực vì kết quả tính toán có thể bị làm tròn. Ví dụ, sau khi tính tỉ lệ phần trăm, cộng các tỉ lệ phần trăm không chắc sẽ đúng bằng 100. 

- Kiểm tra với các đầu vào “không mong đợi” nếu muốn biết chương trình sẽ hoạt động như thế nào khi người khác chạy “khám phá”. Các giá trị không mong đợi có thể là giá trị rất lớn hoặc rất gần số không, giá trị không hợp lệ, …

Câu 2: