Giải Chuyên đề Tin học 12 Chân trời sáng tạo bài 1: Hàng đợi
Bài 1: Hàng đợi
- Khởi động trang 5 Chuyên đề Tin 12 Chân trời
- Câu hỏi 1 trang 7 Chuyên đề Tin 12 Chân trời
- Câu hỏi 2 trang 7 Chuyên đề Tin 12 Chân trời
- Câu hỏi 3 trang 7 Chuyên đề Tin 12 Chân trời
- Câu hỏi 4 trang 7 Chuyên đề Tin 12 Chân trời
- Câu hỏi 1 trang 8 Chuyên đề Tin 12 Chân trời
- Câu hỏi 2 trang 8 Chuyên đề Tin 12 Chân trời
- Luyện tập 1 trang 9 Chuyên đề Tin 12 Chân trời
- Luyện tập 2 trang 9 Chuyên đề Tin 12 Chân trời
- Vận dụng 1 trang 9 Chuyên đề Tin 12 Chân trời
- Vận dụng 2 trang 9 Chuyên đề Tin 12 Chân trời
- Vận dụng 3 trang 9 Chuyên đề Tin 12 Chân trời
Giải Chuyên đề Tin học 12 Hàng đợi được VnDoc.com sưu tầm và xin gửi tới bạn đọc cùng tham khảo. Mời các bạn cùng tham khảo thêm tại mục Tin học 12 Chân trời sáng tạo.
Khởi động trang 5 Chuyên đề Tin 12 Chân trời
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?
Lời giải:
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 “vào trước ra trước, được đặt tên là “hàng đợi” (queue).
Câu hỏi 1 trang 7 Chuyên đề Tin 12 Chân trời
Cho Hình 4, biểu diễn một hàng đợi, hãy cho biết:
a) Phần tử đầu hàng đợi, phần tử cuối hàng đợi.
b) Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử nào?
c) Sau khi thêm vào phần tử k vào thì phần tử cuối hàng đợi là phần tử nào?
Lời giải:
Cho Hình 4, biểu diễn một hàng đợi, gồm có:
a) Phần tử đầu hàng đợi là m, phần tử cuối hàng đợi là x.
b) Sau khi lấy ra một phần tử, thì phần tử đầu hàng đợi là phần tử tiếp ngay sau nó. Ví dụ lấy ra phần tử m, thì phần tử đầu hàng đợi sẽ là +.
c) Sau khi thêm vào phần tử k vào thì phần tử cuối hàng đợi là phần tử k.
Câu hỏi 2 trang 7 Chuyên đề Tin 12 Chân trời
Cho hàng đợi rỗng, hãy vẽ hình minh hoạ từng bước thực hiện các thao tác sau: enqueue (1), enqueue (3), enqueue (5), dequeue (), dequeue (), enqueue (7).
Lời giải:
Câu hỏi 3 trang 7 Chuyên đề Tin 12 Chân trời
Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng 1 chiều là gì?
Lời giải:
Các thông tin cần thiết để biểu diễn hàng đợi bằng mảng 1 chiều là:
Hàng đợi là một dãy các phần tử. Do đó, em có thể dùng mảng 1 chiều để biểu diễn hàng đợi. Phép thêm vào (enqueue) được thực hiện ở đầu rear và phép lấy ra (dequeue) được thực hiện ở đầu font. Phần đầu của hàng đợi được
Câu hỏi 4 trang 7 Chuyên đề Tin 12 Chân trời
Với hàng đợi ở Hình 5, hãy vẽ hình khi thực hiện liên tục các thao tác: thêm vào 0, lấy ra, lấy ra.
Lời giải:
Với hàng đợi ở Hình 5, hãy vẽ hình khi thực hiện liên tục các thao tác: thêm vào 0, lấy ra, lấy ra.
Hàng đợi ban đầu:
| 40 | 20 | 30 | 10 | 60 | 50 | 70 |
Biểu diễn bằng mảng một chiều:
| 40 | 20 | 30 | 10 | 60 | 50 | 70 |
0 1 2 3 4 5 6
Thêm vào 0 (enqueue(0)):
| 40 | 20 | 30 | 10 | 60 | 50 | 70 | 0 |
Biểu diễn bằng mảng một chiều:
| 40 | 20 | 30 | 10 | 60 | 50 | 70 | 0 |
0 1 2 3 4 5 6 7
Lấy ra (dequeue()):
Lấy ra phần tử đầu tiên (40).
| 20 | 30 | 10 | 60 | 50 | 70 | 0 |
Biểu diễn bằng mảng một chiều:
| 20 | 30 | 10 | 60 | 50 | 70 | 0 |
0 1 2 3 4 5 6
Lấy ra (dequeue()):
Lấy ra phần tử tiếp theo (20).
| 30 | 10 | 60 | 50 | 70 | 0 |
Biểu diễn bằng mảng một chiều:
| 30 | 10 | 60 | 50 | 70 | 0 |
0 1 2 3 4 5
Câu hỏi 1 trang 8 Chuyên đề Tin 12 Chân trời
Tại sao không cần sử dụng các chỉ số front, rear khi dùng kiểu list để biểu diễn hàng đợi trong Python?
Lời giải:
Không cần sử dụng các chỉ số front, rear khi dùng kiểu list để biểu diễn hàng đợi trong Python vì:
- Việc sử dụng danh sách giúp đơn giản hóa việc quản lý hàng đợi vì không cần phải theo dõi và cập nhật các chỉ số front và rear. Python tự động quản lý các chỉ số này cho bạn khi bạn thêm hoặc lấy phần tử khỏi danh sách.
- Python cung cấp các phương thức append() để thêm phần tử vào cuối danh sách và pop(0) để lấy phần tử từ đầu danh sách. Những phương thức này trực tiếp thực hiện các thao tác tương ứng mà không cần chỉ số riêng biệt.
- Danh sách trong Python có tính linh hoạt cao và tự động điều chỉnh kích thước khi thêm hoặc bớt phần tử. Điều này loại bỏ sự cần thiết phải kiểm tra và điều chỉnh các chỉ số như front và rear để đảm bảo rằng hàng đợi không bị tràn hoặc rỗng.
Câu hỏi 2 trang 8 Chuyên đề Tin 12 Chân trời
Theo em, có cách nào kiểm tra hàng đợi queue là rỗng mà không dùng hàm len (queue)?
Lời giải:
Có ba phương pháp sau đều giúp kiểm tra hàng đợi có rỗng hay không mà không cần sử dụng hàm len(queue). Tuy nhiên, phương pháp sử dụng boolean (not queue) là ngắn gọn và dễ hiểu nhất.
a). Sử dụng phép kiểm tra boolean: Danh sách rỗng trong Python sẽ trả về giá trị boolean là False, trong khi danh sách không rỗng sẽ trả về True. Do đó, bạn có thể kiểm tra hàng đợi bằng cách sử dụng điều kiện not.
if not queue:
print("Hàng đợi rỗng")
else:
print("Hàng đợi không rỗng")
b). So sánh trực tiếp với danh sách rỗng: có thể so sánh trực tiếp hàng đợi với danh sách rỗng []. Nếu chúng bằng nhau, nghĩa là hàng đợi đang rỗng.
if queue == []:
print("Hàng đợi rỗng")
else:
print("Hàng đợi không rỗng")
c). Sử dụng try-except để kiểm tra việc lấy phần tử đầu tiên: có thể thử lấy phần tử đầu tiên của hàng đợi bằng queue[0] và bắt lỗi nếu hàng đợi rỗng.
try:
first_element = queue[0]
print("Hàng đợi không rỗng")
except IndexError:
print("Hàng đợi rỗng")
Luyện tập 1 trang 9 Chuyên đề Tin 12 Chân trời
Trong Python, khi sử dụng kiểu list để biểu diễn hàng đợi. Hãy cho biết:
a) Chỉ số của phần tử đầu.
b) Chỉ số của phần tử cuối.
Lời giải:
Trong Python, khi sử dụng kiểu list để biểu diễn hàng đợi.
a) Chỉ số của phần tử đầu: Chỉ số của phần tử đầu tiên luôn là 0
b) Chỉ số của phần tử cuối: Chỉ số của phần tử cuối cùng là len(queue) - 1
Luyện tập 2 trang 9 Chuyên đề Tin 12 Chân trời
Theo em, thứ tự thực hiện phép toán enqueue với các giá trị thích hợp để kết quả là một hàng đợi trong Hình 5 là những bước nào?
Lời giải:
Theo em, thứ tự thực hiện phép toán enqueue với các giá trị thích hợp để kết quả là một hàng đợi trong Hình 5 là những bước sau:
1. Bước 1: enqueue(40): | 40 |
2. Bước 2: enqueue(20): | 40 | 20 |
3. Bước 3: enqueue(30):| 40 | 20 | 30 |
4. Bước 4: enqueue(10): | 40 | 20 | 30 | 10 |
5. Bước 5: enqueue(60): | 40 | 20 | 30 | 10 | 60 |
6. Bước 6: enqueue(50): | 40 | 20 | 30 | 10 | 60 | 50 |
7. Bước 7: enqueue(70):| 40 | 20 | 30 | 10 | 60 | 50 | 70 |
Vận dụng 1 trang 9 Chuyên đề Tin 12 Chân trời
Các phần tử trong hàng đợi biểu diễn bằng 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:
|
“Một” |
“Hai” |
“Ba” |
“Bốn” |
Sau đó sử dụng các hàm enqueue(), dequeue() để hang đợi có kết quả là:
|
“Bốn” |
“Ba” |
“Hai” |
“Một” |
“Không” |
Lời giải:
Các phần tử trong hàng đợi biểu diễn bằng kiểu list trong Python có thể thuộc kiểu chuỗi. Ta có thể sử dụng các hàm initQueue(), enqueue() để tạo hàng đợi có các phần tử như sau:
- Khởi tạo hàng đợi với các phần tử "Một", "Hai", "Ba", "Bốn".
- Sử dụng các hàm enqueue() và dequeue() để có kết quả là "Bốn", "Ba", "Hai", "Một", "Không".
Code như sau:
# Khởi tạo hàng đợi rỗng
def initQueue():
return []
# Thêm phần tử vào hàng đợi
def enqueue(queue, item):
queue.append(item)
# Lấy phần tử ra khỏi hàng đợi
def dequeue(queue):
if len(queue) > 0:
return queue.pop(0)
else:
return None
# Khởi tạo hàng đợi và thêm các phần tử ban đầu
queue = initQueue()
enqueue(queue, "Một")
enqueue(queue, "Hai")
enqueue(queue, "Ba")
enqueue(queue, "Bốn")
print("Hàng đợi sau khi khởi tạo:")
print(queue)
# Sử dụng các thao tác enqueue và dequeue để đạt kết quả yêu cầu
# Lấy ra các phần tử để đảo thứ tự
first = dequeue(queue)
second = dequeue(queue)
third = dequeue(queue)
fourth = dequeue(queue)
# Thêm lại các phần tử theo thứ tự đảo ngược
enqueue(queue, fourth)
enqueue(queue, third)
enqueue(queue, second)
enqueue(queue, first)
# Thêm phần tử "Không"
enqueue(queue, "Không")
print("Hàng đợi sau khi thực hiện các thao tác:")
print(queue)
Kết quả của mã trên sẽ là:
Hàng đợi sau khi khởi tạo:
['Một', 'Hai', 'Ba', 'Bốn']
Hàng đợi sau khi thực hiện các thao tác:
['Bốn', 'Ba', 'Hai', 'Một', 'Không']
Giải thích:
initQueue() khởi tạo hàng đợi rỗng.
enqueue(queue, item) thêm một phần tử vào cuối hàng đợi.
dequeue(queue) lấy ra và trả về phần tử đầu tiên trong hàng đợi.
Vận dụng 2 trang 9 Chuyên đề Tin 12 Chân trời
Theo em, có thể dùng danh sách liên kết để biểu diễn hàng đợi hay không?
Lời giải:
Theo em, có thể dùng danh sách liên kết để biểu diễn hàng đợi. Trong danh sách liên kết, mỗi phần tử trong hàng đợi được biểu diễn bởi một nút (node), và mỗi nút sẽ chứa hai thông tin chính là giá trị của phần tử và một con trỏ (hoặc tham chiếu) đến phần tử tiếp theo trong hàng đợi. Ưu điểm của nó như sau:
- Không có giới hạn về kích thước của hàng đợi, vì bạn có thể cấp phát bộ nhớ động cho từng nút.
- Thêm và xóa phần tử ở đầu (enqueue và dequeue) có thể thực hiện nhanh chóng với độ phức tạp thời gian là O(1).
Vận dụng 3 trang 9 Chuyên đề Tin 12 Chân trời
Tạo tệp queue py chứa các hàm enqueue(), dequeue(), front(), rear(), isEmptyQueue() của hàng đợi. Sau đó:
- Khởi tạo hàng đọi rồng han trởi sáng tạo
- Thực hiện các hàm enqueue() với giá trị thích hợp để hàng đợi có kết quả như Hình 6a.
- Thực hiện các hàm enqueue(), dequeue() với các giá trị thích hợp để hàng đợi có kết quả như Hình 6b.
Lời giải:
1. Tạo tệp queue py chứa các hàm enqueue(), dequeue(), front(), rear(), isEmptyQueue() của hàng đợi.
# queue.py
class Queue:
def __init__(self):
self.items = []
def isEmptyQueue(self):
return self.items == []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.isEmptyQueue():
return self.items.pop(0)
else:
raise Exception("Queue is empty")
def front(self):
if not self.isEmptyQueue():
return self.items[0]
else:
raise Exception("Queue is empty")
def rear(self):
if not self.isEmptyQueue():
return self.items[-1]
else:
raise Exception("Queue is empty")
2. Khởi tạo hàng đợi rỗng.
- Khởi tạo hàng đợi rỗng.
3. Thực hiện các hàm enqueue() với giá trị thích hợp để hàng đợi có kết quả như Hình 6a.
- Thực hiện các hàm enqueue() để thêm các giá trị thích hợp.
4. Thực hiện các hàm enqueue(), dequeue() với các giá trị thích hợp để hàng đợi có kết quả như Hình 6b.
- Tiếp tục sử dụng các hàm enqueue() và dequeue() để thêm và lấy ra các giá trị thích hợp.
Code như sâu:
# Sử dụng tệp queue.py để thực hiện yêu cầu
from queue import Queue
# Khởi tạo hàng đợi
q = Queue()
# Thực hiện các hàm enqueue để có kết quả như Hình 6a
q.enqueue(30)
q.enqueue(20)
q.enqueue(10)
q.enqueue(50)
q.enqueue(40)
q.enqueue(60)
print("Hình 6a:")
print("|", end=" ")
for i in range(6):
print(q.items[i], end=" | ")
print()
# Thực hiện thêm và lấy ra các phần tử để có kết quả như Hình 6b
q.enqueue(0)
q.enqueue(80)
q.enqueue(70)
q.dequeue()
q.dequeue()
q.enqueue(90)
q.enqueue(100)
print("Hình 6b:")
print("|", end=" ")
for item in q.items:
print(item, end=" | ")
print()
Kết quả khi chạy mã trên sẽ là:
Hình 6a:
| 30 | 20 | 10 | 50 | 40 | 60 |
Hình 6b:
| 10 | 50 | 40 | 60 | 0 | 80 | 70 | 30 | 90 | 100 |
Trong đó: Hàng đợi ban đầu (Hình 6a) được thêm từng phần tử theo thứ tự. Hàng đợi sau khi thực hiện các phép enqueue và dequeue (Hình 6b) đạt được kết quả yêu cầu.
