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

Trả lời Câu Fcs44 trang 65 SBT Tin học 11 sách Cánh diều hay nhất, chi tiết sẽ giúp học sinh dễ dàng làm bài tập Tin học 11.

1 187 18/10/2023


Giải SBT 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âu Fcs44 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.

1 187 18/10/2023


Xem thêm các chương trình khác: