Giáo án Chuyên đề Tin học 12 Kết nối tri thức Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

Giáo án Chuyên đề Tin học 12 Kết nối tri thức Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 12 Kết nối tri thức chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

- Trình bày các thuật toán duyệt trên cây tìm kiếm nhị phân.

- Trình bày thuật toán sắp xếp dãy số sử dụng cây tìm kiếm nhị phân.

2. Năng lực

Năng lực chung:

- Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.

- Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.

- Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

- Thực hiện được các thuật toán duyệt trên cây tìm kiếm nhị phân.

- Tìm kiếm và 1 sắp xếp dây số dựa trên cây tìm kiếm nhị phân.

3. Phẩm chất

- Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.

- Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.

- Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU:

1. Đối với giáo viên:

- Tài liệu, máy tính, máy trình chiếu.

- SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

2. Đối với học sinh:

- Vở ghi, máy tính.

- SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: HS nhận ra được một mô hình dữ liệu mới khác với kiểu dữ liệu mảng đã học.

b. Nội dung: HS quan sát các hình ảnh, suy nghĩ, thảo luận và trả lời câu hỏi.

c. Sản phẩm học tập: Câu trả lời của HS.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV cho HS thảo luận theo nhóm đôi.

- GV yêu cầu HS quan sát và trả lời câu hỏi Khởi động SGK trang 41

Quan sát cây tìm kiếm nhị phân trong Hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau:

a) Nếu thực hiện thuật toán duyệt giữa (trái - gốc – phải) thì nút đầu tiên được duyệt là nút nào?

b) Nút cuối cùng được duyệt là nút nào?

c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tiếp nhận, thực hiện nhiệm vụ.

- GV hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS trình bày câu trả lời, các HS khác chú ý lắng nghe và nhận xét.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Ở các bài học trước ta đã tìm hiểu về cây tìm kiếm nhị phân, thuật toán tìm kiếm nhị phân. Bài học này chúng ta cùng đi tìm hiểu các thuật toán duyệt trên cây tìm kiếm nhị phân - Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Các thuật toán duyệt cây tìm kiếm nhị phân

a. Mục tiêu: HS biết và hiểu được cách thiết lập các thuật toán duyệt cây tìm kiếm nhị phân, biết được sự khác biệt của các thuật toán này so với các thuật toán duyệt đã biết trong Bài 6, biết được ý nghĩa thuật toán duyệt giữa và duyệt ngược trên cây tìm kiếm nhị phân.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Hình thành được kiến thức bài học. HS trình bày được các cách thiết lập các thuật toán duyệt cây tìm kiếm nhị phân.

d. Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập - GV cho HS hoạt động nhóm 4, thảo luận: + Phân biệt sự khác nhau giữa các thuật toán duyệt cây nhị phân đã học trong Bài 6 và các thuật toán duyệt trong bài học này. + Nếu cây tìm kiểm nhị phân được biểu diễn bằng mảng T thì cần kiểm tra điều kiện gì? - GV yêu cầu HS tìm hiểu về thuật toán duyệt trước, duyệt sau, duyệt giữa, duyệt ngược; sau đó trình bày các thuật toán. - GV chú ý: + Khi thực hiện các thuật toán duyệt trên cây nhị phân cần chú ý đến hai thuật toán duyệt giữa và duyệt ngược, hai thuật toán này sẽ duyệt lần lượt các phần tử của cây theo thứ tự tăng dần và giảm dần của khoá.

1. Các thuật toán duyệt cây tìm kiếm nhị phân Hướng dẫn trả lời câu hỏi thảo luận: - Trong Bài 6, mô hình cây được học là cây nhị phân hoàn chỉnh, còn trong bài học này thì cây tìm kiếm nhị phân đã được bổ sung thêm các phần tử giả None để trở thành cây nhị phân hoàn chỉnh, do vậy trong quá trình duyệt luôn phải kiểm tra xem nút đang duyệt có phải là nút giả None hay không. - Nếu cây tìm kiếm nhị phân được biểu diễn bằng mảng T thì cần kiểm tra điều kiện k < len(T) và T[k] ≠ None để nút tại chỉ số k không là nút giả None. a) Thuật toán duyệt trước Thuật toán duyệt trước bắt đầu từ nút k: Lệnh duyệt trước toàn bộ cây tìm kiếm nhị phân T là: b) Thuật toán duyệt sau Thuật toán duyệt trước bắt đầu từ nút k:

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 12 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Chuyên đề Tin học lớp 12 Kết nối tri thức hay, chuẩn khác:

• Giáo án Chuyên đề Tin học 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

• Giáo án Chuyên đề Tin học 12 Bài 11: Khái niệm đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Giáo án Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

---