Câu hỏi:
13/07/2024 177
Thiết lập hàng đợi và các thao tác cơ bản với hàng đợi từ mảng T
Câu hỏi trong đề:
Giải chuyên đề Tin 12 KNTT Bài 4: Kiểu dữ liệu hàng đợi có đáp án !!
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Thiết lập hàng đợi và các thao tác cơ bản với hàng đợi từ mảng T như sâu:
- Để thiết lập dữ liệu hàng đợi từ mảng T cho trước cần có thêm biến backldx mô tả chỉ số của phần tử đuôi của hàng đợi. Ban đầu thiết lập backldx = -1 tương ứng với hàng đợi rỗng.
- Cần viết thêm hàm isFullQueue(Q) kiểm tra xem hàng đợi đã đầy chưa. Hàm trả về True nếu hàng đợi Q đã đầy (backIdx = N-1), ngược lại trả về False.
Để thiết lập hàng đợi từ mảng TTT và thực hiện các thao tác cơ bản với hàng đợi, ta có thể làm như sau:
- Khởi tạo hàng đợi từ mảng TTT.
- Thiết lập biến backIdx để theo dõi chỉ số của phần tử đuôi của hàng đợi.
- Viết các hàm kiểm tra hàng đợi có đầy không, thêm phần tử vào hàng đợi, và loại bỏ phần tử khỏi hàng đợi.
Hướng dẫn chương trình ghi mã nguồn chi tiết trong Python:
class Queue:
def __init__(self, N):
self.queue = [None] * N # Khởi tạo mảng với kích thước N
self.N = N # Lưu trữ kích thước của hàng đợi
self.backIdx = -1 # Khởi tạo chỉ số phần tử đuôi của hàng đợi
def isFullQueue(self):
return self.backIdx == self.N - 1
def isEmptyQueue(self):
return self.backIdx == -1
def enqueue(self, value):
if self.isFullQueue():
print("Queue is full. Cannot enqueue.")
else:
self.backIdx += 1
self.queue[self.backIdx] = value
def dequeue(self):
if self.isEmptyQueue():
print("Queue is empty. Cannot dequeue.")
return None
else:
value = self.queue[0]
for i in range(1, self.backIdx + 1):
self.queue[i - 1] = self.queue[i]
self.queue[self.backIdx] = None # Xóa phần tử cuối cùng
self.backIdx -= 1
return value
def front(self):
if self.isEmptyQueue():
print("Queue is empty. No front element.")
return None
else:
return self.queue[0]
def rear(self):
if self.isEmptyQueue():
print("Queue is empty. No rear element.")
return None
else:
return self.queue[self.backIdx]
def length(self):
return self.backIdx + 1
def display(self):
if self.isEmptyQueue():
print("Queue is empty.")
else:
print("Queue contents:", end=" ")
for i in range(self.backIdx + 1):
print(self.queue[i], end=" ")
print()
# Khởi tạo mảng T
T = [1, 2, 3, 4, 5]
N = len(T)
# Tạo hàng đợi từ mảng T
queue = Queue(N)
for item in T:
queue.enqueue(item)
# Hiển thị hàng đợi
queue.display()
# Ví dụ về các thao tác cơ bản
print("Dequeue:", queue.dequeue())
queue.display()
print("Enqueue 6")
queue.enqueue(6)
queue.display()
print("Front element:", queue.front())
print("Rear element:", queue.rear())
print("Queue length:", queue.length())
Ghi chú giải thích chi tiết:
Lớp Queue:
- Phương thức init: Khởi tạo hàng đợi với kích thước N và biến backIdx ban đầu là -1 để biểu diễn hàng đợi rỗng.
- Phương thức isFullQueue: Kiểm tra xem hàng đợi đã đầy chưa bằng cách so sánh backIdx với N-1.
- Phương thức isEmptyQueue: Kiểm tra xem hàng đợi có rỗng không bằng cách kiểm tra backIdx có bằng -1 hay không.
- Phương thức enqueue: Thêm một phần tử vào cuối hàng đợi nếu hàng đợi chưa đầy.
- Phương thức dequeue: Loại bỏ phần tử đầu tiên của hàng đợi nếu hàng đợi không rỗng. Các phần tử còn lại sẽ được dịch chuyển lên một vị trí.
- Phương thức front: Trả về phần tử đầu tiên của hàng đợi.
- Phương thức rear: Trả về phần tử cuối cùng của hàng đợi.
- Phương thức length: Trả về số lượng phần tử hiện có trong hàng đợi.
- Phương thức display: Hiển thị các phần tử trong hàng đợi.
Nhà sách VIETJACK:
Sổ tay lí thuyết trọng tâm Địa Lí 12 VietJack - Sách 2025 theo chương trình mới cho 2k7
Đã bán 1,7k
₫ 36.000
₫ 18.000
Sổ tay lí thuyết trọng tâm Lịch Sử 12 VietJack - Sách 2025 theo chương trình mới cho 2k7
Đã bán 769
₫ 36.000
₫ 18.000
Combo - Sổ tay Lý thuyết trọng tâm lớp 12 các môn Toán, Lí, Hóa, Văn, Sử, Địa, KTPL
Đã bán 1,5k
₫ 70.000
₫ 36.000
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi được cài đặt bằng danh sách (kiểu list của Python).
Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi được cài đặt bằng danh sách (kiểu list của Python).
Xem đáp án »
13/07/2024
226
Câu 2:
Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n), với n là độ dài của hàng đợi hiện thời.
Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n), với n là độ dài của hàng đợi hiện thời.
Xem đáp án »
13/07/2024
219
Câu 3:
Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết chỉ số của các phản tử tại đầu (front) và đuôi (rear). So sánh các chỉ số này với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp (cũng được cài đặt bằng danh sách).
Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết chỉ số của các phản tử tại đầu (front) và đuôi (rear). So sánh các chỉ số này với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp (cũng được cài đặt bằng danh sách).
Xem đáp án »
13/07/2024
209
Câu 5:
Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết cách tính số phần tử của hàng đợi này.
Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết cách tính số phần tử của hàng đợi này.
Xem đáp án »
13/07/2024
178
Câu 6:
Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn hàng đợi bằng mảng một chiều. Em hãy trả lời các câu hỏi sau:
1. Có thể biểu diễn hàng đợi bằng mảng một chiều được không?
2. Cần có các biến nào để thực hiện các phép toán thêm vào và lấy ra?
Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn hàng đợi bằng mảng một chiều. Em hãy trả lời các câu hỏi sau:
1. Có thể biểu diễn hàng đợi bằng mảng một chiều được không?
2. Cần có các biến nào để thực hiện các phép toán thêm vào và lấy ra?
Xem đáp án »
13/07/2024
170
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 18 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 16 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 21 có đáp án
-
Trắc nghiệm Tin học 12 KNTT Bài 17: Các mức ưu tiên của bộ chọn
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 20 có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận