Câu hỏi:

25/09/2023 562

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?

Xem lời giải

Câu hỏi trong đề: Giải SBT Tin học 11 Cánh diều Bài 15. Cấu trúc dữ liệu sanh sách liên kế và ứng dụng có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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

Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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

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ụ:

Xem đáp án

Lời giải

Hướng dẫn: Có thể áp dụng danh sách liên kết vòng để giải quyết bài toán trên. Thao tác xoá phần tử được vận dụng nhiều.

Chương trình mẫu:

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,..., . (ảnh 2)

Câu 2

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?

Xem đáp án

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

Câu 3

Để 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, Ti tiến hành kiểm thử, tuy nhiên lại không tự tin 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:

class Node:

def

init self.data self.next

(self, data):

= data

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:

def rotate (head, k) -> Node: # Hoàn thiện phần thân hàm

def reverseList (head) -> Node: # Hoàn thiện phần thân hàm

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Câu 4

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:

• Dòng đầu tiên chứa hai số nguyên dương n, m (n, m ≤ 10).

• m dòng tiếp theo, mỗi dòng chứa hai số nguyên dương a, vi

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.

Xem đáp án

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem thêm các câu hỏi khác »

Hỏi bài tập

Đăng ký gói thi VIP

VIP +1 tháng ( 199,000 VNĐ )

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
Tải xuống đề thi [DOCX] với đầy đủ đáp án
Xem bài giảng đính kèm củng cố thêm kiến thức
Bao gồm tất cả các bậc từ Tiểu học đến Đại học
Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 tháng ( 299,000 VNĐ )

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
Tải xuống đề thi [DOCX] với đầy đủ đáp án
Xem bài giảng đính kèm củng cố thêm kiến thức
Bao gồm tất cả các bậc từ Tiểu học đến Đại học
Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 tháng ( 399,000 VNĐ )

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
Tải xuống đề thi [DOCX] với đầy đủ đáp án
Xem bài giảng đính kèm củng cố thêm kiến thức
Bao gồm tất cả các bậc từ Tiểu học đến Đại học
Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 tháng ( 499,000 VNĐ )

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
Tải xuống đề thi [DOCX] với đầy đủ đáp án
Xem bài giảng đính kèm củng cố thêm kiến thức
Bao gồm tất cả các bậc từ Tiểu học đến Đại học
Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

Bình luận

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?

VIP +1 tháng ( 199,000 VNĐ )

VIP +3 tháng ( 299,000 VNĐ )

VIP +6 tháng ( 399,000 VNĐ )

VIP +12 tháng ( 499,000 VNĐ )

🔥 Đề thi HOT:

CHỌN BỘ SÁCH BẠN MUỐN XEM

Đăng ký

Đăng nhập

Quên mật khẩu