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

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

Với giải Câu F^cs43 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^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?

Lời giải:

Vì em không có cách truy cập ngẫu nhiên tới phần tử thứ k, do đó ta buộc phải nhảy k − 1 lần bắt đầu từ phần tử đầu tiên. Vì vậy độ phức tạp là O(k).

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

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:

Bài 10, 11, 12, 13, 14: Thiết kế chương trình từ trên xuống và phương pháp mô đun hoá, Thực hành thiết kế và lập trình theo mô đun, Thực hành về thư viện các hàm tự định nghĩa