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

CÁNH DIỀU ĐỀ SỐ 5

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át biểu nào sai khi nói về hệ CSDL tập trung?

• A. Phần lớn các cơ quan, doanh nghiệp, tổ chức dùng hệ CSDL tập trung.      
• B. Kiến trúc ngang hàng cho hệ CSDL tập trung có mỗi máy tính hoạt động như một máy khách và máy chủ để truyền tải các dịch vụ CSDL.        
• C. Hệ CSDL tập trung có chi phí thấp hơn hệ CSDL phân tán.        
• D. Một CSDL tập trung được lưu trữ trên một máy tính.

Câu 2. Độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính là:

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

Câu 3. 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.  với  là độ dài của dãy.      
• B.  với  là độ dài của dãy.                             
• C.  với  là độ dài của dãy.                                      
• D.  với  là độ dài của dãy.

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

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

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

• A. Cấu trúc rẽ nhánh (phép lựa chọn) dùng mẫu câu lệnh .  
• B. Lời chú thích bắt đầu bằng dấu “//” cho đến hết dòng.         
• C.  0 nghĩa là gán  nhận giá trị bằng 0.                            
• D. Sử dụng các mức thụt lùi đầu dòng để đánh dấu kết thúc dãy lệnh tuần tự trong mỗi nhánh rẽ của phép lựa chọn hay trong thân vòng lặp của phép lặp.

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

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

Câu 7. 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. ONLY                                        
• C. DISTINCT                                                 
• D. SEPARATE

Câu 8. Lệnh mở tệp ở chế độ “viết” và dùng kí tự tiếng Việt là:

Câu 9. Phương thức nào trong Python dùng để chèn thêm  thành phần tử chỉ số  trong danh sách (ds )?

Câu 10. 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 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. Sử dụng tường lửa.
• D. Mã hoá dữ liệu.

Câu 12. 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 13. Ma trận  có:

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

Câu 14. “Năng lực xác định, kiểm tra và phát hiện các vấn đề tiềm ẩn, nguyên nhân và giải pháp khắc phục các sự cố về CSDL” thuộc kĩ năng nào trong yêu cầu của nghề quản trị CSDL?

• A. Kĩ năng giải quyết vấn đề.                                     
• B. Kĩ năng phân tích dữ liệu.
• C. Kĩ năng tổ chức.                                                 
• D. Kĩ năng giao tiếp.

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í chính giữa dãy số.                                     
• D. Vị trí bất kì.

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

• A. Danh sách liên kết (linked list) cũng gọi là mảng móc nối, gồm các phần tử gọi là nút (node).                      
• B. Một nú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.                     
• C. 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ớ.
• D. Có thể thêm nút vào đầu, cuối hay giữa danh sách liên kết.

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

• A. A = [0, 1.5, 6, “Python”].                                   
• B. B = [[“Two”, 2], [“Seven”, 7], [“Eight”, 8]].
• C. C = [“Computer”, 6.3, 9.0, 4.1].                          
• D. D = [“Black”, “White”, “Pink”, “Blue”].

Câu 18. Độ phức tạp thời gian của thao tác gỡ bỏ nút đầu hay cuối danh sách liên kết là:

• A. 0(1)                           
• B. 0($n^2$) với  là số nút của danh sách.                      
• C. 0($log_{2}n$)  với  là số nút của danh sách.                          
• D. 0(n) với  là số nút của danh sách.

Câu 19. 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.find()                         
• B.search()                               
• C.index()                                                  
• D.position()

Câu 20. 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. Khả năng tái sử dụng.
• C. Tăng tốc độ thực hiện chương trình.    
• D. Dễ kiểm thử và sửa lỗi hơn.

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

• A. Dãy số đã sắp thứ tự tăng dần (không giảm) có thể dùng hàm bisect_right (trong mô đun bisect) để tìm các vị trí phân chia dãy.              
• B. Dãy số đã sắp thứ tự tăng dần (không giảm) có thể dùng hàm bisect_left (trong mô đun bisect) để tìm các vị trí phân chia dãy.        
• C. Dãy số đã sắp thứ tự giảm dần (không tăng) có thể dùng hàm bisect_left (trong mô đun bisect) để tìm các vị trí phân chia dãy.        
• D. Dãy số đã sắp thứ tự giảm dần (không tăng) có thể dùng hàm bisect_right (trong mô đun bisect) để tìm các vị trí phân chia dãy.

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

• A. Lỗi thời gian chạy hay xảy ra trong quá trình soạn thảo chương trình.
• B. Phát hiện lỗi và sửa lỗi là hai việc đan xen trong một quá trình.
• C. Hiện nay, các môi trường tích hợp phát triển phần mềm IDE có công cụ soạn thảo chương trình nhằm hạn chế những sai sót có thể sinh ra lỗi cú pháp.
• D. 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 cú pháp.

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

• A. Thuật toán có độ phức tạp thời gian tuyến tính nếu số phép toán cần thực hiện không phụ thuộc kích thước  của dữ liệu đầu vào.
• B. T(n)=0($C^{n}$)(C$\geq $1)  nghĩa là độ phức tạp thời gian của thuật toán là hàm mũ.
• C. Lời gọi các hàm toán học sơ cấp, các hàm thư viện, … với đầu vào là giá trị cụ thể không phụ thuộc  có độ phức tạp thời gian là T(n)=0(1)
• D. Phép lặp (mô tả bằng cấu trúc lặp) và phép lựa chọn (mô tả bằng cấu trúc rẽ nhánh) là phép toán sơ cấp.

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

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

Câu 1 (2,0 điểm): Em hãy nêu:

a)     Ý tưởng của thuật toán sắp xếp nhanh (Quick Sort).

b)    Ý tưởng chính của thuật toán sắp xếp nhanh áp dụng phân định Hoare.

Câu 2 (2,0 điểm): Em hãy viết chương trình Python thực hiện tìm kiếm tuần tự. 

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:

a) Thuật toán theo chiến lược chia để trị, lặp lại nhiều lần việc phân đoạn dãy đầu vào thành hai đoạn con. Sau một lần phân đoạn, chỉ cần sắp xếp trong nội bộ hai đoạn con. Bài toán sắp xếp ban đầu được chia thành hai bài toán con nhỏ hơn. Việc phân đoạn lặp lại nhiều lần. Hai đoạn con lại được tiếp tục phân đoạn thành 4 đoạn con, 8 đoạn con, … cho đến khi tất cả các đoạn con đều chỉ còn không quá một phần tử. Dãy ban đầu được sắp xếp xong.

b) Ý tưởng chính của thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare là đổi chỗ nhảy qua điểm phân tách (pivot), rà soát từ hai phía, trái và phải, cùng tiến dần từng bước vào giữa. Tạm dừng khi khi phát hiện phần tử vi phạm yêu cầu phân đoạn ở mỗi phía và đổi chỗ chúng cho nhau. Rà soát từ hai điểm tạm dừng đi vào giữa cho đến khi gặp nhau thì kết thúc việc phân đoạn. Điểm gặp nhau là vị trí phân tách dãy thành hai đoạn con.

Câu 2: