Giáo án chuyên đề Khoa học máy tính 12 chân trời Bài 2.1: Cây và cây nhị phân
Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 12 - Định hướng Khoa học máy tính bộ sách Chân trời sáng tạo Bài 2.1: Cây và cây nhị phân. Bộ giáo án giúp giáo viên hướng dẫn học sinh mở rộng kiến thức, phát triển năng lực, nâng cao khả năng định hướng nghề nghiệp cho các em sau này. Thao tác tải về rất đơn giản, tài liệu file word có thể chỉnh sửa dễ dàng. Mời quý thầy cô tham khảo bài soạn.
Xem: => Giáo án Tin học 12 - Định hướng Khoa học máy tính chân trời sáng tạo
Xem toàn bộ: Giáo án chuyên đề Khoa học máy tính 12 chân trời sáng tạo đủ cả năm
Ngày soạn: …/…/…
Ngày dạy: …/…/…
CHUYÊN ĐỀ 2: TÌM HIỂU CÂY TÌM KIẾM
NHỊ PHÂN TRONG SẮP XẾP VÀ TÌM KIẾM
BÀI 2.1: CÂY VÀ CÂY 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êu được khái niệm cây, cây nhị phân.
Biểu diễn được cây nhị phân bằng mảng một chiều.
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:
NLa và NLc: Biểu diễn được cây nhị phân bằng mảng một chiều.
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 – Chân trời sáng tạo.
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 - Chân trời sáng tạo.
III. TIẾN TRÌNH DẠY HỌC
A. HOẠT ĐỘNG KHỞI ĐỘNG
a. Mục tiêu: HS tiếp cận với mô hình “cây” trong thực tế, để thêm sự liên hệ giữa giữa tổ chức thông tin, dữ liệu với “cây”.
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 26:
Quan sát sơ đồ tổ chức của một công ty ở Hình 1 và cho biết các phòng ban chức năng trong công ty được tổ chức như thế nào.
Hình 1. Sơ đồ tổ chức của một công ty theo chức năng
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: Trong chuyên đề này, ta đi tìm hiểu về cây tìm kiếm nhị phân trong sắp xếp và tìm kiếm. Trước hết ta đi tìm hiểu thế nào là cây, cây nhị phân, cách biểu diễn cây nhị phân bằng mảng một chiều - Bài 2.1: Cây và cây nhị phân.
B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1. Tìm hiểu cây và cây nhị phân
a. Mục tiêu: HS nêu được khái niệm cây và cây nhị phân.
b. Nội dung: GV giao nhiệm vụ; HS hoạt động cá nhân, tìm hiểu nội dung mục
1. Tìm hiểu cây và cây nhị phân và thực hiện nhiệm vụ học tập.
c. Sản phẩm: Các khái niệm về cây và cây 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 giới thiệu về cấu trúc dữ liệu tuyến tính và phi tuyến tính. - GV yêu cầu HS tìm hiểu nội dung SGK và trình bày về: + Khái niệm cây và các khái niệm cơ bản về cây. + Chỉ ra các khái niệm chính của cây tương ứng.
- GV phân tích Hình 2 để HS hiểu rõ hơn các khái niệm cơ bản về cây. - GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm tr.28 SGK: Cho các cây như ở Hình 3. Cho biết: a) Nút gốc, nút nhánh, nút lá ở Hình 3a. b) Mức và chiều cao của cây trong Hình 3b. Hình 3a. Hình 3b. Hình 3. Biểu diễn cây Bước 2: HS thực hiện nhiệm vụ học tập - HS tìm hiểu nội dung SGK và trả lời các câu hỏi mà GV đưa ra. - GV quan sát, 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ả lời các câu hỏi và nhận xét lẫn nhau. Hướng dẫn trả lời câu hỏi hoạt động Làm tr.28 SGK: a) Hình 3a trong SGK. + Nút gốc: 2. + Nút nhánh: 24, 11, 20, 8. + Nút lá: 83, 3, 10, 15, 9. b) Hình 3b trong SGK. + Mức của nút 2 là 0. + Mức của các nút 24, 11 là 1. + Mức của các nút 8, 3, 8,9 là 2. + Chiều cao của cây là 2. Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nêu nhận xét, chính xác hoá lại các nội dung trả lời của HS. - GV chốt kiến thức như nội dung ở hoạt động Ghi nhớ:
| 1. Giới thiệu cây, cây nhị phân a) Cây - Cấu trúc dữ liệu tuyến tính bao gồm các phần tử tạo thành một dãy nối tiếp nhau và thông thường thao tác duyệt được thực hiện tuần tự theo trình tự của các phần tử. Mỗi phần tử có nhiều nhất một phần tử kề đi sau nó. - Cấu trúc dữ liệu phi tuyến tính bao gồm các phần tử không tạo thành một dãy nối tiếp nhau. Mỗi phần tử có thể có nhiều phần tử kề đi sau nó. Ví dụ: Cấu trúc dữ liệu cây là cấu trúc dữ liệu phi tuyến. - Cây là một tập hợp rỗng hoặc bao gồm nhiều phần tử được gọi là nút. - Cây rỗng là cây cây không có nút nào. Ngược lại, các nút có liên kết “cha – con” với nhau:
- Biểu diễn nút trên cây:
Cây có cấu trúc đệ quy: một cây có thể chứa các cây con. - Một số khái niệm cơ bản về cây: + Nút gốc:
+ Nút lá:
+ Nút nhánh (nút trong):
+ Mức của một nút:
+ Chiều cao của cây:
+ Đường đi từ nút gốc đến nút x là dãy các cạnh từ nút gốc đến nút x. Hình 2. Minh hoạ các khái niệm trên cây Trong Hình 2:
| |
Bước 1: GV chuyển giao nhiệm vụ học tập - GV yêu cầu HS tìm hiểu về cây nhị phân và trình bày: + Thế nào là cây nhị phân? + Một số dạng đặc biệt của cây nhị phân. + Một số tính chất của cây nhị phân. - GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm tr.29 SGK: Cho biết cây nào ở Hình 3 là cây nhị phân. Bước 2: HS thực hiện nhiệm vụ học tập - HS tìm hiểu nội dung SGK và trả lời các câu hỏi mà GV đưa ra. - GV quan sát, 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ả lời các câu hỏi và nhận xét lẫn nhau. Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.29: Cây ở Hình 3b là cây nhị phân. Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nêu nhận xét, chính xác hoá lại các nội dung trả lời của HS. - GV chốt kiến thức như nội dung ở hoạt động Ghi nhớ:
| b) Cây nhị phân - Khái niệm: Cây nhị phân là cây mà mỗi nút của cây có tối đa hai cây con (cây con trái và cây con phải). - Một số dạng đặc biệt của cây nhị phân: Gọi h là chiều cao của cây nhị phân.
Hình 4a. Cây nhị phân hoàn chỉnh
Hình 4b. Cây nhị phân hoàn hảo - Một số tính chất của cây nhị phân:
|
Hoạt động 2. Biểu diễn cây nhị phân
a. Mục tiêu: HS biết cách biểu diễn cây nhị phân bằng mảng một chiều.
b. Nội dung: GV giao nhiệm vụ; HS hoạt động cá nhân, tìm hiểu nội dung mục
2. Biểu diễn cây nhị phân và thực hiện nhiệm vụ học tập.
c. Sản phẩm: Cách biểu diễn và cài đặt cây nhị phân bằng mảng một chiều.
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 tìm hiểu và trình bày: Cách biểu diễn cây nhị phân bằng mảng một chiều. - GV hướng dẫn HS biểu diễn cây nhị phân bằng mảng một chiều thông qua Ví dụ 1 và Ví dụ 2. - GV hướng dẫn HS thực hiện cài đặt cây nhị phân bằng mảng một chiều. - GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi hoạt động Làm SGK tr.31: Xây dựng mảng một chiều biểu diễn cây ở Hình 7. Hình 7. Cây nhị phân Bước 2: HS thực hiện nhiệm vụ học tập - HS tìm hiểu nội dung SGK và thực hiện các yêu cầu mà GV đưa ra. - GV quan sát, 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ả lời các câu hỏi và nhận xét lẫn nhau. Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.31 Mảng một chiều biểu diễn cây ở Hình 7 là: Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nêu nhận xét, chính xác hoá lại các nội dung trả lời của HS. - GV chốt kiến thức như nội dung ở hoạt động Ghi nhớ: ……………………… | 2. Biểu diễn cây nhị phân a) Biểu diễn cây nhị phân bằng mảng một chiều - Cây nhị phân có thể được biểu diễn bằng mảng một chiều bằng cách đánh chỉ số cho các nút của cây bắt đầu từ nút gốc. - Theo Tính chất 4 ở mục 1b, cây nhị phân có thể được lưu trữ trong mảng một chiều có () phần tử như sau:
Điều này có nghĩa là thêm các nút None vào cây nhị phân tổng quát để cây này trở thành cây nhị phân hoàn chỉnh. Ví dụ 1: Biểu diễn cây nhị phân ở Hình 3b (cây nhị phân hoàn hảo) bằng mảng một chiều: Đánh chỉ số bắt đầu từ 0 cho các nút theo thứ tự từ mức 0 đến mức cuối cùng, từ trái sang phải trên cùng một mức. Hình 5. Đánh chỉ số cho các nút Lưu các nút vào mảng một chiều: nút có chỉ số i được lưu vào phần tử có chỉ số i. Ví dụ 2: Biểu diễn cây nhị phân tổng quát bằng mảng một chiều: Thêm vào cây một số nút giả và gán giá trị None để được cây nhị phân hoàn chỉnh. …………………… |
---------------------------------------
------------------ Còn tiếp ------------------------
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
MỘT VÀI THÔNG TIN:
- Powerpoint soạn: Hiện đại, đẹp mắt để tạo hứng thú học tập
- Giáo án word và PPT đồng bộ với nhau
- Các phản hồi của giáo viên được trả lời ngay và luôn
Thời gian bàn giao giáo án
- Khi đặt nhận đủ chuyên đề I
- 30/11 bàn giao chuyên đề II
- 30/01 bàn giao chuyên đề III
Phí giáo án chuyên đề
- Giáo án word: 300k
- Giáo án Powerpoint: 400k
- Trọn bộ word + PPT: 650k
Chỉ gửi trước 350k. Sau đó, gửi dần trong quá trình nhận. Đến lúc nhận đủ kì 1 thì gửi nốt số còn lại
=> Khi đặt sẽ nhận ngay và luôn:
- Phiếu trắc nghiệm cấu trúc mới: 5-7 phiếu
- Nhận đủ chuyên đề I
- Một số đề kiểm tra giữa kì I - có ma trận, lời giải...
- PPCT, file word đáp án sgk
Cách đặt:
- Bước 1: Gửi phí vào tk: 10711017 - Chu Văn Trí - Ngân hàng ACB (QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận giáo án
Xem toàn bộ: Giáo án chuyên đề Khoa học máy tính 12 chân trời sáng tạo đủ cả năm
ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC
Đủ giáo án word và powerpoint các môn lớp 12 kết nối tri thức
Đủ giáo án word và powerpoint các môn lớp 12 cánh diều
GIÁO ÁN WORD LỚP 12 CHÂN TRỜI SÁNG TẠO
Giáo án toán 12 chân trời sáng tạo
Giáo án đại số 12 chân trời sáng tạo
Giáo án hình học 12 chân trời sáng tạo
Giáo án sinh học 12 chân trời sáng tạo
Giáo án hoá học 12 chân trời sáng tạo
Giáo án vật lí 12 chân trời sáng tạo
Giáo án ngữ văn 12 chân trời sáng tạo
Giáo án lịch sử 12 chân trời sáng tạo
Giáo án kinh tế pháp luật 12 chân trời sáng tạo
Giáo án âm nhạc 12 chân trời sáng tạo
Giáo án Tin học 12 - Định hướng Khoa học máy tính chân trời sáng tạo
Giáo án Tin học 12 - Định hướng Tin học ứng dụng chân trời sáng tạo
Giáo án hoạt động trải nghiệm hướng nghiệp 12 chân trời sáng tạo bản 1
Giáo án hoạt động trải nghiệm hướng nghiệp 12 chân trời sáng tạo bản 2
GIÁO ÁN POWERPOINT LỚP 12 CHÂN TRỜI SÁNG TẠO
Giáo án powerpoint đại số 12 chân trời sáng tạo
Giáo án powerpoint hình học 12 chân trời sáng tạo
Giáo án powerpoint Tin học 12 - Định hướng Khoa học máy tính chân trời sáng tạo
Giáo án powerpoint Tin học 12 - Định hướng Tin học ứng dụng chân trời sáng tạo
Giáo án powerpoint hoạt động trải nghiệm hướng nghiệp 12 chân trời sáng tạo bản 2
GIÁO ÁN CHUYÊN ĐỀ LỚP 12 CHÂN TRỜI SÁNG TẠO
Giáo án chuyên đề ngữ văn 12 chân trời sáng tạo
Giáo án chuyên đề toán 12 chân trời sáng tạo
Giáo án chuyên đề kinh tế pháp luật 12 kết nối tri thức
Giáo án chuyên đề vật lí 12 chân trời sáng tạo
Giáo án chuyên đề hoá học 12 chân trời sáng tạo
Giáo án chuyên đề sinh học 12 chân trời sáng tạo
Giáo án chuyên đề lịch sử 12 chân trời sáng tạo
Giáo án chuyên đề địa lí 12 chân trời sáng tạo
Giáo án chuyên đề âm nhạc 12 chân trời sáng tạo
Giáo án chuyên đề Tin học 12 - Định hướng Tin học ứng dụng chân trời sáng tạo
Giáo án chuyên đề Tin học 12 - Định hướng Khoa học máy tính chân trời sáng tạo
GIÁO ÁN POWERPOINT CHUYÊN ĐỀ LỚP 12 CHÂN TRỜI SÁNG TẠO
Giáo án powerpoint chuyên đề ngữ văn 12 chân trời sáng tạo
Giáo án powerpoint chuyên đề địa lí 12 chân trời sáng tạo
Giáo án powerpoint chuyên đề Tin học Khoa học máy tính 12 chân trời sáng tạo
GIÁO ÁN DẠY THÊM LỚP 12 CHÂN TRỜI SÁNG TẠO
Giáo án dạy thêm ngữ văn 12 chân trời sáng tạo
Giáo án powerpoint dạy thêm ngữ văn 12 chân trời sáng tạo
Giáo án dạy thêm toán 12 chân trời sáng tạo
Giáo án powerpoint dạy thêm toán 12 chân trời sáng tạo