Cho một danh sách liên kết đơn có giá trị các nút được sắp xếp theo thứ tự

Sách bài tập Tin học 11 Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng - Cánh diều

Câu F^cs44 trang 65 SBT Tin học 11: Cho một danh sách liên kết đơn có giá trị các nút được sắp xếp theo thứ tự không giảm (nghĩa là node.Data < node.Next.Data) và một phần tử x. Hỏi độ phức tạp để chèn một nút có giá trị là x vào danh sách liên kết sao cho không thay đổi tính chất của danh sách là bao nhiêu?

Lời giải:

Độ phức tạp là O(n) với n là số phần tử của danh sách.

Cách làm: Đầu tiên em tìm nút node mà node.Next.Data có giá trị lớn hơn hoặc bằng x hoặc node.Next rỗng, sau đó chèn node có giá trị x vào giữa

node và node.Next.

Lời giải SBT Tin 11 Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng hay khác:

• Câu F^cs43 trang 65 SBT Tin học 11: Giả sử em phải truy cập phần tử thứ k trong danh sách. Độ phức tạp thời gian để truy cập phần tử đó ....

• Câu F^cs45 trang 65 SBT Tin học 11: Bài toán Josephus được phát biểu như sau: Có n người đứng thành một vòng tròn, được đánh số thứ tự 1, 2, 3, 4 ....

• Câu F^cs46 trang 66 SBT Tin học 11: Em đang cần mô phỏng lại một mạng xã hội. Có tổng cộng n người dùng. Các người dùng được đánh số từ 1 tới n ....

• Câu F^cs47 trang 66 SBT Tin học 11: Để hiểu rõ hơn về danh sách liên kết và các thao tác trên danh sách liên kết, Tí thực hiện các thao tác thuộc hai loại sau ....