Chủ đề Fcs : Giải quyết vấn đề với sự trợ giúp của máy tính – Kĩ thuật lập trình – Bài 15. Cấu trúc dữ liệu danh sách liên kết và ứng dụng – sách giáo khoa trang 146 lớp 11 Khoa học máy tính – Cánh Diều, mời các em tham khảo cùng Bumbii.
Chủ đề Fcs : Giải quyết vấn đề với sự trợ giúp của máy tính – Bài 15. Cấu trúc dữ liệu danh sách liên kết và ứng dụng
KHỞI ĐỘNG
Em hãy nêu nhược điểm của danh sách mảng?
Lời giải:
Nhược điểm của danh sách mảng: Không thể thay đổi kích thước của mảng khi chương trình đang thực hiện.
LUYỆN TẬP
Dựa trên hình minh hoạ, mô tả các bước thực hiện các phép toán sau của danh sách liên kết để minh hoạ chúng đều có thời gian là O(1).
a) Thêm nút vào cuối danh sánh, thêm nút vào giữa danh sách.
b) Gỡ bỏ nút ở cuối danh sánh, ở đầu danh sách.
Lời giải:
a) Thêm nút vào cuối danh sách:
- Thao tác theo 3 bước như minh hoạ ở hình Hình 2b (SGK trang 147).
- Mỗi bước là một phép gán, tức là một phép toán sơ cấp.
- Thời gian thực hiện là O(1), không phụ thuộc độ dài danh sách.
Thêm nút vào giữa danh sách:
- Thao tác theo các bước như minh hoạ ở hình Hình 2c (SGK trang 147).
- Mỗi bước là một phép gán, tức là một phép toán sơ cấp.
- Thời gian thực hiện là O(1), không phụ thuộc độ dài danh sách.
b) Gỡ bỏ nút ở đầu danh sách:
- Dựa theo hình minh hoạ ở Hình 3 (SGK trang 147) cho trường hợp gỡ bỏ nút ở giữa danh sách có thể thấy khi gỡ bỏ nút ở đầu danh sách chỉ cần gán lại Head = B.
- Thời gian thực hiện gỡ bỏ là O(1), không phụ thuộc độ dài danh sách.
Gỡ bỏ nút ở cuối danh sách:
- Dựa theo hình minh hoạ ở Hình 3 (SGK trang 147) chỉ cần gán lại Tail = C và C.next = Null.
- Thời gian thực hiện gỡ bỏ là O(1), không phụ thuộc độ dài danh sách.
VẬN DỤNG
Phân tích yêu cầu ứng dụng của một danh sách nhóm đứng đâu top N và cho biết, nếu dùng kiểu danh sách của Python để thực hiện thì:
a) Những thao tác cần làm với danh sách top N sẽ thực hiện qua các phép toán danh sách Python như thế nào?
b) Kể tên một vài phép toán danh sách của Python không cần dùng đến cho trường hợp này.
Lời giải:
Từ những phân tích trong mục 2, việc cập nhật danh sách top N sẽ cần các thao tác:
– Gỡ bỏ một số phần tử bị loại khỏi top N; các phần từ này có thể ở bất kì vị trí nào trong top N kì trước,
– Chèn thêm phần từ mới được xếp vào top N cho kì này vào đúng vị trí theo xếp hạng, có thể là bất kì vị trí nào.
a) Những thao tác cần làm với danh sách top N thực hiện được qua các phép toán danh sách Python:
- topN.pop(pos): gỡ bỏ phần tử tại vị trí pos.
- topN.remove(elem): gỡ bỏ phần tử elem.
- topN.insert(pos, elem): chèn thêm phần tử elem vào vị trí pos.
- topN.append(elem).
b) Một vài phép toán danh sách Python không cần dùng đến cho trường hợp làm danh sách top N: index(), extend().
CÂU HỎI
Câu 1. Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(1).
Lời giải:
Các phép toán danh sách liên kết có thời gian thực hiện O(1):
– Thêm nút vào bất kì chỗ nào.
– Gỡ bỏ bất kì nút nào.
Câu 2. Hãy nêu các phép toán danh sách liên kết có thời gian thực hiện O(n).
Lời giải:
Các phép toán danh sách liên kết có thời gian thực hiện O(n): Phép duyệt tìm kiếm tuần tự.
Câu 3. Nếu muốn truy cập nút chứa dữ liệu X thì phải làm gì? Ước lượng thời gian thực hiện.
Lời giải:
Để truy cập phần tử chứa dữ liệu X thì phải tìm kiếm tuần tự từ đầu danh sách. Độ phức tạp thời gian là O(n).
Xem các bài giải khác: Giải Bài Tập Sách Giáo Khoa Tin Học Lớp 11 Khoa Học Máy Tính – Cánh Diều
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
