Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 1.1: Hàng đợi

BÀI 1.1: HÀNG ĐỢI

Thân ái chào các em học sinh đến với tiết học ngày hôm nay!

A. KHỞI ĐỘNG

Khi làm thủ tục tại các cơ quan hành chính nhà nước, em sẽ gặp các hệ thống xếp hàng tự động (Hình 1). Theo em, các hệ thống này hoạt động theo nguyên tắc nào?

Hình 1. Hệ thống xếp hàng tự động

Gợi ý trả lời:

Nguyên tắc của hệ thống xếp hàng tự động là ai đến trước sẽ được xếp hàng trước để xử lí công việc trước, những người tiếp theo cứ xếp hàng lần lượt như vậy.

B. HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Tìm hiểu về hàng đợ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.

Dự kiến sản phẩm:

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

+ enqueue: Thêm vào phần tử mới ở cuối hàng đợi.

+ dequeue: Lấy ra  một phẩn tử ở đầu hàng đợi.

+ front: Trả về giá trị của phần tử đầu hàng đợi.

+ rear (hay back): Trả về giá trị của phần tử cuối hàng đợi.

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

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

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

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.

Dự kiến sản phẩm:

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].

C. LUYỆN TẬP

Hoàn thành phiếu bài tập sau:

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.

………………………..

Gợi ý trả lời:

D. VẬN DỤNG

1. Các phần tử trong hàng đợi biểu diễn kiểu list trong Python có thể thuộc kiểu chuỗi hay không? Nếu có, sử dụng các hàm initQueue(), enqueue() để tạo hàng đợi có các phần tử như sau:

Sau đó, sử dụng các hàm enqueue(), dequeue() để hàng đợi trên có kết quả là:

2. Theo em, có thể dùng danh sách liên kết để biểu diễn hàng đợi hay không?

HƯỚNG DẪN VỀ NHÀ

- Xem lại kiến thức đã học ở Bài 1.1.

- Xem trước nội dung Bài 1.2: Ngăn xếp.