Chuyên đề Tin học 12 Bài 1 (Kết nối tri thức): Mô hình dữ liệu ngăn xếp và hàng đợi

Giải Chuyên đề Tin học 12 Bài 1: Mô hình dữ liệu ngăn xếp và hàng đợi

Khởi động trang 5 Chuyên đề Tin học 12: 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ần đượ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?

Lời giải:

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

b) Người gần cây rút tiền nhất 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 người trước đó rút được tiền.

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

Hoạt động 1 trang 5 Chuyên đề Tin học 12: Tìm hiểu mô hình dữ liệu ngăn xếp

Đọc, trao đổi và thảo luận để hiểu về mô hình dữ liệu ngăn xếp và cơ chế hoạt động “vào sau, ra trước” (LIFO-Last in, First Out) của mô hình dữ liệu này.

Lời giải:

Mô hình dữ liệu ngăn xếp và cơ chế hoạt động “vào sau, ra trước” (LIFO-Last in, First Out) của mô hình dữ liệu: Có thể hiểu ngăn xếp là đối tượng dữ liệu, trong đó việc đưa dữ liệu vào và lấy dữ liệu ra ở cùng 1 đầu, theo cơ chế hoạt động LIFO. Thao tác đưa dữ liệu vào là push và lấy dữ liệu ra gọi 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.

Câu hỏi 1 trang 7 Chuyên đề Tin học 12: Muốn lấy ra phần tử ở đáy của ngăn xếp thì phải làm thế nào?

Lời giải:

Muốn lấy ra phần tử ở đáy của ngăn xếp thì phải thực hiện cơ chế hoạt động “vào sau, ra trước” (LIFO-Last in, First Out).

Câu hỏi 2 trang 7 Chuyên đề Tin học 12: 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);

Lời giải:

Push(s,1): Đưa phần tử 1 vào đỉnh ngăn xếp s.

push(s,5): Đưa phần tử 5 vào đỉnh ngăn xếp s.

pop(s): Lấy ra một phần tử từ đỉnh của ngăn xếp S và trả về phần tử này.

push(s,10): Đưa phần tử 10 vào đỉnh ngăn xếp s.

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

Hoạt động 2 trang 7 Chuyên đề Tin học 12: Tìm hiểu mô hình dữ liệu hàng đợi

Đọc, trao đổi và thảo luận để hiểu về mô hình dữ liệu hàng đợi và cơ chế hoạt động “vào trước, ra trước” (FIFO-First in, First out) của mô hình dữ liệu này.

Lời giải:

Mô hình dữ liệu hàng đợi và cơ chế hoạt động “vào trước, ra trước” (FIFO-First in, First out) của mô hình dữ liệu: là đối tượng dữ liệu trong đó việc đưa dữ liệu vào tại một đầu và lấy dữ liệu ra ở đầu khác, theo cơ chế hoạt động FIFO. Hàng đợi có các thao tác đưa phần tử đư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 để đư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 (font, head) của hàng đợi.

Câu hỏi 1 trang 8 Chuyên đề Tin học 12: Hãy chỉ ra những điểm giống nhau và khác nhau giữa ngăn xếp và hàng đợi

Lời giải:

Giống nhau giữa ngăn xếp và hàng đợi: đều là kiểu dữ liệu tuyến tính, đều phải đưa dữ liệu vào và lấy dữ liệu ra.

Khác nhau:

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

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

Câu hỏi 2 trang 8 Chuyên đề Tin học 12: 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)

Lời giải:

Q=Queue(): Tạo một hàng đợi rông

Enqueue(Q,2): Đưa phần tử 2 vào vào cuối của hàng đợi Q.

Enqueue(Q,10): Đưa phần tử 10 vào vào cuối của hàng đợi Q.

Dequeue(Q): Lấy ra một phần tử tại đầu của hàng đợi Q và trả về phần tử này.

Enqueue(Q,1): Đưa phần tử 1 vào vào cuối của hàng đợi Q.

Dequeue(Q): Lấy ra một phần tử tại đầu của hàng đợi Q và trả về phần tử này.

Luyện tập 1 trang 8 Chuyên đề Tin học 12: 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?

Lời giải:

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 giống thứ tự như dãy số đã cho. Đây là kiểu hàng đợi “vào trước, ra trước”.

Luyện tập 2 trang 8 Chuyên đề Tin học 12: 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?

Lời giải:

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ố sau: 5,1,10,0,2.

Vận dụng 1 trang 8 Chuyên đề Tin học 12: 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.

Lời giải:

- Ví dụ thực tế của ngăn xếp: Chức năng Undo thường được sử dụng khi soạn thảo văn bản. Lệnh Undo giúp người sử dụng huỷ bỏ kết quả của thao tác gần nhất. Mô hình quản lí các dữ liệu Undo chính là các ngăn xếp. 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.

- Ví dụ thực tế của hàng đợi: hàng đợi của máy in. Máy in trong văn phòng thường được sử dụng cho nhiều người, trong đó mỗi người có thể đưa ra các lệnh in bất cứ lúc nào. Máy in sẽ lưu trữ các nội dung in vào một hàng đợi, nội dung nò vào trước sẽ in trước, nội dung nào vào sau sẽ in sau.

Vận dụng 2 trang 8 Chuyên đề Tin học 12: 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, 1, 2 (từ đỉnh xuống đáy).

Lời giải:

Sắp xếp các phần tử của ngăn xếp S theo thứ tự 3, 1, 2 (từ đỉnh xuống đáy):

Push(s,2); Push(s,1); Push(s,3);