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

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

 - GV cho HS thảo luận theo bàn, đọc và tìm hiểu thông tin trong mục 1.SGK-tr.5,6 để trả lời các câu hỏi:  + Hàng đợi là gì? Cơ chế hoạt động của hàng đợi là gì?  + Trình bày các thao tác cơ bản “Thêm vào” và “Lấy ra” trên hàng đợi.  - GV triển khai mục Câu hỏi củng cố SGK-tr.7 và cho HS thảo luận nhóm đôi để thực hiện:

1. Cho Hình 4 biểu diễn một hàng đợi, hãy cho biết:

a) Phần tử đầu hàng đợi, phần tử cuối hàng đợi.

b) Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử nào?

c) Sau khi thêm vào phần tử “k” vào thì phần tử cuối hàng đợi là phần tử nào?

Hình 4. Hàng đợi và hai đầu front, rear

2. Cho một hàng đợi rỗng, hãy vẽ hình minh họa từng bước thực hiện các thao tác sau: enqueue(1), enqueue(3), enqueue(5), dequeue(), dequeue(), enqueue(7).

 + Sau thời gian thảo luận, GV chỉ định lần lượt các HS thực hiện yêu cầu của câu hỏi.

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

 - HS tìm hiểu nội dung phần a, mục 1 SGK tr.5 sau đó trao đổi, thảo luận 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

 - GV mời đại diện các nhóm báo cáo kết quả thảo luận.  - Hướng dẫn trả lời câu hỏi củng cố SGK-tr.7

1. a) Phần tử đầu hàng đợi: m;

Phần tử cuối hàng đợi: x.

b) Sau khi lấy ra một phần tử thì phần tử đầu hàng đợi là: +.

c) Sau khi thêm vào phần tử “k” vào thì phần tử cuối hàng đợi là phần tử: k.

2.

 - GV mời HS khác nhận xét, bổ sung.

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

 - Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.  - GV chính xác hoá lại các nội dung kiến thức.  - GV kết luận:  + Khái niệm: hàng đợi là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử.  + Hai thao tác cơ bản trên hàng đợi: thao tác thêm vào (enqueue) ở cuối hàng đợi (rear) và thao tác lấy ra (dequeue) ở đầu hàng đợi (front). Hai thao tác này thể hiện cơ chế hoạt động “Vào trước - Ra trước” (FIFO – First In, First Out).

1. Hàng đợi

 - Khái niệm: Hàng đợi là một cấu trúc dữ liệu tuyến tính dùng để lưu danh sách các phần tử.  - Cơ chế hoạt động của hàng đợi được căn cứ theo thứ tự các phần tử được thêm vào hàng đợi, gọi là vào trước ra trước (FIFO – First In, First Out).

Hình 2. Cơ chế FIFO của hàng đợi

 - Các thao tác  cơ bản:  + Thao tác enqueue: Thêm vào phần tử mới ở cuối hàng đợi.  + Thao tác dequeue: Lấy ra  một phẩn tử ở đầu hàng đợi.  + Thao tác front: Trả về giá trị của phần tử đầu hàng đợi.  + Thao tác rear (hay back): Trả về giá trị của phần tử cuối hàng đợi.  + Thao tác kiểm tra hàng đợi rỗng.

Các thao tác được thể hiện trong Hình 3.

Hình 3. Thao tác enqueue, dequeue, trên hàng đợi và hai đầu front, rear.

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

a) Biểu diễn hàng đợi bằng mảng một chiều.

 - GV trình chiếu Hình 5 và cho HS đọc và nghiên cứu mục 2, phần a SGK-tr.7 để trả lời câu hỏi sau:

 + Dựa vào Hình 5, cho biết chỉ số của phần tử đầu hàng đợi và chỉ số của phần tử cuối hàng đợi trong mảng là bao nhiêu?  - GV cho HS thảo luận nhóm đôi, thực hiện mục Câu hỏi củng cố SGK-tr.7

1. Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng một chiều là gì?

2. Với hàng đợi ở hình 5, hay vẽ hình thực hiện liên tục các thao tác: Thêm vào 0, lấy ra, lấy ra.

b) Cài đặt hàng đợi bằng mảng một chiều trong Python

 - HS thảo luận theo nhóm 4HS tìm hiểu thông tin trong mục 2, phần b SGK-tr.8 để thực hiện các câu hỏi sau:  + Các phép toán cơ bản cho hàng đợi được cài đặt thông qua những hàm nào? Cho biết ý nghĩa của những hàm đó.  - GV cho HS thực hiện cá nhân phần câu hỏi củng cố SGK-tr.8:

1. Tại sao không cần sử dụng các chỉ số front, rear khi dùng kiểu list để biểu diễn hàng đợi trong Python?

2. Theo em, có cách nào kiểm tra hàng đợi queue là rỗng mà không dùng hàm len(queue)?

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

 - HS tiếp nhận và thực hiện nhiệm vụ theo đúng hướng dẫn để hoàn thành yêu cầu.  - Trong quá trình HS thực hành, GV quan sát, hỗ trợ, giải đáp các vướng mắc của HS.

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

 - Nếu HS có vướng mắc trong quá trình thực hành, GV yêu cầu HS thảo luận, tìm giải pháp khắc phục.  - HS báo cáo, chia sẻ giải pháp tìm được.  - Hướng dẫn thực hiện câu hỏi củng cố SGK-tr.7

1.

 + Mảng: Một mảng một chiều để lưu trữ các phần tử của hàng đợi.  + Chỉ số đầu và chỉ số cuối của hàng đợi: Chỉ số đầu dùng để trỏ đến phần tử đầu tiên của hàng đợi, chỉ số cuối dùng để trỏ đến phần tử cuối cùng của hàng đợi.  + Số lượng phần tử hiện có trong hàng đợi: Điều này cho phép chúng ta biết hàng đợi hiện tại đang chứa bao nhiêu phần tử và khi nào nó đầy.

