Giáo án điện tử chuyên đề khoa học máy tính 12 kết nối bài 1: Mô hình dữ liệu ngăn xếp và hàng đợi

BÀI 1: MÔ HÌNH DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI

Chào mừng các em đến với bài học ngày hôm nay!

A. KHỞI ĐỘNG

Em hãy quan sát các hình ảnh về đồ vật và hiện tượng trong thực tế trong Hình 1.1 và cho biết:

a) Trong chồng đĩa, đĩa nào được xếp vào sau cùng? Đĩa nào được lấy ra đầu tiên?

b) Ai sẽ là người được rút tiền trước tại cây ATM? Người xếp hàng cuối cùng sẽ được rút tiền khi nào?

Gợi ý trả lời:

- Hình a: Đĩa nào cho vào trước thì sẽ lấy ra sau cùng, đĩa nào cho vào sau cùng sẽ lấy ra đầu tiên.

Đây là cơ chế hoạt động của mô hình dữ liệu ngăn xếp (stack).

- Hình b: Ai xếp hàng trước sẽ được rút tiền trước, ai xếp sau sẽ rút tiền sau theo đúng thứ tự. 

Đây là cơ chế hoạt động của mô hình hàng đợi (queue).

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

Hoạt động 1. Tìm hiểu mô hình dữ liệu ngăn xếp

+ Mô hình dữ liệu ngăn xếp hoạt động theo cơ chế gì?

+ Em hãy nêu một ví dụ khác về ngăn xếp và mô tả cách hoạt động của ví dụ này.

+ Em hãy mô tả mô hình dữ liệu ngăn xếp.

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

1. Mô hình dữ liệu ngăn xếp

- Cơ chế hoạt động của mô hình dữ liệu ngăn xếp: “vào sau, ra trước” (LIFO – Last In, First Out).

- Ví dụ khác về ngăn xếp: chức năng Undo khi soạn thảo văn bản. Mỗi khi thực hiện một thao tác mới, trạng thái hiện tại của văn bản được đưa vào đỉnh của ngăn xếp Undo. Khi yêu cầu Undo, trạng thái hiện tại được lấy ra từ đỉnh ngăn xếp và khôi phục lại.

- Mô hình dữ liệu ngăn xếp được mô tả như sau:

+ Ngăn xếp là một dãy tuyến tính các phần tử dữ liệu.

+ Ngăn xếp có các thao tác đưa phần tử vào và lấy phần tử ra tại cùng một đầu của ngăn xếp. Thao tác đưa dữ liệu vào là push và lấy dữ liệu ra là pop.

+ Quy ước đầu dùng để đưa dữ liệu vào và lấy dữ liệu ra là đỉnh (top) của ngăn xếp. Đầu ngược lại là đáy (bottom) của ngăn xếp.

+ Mô hình dữ liệu ngăn xếp hoạt động theo cơ chế LIFO.

………………………………………………

Hoạt động 2. Tìm hiểu mô hình dữ liệu hàng đợi

+ Mô hình dữ liệu hàng đợi hoạt động theo cơ chế gì?

+ Em hãy nêu một ví dụ của mô hình hàng đợi và mô tả cách hoạt động của ví dụ này.

+ Em hãy mô tả mô hình dữ liệu hàng đợi.

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

2. Mô hình dữ liệu hàng đợi

- Cơ chế hoạt động của mô hình dữ liệu hàng đợi: “vào trước, ra trước” (FIFO – First In, First Out).

- Ví dụ của mô hình hàng đợi: máy in.

Máy in sẽ lưu trữ các nội dung in vào một hàng đợi, nội dung nào vào trước sẽ được in trước, nội dung nào vào sau được in sau.

- Mô hình dữ liệu hàng đợi được mô tả như sau:

+ Hàng đợi là một dãy tuyến tính các phần tử dữ liệu.

+ Hàng đợi có các thao tác đưa phần tử vào ở một đầu và lấy phần tử ra tại một đầu khác của hàng đợi. Thao tác đưa dữ liệu vào là enqueue và lấy dữ liệu ra là dequeue.

+ Quy ước đầu dùng để đưa dữ liệu vào là đuôi (back, rear, tail) của hàng đợi. Đầu ngược lại dùng để lấy dữ liệu ra là đầu (front, head) của hàng đợi.

+ Mô hình dữ liệu hàng đợi hoạt động theo cơ chế FIFO.

C. LUYỆN TẬP

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

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

Câu 1. Lệnh tạo một ngăn xếp rỗng là

A. Stack = ().         

B. Q = Queue().               

C. S = Stack().                 

D. S = isEmptyStack().

Câu 2. Có thể thiết lập các lệnh thực hiện các thao tác cơ bản trên dữ liệu hàng đợi đều có độ phức tạp thời gian là bao nhiêu?

A. với là độ dài của hàng đợi.       

B. .

C. với là độ dài của hàng đợi.                 

D. với là độ dài của hàng đợi.

Câu 3. Phát biểu nào sau đây đúng khi nói về mô hình dữ liệu ngăn xếp?

A. Xếp hàng chờ lên máy bay là một ví dụ về ngăn xếp.

B. Ngăn xếp thuộc kiểu dữ liệu phi tuyến tính.

C. Ngăn xếp có hàm pop() để đưa dữ liệu vào và hàm push() để lấy dữ liệu ra.

D. Ngăn xếp hoạt động theo cơ chế LIFO.

Câu 4. Hàm nào sau đây trả về phần tử đầu của hàng đợi Q và Q không thay đổi?

A. top(Q).              

B. dequeue(Q).                

C. front(Q).           

D. first(Q).

Câu 5. Sau khi thực hiện các lệnh sau, hỏi trong hàng đợi Q có những giá trị nào?

Q = Queue()

enqueue(Q, 5); enqueue(Q, 2); enqueue(Q, 8); dequeue(Q).

A. 2, 8.                             

B. 5, 2.                           

C. 5, 8.                           

D. 5.

Gợi ý trả lời:

D. VẬN DỤNG

Câu 1. Tìm thêm các ví dụ thực tế của ngăn xếp và hàng đợi, mô tả hoạt động của các ví dụ này.

Câu 2. Giả sử ngăn xếp S chứa các phần tử theo thứ tự từ đỉnh xuống đáy là 2, 1, 3. Được phép sử dụng một hàng đợi rỗng Q, em hãy sắp xếp các phần tử của ngăn xếp S theo thứ tự 3, 2, 1 (từ đỉnh xuống đáy).

Hướng dẫn về nhà:

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

- Xem trước nội dung Bài 2: Kiểu dữ liệu ngăn xếp.

Xin trận trọng cảm ơn sự quan tâm theo dõi của các em, hẹn gặp lại!