Sách bài tập Tin học 11 Bài 21 (Kết nối tri thức): Các thuật toán sắp xếp đơn giản
Với giải sách bài tập Tin học 11 Bài 21: Các thuật toán sắp xếp đơn giản sách Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập trong SBT Tin học 11 Bài 21.
Giải SBT Tin học 11 Bài 21: Các thuật toán sắp xếp đơn giản
Câu 21.1 trang 69 SBT Tin học 11: Thuật toán sắp xếp chèn có ý tưởng ban đầu như sau:
1 Cho chỉ số i chạy từ phần từ thứ hai đến cuối dây
2 Chèn phần tử A[i] vào vị trí đúng của dây đã sắp xếp A[0], A[1], A[i-1]
Nếu công việc chèn tại dòng 2 ở trên được thực hiện như sau:
while j>e and A[j] < A[j-1]:
đổi chỗ Aljl, Aj-1]
j = j - 1
Thuật toán được mô tả theo cách trên có đúng không?
Lời giải:
Thuật toán sắp xếp chèn có ý tưởng ban đầu như sau:
1 Cho chỉ số i chạy từ phần từ thứ hai đến cuối dây
2 Chèn phần tử A[i] vào vị trí đúng của dây đã sắp xếp A[0], A[1], A[i-1]
Nếu công việc chèn tại dòng 2 ở trên được thực hiện như sau:
j = i
while j>e and A[j] < A[j-1]:
đổi chỗ Aljl, Aj-1]
j = j - 1
Thuật toán được mô tả theo cách trên là đúng.
Lời giải:
Với thuật toán sắp xếp chèn, khi dãy ban đầu đã sắp xếp đúng thì thuật toán thực hiện ít phép so sánh nhất.
Lời giải:
Khi dãy ban đầu đã được sắp xếp theo chiều ngược lại.
Câu 21.5 trang 69 SBT Tin học 11: Quan sát lại ý tưởng của thuật toán sắp xếp chèn
1 Cho chỉ số i chạy từ phần tử thứ hai đến cuối dày
2 Chèn phần tử A[i] vào vị trí đúng của dây đã sắp xếp A[e], A[1], ..., A[i-1]
Lời giải:
Có thể được. Chẳng hạn hàm đó là chen() có thể như sau:
3 Chọn phần tử nhỏ nhất trong dây A[i], A[i+1], A[n-1]
4 Đồi chỗ phần từ này với A[i]
Nếu thay dòng 3 bằng A + 1] A + 2]. ... An – 1] thì thuật toán còn đúng không?
Lời giải:
Nếu thay dòng 3 bằng A + 1] A + 2]. ... An – 1] thì thuật toán sẽ sai.
Lời giải:
Sau đây là một cách thiết lập thuật toán chọn sử dụng hàm min().
Lời giải:
Trong trường hợp khi dãy ban đầu đã sắp xếp đúng thì thuật toán sắp xếp chọn theo cách trên sẽ không cần thực hiện lệnh đổi chỗ hai phần tử tại dòng 8 của mô tả thuật toán trong sách giáo khoa.
Ý tưởng này được mô tả bằng đoạn mã giả sau:
2 Cho chỉ số j chạy từ phải sang đến vị trí thứ 2 của dãy
3 Nếu A[j] < A[j-1] thì đổi chỗ 2 phần tử A[j], A[j-1]
Em hãy viết chương trình mô tả đoạn mã giả trên.
Lời giải:
Với mỗi phần tử của B được chèn vào đúng vị trí trong dãy A.
Xem thêm lời giải sách bài tập Tin học lớp 11 bộ sách Kết nối tri thức hay, chi tiết khác:
Bài 22: Thực hành bài toán sắp xếp
Bài 23: Kiểm thử và đánh giá chương trình
Bài 24: Đánh giá độ phức tạp thời gian thuật toán
Xem thêm các chương trình khác:
- Soạn văn lớp 11 Kết nối tri thức - hay nhất
- Văn mẫu lớp 11 - Kết nối tri thức
- Tóm tắt tác phẩm Ngữ văn 11 – Kết nối tri thức
- Tác giả tác phẩm Ngữ văn 11 - Kết nối tri thức
- Giải SBT Ngữ văn 11 – Kết nối tri thức
- Bố cục tác phẩm Ngữ văn 11 – Kết nối tri thức
- Giải Chuyên đề học tập Ngữ văn 11 – Kết nối tri thức
- Nội dung chính tác phẩm Ngữ văn lớp 11 – Kết nối tri thức
- Soạn văn 11 Kết nối tri thức (ngắn nhất)
- Giải sgk Toán 11 – Kết nối tri thức
- Giải Chuyên đề học tập Toán 11 – Kết nối tri thức
- Lý thuyết Toán 11 - Kết nối tri thức
- Giải sbt Toán 11 – Kết nối tri thức
- Bài tập Tiếng Anh 11 Global success theo Unit có đáp án
- Giải sgk Tiếng Anh 11 – Global success
- Giải sbt Tiếng Anh 11 - Global Success
- Trọn bộ Từ vựng Tiếng Anh 11 Global success đầy đủ nhất
- Ngữ pháp Tiếng Anh 11 Global success
- Giải sgk Vật lí 11 – Kết nối tri thức
- Lý thuyết Vật lí 11 – Kết nối tri thức
- Giải sbt Vật lí 11 – Kết nối tri thức
- Giải Chuyên đề học tập Vật lí 11 – Kết nối tri thức
- Chuyên đề dạy thêm Vật lí 11 cả 3 sách (2024 có đáp án)
- Giải sgk Hóa học 11 – Kết nối tri thức
- Giải Chuyên đề học tập Hóa học 11 – Kết nối tri thức
- Lý thuyết Hóa 11 - Kết nối tri thức
- Giải sbt Hóa học 11 – Kết nối tri thức
- Chuyên đề dạy thêm Hóa 11 cả 3 sách (2024 có đáp án)
- Giải sgk Sinh học 11 – Kết nối tri thức
- Lý thuyết Sinh học 11 – Kết nối tri thức
- Giải Chuyên đề học tập Sinh học 11 – Kết nối tri thức
- Giải sbt Sinh học 11 – Kết nối tri thức
- Giải sgk Giáo dục Kinh tế và Pháp luật 11 – Kết nối tri thức
- Giải Chuyên đề học tập Kinh tế pháp luật 11 – Kết nối tri thức
- Lý thuyết Kinh tế pháp luật 11 – Kết nối tri thức
- Giải sbt Kinh tế pháp luật 11 – Kết nối tri thức
- Giải sgk Lịch sử 11 – Kết nối tri thức
- Giải Chuyên đề học tập Lịch sử 11 – Kết nối tri thức
- Lý thuyết Lịch sử 11 - Kết nối tri thức
- Giải sbt Lịch sử 11 – Kết nối tri thức
- Giải sgk Địa lí 11 – Kết nối tri thức
- Giải Chuyên đề học tập Địa lí 11 – Kết nối tri thức
- Lý thuyết Địa lí 11 - Kết nối tri thức
- Giải sbt Địa lí 11 – Kết nối tri thức
- Giải sgk Công nghệ 11 – Kết nối tri thức
- Lý thuyết Công nghệ 11 - Kết nối tri thức
- Giải sbt Công nghệ 11 – Kết nối tri thức
- Giải sgk Giáo dục quốc phòng an ninh 11 – Kết nối tri thức
- Lý thuyết Giáo dục quốc phòng 11 – Kết nối tri thức
- Giải sbt Giáo dục quốc phòng 11 – Kết nối tri thức
- Giải sgk Hoạt động trải nghiệm 11 – Kết nối tri thức