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

Đỗ Thị Ngọc Ánh Ngày: 27-11-2023 Lớp 11

145

Với giải Câu F^cs44 trang 65 SBT Tin học 11 Cánh diều chi tiết trong Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập trong SBT Tin học 11. Mời các bạn đón xem:

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

Xem thêm lời giải Sách bài tập Tin học lớp 11 Cánh diều hay, chi tiết 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ử đó là bao nhiêu và tại sao?...

Câu F^cs45 trang 65 SBT Tin học 11: Bài toán Josephus được phát biểu như sau:...

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ó tổng cộng m yêu cầu kết bạn, được liệt kê theo thời gian gửi tăng dần; tất cả yêu cầu đều được đồng ý ngay tại thời điểm gửi. Với mỗi người, em cần in ra danh sách bạn bè của họ. Dữ liệu: Nhập từ thiết bị vào chuẩ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:...

Xem thêm các bài giải SBT Tin học lớp 11 Cánh diều hay, chi tiết khác: