logo

Soạn Tin học 11 Cánh Diều Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng (trang 146, 149)

Hướng dẫn Soạn Tin học 11 Cánh Diều Bài 15 trang 146, 149: Cấu trúc dữ liệu danh sách liên kết và ứng dụng ngắn gọn, hay nhất theo chương trình Sách mới.

Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

Lý thuyết Tin học 11 Cánh Diều Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

Sơ đồ tư duy Tin học 11 Cánh Diều Bài 15: Thiết kế chương trình từ trên xuống và phương pháp mô đun hóa


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). 

Trả lời:

Thời gian thực hiện của các phép toán danh sách liên kết phụ thuộc vào cách triển khai danh sách liên kết. Các phép toán danh sách liên kết có thời gian thực hiện O(1) là:

- Truy cập phần tử đầu tiên (head) và phần tử cuối cùng (tail) của danh sách liên kết: truy cập trực tiếp vào head hoặc tail của danh sách mà không cần duyệt qua toàn bộ danh sách.

- Thêm phần tử vào đầu danh sách và cuối danh sách: phép toán này sẽ tạo một phần tử mới rồi gán con trỏ next của phần tử mới thành head hoặc tail của danh sách và cập nhật lại head hoặc tail.

Xóa phần tử đầu danh sách và cuối danh sách: phép toán này sẽ xóa phần tử head hoặc tail của danh sách và cập nhật lại head hoặc tail.


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). 

Trả lời:

Các phép toán danh sách liên kết có thời gian thực hiện O(n) là:

- Tìm kiếm một phần tử: phép toán thực hiện duyệt qua từng nút của danh sách một cách tuần tự để tìm kiếm phần tử cần tìm. 

- Chèn một phần tử vào cuối danh sách: thực hiện duyệt qua từng nút của danh sách để đến cuối danh sách và thêm phần tử vào cuối danh sách. 

- Xóa một phần tử khỏi danh sách: phép toán này sẽ tìm kiếm phần tử đó trong danh sách rồi thực hiện xóa phần tử đó bằng cách điều chỉnh các liên kết giữa các nút trong danh sách. 

- Đảo ngược danh sách: thực hiện duyệt qua từng nút của danh sách, thay đổi liên kết giữa các nút để đảo ngược danh sách. 


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.

Trả lời:

- Để truy cập nút chứa dữ liệu X trong danh sách liên kết thì chúng ta phải duyệt toàn bộ các nút của danh sách từ đầu đến cuối, kiểm tra giá trị của mỗi nút để tìm nút chứa dữ liệu X. Khi đã tìm được nút chứa dữ liệu X thì chúng ta có thể thực hiện các thao tác khác với nút đó như xoá nút đó khỏi danh sách.

- Do phải duyệt toàn bộ danh sách nên thời gian thực hiện của việc truy cập nút chứa dữ liệu X là O(n), trong đó n là số lượng nút trong danh sách.

>>> Xem toàn bộ: Soạn Tin 11 Cánh diều

-------------------------------------

Trên đây Toploigiai đã cùng các bạn Soạn Tin học 11 Cánh Diều Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng trong bộ SGK Cánh Diều theo chương trình sách mới. Chúng tôi hi vọng các bạn đã có kiến thức hữu ích khi đọc bài viết này. Click vào trang chủ Toploigiai để tham khảo và chuẩn bị bài cho năm học mới nhé. Chúc các bạn học tốt!

icon-date
Xuất bản : 27/02/2023 - Cập nhật : 19/07/2023