Bài 22 Thực hành bài toán sắp xếp
Lớp 11Tin Học11 câu hỏiBài tập
Phần 1
Câu 1
(Câu 22.1 trang 70 SBT Tin học 11) Áp dụng thuật toán sắp xếp chọn cho dãy số A = [4, 6, 1, 3, 10, 7]. Thứ tự các phần tử trong dãy như thế nào sau vòng lặp đầu tiên?
A1, 6, 4, 3, 10, 7.
B3, 1, 4, 6, 10, 7.
C1, 4, 6, 3, 10, 7.
D1, 3, 4, 6, 7, 10.
Câu 2
(Câu 22.2 trang 70 SBT Tin học 11) Trong một số ứng dụng, chúng ta phải sắp xếp dữ liệu ngay khi chúng được thêm vào một dãy số. Ví dụ, giả sử đã có một danh sách dữ liệu đã sắp xếp và thường xuyên phải bổ sung thêm các dữ liệu mới vào danh sách. Theo em, thuật toán sắp xếp nào là phù hợp nhất với ứng dụng ở trên?
ASắp xếp chèn.
BSắp xếp chọn.
CSắp xếp nổi bọt.
DCá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 đều không phù hợp.
Câu 3
(Câu 22.3 trang 70 SBT Tin học 11) Mô tả “Thuật toán lần lượt duyệt từng cặp phần tử trong danh sách, đổi chỗ các cặp phần tử chưa đúng thứ tự” là đúng nhất với thuật toán sắp xếp nào sau đây?
AThuật toán sắp xếp nổi bọt.
BThuật toán sắp xếp chèn.
CThuật toán sắp xếp chọn.
DCá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 đều không phù hợp.
Câu 4
(Câu 22.4 trang 71 SBT Tin học 11) Mô tả “Ở mỗi bước thuật toán lấy một phần tử ở phần chưa được sắp xếp và đưa vào đúng vị trí của nó trong phần dãy số đã được duyệt” là đúng nhất với thuật toán sắp xếp nào sau đây?
AThuật toán sắp xếp chèn.
BThuật toán sắp xếp chọn.
CThuật toán sắp xếp nổi bọt.
DCá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 đều không phù hợp.
Câu 5
(Câu 22.5 trang 71 SBT Tin học 11) Mô tả “Ở mỗi bước lặp, thuật toán tìm kiếm phần tử lớn nhất hoặc nhỏ nhất trong dãy để đưa về đúng vị trí của nó” là đúng nhất với thuật toán sắp xếp nào sau đây?
AThuật toán sắp xếp chọn.
BThuật toán sắp xếp chèn.
CThuật toán sắp xếp nổi bọt.
DCá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 đều không phù hợp.
Câu 6
(Câu 22.6 trang 71 SBT Tin học 11) Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của một thuật toán sắp xếp được mô tả như sau: 1, 4, 10, 9, 3, 7, 12, 20; 1, 3, 10, 9, 4, 7, 12, 20; 1, 3, 4, 9, 10, 7, 12, 20. Thuật toán sắp xếp được sử dụng là gì?
AThuật toán sắp xếp chọn.
BThuật toán sắp xếp chèn.
CThuật toán sắp xếp nổi bọt.
DThuật toán tìm kiếm nhị phân.
Câu 7
(Câu 22.7 trang 72 SBT Tin học 11) Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của thuật toán sắp xếp được mô tả như sau: 5, 8, 1, 4, 7, 10; 5, 1, 8, 4, 7, 10; 5, 1, 4, 8, 7, 10. Thuật toán sắp xếp được sử dụng là gì?
AThuật toán sắp xếp nổi bọt.
BThuật toán sắp xếp chọn.
CThuật toán sắp xếp chèn.
DThuật toán tìm kiếm tuần tự.
Câu 8
(Câu 22.8 trang 72 SBT Tin học 11) Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của thuật toán sắp xếp được mô tả như sau: 5, 7, 4, 6, 9, 20, 8; 4, 5, 7, 6, 9, 20, 8; 4, 5, 6, 7, 9, 20, 8. Thuật toán sắp xếp được sử dụng là gì?
AThuật toán sắp xếp chèn.
BThuật toán sắp xếp chọn.
CThuật toán sắp xếp nổi bọt.
DThuật toán tìm kiếm nhị phân.
Phần 2
Câu 1
(Câu 22.9 trang 72 SBT Tin học 11) Cho trước danh sách lớp chưa được sắp xếp: Nam, An, Cường, Sơn, Trung, Bình. Hãy xét kết quả sắp xếp danh sách theo thứ tự bảng chữ cái bằng các thuật toán sắp xếp.
a)Với thuật toán sắp xếp chèn, sau bước lặp thứ nhất có thể thu được danh sách: An, Nam, Cường, Sơn, Trung, Bình.
b)Với thuật toán sắp xếp chọn, sau bước lặp thứ hai có thể thu được danh sách: An, Bình, Cường, Sơn, Trung, Nam.
c)Với thuật toán sắp xếp nổi bọt, quá trình sắp xếp có thể đổi chỗ các cặp tên liền kề chưa đúng thứ tự.
d)Sau khi sắp xếp xong theo thứ tự bảng chữ cái, danh sách đúng là: Nam, Trung, Sơn, Cường, Bình, An.
Câu 2
(Câu 22.10 trang 72 SBT Tin học 11) Viết chương trình cho phép người dùng nhập các số nguyên từ bàn phím, sắp xếp các số đã nhập theo thứ tự tăng dần và in ra màn hình dãy số đã sắp xếp; nhập từ khoá “end” để kết thúc chương trình. Yêu cầu ngay khi nhập xong dữ liệu thì dãy số cũng sắp xếp xong.
a)Thuật toán phù hợp với bài toán này là thuật toán sắp xếp chèn.
b)Mỗi khi nhập một số mới, có thể chèn số đó vào đúng vị trí trong dãy đã được sắp xếp.
c)Khi người dùng nhập “end”, chương trình có thể dừng việc nhập dữ liệu và in ra dãy đã sắp xếp.
d)Với yêu cầu này, bắt buộc phải nhập toàn bộ dãy rồi mới được sắp xếp lại từ đầu bằng thuật toán sắp xếp chọn.
Câu 3
(Câu 22.11 trang 72 SBT Tin học 11) Khi sử dụng dịch vụ tìm kiếm phòng nghỉ của một số trang đặt phòng trực tuyến, hệ thống thường cho phép sắp xếp theo giá tăng dần hoặc giá giảm dần. Xét một số cách xử lí yêu cầu sắp xếp này.
a)Cách 1 là viết riêng chương trình sắp xếp tăng dần và chương trình sắp xếp giảm dần; ưu điểm là không làm tăng số phép toán trong mỗi lần sắp xếp.
b)Cách 2 là dùng câu lệnh IF trước khi so sánh “lớn hơn” hoặc “nhỏ hơn” trong vòng lặp sắp xếp; ưu điểm là không cần viết riêng hai chương trình sắp xếp.
c)Cách 3 là nếu cần sắp xếp giảm dần thì nhân toàn bộ phần tử của dãy với -1 rồi vẫn dùng thuật toán sắp xếp tăng dần; nhược điểm là làm tăng số phép toán.
d)Nếu đã sắp xếp dữ liệu theo thứ tự tăng dần thì không thể hiển thị dữ liệu theo thứ tự giảm dần.