Bài 23.2. Giả sử một chương trình đã được kiểm tra chạy chính xác với hơn 1000 lần test. Mệnh đề nào sau đây là đúng?

A. Chương trình đó hoàn toàn chính xác. 

B. Chương trình đó chắc là sai ít đúng nhiều. 

C. Chương trình đó có độ tin cậy cao.

D. Chưa thể nói gì được về chương trình đó.

Bài 23.4. Cùng một chương trình, với hai bộ dữ liệu đầu vào khác nhau (cùng kích thước) thì thời gian chạy chương trình với hai bộ dữ liệu này sẽ giống nhau hay khác nhau?

Bài 23.6. Trong các bài toán sau, kích thước đầu vào của bài toán là gì, được tính như thế nào?

a) Bài toán sắp xếp dãy số A theo thứ tự tăng dần.

b) Bài toán tính tổng 1+ 2+ ... + n với n là số tự nhiên cho trước.

c) Bài toán tính gcd(a,b) - ước chung lớn nhất của hai số tự nhiên cho trước a, b.

Bài 23.8. Hàm sau tạo một dãy số nguyên có n phần tử và các giá trị nằm ngẫu nhiên trong phạm vi [a, b].

Em hãy viết chương trình tạo dãy A như trên với độ dài n và thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A. Sau đó tính thời gian chạy của các thuật toán này. Ghi lại bảng kết quả với các giá trị của n = 100, 1000, 10 000, 100 000.