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

Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 10: THỰC HÀNH TỔNG HỢP VỚI CÂY TÌM KIẾM NHỊ PHÂN

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Ôn luyện kiến thức tổng hợp về cây tìm kiếm nhị phân gồm các thao tác: thêm, tìm kiếm và duyệt nút gồm nhiều trường thông tin.

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:

• Vận dụng cây tìm kiếm nhị phân vào các bài toán cụ thể.

• Sử dụng các phương thức duyệt cây tìm kiếm nhị phân để in danh sách các đối tượng theo thứ tự tăng dần hoặc giảm dần của khoá.

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: Tạo tâm thế cho HS vào bài học mới.

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

Trong Bài 9, chúng ta đã học thao tác duyệt cây. Với bài toán thực tế quản lí danh bạ điện thoại, làm thế nào để sử dụng các thao tác đó vào cây tìm kiếm nhị phân để thêm, tìm kiếm, hiển thị toàn bộ các liên hệ theo thứ tự sắp xếp của tên liên hệ trong danh bạ?

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 tiết trước, chúng ta đã được học về cây tìm kiếm nhị phân, các thuật toán duyệt trên cây tìm kiếm nhị phân. Bài hôm nay chúng ta cùng đi thực hành các thuật toán duyệt trên cây tìm kiếm nhị phân: các thao tác thêm, tìm kiếm, duyệt dữ liệu với cây tìm kiếm nhị phân. – Bài 8: Thực hành cây tìm kiếm nhị phân.

B. HOẠT ĐỘNG THỰC HÀNH

Hoạt động: Viết chương trình quản lí thực đơn.

a. Mục tiêu: HS luyện tập kiến thức tổng hợp về cây tìm kiếm nhị phân để thêm, sửa, tìm kiếm, hiển thị danh sách đối tượng theo thứ tự sắp xếp từ nhỏ đến lớ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: HS viết được chương trình quản lí danh bạ điện thoại.

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

C. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Giúp HS luyện tập kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phần luyện tập SGK.

c. Sản phẩm học tập: Kết quả bài tập 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 yêu cầu HS hoạt động cá nhân, hoàn thành phần Luyện tập SGK tr.29)

Câu 1. Hãy vẽ cây tìm kiếm nhị phân ứng với:

a) Dữ liệu tệp contacts.inp ở trong phần thực hành.

b) Từ cây nhận được ở ý a, thêm liên hệ "Anh, Nguyễn Văn Tùng, 0982 000 134".

Câu 2. Tiếp tục với ứng dụng quản lí danh bạ, chức năng hiển thị danh sách liên hệ theo thứ tự từ điển. Do hạn chế của màn hình, mỗi trang chỉ hiển thị được 20 liên hệ. Hãy thêm tính năng in các liên hệ ở trang n bất kì do người dùng nhập vào, điều kiện n nguyên, lớn hơn 0 và nhỏ hơn hoặc bằng tổng số trang có thể hiển thị.

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

- HS suy nghĩ, hoàn thành các bài tập GV yêu cầu.

- GV quan sát và hỗ trợ, hướng dẫn.

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

- Mỗi bài tập GV mời 1 đến 2 HS trình bày. Các HS khác chú ý chữa bài, theo dõi nhận xét bài làm của các bạn.

Gợi ý đáp án: 

Câu 1. 

a) Để vẽ lại cây tìm kiếm nhị phân ứng với tệp contacts.inp hãy thực hiện dẫn các bước của thuật toán chèn cho từng liên hệ trong tệp contacts.inp. Do dữ liệu chỉ gồm 4 liên hệ trong đó 3 liên hệ đầu tiên được chèn vào lại đúng với thứ tự khoá của chúng, nút “Bố” và “Mẹ” đều nằm ở nhánh phải của cây. Vì “ICTLab Station" < "Mẹ" nên “ICTLab Station" là nút con trái của “Mẹ”. Cây tìm kiếm nhị phân thu được, không may thay, có dạng “cây suy biến” như Hình.

b) Khi thêm liên hệ mới có khoá “Anh” vào cây, do nút này có khoá nhỏ hơn khoá ở nút gốc “Anh An” nên liên hệ này được thay vào nút con trái None của nút gốc và ta thu được cây như Hình.

Câu 2.

Để in được các danh bạ ở một trang, cần phải đếm thứ tự các liên hệ khi duyệt cây. 

Sử dụng biến toàn cục count để đếm khi duyệt bằng hàm inorder và các biến starting, ending để đánh dấu vị trí đầu tiên và cuối cùng của trang cần tìm. Mã nguồn tham khảo như sau:

----------------------------------

------------------ Còn tiếp ---------------------