Giải SBT Tin học 11 định hướng KHMT Cánh diều bài 15 Cấu trúc dữ liệu danh sách liên kết và ứng dụng
Giải chi tiết sách bài tập SBT Tin học 11 định hướng khoa học máy tính Cánh diều bài 15 Cấu trúc dữ liệu danh sách liên kết và ứng dụng. Tech12h sẽ hướng dẫn giải tất cả câu hỏi và bài tập với cách giải nhanh và dễ hiểu nhất. Hi vọng, thông qua đó học sinh được củng cố kiến thức và nắm bài học tốt hơn.
Fcs43. 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?
Trả lời:
Vì em không có 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).
Fcs44. 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?
Trả lờ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.
Fcs45. 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,..., n. Trò chơi bắt đầu từ người thứ nhất (đánh số 1). Mọi người sẽ lần lượt đếm 1 – 2 – 1 – 2 – 1 – 2 - … khi tới lượt của mình, bất kì ai sau khi đếm được số 2 thì phải bước ra khỏi vòng tròn. Trong toán học, người ta rút ra được một số công thức để tính ra được người còn sót lại cuối cùng trong vòng tròn, với luật chơi tổng quát (đếm tới k thay vì 2). Tuy nhiên, ở đây em lại quan tâm diễn biến của trò chơi này hơn. Em hãy dùng danh sách liên kết để mô phỏng lại trò chơi trên.
Dữ liệu: Dòng duy nhất chứa số nguyên i
Kết quả: Dòng duy nhất chứa n số là số hiệu của những người chơi bị loại ra khỏi vòng tròn theo thứ tự.
Ví dụ:
Input | Output |
9 | 2 4 6 8 1 5 9 7 3 |
Trả lời:
Fcs46. Em đang cần mô phỏng lại một trang 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 đến 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:
Dòng đầu tiên chứa hai số nguyên dương n, m n,m ≤105
m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v.
Kết quả: Hiển thị ở thiết bị ra chuẩn n dòng, với mỗi dòng i (1≤i≤n) là danh sách bạn bè của người thứ i. Danh sách bạn bè được in theo thứ tự kết bạn.
Ví dụ:
Input | Output |
5 5 1 2 1 3 3 5 4 5 4 3 | 2 3 1 1 5 4 5 3 3 4 |
Trả lời:
Fcs47. Để 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:
Loại 1: “Quay” k lần: tức là Tí sẽ lấy phần tử đầu tiên của danh sách liên kết và chèn nó vào sau phần tử cuối cùng, thực hiện k lần như vậy.
Loại 2: Đảo ngược danh sách liên kết.
Sau nhiều giờ lập trình, Tí tiến hành kiểm thử, tuy nhiên lại không tự ti vào kết quả của mình. Tí nhờ bạn code để đối chiếu kết quả.
Biết rằng Tí đã cài sẵn danh sách liên kết trong một mô đun và import nó vào trong chương trình. Danh sách liên kết này đảm bảo hoạt động chính xác. Tí cũng code sẵn phần xử lý nhập vào, in ra dữ liệu. Hãy hoàn thiện hai hàm rotate (quay mảng) và reverseList (đảo ngược).
Cấu trúc nút được định nghĩa như sau:
Giả sử có một biến tên node thuộc kiểu Node tượng trưng cho một nút trong danh sách liên kết. Để lấy nút tiếp theo, ta viết node.next; để lấy ra giá trị, ta viết node.data. Để tạo ra một nút mới có giá trị là value, ta viết node = Node(value).
Hai hàm cần cài đặt được cung cấp tham số head: nút trỏ tới đầu của danh sách liên kết. Hàm trả về biến kiểu Node, trỏ tới phần tử đầu tiên của danh sách liên kết mới được thay đổi sau các truy vấn.
Cụ thể hơn, các hàm này được định nghĩa như sau:
Trả lời:
Nội dung quan tâm khác
Thêm kiến thức môn học
Giải bài tập những môn khác
Giải sgk lớp 11 KNTT
Giải sgk lớp 11 CTST
Giải sgk lớp 11 cánh diều
Giải SBT lớp 11 kết nối tri thức
Giải SBT lớp 11 chân trời sáng tạo
Giải SBT lớp 11 cánh diều
Giải chuyên đề học tập lớp 11 kết nối tri thức
Giải chuyên đề toán 11 kết nối tri thức
Giải chuyên đề ngữ văn 11 kết nối tri thức
Giải chuyên đề vật lí 11 kết nối tri thức
Giải chuyên đề hóa học 11 kết nối tri thức
Giải chuyên đề sinh học 11 kết nối tri thức
Giải chuyên đề kinh tế pháp luật 11 kết nối tri thức
Giải chuyên đề lịch sử 11 kết nối tri thức
Giải chuyên đề địa lí 11 kết nối tri thức
Giải chuyên đề mĩ thuật 11 kết nối tri thức
Giải chuyên đề âm nhạc 11 kết nối tri thức
Giải chuyên đề công nghệ chăn nuôi 11 kết nối tri thức
Giải chuyên đề công nghệ cơ khí 11 kết nối tri thức
Giải chuyên đề tin học 11 định hướng Khoa học máy tính kết nối tri thức
Giải chuyên đề tin học 11 định hướng Tin học ứng dụng kết nối tri thức
Giải chuyên đề quốc phòng an ninh 11 kết nối tri thức
Giải chuyên đề hoạt động trải nghiệm hướng nghiệp 11 kết nối tri thức
Giải chuyên đề học tập lớp 11 chân trời sáng tạo
Giải chuyên đề học tập lớp 11 cánh diều
Trắc nghiệm 11 Kết nối tri thức
Trắc nghiệm 11 Chân trời sáng tạo
Trắc nghiệm 11 Cánh diều
Bộ đề thi, đề kiểm tra lớp 11 kết nối tri thức
Đề thi Toán 11 Kết nối tri thức
Đề thi ngữ văn 11 Kết nối tri thức
Đề thi vật lí 11 Kết nối tri thức
Đề thi sinh học 11 Kết nối tri thức
Đề thi hóa học 11 Kết nối tri thức
Đề thi lịch sử 11 Kết nối tri thức
Đề thi địa lí 11 Kết nối tri thức
Đề thi kinh tế pháp luật 11 Kết nối tri thức
Đề thi công nghệ cơ khí 11 Kết nối tri thức
Đề thi công nghệ chăn nuôi 11 Kết nối tri thức
Đề thi tin học ứng dụng 11 Kết nối tri thức
Đề thi khoa học máy tính 11 Kết nối tri thức
Bộ đề thi, đề kiểm tra lớp 11 chân trời sáng tạo
Bộ đề thi, đề kiểm tra lớp 11 cánh diều
Đề thi Toán 11 Cánh diều
Đề thi ngữ văn 11 Cánh diều
Đề thi vật lí 11 Cánh diều
Đề thi sinh học 11 Cánh diều
Đề thi hóa học 11 Cánh diều
Đề thi lịch sử 11 Cánh diều
Đề thi địa lí 11 Cánh diều
Đề thi kinh tế pháp luật 11 Cánh diều
Đề thi công nghệ cơ khí 11 Cánh diều
Đề thi công nghệ chăn nuôi 11 Cánh diều
Đề thi tin học ứng dụng 11 Cánh diều
Đề thi khoa học máy tính 11 Cánh diều
Bình luận