Giải chuyên đề Tin 12 Cánh diều Bài 1: Kiểu dữ liệu hàng đợi có đáp án

Một phòng máy thực hành có 50 máy tính nối mạng với một máy in duy nhất (Hình 1). Có nhiều người dùng trong phòng đều có nhu cầu in tệp dữ liệu của họ. Theo em, các tệp dữ liệu đó sẽ được in theo thứ tự mà chúng được gửi đến hàng đợi của máy in và để làm được điều đó hệ thống phải sắp xếp các tệp dữ liệu này theo nguyên tắc FIFO, tức là tệp nào được gửi đến hàng đợi in trước thì sẽ in trước.

a) Những thao tác sau cần được thực hiện để có thể lấy số 6 ra khỏi hàng đợi ở Hình 4a và vẽ hàng đợi biểu diễn bởi mảng một chiều tại thời điểm lấy xong số 6. Giá trị biến Front thay đổi thế nào so với trạng thái ở Hình 4b.

- Thực hiện thao tác dequeue (lấy ra) cho đến khi gặp số 6.

- Cập nhật giá trị biến Front sau mỗi lần dequeue.

- Hàng đợi sau khi lấy xong số 6 sẽ có dạng: -7, 12, 4, 9 và các ô trống ở đầu hàng đợi.

- Biến Front sẽ trỏ đến vị trí của số -7.

b) Vẽ hàng đợi thu được khi tiếp tục thực hiện một thao tác thêm vào số 8. Giá trị biến Back thay đổi so với Hình 4b như sau:

- Thực hiện thao tác enqueue (thêm vào) số 8 vào cuối hàng đợi.

- Cập nhật giá trị biến Back sau khi thêm.

- Hàng đợi sau khi thêm số 8 sẽ có dạng: -7, 12, 4, 9, 8 và các ô trống ở đầu và cuối hàng đợi.

- Biến Back sẽ trỏ đến vị trí mới sau số 9.

c) Tiếp tục thực hiện các thao tác lấy ra cho đến khi hàng đợi rỗng, mối quan hệ giữa giá trị biến Front và Back khi hàng đợi rỗng như sau:

- Tiếp tục thực hiện thao tác dequeue cho đến khi hàng đợi không còn phần tử nào.

- Khi hàng đợi rỗng, biến Front và Back sẽ trỏ đến cùng một vị trí, thường là vị trí đầu tiên của mảng nếu hàng đợi được triển khai theo cách này.

a)  Dấu ‘?’ trong hàm dequeue(Q) cần được thay bằng 0 để lấy phần tử đầu tiên ra khỏi hàng đợi.

b) 

- Hàng đợi queue sẽ chứa các phần tử sau khi thực hiện các thao tác enqueue: 2, 4, 6.

- Kết quả in trên màn hình sau khi chạy chương trình sẽ là phần tử đầu tiên được lấy ra khỏi hàng đợi, tức là 2.

c) Kết quả in trên màn hình sẽ là các phần tử lần lượt được lấy ra khỏi hàng đợi: 2, 4, 6. Nếu thực hiện thêm lần nữa, sẽ in ra thông báo hàng đợi rỗng.

d) Viết hàm isEmptyQueue(Q) với tham số truyền vào là hàng đợi Q. Hàm trả về giá trị True nếu hàng đợi Q đang rỗng không chứa phần tử nào, ngược lại hàm trả về giá trị False:

Chương trình Python:

def isEmptyQueue(Q):

   return len(Q) == 0

e) Đoạn chương trình ở Hình 11 kiểm tra xem hàng đợi có rỗng trước khi thực hiện thao tác dequeue. Nếu hàng đợi không rỗng, sẽ in ra phần tử được lấy ra. Nếu hàng đợi rỗng, sẽ in ra thông báo “Hàng đợi rỗng, không thể thực hiện được thao tác dequeue”.

Tại căng tin, các bạn học sinh đang xếp thành hai hàng để chờ đến lượt nhận suất ăn trưa. Đề công bằng, bác đầu bếp sẽ phát suất ăn trưa cho lần lượt từng bạn theo quy tắc: bạn đầu hàng của hàng thứ nhất, rồi đến bạn đầu hàng của hàng thứ hai. Thứ tự này lặp đi lặp lại cho đến khi một trong hai hàng không còn học sinh. Khi đó, những bạn ở hàng còn lại sẽ được tiếp tục phát theo thứ tự lần lượt từ đầu đến cuối hàng cho đến khi tất cả các học sinh đều nhận được suất ăn của mình. Em viết hàm nhan_suat_an(QI, Q2) với tham số đầu vào là hai hàng đợi Q1, Q2. Hàm thực hiện in ra màn hình tên của các học sinh một cách lần lượt theo đúng thứ tự nhận suất ăn trưa như sau:

1. Khởi tạo hàng đợi: Chuyển danh sách Q1 và Q2 thành hàng đợi deque để sử dụng các phương thức hàng đợi như popleft.

2. Duyệt qua các hàng đợi:

Sử dụng một vòng lặp while để tiếp tục duyệt cho đến khi cả hai hàng đợi đều trống.

Trong mỗi lần lặp, kiểm tra nếu queue1 không trống, lấy phần tử đầu tiên từ queue1 và thêm vào kết quả.

Tiếp theo, nếu queue2 không trống, lấy phần tử đầu tiên từ queue2 và thêm vào kết quả.

3. In kết quả:

Sau khi vòng lặp kết thúc, danh sách result chứa các tên học sinh theo thứ tự nhận suất ăn.

Sử dụng join để kết hợp các tên trong danh sách thành một chuỗi và in ra màn hình.

* Code như sau:

from collections import deque

def nhan_suat_an(Q1, Q2):

   # Chuyển đổi danh sách đầu vào thành deque để sử dụng như hàng đợi

   queue1 = deque(Q1)

   queue2 = deque(Q2)

   result = []

   # Lặp lại cho đến khi cả hai hàng đều trống

   while queue1 or queue2:

        if queue1:

            result.append(queue1.popleft())

        if queue2:

            result.append(queue2.popleft())

   # In kết quả ra màn hình

   print(", ".join(result))

# Ví dụ đầu vào

Q1 = ["Thái", "Trà", "Mai"]

Q2 = ["Đức", "Hùng", "Cường", "Bình", "Phước"]

# Gọi hàm và in kết quả

nhan_suat_an(Q1,Q2)

a) Đúng. Hàng đợi hoạt động theo nguyên tắc FIFO (First In, First Out), nghĩa là phần tử nào vào trước sẽ được ra trước.

b) Đúng. Trong một hàng đợi chuẩn, bạn chỉ có thể truy cập phần tử ở đầu hàng đợi (front) hoặc thêm phần tử vào cuối hàng đợi (rear). Bạn không thể truy cập các phần tử ở giữa trực tiếp như với mảng.

c) Sai. Khi thêm một phần tử vào hàng đợi, phần tử này sẽ được thêm vào cuối hàng đợi, không phải đầu hàng đợi.

d) Sai. Bạn chỉ có thể lấy phần tử ở đầu hàng đợi (front). Bạn không thể lấy các phần tử ở giữa hoặc cuối hàng đợi tùy ý.

e) Sai. Bạn chỉ có thể thêm phần tử vào cuối hàng đợi (rear). Bạn không thể thêm vào bất kỳ vị trí nào khác.

Vậy các câu đúng là: a, b.