2.

 - Hướng dẫn thực hiện câu hỏi củng cố SGK-tr.8

1.

Trong Python, khi sử dụng kiểu danh sách (list) để biểu diễn hàng đợi, chúng ta không cần phải sử dụng các chỉ số front và rear vì danh sách có thể mở rộng linh hoạt và các phần tử có thể được thêm vào và lấy ra từ cả hai đầu của danh sách một cách dễ dàng. Thêm vào đó, Python cung cấp các phương thức sẵn có như append() để thêm phần tử vào cuối danh sách và pop(0) để lấy phần tử từ đầu danh sách. Điều này giúp làm giảm đáng kể sự phức tạp của việc quản lý chỉ số front và rear.

2.

 - Kiểm tra độ dài của hàng đợi bằng phương thức len() và so sánh với 0 mà không cần truy cập trực tiếp đến hàng đợi:

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

 - Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.  - GV chính xác hoá lại các nội dung kiến thức.  - GV kết luận:

Hàng đợi là một dãy các phần tử. Do đó, hàng đợi có thể được biểu diễn bằng mảng một chiều hoặc danh sách (kiểu list của Python). Khi hàng đợi là danh sách (kiểu list), hàm thêm vào enqueue() dùng hàm append() của kiểu list và hàm lấy ra dequeue() dùng hàm pop() của kiểu list.

2. Biểu diễn và cài đặt hàng đợi bằng mảng một chiều

a) Biểu diễn hàng đợi bằng mảng một chiều.

 - Phần tử đầu của hàng đợi được đặt vào phần tử có chỉ số front = 0.  - Phần tử cuối hàng đợi được đặt vào phần tử có chỉ số rear = 6.

b) Cài đặt hàng đợi bằng mảng một chiều trong Python

 - Các phép toán cơ bản cho hàng đợi được cài đặt thông qua các hàm sau:  + Khởi tạo hàng đợi rỗng:

 + Kiểm tra hàng đợi rỗng:

 + Phép toán enqueue: Sử dụng hàm append() để thêm phần tử vào cuối hàng đợi.

 + Phép toán dequeue: thao tác dequeue bắt đầu bằng việc kiểm tra hàng đợi có rỗng hay không. Nếu không, sử dụng hàm pop() với chỉ số 0 để xóa phần tử đầu hàng đợi đi.

 + Phép toán front: kiểm tra nếu hàng đợi không rỗng thì trả về giá trị của queue[0].

Phép toán rear: kiểm tra nếu hàng đợi không rỗng thì trả về giá trị của queue[len(queue)-1].

Trường THPT:………………………………………….

Lớp:……………………………………………………...

Họ và tên:……………………………………………….

PHIẾU BÀI TẬP CHUYÊN ĐỀ TIN HỌC 12 – ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH – CHÂN TRỜI SÁNG TẠO

BÀI 1.1: HÀNG ĐỢI

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Thao tác nào được thực hiện trên hàng đợi khi một phần tử mới được thêm vào?

A. Gán giá trị cuối cùng.

B. Xóa phần tử đầu tiên.

C. Kiểm tra sự tồn tại của phần tử.

D. Thêm vào phần tử cuối cùng.

Câu 2. Đặc điểm nào phản ánh cơ chế hoạt động của hàng đợi?

A. Thứ tự ngẫu nhiên khi lấy ra.

B. Thêm và lấy ra theo thứ tự FIFO.

C. Ưu tiên các phần tử đã tồn tại.

D. Lựa chọn phần tử ngẫu nhiên khi thêm vào.

Câu 3. Làm thế nào để biểu diễn hàng đợi bằng mảng một chiều?

A. Sử dụng con trỏ để chỉ đến phần tử đầu và cuối của mảng.

B. Sử dụng một mảng với phần tử đầu tiên là đầu hàng đợi và phần tử cuối cùng là cuối hàng đợi.

C. Sử dụng một danh sách liên kết đôi để lưu trữ các phần tử trong hàng đợi.

D. Sử dụng một danh sách liên kết đơn để lưu trữ các phần tử trong hàng đợi.

Câu 4. Khi biểu diễn hàng đợi bằng mảng một chiều, thao tác thêm vào và lấy ra phần tử thường được thực hiện ở vị trí nào của mảng?

A. Thêm vào vị trí cuối mảng, lấy ra từ vị trí đầu mảng.

B. Thêm vào vị trí đầu mảng, lấy ra từ vị trí cuối mảng.

C. Thêm vào và lấy ra đều từ vị trí giữa mảng.

D. Thêm vào và lấy ra từ cả hai đầu mảng.

Câu 5. Trong Python, cách nào sau đây thích hợp để cài đặt hàng đợi bằng mảng một chiều?

A. Sử dụng module collections.deque.

B. Sử dụng module queue.Queue.

C. Sử dụng một danh sách (list) và thêm vào từ đầu, lấy ra từ cuối.

D. Sử dụng một danh sách (list) và thêm vào từ cuối, lấy ra từ đầu.

Câu 6. Ý nghĩa của phép toán enqueue là gì?

A. Kiểm tra hàng đợi rỗng.

B. Khởi tạo hàng đợi rỗng.

C. Sử dụng hàm append() để thêm phần tử vào cuối hàng đợi.

D. Kiểm tra nếu hàng đợi không rỗng thì trả về giá trị của queue[0].

Câu 7. Cho một chương trình hàng đợi như sau:

Trong chương trình hàng đợi được triển khai trong Python trên, hàm nào nào được sử dụng để lấy ra phần tử từ đầu hàng đợi?

A. front().

B. pop().

C. dequeue().

D. remove().