Anonymous
0
0
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
- asked 6 months agoVotes
0Answers
0Views
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.