Giáo án Chuyên đề Tin học 12 Kết nối tri thức Bài 7: 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 7: 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ẽ:

- Nêu được khái niệm cây tìm kiếm nhị phân.

- Trình bày các thuật toán tạo cây tìm kiếm nhị phân, chèn thêm nút vào cây tìm kiếm nhị phân.

- Trình bày thuật toán tìm kiếm khoá trên 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:

- Trình bày được khái niệm cây tìm kiếm nhị phân.

- Mô phỏng được thuật toán tạo cây tìm kiếm nhị phân từ một tập hợp các số cho trước.

- Biết và thực hiện được thuật toán tìm kiếm một giá trị của 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 biết được một dạng đặc biệt của cây nhị phân: Cây tìm kiếm nhị phân (BST- Binary Search Tree).

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 30:

Quan sát các cây nhị phân sau, em có nhận xét gì về giá trị của các nút trên cây?

Gợi ý:

- Tại mỗi nút, so sánh dữ liệu của các nút của cây con trái và của cây con phải với nút này.

- Tại mỗi nút, so sánh dữ liệu của nút con trái và của nút con phải với nút này.

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: Bài học hôm nay, chúng ta cùng đi tìm hiểu về cây tìm kiếm nhị phân, thuật toán tạo cây tìm kiếm nhị phân và thuật toán tìm kiếm một giá trị của cây tìm kiếm nhị phân - Bài 7: 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. Tìm hiểu cấu trúc cây tìm kiếm nhị phân

a. Mục tiêu: HS biết được định nghĩa chính xác của cây tìm kiếm nhị phân và biết được một số cách biểu diễn cây tìm kiếm nhị phân trên máy tính.

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 nhận biế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 yêu cầu HS thảo luận, tìm hiểu nội dung mục 1 và trả lời một số câu hỏi: + Nêu khái niệm cây tìm kiếm nhị phân. + Có thể biểu diễn dữ liệu cây nhị phân theo những cách nào? Trình bày cách biểu diễn.

1. Cây tìm kiếm nhị phân Cây tìm kiếm nhị phân (BST – Binary Search Tree) là một dạng đặc biệt của cây nhị phân thông thường, được tạo ra với mục đích hỗ trợ thuận tiện cho các bài toán tìm kiếm, chèn, xoá, sắp xếp. a) Mô hình dữ liệu cây nhị phân Có hai cách biểu diễn cây nhị phân tổng quát: - Cách 1: Sử dụng cấu trúc nút liên kết. Cách biểu diễn này sẽ cần hai cấu trúc: + Cấu trúc Node để thể hiện thông tin từng nút (node) của cây nhị phân. + Cấu trúc Tree chỉ có thuộc tính root sẽ chỉ vào nút gốc của cây nhị phân. - Cách 2: Sử dụng mảng một chiều. Với cách này, cây nhị phân tổng quát cần được bổ sung thêm các nút giả (có giá trị None) để tạo thành cây nhị phân hoàn chỉnh đã biến đổi, sau đó sử dụng cách biểu diễn cây hoàn chỉnh này để biểu diễn. + Ví dụ: Cho mảng T = [5, 3, 7, 6].

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

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

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

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 8: Thực hành cây tìm kiếm nhị phân

• Giáo án Chuyên đề Tin học 12 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 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ị

---