Trắc nghiệm 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ánh diều

Đáp án: B

Giải thích: Danh sách liên kết bao gồm các nút không được lưu trữ thành một khối liên tục mà có thể nằm rải rác trong bộ nhớ.

Đáp án: D

Giải thích: Thành phần của một nút trong danh sách liên kết bao gồm Data và Next (hoặc Previous trong danh sách liên kết kép). "Address" không phải là một thành phần riêng biệt.

Đáp án: B

Giải thích: Thêm nút vào đầu danh sách liên kết có thời gian thực hiện là O(1), không phụ thuộc vào độ dài của danh sách.

Đáp án: B

Giải thích: Danh sách liên kết có lợi thế khi cần thực hiện nhiều thao tác thêm và gỡ bỏ phần tử ở bất kỳ vị trí nào trong danh sách.

Đáp án: B

Giải thích: Để gỡ bỏ một nút, cần phải thay đổi con trỏ của nút trước nó để trỏ đến nút sau nó, điều này giúp duy trì tính liên kết của danh sách.

Đáp án: B

Giải thích: Danh sách liên kết kép có cả con trỏ Next (trỏ đến nút tiếp theo) và con trỏ Prev (trỏ đến nút trước đó).

Đáp án: C

Giải thích: Danh sách liên kết cần thêm bộ nhớ để lưu trữ con trỏ Next, đây là nhược điểm so với mảng.

Đáp án: C

Giải thích: Danh sách liên kết phát huy ưu điểm trong những trường hợp mà độ dài danh sách thay đổi nhanh và nhiều trong quá trình sử dụng.

Đáp án: B

Giải thích: Phép tìm kiếm trong danh sách liên kết có độ phức tạp là O(n) vì cần phải thực hiện tìm kiếm tuần tự từ đầu danh sách.

Đáp án: B

Giải thích: Danh sách liên kết cho phép thực hiện dễ dàng các thao tác thêm và gỡ bỏ nút, điều này rất quan trọng trong việc mô hình hóa mạng lưới hoặc cấu trúc phân cấp.

a) Đúng. Thời gian thực hiện thao tác thêm và gỡ bỏ nút trong danh sách liên kết là O(1), không phụ thuộc vào độ dài của danh sách, điều này giúp tăng hiệu suất trong một số tình huống.

b) Sai. Danh sách liên kết không lưu trữ các nút thành một khối liên tục mà có thể nằm rải rác trong bộ nhớ, đây là điểm khác biệt chính giữa danh sách liên kết và mảng.

c) Đúng. Trong danh sách liên kết, các nút không có chỉ số như trong mảng. Thay vào đó, chúng được truy cập thông qua các con trỏ, cho phép linh hoạt hơn trong việc thêm và gỡ bỏ nút.

d) Sai. Danh sách liên kết thường chiếm nhiều bộ nhớ hơn so với mảng do cần lưu trữ thêm thông tin về con trỏ.

a) Đúng. Danh sách liên kết rất phù hợp để mô hình hóa các cấu trúc như mạng lưới hoặc cây phân cấp do tính linh hoạt trong việc thay đổi kích thước và cấu trúc của nó.

b) Sai. Danh sách liên kết hoàn toàn có thể thực hiện thao tác thêm phần tử vào giữa danh sách thông qua việc thay đổi các con trỏ.

c) Đúng. Để cập nhật danh sách top N, cần thực hiện các thao tác như gỡ bỏ một số phần tử tại các vị trí bất kỳ và chèn thêm phần tử vào vị trí bất kỳ, điều này dễ dàng thực hiện trong danh sách liên kết.

d) Sai. Một trong những ưu điểm của danh sách liên kết là nó có khả năng thay đổi độ dài một cách linh hoạt mà không gặp phải các giới hạn như trong mảng.

Đáp án: Danh sách liên kết cho phép thực hiện thao tác thêm và gỡ bỏ nút với thời gian O(1), không phụ thuộc vào độ dài của danh sách.

Giải thích: Khi thêm một nút mới vào danh sách liên kết, ta chỉ cần cập nhật các con trỏ mà không cần di chuyển các nút khác, điều này giúp tiết kiệm thời gian. Ngược lại, trong mảng, việc thêm hoặc gỡ bỏ một nút có thể yêu cầu di chuyển nhiều phần tử để duy trì cấu trúc, dẫn đến độ phức tạp lớn hơn.

Đáp án: Danh sách liên kết cho phép linh hoạt trong việc gỡ bỏ và chèn thêm phần tử tại bất kỳ vị trí nào trong danh sách.

Giải thích: Trong một danh sách top N, các bài hát có thể được thêm, gỡ bỏ hoặc cập nhật thường xuyên. Danh sách liên kết cho phép thực hiện các thao tác này một cách dễ dàng và hiệu quả mà không cần di chuyển nhiều phần tử, điều này rất quan trọng khi danh sách cần cập nhật nhanh chóng.

Đáp án: Một trong những nhược điểm của danh sách liên kết là cần thêm bộ nhớ để lưu trữ con trỏ cho mỗi nút.

Giải thích: Mỗi nút trong danh sách liên kết không chỉ lưu trữ dữ liệu mà còn cần bộ nhớ cho con trỏ trỏ đến nút tiếp theo. Điều này dẫn đến việc tiêu tốn thêm bộ nhớ so với mảng, nơi mà các phần tử được lưu trữ liên tục và không cần thêm bộ nhớ cho con trỏ. Do đó, trong các trường hợp mà bộ nhớ hạn chế, mảng có thể là lựa chọn tốt hơn.