Trắc nghiệm Cánh diều Tin học 11 KHMT Giải 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

1. Việc chèn một nút mới vào giữa danh sách liên kết đơn đòi hỏi bao nhiêu thao tác cập nhật con trỏ (pointer updates) trong trường hợp tốt nhất (biết trước nút cần chèn vào sau)?

A. 1.

B. 2.

C. 3.

D. 4.

2. Cấu trúc dữ liệu double-ended queue (deque) có thể được triển khai hiệu quả bằng loại danh sách liên kết nào?

A. Danh sách liên kết đơn.

B. Danh sách liên kết vòng.

C. Danh sách liên kết kép.

D. Cả danh sách liên kết đơn và kép đều có thể.

3. Trong một danh sách liên kết kép, nếu ta có con trỏ đến một nút bất kỳ và muốn xóa nút đó, ta cần cập nhật bao nhiêu con trỏ?

A. 1.

B. 2.

C. 3.

D. 4.

4. Danh sách liên kết được ứng dụng để triển khai cấu trúc dữ liệu nào sau đây một cách hiệu quả?

A. Hàng đợi ưu tiên (Priority Queue).

B. Ngăn xếp (Stack).

C. Cây tìm kiếm nhị phân (Binary Search Tree).

D. Tất cả các lựa chọn trên.

5. Trong một danh sách liên kết đơn, nếu head là con trỏ đến nút đầu tiên và current là con trỏ duyệt danh sách, biểu thức `current = current.next` thực hiện hành động gì?

A. Di chuyển current về nút đầu tiên.

B. Sao chép dữ liệu của nút hiện tại vào nút tiếp theo.

C. Di chuyển current đến nút kế tiếp trong danh sách.

D. Xóa nút hiện tại.

6. Cho một danh sách liên kết đơn với các nút chứa giá trị lần lượt là 10 -> 20 -> 30 -> 40. Nếu ta muốn chèn nút chứa giá trị 25 vào sau nút 20, thao tác nào là cần thiết?

A. Tạo nút mới với dữ liệu 25, đặt con trỏ next của nó trỏ tới nút 30, và đặt con trỏ next của nút 20 trỏ tới nút mới.

B. Tạo nút mới với dữ liệu 25, đặt con trỏ next của nó trỏ tới nút 20, và đặt con trỏ next của nút 30 trỏ tới nút mới.

C. Tạo nút mới với dữ liệu 25, đặt con trỏ next của nút 20 trỏ tới nút mới, và đặt con trỏ next của nút mới trỏ tới nút 20.

D. Tạo nút mới với dữ liệu 25, đặt con trỏ next của nút 20 trỏ tới nút mới, và đặt con trỏ next của nút mới trỏ tới nút 30.

7. Khi thực hiện xóa nút chứa giá trị 30 khỏi danh sách liên kết đơn 10 -> 20 -> 30 -> 40, thao tác nào là chính xác?

A. Tìm nút 20, đặt con trỏ next của nó trỏ tới nút 40.

B. Tìm nút 30, đặt con trỏ next của nó trỏ tới nút 20.

C. Tìm nút 40, đặt con trỏ next của nó trỏ tới nút 30.

D. Tìm nút 20, đặt con trỏ next của nút 30 trỏ tới nút 40.

8. Khi duyệt một danh sách liên kết đơn để tìm kiếm một giá trị cụ thể, nếu giá trị đó không tồn tại trong danh sách, thuật toán sẽ kết thúc như thế nào?

A. Trả về giá trị đầu tiên.

B. Dừng khi con trỏ hiện tại trở thành NULL và không tìm thấy giá trị.

C. Trả về một giá trị lỗi.

D. Tiếp tục duyệt vô hạn.

9. Để xóa phần tử đầu tiên của một danh sách liên kết đơn, điều cần làm sau khi tìm thấy nút đầu tiên là gì?

A. Cập nhật head pointer để trỏ đến nút thứ hai.

B. Cập nhật con trỏ next của nút cuối cùng.

C. Cập nhật head pointer để trỏ đến nút cuối cùng.

D. Gán head pointer bằng NULL.

10. Một danh sách liên kết vòng (circular linked list) khác với danh sách liên kết đơn ở điểm nào?

A. Nút cuối cùng trỏ đến nút đầu tiên.

B. Nút đầu tiên trỏ đến nút cuối cùng.

C. Mỗi nút đều có hai con trỏ.

D. Không có con trỏ next.

11. Nhược điểm chính của danh sách liên kết đơn khi cần truy cập một phần tử ở vị trí thứ k là gì?

A. Tốn nhiều bộ nhớ hơn mảng.

B. Phải duyệt tuần tự từ đầu danh sách.

C. Không thể thêm phần tử vào cuối danh sách.

D. Độ phức tạp khi xóa phần tử là O(n).

12. Tại sao việc tìm kiếm một phần tử cụ thể trong danh sách liên kết thường kém hiệu quả hơn so với mảng?

A. Danh sách liên kết có truy cập ngẫu nhiên.

B. Danh sách liên kết yêu cầu duyệt tuần tự, không có truy cập ngẫu nhiên.

C. Mảng có kích thước cố định.

D. Danh sách liên kết không lưu trữ dữ liệu.

13. Nếu ta cần một cấu trúc dữ liệu cho phép thêm và xóa hiệu quả ở cả hai đầu, danh sách liên kết nào là lựa chọn tốt nhất?

A. Danh sách liên kết đơn.

