a) Chồng đĩa

b) Xếp hàng rút tiền tại ATM

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 đọc, trao đổi và thảo luận theo nhóm đôi tìm hiểu nội dung mục 1 SGK tr.5 – 6, trả lời các câu hỏi sau:

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

Hình 1.2. Mô hình ngăn xếp

+ Hãy ghép nối các nội dung cột A với cột B để có kết quả đúng nhất.

- GV yêu cầu HS đọc hiểu Ví dụ 1, 2 tr.6 SGK.

- 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 Củng cố tr.7 SGK:

Câu 1. Muốn lấy ra phần tử nằm ở đáy của ngăn xếp thì phải làm như thế nào?

Câu 2. Cho S là một ngăn xếp rỗng. Em hãy cho biết, khi thực hiện các lệnh sau thì S sẽ chứa những phần tử nào?

push(S,1); push(S,5); pop(S); push(S,10).

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

- HS tìm hiểu nội dung mục 1 SGK tr. 5 – 6 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ố tr.7 SGK:

Câu 1. Để lấy ra phần tử nằm ở đáy của ngăn xếp thì phải pop(S) tất cả các phần tử trong Stack.

Câu 2. S sẽ chứa phần tử 1, 10.

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

+ Đặc điểm: Ngăn xếp (stack) thuộc kiểu dữ liệu tuyến tính có các hàm cơ bản: hàm push() để đưa dữ liệu vào và hàm pop() để lấy dữ liệu ra ở cùng một đầu là đỉnh của ngăn xếp. Một số hàm khác là isEmptyStack(), top().

+ Cơ chế hoạt động: Ngăn xếp hoạt động theo cơ chế “vào sau, ra trước” (LIFO).

- GV chuyển sang nội dung Thực hành làm quen với phần mềm GanttProject.

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.

- Các thao tác cơ bản trên dữ liệu ngăn xếp:

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 đọc, trao đổi và thảo luận theo nhóm đôi tìm hiểu nội dung mục 2 SGK tr.7 – 8, trả lời các câu hỏi sau:

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

Hình 1.3. Mô hình hàng đợi

+ Hãy ghép nối các nội dung cột A với cột B để có kết quả đúng nhất.

- GV yêu cầu HS đọc hiểu Ví dụ 1, 2 tr.8 SGK.

- 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 Củng cố tr.8 SGK:

Câu 1. Hãy chỉ ra những điểm giống và khác nhau giữa ngăn xếp và hàng đợi.

Câu 2. 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,2); enqueue(Q,10); dequeue(Q); enqueue(Q,1); dequeue(Q).

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

- HS tìm hiểu nội dung mục 2 SGK tr. 7 – 8 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ố tr.8 SGK:

Câu 1.

Câu 2. Trong hàng đợi Q có giá trị 1.

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

+ Đặc điểm: Hàng đợi (queue) thuộc kiểu dữ liệu tuyến tính có các hàm cơ bản: hàm enqueue() để đưa dữ liệu vào ở đuôi hàng đợi và hàm dequeue() để lấy dữ liệu ra ở đầu hàng đợi. Một số hàm khác là isEmptyQueue(), front().

+ Cơ chế hoạt động: Hàng đợi hoạt động theo cơ chế “vào trước, ra trước” (FIFO).

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ác thao tác cơ bản trên dữ liệu hàng đợi:

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 – KẾT NỐI TRI THỨC

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

A. PHẦN TRẮC NGHIỆM

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.

Câu 6. Để đưa phần tử 6 vào đỉnh ngăn xếp S, ta sử dụng lệnh nào sau đây?

A. push(6, S).

B. push(S, 6).

C. pop(S, 6).

D. top(6, S).

Câu 7. Phát biểu nào sau đây sai khi nói về mô hình dữ liệu hàng đợi?

A. Hàng đợi hoạt động theo cơ chế FIFO.                          

B. Hàng đợi thuộc kiểu dữ liệu tuyến tính.                       

C. Hàng đợi 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 hàng đợi.

D. Hàm isEmptyQueue(Q) sẽ trả về True nếu Q rỗng, ngược lại trả về False.

B. PHẦN TỰ LUẬN (Luyện tập SGK tr.8)

Câu 1. Cho trước một dãy số, nếu đưa các số này lần lượt từ trái qua phải vào một ngăn xếp, sau đó lại lấy các số này ra từ ngăn xếp và xếp theo thứ tự lấy ra cũng từ trái qua phải, thì sẽ thu được dãy số mới như thế nào?

Câu 2. Giả sử cho một dãy các số, ví dụ 2, 5, 1, 0, 10, các số này lần lượt được kiểm tra, nếu là số chẵn sẽ được đưa vào hàng đợi Q, nếu là số lẻ thì đưa vào ngăn xếp S. Sau đó lần lượt lấy tất cả các số từ S và in ra màn hình. Hỏi các số được in ra màn hình lần lượt là các số nào?

………………………………………………...

Câu 1

Câu 2

Câu 3

Câu 4

Câu 5

Câu 6

Câu 7

C

B

D

C

A

B

C