BÀI 5: ĐÁNH GIÁ THUẬT TOÁN
A. TRẮC NGHIỆM
1. NHẬN BIẾT
Câu 1: Các thuật toán được đánh giá và so sánh dựa trên một tiêu chuẩn quan trọng đó là ?
- Tính hiệu quả
- Tính chính xác
- Tính khoa học
- A và C đúng
Câu 2: thuật toán được coi là hiệu quả hơn khi?
- Thời gian thực hiện chương trình ít hơn
- Lượng bộ nhớ mà máy tính cần dùng là ít hơn
- Thời gian thực hiện chương trình và lượng bộ nhớ mà máy tính cần dùng là nhiều hơn
- A và B đúng
Câu 3: điền từ thích hợp vào chỗ trống
Python có lệnh…cho phép bấm giờ tính thời gian chạy thực thi chương trình
- Start
- End
- Time
- Copy
Câu 4: cách tính giờ chạy thực thi chương trình cụ thể không áp dụng được vì nó dẫn đến các vấn đề nào?
- Phải lập trình và chạy thử chương trình của tất cả các thuật toán cần so sánh
- Thời gian đo được phụ thuộc vào nhiều yếu tố không liên quan tới thuật toán chương trình chạy nhanh hay chậm
- Không khả thi nếu muốn chọn cách lập nhiều chương trình khác nhau rồi tính thời gian thực thi trung bình
- Tất cả đáp án trên đều đúng
Câu 5: độ phức tạp thời gian là?
- Là một khái niệm trong khoa học máy tính
- Là kết quả ước lượng thời gian thực hiện các chương trình cài đặt thuật toán để xử lí một lượng dữ liệu đầu vào có độ lớn n
- Tất cả đáp án trên đúng
Câu 6: điền từ thích hợp vào chỗ trống?
Một phép toán sơ cấp là phép toán có thời gian thực hiện không lớn hơn …nào đó, không phụ thuộc n
- Một số
- Hằng số
- Hai số
- Ba số
Câu 7: phép toán nào sau đây không phải là phép toán sơ cấp?
- Phép sao chép, phép lựa chọn
- Phép lặp, phép lựa chọn
- Phép lặp, phép bổ sung
- Phép sao chép, phép bổ sung
Câu 8: thuật toán có độ phức tạp thời gian hằng số khi nào?
- Khi mà số phép toán cần thực hiện không phụ thuộc kích thước n của dữ liệu đầu vào
- Khi mà số phép toán cần thực hiện phụ thuộc kích thước n của dữ liệu đầu vào
- Khi mà số phép toán cần thực hiện không phụ thuộc kích thước n của dữ liệu đầu ra
- Khi mà số phép toán cần thực hiện phụ thuộc kích thước n của dữ liệu đầu ra
Câu 9: cách giải thuật toán có độ phức tạp thời gian hằng số là?
- T(n)=1
- T(n)=2
- T(n)=3
- T(n)=4
Câu 10: Cách giải thuật toán có độ phức tạp thời gian tuyến tính là ?
- T(n)= n - 5
- T(n) = n - 3
- T(n)= n – 1
- T(n) = n
2. THÔNG HIỂU
Câu 1: đối với bài toán tìm số lớn nhất trong dãy số cần xét mấy trường hợp?
- 2
- 3
- 4
- 5
Câu 2: Đó là những trường hợp nào?
- Trường hợp thuận lợi nhất, trường hợp bất lợi nhất
- Trường hợp bất lợi nhất, trường hợp ngẫu nhiên
- Trường hợp thuận lợi nhất, trường hợp bất lợi nhất, trường hợp ngẫu nhiên
- Trường hợp thuận lợi nhất, trường hợp ngẫu nhiên
Câu 3: Điền từ thích hợp vào chỗ trống
Nếu số phép số phép toán sơ cấp cần thực hiện không vượt qua một hàm tuyến tính của n,…thì độ phức tạp thời gian của thuật toán là tuyến tính.
3. VẬN DỤNG
Câu 1: Độ phức tạp thời gian của thuật toán tuyến tính được viết ngắn gọn là?
Câu 2: mô tả thuật toán được sử dụng cấu trúc nào?
- Cấu trúc tuần tự
- Cấu trúc rẽ nhánh
- Cấu trúc lặp
- Tất cả đáp án trên đúng
Câu 3: ước lượng độ phức tạp thời gian chia thành trường hợp nào?
- 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 n
- Lời gọi gàm trong trường hợp còn lại sẽ được ước lượng độ phức tạp như với một thuật toán
- A và B đúng
- A và B sai
4. VẬN DỤNG CAO
Câu 1: cấu trúc tuần tự là một dãy gồm….phép toán;…là số xác định, không phụ thuộc n
- C - D
- C - C
- B – C
- B - D
Câu 2: Thời gian thực hiện cấu trúc vòng lặp được tính bằng gì?
- Số lần lặp cộng với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp
- Số lần lặp nhân với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp
- Số lần lặp chia với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp
- Số lần lặp chia với tổng thời gian kiểm tra điều kiện lặp và thời gian thực hiện thân vòng lặp