Đáp án: C

Giải thích: Độ phức tạp tính toán đánh giá tốc độ thực thi và không gian bộ nhớ mà thuật toán cần, từ đó xác định khả năng tối ưu của thuật toán.

Đáp án: B

Giải thích: Các bộ dữ liệu kiểm thử giúp tăng độ tin cậy của chương trình bằng cách tìm và sửa lỗi, nhưng không đảm bảo tính đúng hoàn toàn của thuật toán.

Đáp án: B

Giải thích: Quy nạp toán học là phương pháp giúp chứng minh tính đúng của thuật toán bằng cách lập luận logic, đảm bảo tính đúng trong mọi trường hợp đầu vào.

a) Sai. Sử dụng các bộ dữ liệu kiểm thử giúp tăng độ tin cậy của chương trình nhưng không thể chứng minh tính đúng đắn tuyệt đối của chương trình.

b) Đúng. Mục đích của các bộ dữ liệu kiểm thử là phát hiện lỗi có thể có và đánh giá độ tin cậy của chương trình.

c) Sai. Kiểm tra tốc độ thực thi là một yếu tố khác trong đánh giá hiệu quả, nhưng không phải là mục tiêu chính của việc kiểm thử.

d) Sai. Mục tiêu tiết kiệm bộ nhớ thuộc về tối ưu hóa bộ nhớ, không phải mục đích của kiểm thử bằng bộ dữ liệu kiểm thử

a) Đúng. Thời gian chạy của thuật toán là một tiêu chí quan trọng để đánh giá hiệu quả của nó, đặc biệt là khi xét đến độ phức tạp thời gian.

b) Sai. Bộ nhớ ít cũng quan trọng, nhưng không phải là yếu tố quan trọng nhất trong mọi trường hợp.

c) Sai. Rõ ràng và dễ hiểu giúp lập trình dễ bảo trì, nhưng không phải là tiêu chí chính để đánh giá hiệu quả.

d) Sai. Tính đúng đắn là yêu cầu cần có, nhưng tính hiệu quả còn đòi hỏi thuật toán phải chạy nhanh và sử dụng bộ nhớ hợp lý.

Đáp án: Kiểm thử chương trình giúp tăng độ tin cậy của chương trình bằng cách phát hiện và sửa các lỗi thông qua việc sử dụng các bộ dữ liệu đầu vào khác nhau. Tuy nhiên, kiểm thử không thể chứng minh tính đúng đắn hoàn toàn của một thuật toán.

Giải thích: Kiểm thử có thể phát hiện lỗi khi chương trình không cho ra kết quả đúng với các bộ dữ liệu đầu vào cụ thể. Tuy nhiên, vì số lượng trường hợp đầu vào là vô hạn, nên kiểm thử không đảm bảo rằng chương trình luôn đúng với mọi trường hợp. Để chứng minh tính đúng của một thuật toán, ta cần sử dụng các phương pháp chứng minh logic hoặc toán học.

Đáp án: Ta có thể kiểm tra tính đúng của thuật toán sắp xếp chèn bằng cách sử dụng bất biến vòng lặp. Sau mỗi bước lặp, dãy con từ đầu đến phần tử hiện tại phải được sắp xếp đúng theo thứ tự tăng dần

Giải thích: Phương pháp lập luận logic như bất biến vòng lặp giúp chúng ta theo dõi trạng thái của chương trình ở từng bước, đảm bảo rằng các phần tử trong dãy con từ đầu đến vị trí hiện tại luôn được sắp xếp đúng. Nếu bất biến này đúng sau mỗi bước lặp và duy trì đến cuối vòng lặp, thì dãy đã được sắp xếp tăng dần, chứng tỏ thuật toán sắp xếp chèn là đúng.

Đáp án: Hai tiêu chí quan trọng nhất để đánh giá hiệu quả của một chương trình là độ phức tạp thời gian và độ phức tạp không gian

Giải thích: Độ phức tạp thời gian cho biết thời gian thực hiện của chương trình và có ảnh hưởng trực tiếp đến tốc độ xử lý, đặc biệt là khi xử lý lượng lớn dữ liệu. Độ phức tạp không gian liên quan đến lượng bộ nhớ mà chương trình sử dụng. Trong nhiều ứng dụng, tối ưu thời gian thường quan trọng hơn, nhưng với các thiết bị có hạn chế về bộ nhớ, việc tiết kiệm không gian cũng rất cần thiết.