15 câu Trắc nghiệm Tin học 11 Cánh diều Định hướng KHMT Bài 5: Đánh giá thuật toán có đáp án
15 câu hỏi
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Độ phức tạp thời gian của thuật toán được xác định bởi yếu tố nào?
Kích thước dữ liệu đầu vào
Ngôn ngữ lập trình
Kỹ năng lập trình viên
Thời gian thực hiện cụ thể của thuật toán
Đáp án: A
Giải thích: Độ phức tạp thời gian chủ yếu phụ thuộc vào kích thước dữ liệu đầu vào (n). Các yếu tố khác như ngôn ngữ lập trình hay kỹ năng lập trình viên có thể ảnh hưởng đến hiệu suất thực tế nhưng không phải là yếu tố chính để xác định độ phức tạp.
Độ phức tạp thời gian tuyến tính được ký hiệu là gì?
O(1)
O(log n)
O(n)
O(n^2)
Đáp án: C
Giải thích: Độ phức tạp thời gian tuyến tính được ký hiệu là O(n), có nghĩa là số phép toán cần thực hiện tỷ lệ thuận với kích thước đầu vào n.
Phép toán nào được coi là phép toán sơ cấp?
Phép cộng hai số
Phép lặp
Phép lựa chọn
Phép khai căn
Đáp án: A
Giải thích: Phép cộng hai số là phép toán sơ cấp vì nó thực hiện trong thời gian không phụ thuộc vào kích thước n của dữ liệu đầu vào. Các phép lặp và lựa chọn không được coi là sơ cấp.
Thuật toán nào sau đây có độ phức tạp thời gian hằng số?
Tìm kiếm một phần tử trong danh sách
Tính tổng dãy số từ 1 đến n bằng công thức
Sắp xếp một danh sách số
Tính giai thừa của n
Đáp án: B
Giải thích: Tính tổng dãy số từ 1 đến n bằng công thức S = n(n + 1)/2 có độ phức tạp thời gian hằng số (O(1)) vì số phép toán không phụ thuộc vào n.
Khi ước lượng độ phức tạp thời gian của thuật toán, quy tắc nào được áp dụng?
Chỉ giữ lại các phép toán có bậc thấp nhất
Bỏ qua các hằng số nhân
Chỉ xem xét các phép toán không sơ cấp
Tính tổng tất cả các phép toán thực hiện
Đáp án: B
Giải thích: Khi ước lượng, chúng ta bỏ qua các hằng số nhân và chỉ giữ lại các phần có bậc lớn nhất để đơn giản hóa biểu thức.
Trong trường hợp nào thuật toán có thể có độ phức tạp thời gian tuyến tính?
Tìm số lớn nhất trong một dãy số không tăng
Sắp xếp một danh sách số ngẫu nhiên
Tìm kiếm một phần tử cụ thể trong danh sách
Tính giai thừa của một số
Đáp án: C
Giải thích: Tìm kiếm một phần tử trong danh sách có thể có độ phức tạp thời gian tuyến tính (O(n)) trong trường hợp xấu nhất khi phải kiểm tra từng phần tử một.
Phép toán nào không được coi là sơ cấp?
Phép nhân hai số
Phép lặp qua một dãy số
Phép so sánh hai giá trị
Phép khai thác giá trị tuyệt đối
Đáp án: B
Giải thích: Phép lặp không được coi là phép toán sơ cấp vì nó liên quan đến việc thực hiện nhiều phép toán qua từng lần lặp, do đó không thể xác định thời gian thực hiện như một hằng số.
Cách nào được coi là ước lượng làm giả thêm?
Tính toán độ phức tạp thực tế của một thuật toán
Tìm số phép toán tối thiểu và tối đa cần thiết cho một thuật toán
Xác định ước lượng trung bình cho tất cả các trường hợp
Lựa chọn phương pháp ước lượng đảm bảo không vượt quá giá trị ước tính
Đáp án: D
Giải thích: Ước lượng làm giả thêm là cách ước lượng mà đảm bảo trong thực tế sẽ không có trường hợp nào vượt quá ước lượng đã đưa ra.
Khi nào độ phức tạp thời gian của thuật toán là O(n^2)?
Khi thực hiện một lần lặp qua n phần tử
Khi thực hiện hai lần lặp lồng nhau qua n phần tử
Khi thực hiện tìm kiếm nhị phân
Khi thực hiện phép cộng n số
Đáp án: B
Giải thích: Độ phức tạp thời gian O(n^2) xảy ra khi có hai vòng lặp lồng nhau, mỗi vòng lặp chạy qua n phần tử.
Đặc điểm nào sau đây không thuộc về độ phức tạp thời gian hằng số?
T(n) = C với C là một hằng số
Số phép toán thực hiện không phụ thuộc vào kích thước n
Được ký hiệu là O(1)
Số phép toán tăng theo kích thước n
Đáp án: D
Giải thích: Độ phức tạp thời gian hằng số không thay đổi khi kích thước n tăng lên, do đó không có số phép toán nào tăng theo kích thước n.
PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai
Thuật toán nào sau đây có độ phức tạp thời gian hằng số?
a) Tính tổng dãy số bằng cách cộng dồn từng số.
b) Tính tổng dãy số bằng công thức tính tổng cấp số cộng S=
c) Tìm kiếm một phần tử trong danh sách đã sắp xếp bằng cách sử dụng thuật toán tìm kiếm nhị phân.
d) Sắp xếp một dãy số bằng thuật toán sắp xếp nổi bọt (bubble sort).
a) Sai. Phương pháp cộng dồn từng số có độ phức tạp thời gian tuyến tính O(n) vì phải thực hiện n phép cộng.
b) Đúng. Công thức tính tổng cấp số cộng chỉ yêu cầu thực hiện 3 phép toán, không phụ thuộc vào kích thước đầu vào n, nên có độ phức tạp thời gian hằng số O(1)
c) Sai. Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(logn), không phải hằng số.
d) Sai. Thuật toán sắp xếp nổi bọt có độ phức tạp thời gian là O(n2) trong trường hợp xấu nhất.
Cách nào dưới đây có độ phức tạp thời gian tuyến tính?
a) Tìm số lớn nhất trong dãy số bằng cách so sánh từng cặp.
b) Tính giai thừa của một số nguyên n bằng đệ quy.
c) Sắp xếp một dãy số bằng thuật toán Quick Sort.
d) Tìm kiếm một số trong dãy số không sắp xếp bằng cách lặp qua từng phần tử.
a) Đúng – Độ phức tạp thời gian là O(n) vì phải duyệt qua từng phần tử để so sánh.
b) Sai – Độ phức tạp thời gian là O(n) nhưng không được coi là tuyến tính trong trường hợp này do bản chất của đệ quy liên quan đến nhiều lời gọi hàm chồng chéo.
c) Sai. Thuật toán Quick Sort có độ phức tạp thời gian trung bình là O(nlogn)
d) Đúng. Tìm kiếm một số trong dãy số không sắp xếp bằng cách lặp qua từng phần tử có độ phức tạp thời gian O(n), vì phải kiểm tra tất cả n phần tử.
PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3
Tại sao cần phải ước lượng độ phức tạp thời gian của một thuật toán?
Đáp án:Để so sánh hiệu quả của các thuật toán khác nhau.
Giải thích:Độ phức tạp thời gian giúp lập trình viên xác định được thời gian thực hiện và tài nguyên mà thuật toán cần, từ đó lựa chọn thuật toán phù hợp nhất cho bài toán cụ thể. Điều này đặc biệt quan trọng khi xử lý lượng dữ liệu lớn hoặc khi thời gian thực hiện là yếu tố quyết định trong ứng dụng.
Thế nào là độ phức tạp thời gian hằng số?
Đáp án:Độ phức tạp thời gian hằng số là khi số phép toán cần thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào.
Giải thích:Thuật toán có độ phức tạp thời gian hằng số thực hiện một số lượng phép toán cố định, không tăng theo kích thước n. Ví dụ, nếu một thuật toán chỉ cần thực hiện ba phép toán để cho ra kết quả, thì nó có độ phức tạp thời gian hằng số T(n) = 3, tức là O(1).
Độ phức tạp thời gian tuyến tính có ý nghĩa gì trong việc đánh giá thuật toán?
Đáp án:Độ phức tạp thời gian tuyến tính có nghĩa là số phép toán thực hiện tỷ lệ thuận với kích thước đầu vào.
Giải thích:Khi một thuật toán có độ phức tạp thời gian tuyến tính, điều này cho thấy rằng thời gian thực hiện sẽ tăng lên theo từng đơn vị kích thước dữ liệu. Ví dụ, nếu một thuật toán phải kiểm tra từng phần tử trong danh sách để tìm một giá trị cụ thể, thì số phép toán sẽ tương ứng với số lượng phần tử trong danh sách. Nếu danh sách có n phần tử, thì số phép toán sẽ là n, ký hiệu là T(n) = n, tức là O(n).