Truy cập không giới hạn toàn bộ khóa học. Đăng ký ngay

✕

Kích hoạt VIP

Kích hoạt VIP

Tạo VIP

Giải SGK Chuyên đề Tin học 11 Bài 13. Kĩ thuật duyệt quay lùi

42 người thi tuần này 4.6 781 lượt thi 15 câu hỏi

Đề số 1

🔥 Học sinh cũng đã học

78 người thi tuần này

Đề thi cuối kì 2 Tin học 11 năm 2024-2025 Sở Nam Định có đáp án

547 lượt thi 30 câu hỏi

129 người thi tuần này

Đề thi cuối kì 2 Tin học 11 năm 2025-2026 THPT Xuyên Mộc (TP.HCM) có đáp án

598 lượt thi 31 câu hỏi

63 người thi tuần này

Đề thi cuối kì 2 Tin học 11 năm 2024-2025 THPT Gio Linh (Quảng Trị) có đáp án

532 lượt thi 23 câu hỏi

63 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2025-2026 THPT Xuyên Mộc (TP.HCM) có đáp án

633 lượt thi 28 câu hỏi

67 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2024-2025 THPT Hồ Nghinh (Quảng Nam) có đáp án

637 lượt thi 20 câu hỏi

128 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2025-2026 THPT Hùng Vương (Đà Nẵng) có đáp án

698 lượt thi 20 câu hỏi

68 người thi tuần này

Đề thi giữa kì 2 Tin học 11 năm 2024-2025 THPT (Bắc Giang) có đáp án

638 lượt thi 23 câu hỏi

67 người thi tuần này

Đề thi cuối kì 1 Tin học 11 năm 2024-2025 THPT Gio Linh (Quảng Trị) có đáp án

378 lượt thi 29 câu hỏi

Danh sách câu hỏi:

Câu 1/15

Chúng ta đã biết từ bài học trước, thiết lập các thuật toán duyệt sẽ phụ thuộc hoàn toàn vào mô hình và cấu trúc của miền dữ liệu cần tìm kiếm. Từ lâu các nhà khoa học đã nhìn thấy rất nhiều bài toán khó không tìm được cách duyệt hữu hiệu, điển hình nhất là bài toán tìm đường đi trong mê cung.

Bài toán tìm đường đi trong mê cung lần đầu tiên được đưa ra trong cuốn sách Récréations Mathématiques của tác giả Édouard Lucas năm 1882 tại Pháp. Cũng trong cuốn sách đó Lucas đã đưa ra phác thảo đầu tiên của một phương pháp giải bài toán tìm đường đi trong mê cung mà bây giờ chúng ta gọi là thuật toán duyệt quay lui, hay đơn giản là thuật toán quay lui (backtracking).

Trong trò chơi mê cung (xem hình) em cần tìm một đường đi xuất phát từ lối vào và ra khỏi mê cung tại lối ra. Em có đề xuất gì để giải bài toán này.

Xem đáp án

Lời giải

Đề xuất: Xuất phát từ vị trí gốc, thuật toán sẽ gọi hàm tìm bước đi tiếp theo. Nếu thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Cứ như vậy cho đến khi ra được khỏi mê cũng

Câu 2/15

Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung.

Xem đáp án

Lời giải

Ý tưởng của thuật toán duyệt quay lui là luôn tìm cách đi tiếp theo. Xuất phát từ vị trí gốc, thuật toán sẽ gọi hàm tìm bước đi tiếp theo. Nếu thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Thuật toán sẽ sử dụng kĩ thuật đệ quy khi gọi hàm cho bước đi tiếp theo.

Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung. (ảnh 1)

Câu 3/15

Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm có dừng không?

Xem đáp án

Lời giải

Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm không dừng. Nếu đã đến đích thì thông báo tìm thấy thấy nghiệm tại dòng thứ 7, nếu chưa tìm thấy thì gọi đệ quy lại hàm gốc để đi tiếp tại dòng 10. Nếu không thể đi tiếp thì quay lui tại dòng 11, xóa dấu vết và quay lại vòng lặp 2.

Câu 4/15

Lệnh gọi hàm chính của chương trình trên là gì?

Xem đáp án

Lời giải

Lệnh gọi hàm chính của chương trình trên là dòng số 2, lặp trên tập hợp các khả năng có thể đi tiếp

Câu 5/15

Nếu yêu cầu bổ sung thêm 1 lệnh “Nếu thấy <lối ra> thì thông báo và dừng chương trình” thì lệnh này sẽ đặt ở đâu trong chương trình trên?

Xem đáp án

Lời giải

Lệnh “Nếu thấy <lối ra> thì thông báo và dừng chương trình” đặt ở trước dòng lệnh số 9.

Câu 6/15

Quan sát, thực hiện và thảo luận các bước thiết kế mô hình tổng quát của kĩ thuật duyệt quay lui.

Xem đáp án

Lời giải

Mô hình thuật toán quay lui tổng quát quy định việc tìm trên các dãy số nguyên ( $x_{1}, x_{2}, ..., x_{k}$ sử dụng lệnh gọi đệ quy để mô tả bước đi tiếp theo với k + 1, nếu không tìm được bước đi tiếp theo thì quay lui để tìm hướng đi khác.

Mô hình tổng quát duyệt quay lui sử dụng đệ quy như sau:

Quan sát, thực hiện và thảo luận các bước thiết kế mô hình tổng quát của kĩ thuật duyệt quay lui. (ảnh 1)

Câu 7/15

Trạng thái "quay lui" của thuật toán trên nằm ở đâu?

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 8/15

Có cách nào đếm được tất cả các nghiệm từ thuật toán trên được không? Nếu có thì làm cách nào?

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 9/15

Cùng thực hiện, trao đổi, thảo luận thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui.

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 10/15

Trong chương trình 1, động tác “quay lui” nằm ở đâu?

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 11/15

Giải thích ý nghĩa của lệnh A.pop() tại dòng 8 của chương trình 2. Vì sao lệnh này không có trong chương trình 1?

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 12/15

Sửa các chương trình trên bổ sung thêm chức năng: sau khi in ra tất cả các xâu nhị phân thi thông báo tổng số nghiệm.

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 13/15

Viết chương trình sinh tất cả các xâu (hoặc dãy) bao gồm n kí tự dạng “R”, “G” và "B".

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 14/15

Viết chương trình sinh tất cả các số hex (hệ đếm 16) có 3 chỉ số.

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 15/15

Viết chương trình sinh xâu nhị phân thực sự có độ dài n, tức là kết quả in ra phải là các xâu kí tự chứ không phải là danh sách (list) như trong các chương trình trên.

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem tiếp với tài khoản VIP

Còn 9/15 câu hỏi, đáp án và lời giải chi tiết.

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Khóa học 1 - 12

THPT

THCS

Phòng luyện đề

ĐGNL - ĐGTD

Tốt nghiệp THPT

Ôn vào 10

Ô Ôn vào 10

Ôn vào 6

Ô Ôn vào 6

Tài liệu

THPT

THCS

Tin Tuyển Sinh