B. Danh sách liên kết kép.

C. Danh sách liên kết vòng.

D. Mảng.

14. Khi triển khai danh sách liên kết, một head pointer (con trỏ đầu) có vai trò quan trọng như thế nào?

A. Nó trỏ đến nút cuối cùng của danh sách.

B. Nó cho phép truy cập vào nút đầu tiên của danh sách.

C. Nó lưu trữ kích thước của danh sách.

D. Nó dùng để xóa toàn bộ danh sách.

15. Nếu một danh sách liên kết đơn có một vòng lặp (ví dụ: nút cuối cùng trỏ ngược lại một nút ở giữa), hậu quả phổ biến nhất đối với thuật toán duyệt thông thường là gì?

A. Thuật toán sẽ kết thúc ngay lập tức.

B. Thuật toán sẽ duyệt vô hạn (infinite loop).

C. Thuật toán sẽ xóa toàn bộ danh sách.

D. Thuật toán sẽ dừng lại khi gặp nút đầu.

16. Nếu một danh sách liên kết được biểu diễn bằng các nút, mỗi nút chứa một giá trị và một con trỏ, thì con trỏ này thường dùng để chỉ đến đâu?

A. Nút đứng trước nó trong danh sách.

B. Nút đứng kế tiếp nó trong danh sách.

C. Nút đầu tiên của danh sách.

D. Nút cuối cùng của danh sách.

17. Giả sử ta có một danh sách liên kết đơn và muốn chèn một nút mới chứa giá trị X vào vị trí cuối cùng. Việc này yêu cầu ta phải thực hiện thao tác nào?

A. Tìm nút đầu tiên, cập nhật con trỏ next của nó để trỏ tới nút mới.

B. Tìm nút cuối cùng, cập nhật con trỏ next của nó để trỏ tới nút mới.

C. Tìm nút đầu tiên, cập nhật con trỏ next của nút mới để trỏ tới nó.

D. Tìm nút cuối cùng, cập nhật con trỏ next của nút mới để trỏ tới nó.

18. Trong danh sách liên kết kép (doubly linked list), mỗi nút ngoài dữ liệu còn chứa những thành phần gì?

A. Chỉ con trỏ đến nút tiếp theo.

B. Con trỏ đến nút trước đó và con trỏ đến nút tiếp theo.

C. Con trỏ đến nút đầu tiên và con trỏ đến nút cuối cùng.

D. Con trỏ đến nút trước đó.

19. Trong việc quản lý bộ nhớ động, khi một nút trong danh sách liên kết không còn được sử dụng nữa, nó cần được giải phóng để tránh điều gì?

A. Tăng tốc độ truy cập.

B. Giảm khả năng xảy ra tràn bộ nhớ (memory overflow).

C. Giảm phân mảnh bộ nhớ.

D. Tăng dung lượng lưu trữ.

20. Trong thuật toán duyệt danh sách liên kết, để đảm bảo thuật toán dừng lại, điều kiện dừng phổ biến nhất là gì?

A. Khi con trỏ hiện tại bằng con trỏ đầu.

B. Khi con trỏ hiện tại trở thành NULL.

C. Khi gặp một giá trị đặc biệt.

D. Khi đã duyệt đủ số lượng phần tử đã biết trước.

21. So với mảng, việc sử dụng danh sách liên kết có thể gây ra vấn đề gì về mặt hiệu quả sử dụng bộ nhớ?

A. Tạo ra các lỗ trống bộ nhớ (memory holes).

B. Mỗi phần tử (nút) cần thêm bộ nhớ để lưu trữ con trỏ.

C. Yêu cầu cấp phát bộ nhớ liên tục.

D. Bộ nhớ bị phân mảnh nghiêm trọng.

22. Cấu trúc dữ liệu danh sách liên kết nào phù hợp nhất để triển khai hàng đợi (queue) với các thao tác enqueue (thêm vào cuối) và dequeue (lấy ra từ đầu) hiệu quả?

A. Danh sách liên kết đơn với con trỏ tail (cuối).

B. Danh sách liên kết kép.

C. Danh sách liên kết đơn không có con trỏ tail.

D. Mảng động.

23. Ưu điểm chính của danh sách liên kết so với mảng truyền thống là gì khi thực hiện các thao tác thêm hoặc xóa phần tử ở giữa danh sách?

A. Truy cập phần tử theo chỉ số O(1).

B. Hiệu quả cao trong việc thêm/xóa phần tử mà không cần dịch chuyển các phần tử khác.

C. Sử dụng bộ nhớ cố định, không thay đổi.

D. Dễ dàng truy cập ngẫu nhiên đến bất kỳ phần tử nào.

24. Trong cấu trúc dữ liệu danh sách liên kết, mỗi nút (node) thường chứa những thành phần cơ bản nào?

A. Con trỏ đến nút tiếp theo và dữ liệu.

B. Chỉ chứa dữ liệu.

C. Con trỏ đến nút trước đó và con trỏ đến nút tiếp theo.

D. Chỉ chứa con trỏ đến nút tiếp theo.

25. Khi thêm một nút mới vào đầu danh sách liên kết đơn, thao tác đầu tiên cần thực hiện là gì?

A. Tìm nút cuối cùng.

B. Cập nhật con trỏ next của nút mới để trỏ tới nút đầu hiện tại.

C. Cập nhật con trỏ next của nút đầu hiện tại.

D. Gán head pointer bằng NULL.