BÀI TẬP ÔN TẬP CUỐI HK2 MÔN TIN HỌC LỚP 11 – ĐỊNH HƯỚNG CS
Bài 19: Bài toán tìm kiếm
Câu 1: Thuật toán tìm kiếm tuần tự thực hiện công việc gì?
A. Lưu trữ dữ liệu.
B. Sắp xếp dữ liệu theo chiều tăng dần.
C. Xử lí dữ liệu.
D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho.
Câu 2: Thuật toán tìm kiếm tuần tự yêu cầu danh sách cần tìm phải được sắp xếp.
A. Đúng. B. Sai.
Câu 3: Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào?
A. Sắp xếp lại dữ liệu theo thứ tự bảng chữ cái.
B. Xem xét mục dữ liệu đầu tiên, sau đó xem xét từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.
C. Cho nhỏ dữ liệu thành từng phần để tìm kiếm.
D. Bất đầu tìm từ vị trí bất kì trong danh sách.
Câu 4: Trong tìm kiếm tuần tự thì có mấy điều kiện cần kiểm tra để dừng vòng lặp?
A. 1 B. 2 C. 3 D. Không
Câu 5: Thực hiện thuật toán tìm kiếm tuần tự để tìm số 10 trong danh sách [2, 6, 8, 4, 10, 12]. Đâu ra của thuật toán là?
A. Thông báo “Không tìm thấy”.
B. Thông báo “Tìm thấy”.
C. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 5 của danh sách.
D. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 6 của danh sách.
Câu 6: Chọn câu diễn đạt đúng hoạt động của thuật toán tìm kiếm tuần tự.
A. Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
B. Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
C. Tìm trên danh sách bắt kì, bắt đầu từ giữa danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
D. Tìm trên danh sách bất kì, bắt đầu từ đầu danh sách, chừng nào chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
Câu 7: Thuật toán tìm kiếm tuần tự cần bao nhiêu bước để tìm thấy số 25 trong danh sách [3, 5, 12, 7, 11, 25]?
A. 9. B. 6. C. 7. D. 8.
Câu 8: Điều gì xảy ra khi thuật toán tìm kiếm tuần tự không tìm thấy giá trị cần tìm trong danh sách?
A. Tiếp tục tìm kiếm và không bao giờ kết thúc. B. Thông báo “Tìm thấy”.
C. Thông báo “Tìm thấy” và kết thúc. D. Thông báo “Không tìm thấy” và kết thúc
Câu 9: Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:
A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
C. Sắp xếp dãy số theo thức tự tăng dần.
D. So sánh số cần tìm với số ở giữa dãy số.
Câu 10: Thuật toán tìm kiếm tuần tự thực hiện như thế nào?
A. So sánh lần lượt phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
B. So sánh lần lượt phần tử cuối cùng của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
C. So sánh lần lượt phần tử đầu tiên của dãy với phần tử kế tiếp, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
D. So sánh lần lượt phần tử cuối cùng của dãy với giá trị kế tiếp, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
Câu 11: Thuật toán tìm kiếm nhị phân thực hiện như thế nào?
A. Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.
B. Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm lớn hơn.
C. So sánh lần lượt phần tử cuối cùng của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
D. So sánh lần lượt phần tử đầu của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
Câu 12: Dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thư tự không giảm), sau bước Kiểm tra: số cần tìm nhỏ hơn giá trị trên thẻ? nếu nhận kết quả Sai, ta thực hiện bước nào?
A. Xét dãy thẻ số đứng sau thẻ số vừa lật. B. Xét dãy thẻ số đứng trước thẻ số vừa lật.
C. Kết thúc. D. Kiểm tra: dãy rỗng.
Câu 13: Khi dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thư tự không giảm), sau bước Kiểm tra: dãy rỗng? nếu nhận kết quả Sai, ta thực hiện bước nào?
A. Xét dãy thẻ số đứng sau thẻ số vừa lật. B. Lật thẻ số ở giữa dãy.
C. Kết thúc. D. Đầu ra: thông báo không tìm thấy.
Câu 14: Chọn phát biểu sai?
A. Thuật toán tìm kiếm tuần tự chỉ áp dụng với dãy gia trị đã được sắp xếp.
B. Thuật toán tìm kiếm nhị phân chỉ áp dụng với dãy gia trị đã được sắp xếp.
C. Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.
D. Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.
Câu 15: Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia nào?
A. (Số lượng thẻ của dãy +1) : 2. B. Số lượng thẻ của dãy +1 : 2.
C. (Số lượng thẻ của dãy +1) : 3. D. Số lượng thẻ của dãy : 2.
Câu 16: Chọn khẳng định sai trong các khẳng định sau:
A. Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.
B. Thuật toán tìm kiếm tuần tự thực hiện lặp đi lặp lại việc duyệt từng thẻ số, vòng lặp sẽ kết thúc khi tìm thấy số cần tìm hoặc đã duyệt hết các thẻ số.
C. Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm lớn hơn.
D. Cả 3 phương án trên.
Câu 17: Thuật toán tìm kiếm nhị phân áp dụng với bài toán tìm kiếm kiểu nào?
A. Áp dụng được với mọi bài toán tìm kiếm. B. Áp dụng với dãy giá trị đã được sắp xếp.
C. Áp dụng được với dãy giá trị chưa được sắp xếp. D. Cả A, B và C.
Câu 18: Chọn phát biểu sai về thuật toán tìm kiếm nhị phân?
A. Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia (số lượng thẻ của dãy) /2.
B. Khi dãy chỉ còn một thẻ số thì nửa trước (hoặc nửa sau) là dãy rỗng (dãy không có thể số nào).
C. Vòng lặp sẽ kết thúc khi tìm thấy số cần tìm hoặc dãy không còn thẻ số nào nữa.
D. Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.
Câu 19: Khi thực hiện tìm kiếm nhị phân số 25 trong dãy số 18, 21, 25, 27, 67, 69, 72, 77, 79, 81 cần thực hiện mấy vòng lặp?
A. 2. B. 3. C. 4. D. 5.
Câu 20: Tư tưởng của thuật toán tìm kiếm nhị phân là gì?
A. Tìm kiếm dựa vào cây tìm kiếm.
B. Tìm kiếm từ đầu đến cuối dãy.
C. Tại mỗi bước tiến hành so sánh X với phần tử giữa của dãy. Dựa vào bước so sánh này quyết định tìm kiếm ở nửa đầu hay ở nửa sau của danh sách.
D. So sánh X lần lượt với các phần tử a1, a2, …, an
Câu 21: Tại mỗi bước lặp, thuật toán tìm kiếm nhị phân sẽ:
A. Thu hẹp danh sách tìm kiếm chỉ còn một nửa. B. Danh sách sẽ được sắp xếp lại.
C. Các phần tử trong danh sách sẽ giảm một nửa. D. Đáp án khác.
Câu 22: Khi so sánh giá trị cần tìm với giá trị của vị trí giữa, nếu giá trị cần tìm nhỏ hơn giá trị giữa thì:
A. Tìm trong nửa đầu của danh sách. B. Tìm trong nửa sau của danh sách.
C. Dừng lại. D. Tìm trong nửa đầu hoặc nửa sau của danh sách.
Câu 23: Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?
A. Vị trí đầu tiên. B. Vị trí cuối cùng. C. Vị trí giữa. D. Bất kì vị trí nào.
Câu 24. Thuật toán tìm kiếm nhị phân được thực hiện như sau:
– Thiết lập các giá trị left, right là chỉ số phần tử đầu và cuối của dãy A có n phần tử. Như vậy cần tìm K trong dãy A[left…right]. Ban đầu đặt left = 0, right = n – 1.
– So sánh K với phần tử giữa dãy A[mid], với mid là phần nguyên của phép chia
(left + right) cho 2. Nếu K > A[mid] thì giá trị left, right được cập nhật như thế nào?
A. Giá trị left = mid + 1, giữ nguyên giá trị right. B. Giá trị left = mid – 1, giữ nguyên giá trị right.
C. Giá trị right = mid + 1, giữ nguyên giá trị left. D. Giá trị right = mid – 1, giữ nguyên giá trị left.
Câu 25. Phát biểu nào sau đây sai?
A. Thuật toán tìm kiếm nhị phân được áp dụng cho các dãy đã sắp xếp theo thứ tự xác định.
B. Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phần tử của dãy từ đầu đến cuối để tìm phần tử có giá trị bằng giá trị cần tìm.
C. Thuật toán tìm kiếm tuần tự không thể duyệt từ cuối dãy.
D. Thuật toán tìm kiếm nhị phân được thực hiện bằng cách liên tục thu hẹp phạm vi tìm kiếm
Bài 21: Các thuật toán sắp xếp đơn giản
Câu 1: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách nào?
A. Thay thế. B. Thay đổi. C. Hoán đổi. D. Cả A, B và C.
Câu 2: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách hoán đổi các phần tử liền kề bao nhiêu lần?
A. Một lần. B. Hai lần. C. Mười lần. D. Nhiều lần.
Câu 3: Trong thuật toán sắp xếp nổi bọt, ta thực hiện hoán đổi giá trị các phần tử liền kề khi nào?
A. Giá trị của chúng tăng. B. Giá trị của chúng giảm.
C. Giá trị của chúng không đúng thứ tự. D. Giá trị của chúng không bằng nhau.
Câu 4: Trong thuật toán sắp xếp nổi bọt thì dấu hiệu để biết dãy chưa sắp xếp xong là gì?
A. Vẫn còn cặp phần tử liền kế không đúng thứ tự mong muốn. B. Dãy chưa được sắp xếp tăng dần.
C. Dãy chưa được sắp xếp giảm dần. D. Cả A, B và C.
Câu 5: Cho dãy số: 15, 1, 31, 9, 78, 42. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy trên tăng dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?
A. 2 B. 3 C. 4 D. 5
Câu 6: Trong thuật toán sắp xếp nổi bọt kết thúc khi nào?
A. Khi các phần tử đã nằm đúng thứ tự mong muốn.
B. Không còn bất kì cặp liền kề trái thứ tự mong muốn.
C. Không còn xảy ra đổi chỗ lần nào nữa.
D. Cả A, B và C.
Câu 7: Cho dãy số: 6, 4, 5, 3. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần thì sau bao nhiêu vòng lặp thì thuật toán kết thúc?
A. 2 B. 3 C. 4 D. 5
Câu 8: Thuật toán sắp xếp nổi chọn xét từng vị trí phần tử từ:
A. Đầu đến cuối B. Cuối đến đầu C. Giữa đến đầu D. Giữa đến cuối
Câu 9: Tại sao chúng ta chia bài toán thành những bài toán nhỏ hơn?
A. Để thay đổi đầu vào của bài toán. B. Để thay đổi yêu cầu đầu ra của bài toán.
C. Để bài toán dễ giải quyết hơn. D. Để bài toán khó giải quyết hơn.
Câu 10: Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên gồm có mấy bước?
A. 2 B. 3 C. 4 D. 5
Câu 11: Cho dãy số a như hình dưới đây
Sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số theo thứ tự giảm dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?
A. 2 B. 3 C. 4 D. 5
Câu 12: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách?
A. Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách
B. Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách
C. Hoán đổi nhiều lần các giá trị liền kề nếu giá trị của chúng không đúng thứ tự.
D. Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách theo đúng thứ tự.
Câu 13:Thuật toán sắp xếp chọn sẽ so sánh các phần tử ở vị trí nào?
A. So sánh phần tử ở vị trí được xét với các phần tử phía trước.
B. So sánh phần tử ở vị trí được xét với các phần tử phía sau.
C. So sánh phần tử ở vị trí được xét với các phần tử liền kề.
D. So sánh phần tử ở vị trí được xét với các phần tử đầu tiên.
Câu 14. Thuật toán sắp xếp nổi bọt có thể sắp xếp danh sách theo thứ tự?
A. Tăng dần B. Giảm dần C. Tăng dần hoặc giảm dần D. Cả A, B, C đều sai.
Câu 15: Sau vòng lặp thứ nhất của thuật toán sắp xếp chọn, phương án nào đúng?
A. Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
B. Phần tử có giá trị lớn nhất trong dãy được tìm thấy và đổi chỗ cho phần tử đứng đầu dãy.
C. Các phần tử liền kề được hoán đổi.
D. Phần tử có giá trị nhỏ nhất sẽ đổi vị trí cho phần tử cuối dãy.
Câu 16: Các nhiệm vụ để thực hiện việc sắp xếp gồm:
A. So sánh. B. Đổi chỗ. C. So sánh và đổi chỗ. D. Đổi chỗ và xoá.
Câu 17. Chọn câu đúng.
Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử lớn nhất nằm trong dãy A[i], A[i+1], … , A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[n].
B. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử nhỏ nhất nằm trong dãy A[i], A[i+1], … , A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i].
C. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử nhỏ nhất nằm trong dãy A[i], A[i+1], … , A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[n-1].
D. Tại mỗi bước lặp của thuật toán sắp xếp chọn, cần tìm phần tử lớn nhất nằm trong dãy A[i], A[i+1], … , A[n-1] và đổi chỗ phần tử nhỏ nhất này với A[i+1].
Câu 18. Chọn câu sai.
A. Ý tưởng của thuật toán sắp xếp nổi bọt là liên tục đổi chỗ hai phần tử bất kì nếu chúng chưa được sắp thứ tự đúng.
B. Có nhiều cách thể hiện thuật toán sắp xếp nổi bọt, nhưng cách thường dùng là sử dụng hai vòng lặp lồng nhau.
C. Thuật toán sắp xếp nổi bọt lấy ý tưởng từ hiện tượng “nổi bọt” của không khí dưới nước.
D. Thuật toán sắp xếp nổi bọt kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ.
Câu 19. Ý tưởng của thuật toán sắp xếp nổi bọt là cho cho chỉ số j chạy từ:
A. 0 đến n – 2. B. 0 đến n – 1.
C. 1 đến n – 1. D. 1 đến n – 2.
Câu 20. Ý tưởng của thuật toán sắp xếp chọn là cho chỉ số i chạy từ:
A. Phần tử đầu tiên đến phần tử cuối cùng. B. Phần tử đầu tiên đến phần tử gần cuối.
C. Phần tử thứ hai đến phần tử cuối cùng. D. Phần tử thứ hai đến phần tử gần cuối.
Câu 21: Nếu sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số 8, 22, 7, 19, 5 theo thứ tự tăng dần thì số lần thực hiện thao tác hoán đổi giá trị trong vòng lặp thứ nhất là:
A. 2. B. 3. C. 4. D. 5.
Câu 22: Tìm phần tử nhỏ nhất trong dãy và đổi chỗ phần tử này với phần tử đầu tiên của dãy chưa được sắp xếp là ý tưởng của thuật toán nào?
A. Nổi bọt. B. Chọn. C. Chèn. D. Hợp nhất
Câu 23: Hoán đổi vị trí hai phần tử liên tiếp khi chúng không đúng thứ tự là cách sắp xếp của thuật toán nào?
A. Nổi bọt. B. Chọn. C. Chèn. D. Hợp nhất
Câu 24: Cho dãy số sau: 15, 20, 10, 18.
Bạn Minh sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số tăng dần. Mỗi vòng lặp sẽ duyệt từ phần tử cuối đến phần tử đầu tiên. Em hãy chọn phương án mô tả đúng dãy số sắp xếp sau mỗi vòng lặp.
A. 15, 20, 10, 18 – 10, 15, 18, 20 – 10, 15, 18, 20
B. 15, 20, 10, 18 – 10, 20, 15, 18 – 10, 15, 20, 18 – 10, 15, 18, 20.
C. 15,20, 10, 18 – 15, 10, 20, 18 – 10, 15, 18, 20.
D. 15, 20, 10, 18 – 10, 15, 20, 18 – 10, 15, 18, 20.
Câu 25: Dùng thuật toán sắp xếp nổi bọt để sắp xếp một dãy số tăng dần. Mỗi vòng lặp sẽ duyệt các phần tử từ cuối danh sách đến đầu danh sách. Kết thúc vòng lặp thứ nhát, phần tử đầu tiên sẽ có giá trị:
A. Nhỏ nhất trong dãy số. C. Không thay đổi.
B. Lớn nhất trong dãy só. D. Bằng giá trị của phần tử liền trước.
Câu 26. Trong các thuật toán sắp xếp, thuật toán nào cần tìm phần tử nhỏ nhất?
A. Sắp xếp chèn B. Sắp xếp chọn C. Sắp xếp nổi bọt D. Sắp xếp trộn
Câu 27. Trong các thuật toán sắp xếp, thuật toán nào sau mỗi bước lặp đưa phần tử tương ứng về đúng vị trí trong dãy con đã sắp xếp?
Sắp xếp chèn B. Sắp xếp chọn C. Sắp xếp nổi bọt D. Sắp xếp trộn
Câu 28. Trong các thuật toán sắp xếp, thuật toán nào sau mỗi bước lặp đưa phần tử lớn nhất về đúng vị trí của nó?
A. Sắp xếp chèn B. Sắp xếp chọn C. Sắp xếp nổi bọt D. Sắp xếp trộn
Câu 29. Cho dãy số A = [9, 7, 10, 2, 8, 5]. Hãy chọn mô phỏng sau lần duyệt đầu tiên của thuật toán sắp xếp NỔI BỌT để sắp xếp dãy số trên thành dãy tăng dần.
A. 7, 9, 10, 2, 8, 5 -> 7, 9, 10, 2, 8, 5 -> 2, 7, 9, 10, 8, 5 -> 2, 5, 7, 8, 9, 10
B. 2, 7, 10, 9, 8, 5 -> 2, 5, 10, 9, 8, 7 -> 2, 5, 7, 9, 8, 10 -> 2, 5, 7, 8, 9, 10
C. 7, 9, 10, 2, 8, 5 -> 7, 9, 10, 2, 8, 5 ->7, 9, 2, 10, 8, 5 -> 7, 9, 2, 8, 10, 5 -> 7, 9, 2, 8, 5, 10
D. 7, 9, 10, 2, 8, 5 -> 7, 9, 10, 2, 8, 5 -> 7, 9, 2, 8, 10, 5 -> 7, 9, 2, 8, 5, 10
Bài 23: Kiểm thử và đánh giá chương trình
Câu 1: Đâu không là công cụ để kiểm thử chương trình?
A. Công cụ in biến trung gian. B. Công cụ sinh các bộ dữ liệu test.
C. Công cụ thống kê dữ liệu D. Công cụ điểm dừng trong phần mềm soạn thảo lập trình.
Câu 2: Trong các phát biểu sau, phát biểu nào chưa chính xác về kiểm thử chương trình?
A. Hiện nay, có ít phương pháp và công cụ khác nhau để kiểm thử chương trình.
B. Chương trình cần được thử với một số bộ dữ liệu test gồm đầu vào tiêu biểu và kết quả đầu ra biết trước.
C. Các bộ test phụ thuộc vào các tiêu chí khác nhau.
D. Các bộ test dữ liệu nên có nhiều bộ test ngẫu nhiên,…
Câu 3: Phát biểu nào sau đây đúng nhất khi nói về các bộ dữ liệu test khi kiểm thử chương trình?
A. Các bộ test có thể có đầu vào theo các tiêu chí khác nhau.
B. Các bộ test có đầu vào theo một số tiêu chí nhất định.
C. Các bộ test có thể có đầu vào theo các tiêu chí khác nhau như độ lớn, tính đa dạng của dữ liệu.
D. Các bộ test có đầu vào phải theo các tiêu chí về độ lớn, tính đa dạng của dữ liệu.
Câu 4: Số phát biểu đúng trong các phát biểu sau:
1) Cần chú ý nên có nhiều bộ test khi test các bộ dữ liệu.
2) Việc sinh ngẫu nhiên dữ liệu đầu vào trong miền xác định của chương trình làm tăng khả năng tìm lỗi.
3) Thực tế cho thấy ít khi phát sinh lỗi tại các vùng biên hoặc lân cận biên.
4) Không thể sử dụng các lệnh print() để in ra các biến trung gian.
A. 2. B. 3. C. 1. D. 4.
Câu 5: Chương trình chạy phát sinh lỗi ngoại lệ TypeError, nên xử lí như thế nào?
A. Kiểm tra lại chỉ số trong mảng. B. Kiểm tra lại giá trị số chia.
C. Kiểm tra giá trị của số bị chia. D. Kiểm tra kiểu dữ liệu nhập vào.
Câu 6: Chương trình chạy phát sinh lỗi ngoại lệ NameError, nên xử lí như thế nào?
A. Kiểm tra lại chỉ số trong mảng. B. Kiểm tra lại tên các biến và hàm.
C. Kiểm tra giá trị của số bị chia. D. Kiểm tra kiểu dữ liệu nhập vào.
Câu 7: Chương trình sau nên sửa như thế nào. Chọn phương án đúng nhất.
fruits = [‘Banana’, ‘Apple’, ‘Lime’]
print(fruits[4])
A. Thay đổi kiểu dữ liệu của từng phần tử trong mảng.
B. Kiểm tra chỉ số của mảng khi thực hiện lệnh.
C. Thay đổi tên mảng.
D. Chương trình không có lỗi.
Câu 8: Phát biểu nào sau đây là đúng về lỗi ngoại lệ?
A. Là lỗi câu lệnh viết không theo đúng quy định của ngôn ngữ.
B. Là lỗi xảy ra khi chương trình đang chạy, một lệnh nào đó không thể thực hiện.
C. Là lỗi mặc dù các câu lệnh viết đúng quy định của ngôn ngữ nhưng sai trong thao tác xử lí nào đó.
D. Tất cả các lỗi trên.
Câu 9: Khẳng định nào sau đây là sai?
A. Lỗi ngữ nghĩa là lỗi khó phát hiện nhất.
B. Ngôn ngữ lập trình Python cung cấp công cụ Debug để gỡ lỗi .
C. Lỗi ngoại lệ là lỗi xảy ra khi chương trình đang chạy, một lệnh nào đó không thể thực hiện. Lỗi này sẽ được hiển thị ngay trên màn hình.
D. Truy vết để tìm lỗi là một quá trình vô cùng đơn giản, không tốn thời gian.
Câu 10. 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 đó.
Câu 11. Để chứng minh một thuật toán là đúng cần phải làm gì? Chọn phương án đúng nhất trong các phương án sau:
A. Cần tiến hành kiểm thử chương trình cài đặt thuật toán, kiểm thử càng nhiều càng tốt.
B. Cần cài đặt thuật toán trên càng nhiều ngôn ngữ lập trình càng tốt.
C. Cần chạy thử chương trình cài đặt thuật toán xem thời gian chạy có nhanh hay không.
D. Cần chứng minh bằng toán học chặt chẽ tính đúng của thuật toán.
Bài 24: Đánh giá độ phức tạp thời gian thuật toán
Câu 1: Các bước giải bài toán trên máy tính được tiến hành theo thứ tự nào sau đây:
A. Xác định bài toán – Lựa chọn thuật toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu
B. Xác định bài toán – Viết chương trình – Lựa chọn thuật toán – Viết tài liệu
C. Lựa chọn thuật toán – Xác định bài toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu
D. Viết chương trình – Hiệu chỉnh – Viết tài liệu
Câu 2: Viết chương trình là?
A. Biểu diễn thuật toán
B. Dùng ngôn ngữ lập trình để diễn đạt bài toán
C. Dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả thuật toán
D. Tất cả đều đúng
Câu 3: Tiêu chuẩn lựa chọn thuật toán:
A. Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép B. Độ phức tạp của thuật toán
C. Các tài nguyên như thời gian thực hiện, số lượng ô nhớ… D. Cả 3 ý trên đều đúng
Câu 4: Tiêu chí lựa chọn hoặc thiết kế thuật toán là?
A. Hiệu quả về thời gian B. Hiệu quả về không gian
C. Khả thi khi cài đặt D. Tất cả đều đúng
Câu 5: Khẳng định “Trong mọi chương trình chỉ có đúng một phép toán tích cực” lá đúng hay sai?
A. Sai B. Đúng C. Ý kiến khác D. Chưa đủ dữ kiện
Câu 6. Phát biểu nào sau đây đúng?
A. Các phương pháp kiểm thử có tính năng chứng minh được tính đúng của một thuật toán.
B. Độ phức tạp tính toán quan trọng nhất là độ phức tạp thời gian liên quan trực tiếp tới dung lượng bộ nhớ được sử dụng để thực hiện chương trình.
C. Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học.
D. Độ phức tạp không gian phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình/thuật toán.
Câu 7. Thuật toán tối ưu là?
A. Sử dụng ít thời gian, ít bộ nhớ…
B. Sử dụng ít thời gian, nhiều bộ nhớ, ít phép toán…
C. Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép toán…
D. Sử dụng ít thời gian, ít bộ nhớ, ít phép toán…
Câu 8: Tính độ phức tạp của các hàm thời gian sau: Tính = 2n(n – 2) + 4.
A. O(n) – tuyến tính B. O(n3) – lũy thừa
C. O(n2) – lũy thừa D. O(n5) – lũy thừa
Câu 9: Tính độ phức tạp của các hàm thời gian sau:
Tính = n3 + 5n – 3.
A. O(n) – tuyến tính B. O(n3) – lũy thừa
C. O(n2) – lũy thừa D. O(n5) – lũy thừa
Câu 10: Viết chương trình là?
A. Biểu diễn thuật toán
B. Dùng ngôn ngữ lập trình để diễn đạt bài toán
C. Dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả thuật toán
D. Tất cả đều đúng
Câu 11. Quy tắc cộng để tính độ phức tạp thời gian thuật toán là
A. O(f(n) + g(n)) = O(min(f(n), g(n))). B. O(f(n) + g(n)) = O(f(n)) + O(g(n)).
C. O(f(n) + g(n)) = O(max(f(n), g(n))). D. O(f(n) + g(n)) = f(n) + g(n).
Câu 12. Giả sử một chương trình P mô tả một thuật toán nào đó. Người ta đo được các thông tin thời gian sau:
T1 = thời gian chương trình nhập dữ liệu input và đưa vào bộ nhớ.
T2 = thời gian chạy chương trình từ khi nhập xong dữ liệu input và tính xong dữ liệu output.
T3 = thời gian đưa dữ liệu output ra thiết bị ngoài chuẩn.
Khi đó thời gian chạy chương trình T(n) dùng để tính độ phức tạp thời gian của thuật toán là phương án nào trong các phương án sau?
A. T1 + T2. B. T2. C. T2+T3. D. T3
Bài 26: Phương pháp làm mịn dần theo thiết kế chương trình
Câu 1: Phương pháp làm mịn dần trong thiết kế chương trình là:
A. quá trình chi tiết hóa từ ý tưởng của các bước trước thành những hành động cụ thể hơn ở các bước sau.
B. hực hiện thiết kế thuật toán và chương trình bằng phương pháp
C. chia việc thiết kế thành từng bước và thực hiện lần lượt các bước
D. mỗi bước lớn có thể được chia thành nhiều bước nhỏ hơn để giải quyết độc lập
Câu 2: Phương pháp làm mịn dần trong thiết kế chương trình phải tuân thủ các quy trình và nguyên tắc sau:
A. Chia việc thiết kế thành từng bước và thực hiện lần lượt các bước
B. Mỗi bước lớn có thể được chia thành nhiều bước nhỏ hơn để giải quyết độc lập
C. Tiếp cận bài toán từ tổng quan đến chi tiết, mỗi bước tiếp theo sẽ phải là thiết kế chi tiết hơn bước trước đó. Quán trình như vậy sẽ tiếp tục cho đến khi viết xong toàn bộ các câu lệnh của chương trình giải bài toán đã cho.
D. Cả 3 đáp án trên
Câu 3: Mệnh đề nào sau đây mô tả đúng về phương pháp thiết kế làm mịn dần?
A. Thiết kế được chia làm nhiều bước, các bước đều độc lập hoàn toàn với nhau.
B. Thiết kế được chia làm nhiều bước, bước sau thường là chi tiết hơn, làm mịn hơn một bước ở trước đó.
C. Thiết kế được chia làm nhiều bước, bước sau thường là tổ hợp, kết hợp các kết quả của các bước trước đó.
D. Thiết kế được chia làm nhiều bước, mỗi bước sẽ tương ứng với một hàm hoặc chương trình con nào đó của bước trước
Bài 28: Thiết kế chương trình theo modul
Câu 1. Thứ tự các bước thiết kế chương trình theo modun
A. Thiết kế chung -> Thiết lập công việc nhập dữ liệu -> Thiết lập công việc xử lý dữ liệu -> Thiết lập báo cáo đưa dữ liệu ra
B. Thiết kế chung -> Thiết lập công việc nhập dữ liệu -> Thiết lập báo cáo đưa dữ liệu ra -> Thiết lập công việc xử lý dữ liệu
C. Thiết kế chung -> Thiết lập báo cáo đưa dữ liệu ra -> Thiết lập công việc xử lý dữ liệu -> Thiết lập công việc nhập dữ liệu
D. Thiết kế chung -> Thiết lập công việc xử lý dữ liệu -> Thiết lập công việc nhập dữ liệu -> Thiết lập báo cáo đưa dữ liệu ra
Câu 2. Lợi ích của thiết kế chương trình theo Modul
A. Chương trình ngắn gọn, sáng sủa, dễ hiểu, dễ dàng bổ sung các modul mới
B. Chương trình dài, tường minh, dễ hiểu, dễ dàng bổ sung các modul mới
C. Chương trình ngắn gọn, sáng sủa, dễ hiểu, khó bổ sung các modul mới
D. Chương trình ngắn gọn, sáng sủa, dễ hiểu, không thay đổi hay chỉnh sửa được
Câu 3. Các modul của chương trình có quan hệ với nhau như thế nào
A. Đầu ra của modul trước là đầu vào của modul sau
B. Đầu ra của modul sau là đầu vào modul trước
C. Các modul độc lập với nhau
D. Đầu ra modul đầu tiên là đầu vào modul cuối cùng
Câu 4: Mỗi mô đun có thể là:
A. một số hàm hoặc thủ tục độc lập B. một hàm riêng biệt
C. một thủ tục D. các hàm và thủ tục con
Câu 5: Chương trình chính là:
A. một bản ghép riêng biệt B. một bản ghép nối các hàm và thủ tục con
C. một thủ tục D. các hàm và thủ tục con
Câu 6: Phương pháp thiết kế chương trình theo mô đun sẽ tách bài toán lớn thành:
A. các bài toán nhỏ
B. thành các mô dun
C. các bài toán nhỏ hơn, hay thành các mô đun, tương đối độc lập với nhau, sau đó tiến hành thiết kế thuật toán và chương trình cho từng mô đun con.
D. thiết kế thuật toán
PHẦN TỰ LUẬN VÀ VẬN DỤNG RA ĐỀ TRẮC NGHIỆM ĐÚNG / SAI.
Câu 1
a. Hãy nêu ý tưởng của thuật toán tìm kiếm tuần tự/nhị phân
b. Cho dãy A = [0, 4, 8, 9, 12, 17, 25] và giá trị cần tìm là K = 4. Hãy mô tả các bước của thuật toán tìm kiếm tuần tự/nhị phân.
Câu 2. Cho dãy A = [81, 72, 16, 35, 10, 4, 93]. Viết chương trình sắp xếp dãy A theo thứ tự tăng dần theo thuật toán sắp xếp chọn
Câu 3. Với thuật toán sắp xếp chèn (trong sách giáo khoa), cùng kích thước n, thì bộ dữ liệu kiểm thử nào cho thời gian chạy:
a) Nhanh nhất? b) Chậm nhất?
Câu 4. 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.
Câu 5. Viết chương trình thực hiện các việc sau:
– Nhập dãy số A từ bàn phím.
– Thực hiện thuật toán sắp xếp nổi bọt trên dãy A.
– Tính thời gian chạy của thuật toán trên đối với dãy A, kết quả đưa ra màn hình
Câu 6. Đánh giá thời gian chạy của chương trình sau:
Câu 7. Đánh giá thời gian chạy của chương trình sau:
Câu 8. Đánh giá thời gian chạy của chương trình sau, trong đó A là ma trận vuông bậc n.
Câu 9. Đánh giá thời gian chạy của thuật toán sắp xếp chèn đã học trong sách giáo khoa.
Câu 10. Đánh giá thời gian chạy của thuật toán sắp xếp nổi bọt đã học trong sách giáo khoa
Câu 11. Tính độ phức tạp của các hàm sau theo kí hiệu O-lớn
a) n + 2n.log(n) + 10.
b) 2n2 + 3n3 log(n) + n3/2.
Câu 12. Cho biết thuật toán sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của thuật toán.
1 def findMax(A):
2 maxVal = A[0]
3 for i in range (1, len (A)):
4 if A[i]>maxVal:
5 maxVal=A[i]
6 return maxVal
Câu 13. Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.
Câu 14. Em hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A.
