Trắc nghiệm Tin học 11 Cánh diều 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. Trong danh sách liên kết, việc chèn một nút mới vào giữa danh sách yêu cầu phải cập nhật ít nhất bao nhiêu con trỏ?
A. Hai con trỏ: con trỏ "next" của nút đứng trước nút mới và con trỏ "next" của chính nút mới. Kết luận Lý giải.
B. Chỉ một con trỏ.
C. Ba con trỏ.
D. Bốn con trỏ.
2. Trong danh sách liên kết, thao tác xóa một nút bất kỳ (không phải nút đầu) yêu cầu biết thông tin gì về nút đó hoặc các nút lân cận?
A. Cần biết con trỏ của nút đứng ngay trước nút cần xóa để cập nhật liên kết. Kết luận Lý giải.
B. Chỉ cần biết con trỏ của chính nút cần xóa là đủ.
C. Cần biết con trỏ của nút đứng ngay sau nút cần xóa.
D. Cần biết con trỏ của cả nút trước và nút sau nút cần xóa.
3. Nếu con trỏ đầu của danh sách liên kết đơn bị mất (không còn tham chiếu đến nút đầu tiên), điều gì sẽ xảy ra?
A. Toàn bộ danh sách sẽ không thể truy cập được nữa, gây ra hiện tượng "mất bộ nhớ" (memory leak) nếu không có cơ chế quản lý bộ nhớ tự động. Kết luận Lý giải.
B. Chỉ nút đầu tiên bị mất, các nút còn lại vẫn có thể truy cập được nếu có con trỏ đến một nút bất kỳ trong danh sách.
C. Danh sách tự động chuyển thành danh sách vòng.
D. Chương trình sẽ báo lỗi biên dịch ngay lập tức.
4. Trong danh sách liên kết, nếu một nút được thêm vào vị trí cuối cùng (khi không có con trỏ cuối), ta cần thực hiện bao nhiêu bước để tìm được nút cuối cùng trước khi thêm nút mới?
A. n-1 bước, trong đó "n" là số phần tử hiện có, để duyệt từ nút đầu đến nút cuối cùng. Kết luận Lý giải.
B. Chỉ 1 bước nếu có con trỏ cuối.
C. n bước.
D. Không cần tìm nút cuối, chỉ cần cập nhật con trỏ đầu.
5. Khi thực hiện thao tác chèn một nút mới vào giữa danh sách liên kết kép, ta cần cập nhật bao nhiêu con trỏ?
A. Bốn con trỏ: con trỏ "next" của nút trước, con trỏ "previous" của nút sau, con trỏ "next" của nút mới và con trỏ "previous" của nút mới. Kết luận Lý giải.
B. Hai con trỏ.
C. Ba con trỏ.
D. Sáu con trỏ.
6. Khi duyệt qua một danh sách liên kết đơn từ đầu đến cuối, nếu muốn truy cập phần tử thứ "k" (với k > 0), ta cần thực hiện tối đa bao nhiêu bước di chuyển qua các liên kết?
A. k bước di chuyển, mỗi bước tương ứng với việc theo dõi trường "next" của nút hiện tại. Kết luận Lý giải.
B. k-1 bước di chuyển.
C. k+1 bước di chuyển, bao gồm cả việc bắt đầu từ con trỏ đầu.
D. Phụ thuộc vào kích thước của danh sách, không thể xác định trước.
7. Độ phức tạp thời gian (time complexity) của thao tác tìm kiếm một phần tử cụ thể trong danh sách liên kết đơn khi phần tử đó nằm ở cuối danh sách là:
A. O(n), trong đó "n" là số lượng phần tử trong danh sách, vì ta phải duyệt qua tất cả các nút. Kết luận Lý giải.
B. O(1), vì chỉ cần truy cập một lần.
C. O(log n), nếu danh sách được sắp xếp.
D. O(n^2), do có thể phải duyệt lại nhiều lần.
8. Trong danh sách liên kết, nếu ta muốn thực hiện thao tác xóa phần tử thứ "k" (với k > 0), thì độ phức tạp thời gian sẽ là bao nhiêu?
A. O(k), vì ta cần duyệt qua "k-1" nút để đến nút cần xóa và nút ngay trước nó. Kết luận Lý giải.
B. O(1).
C. O(N).
D. O(log k).
9. Đâu là ưu điểm chính của danh sách liên kết so với mảng tĩnh 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. Hiệu quả về thời gian, vì chỉ cần thay đổi một vài con trỏ thay vì phải dịch chuyển toàn bộ các phần tử phía sau. Kết luận Lý giải.
B. Tiết kiệm bộ nhớ hơn vì không cần cấp phát trước toàn bộ không gian.
C. Dễ dàng truy cập ngẫu nhiên phần tử theo chỉ số.
D. Bảo mật dữ liệu tốt hơn do cấu trúc phân tán.
10. Đâu là cách hiệu quả nhất để kiểm tra xem một danh sách liên kết đơn có rỗng hay không?
A. Kiểm tra xem con trỏ đầu (head pointer) có trỏ đến NULL hay không. Kết luận Lý giải.
B. Kiểm tra xem con trỏ cuối (tail pointer) có trỏ đến NULL hay không.
C. Duyệt qua toàn bộ danh sách để đếm số phần tử.
D. Kiểm tra kích thước của danh sách nếu có biến lưu kích thước.
11. Trong danh sách liên kết, thao tác thêm một nút vào cuối danh sách khi có cả con trỏ đầu và con trỏ cuối sẽ có độ phức tạp thời gian là bao nhiêu?
A. O(1), vì ta có thể trực tiếp truy cập nút cuối cùng thông qua con trỏ cuối. Kết luận Lý giải.
B. O(N), vì cần duyệt qua tất cả các nút.
C. O(log N).
D. O(N^2).
12. Đâu là điểm khác biệt chính về khả năng truy cập giữa mảng và danh sách liên kết?
A. Mảng cho phép truy cập ngẫu nhiên theo chỉ số (O(1)), còn danh sách liên kết yêu cầu duyệt tuần tự (O(n)). Kết luận Lý giải.
B. Cả hai đều cho phép truy cập ngẫu nhiên.
C. Danh sách liên kết cho phép truy cập ngẫu nhiên nhanh hơn.
D. Mảng chỉ cho phép truy cập tuần tự.
13. Nếu một danh sách liên kết đơn có N nút, thì thao tác thêm một nút vào vị trí đầu danh sách có độ phức tạp thời gian là bao nhiêu?
A. O(1), vì chỉ liên quan đến việc thay đổi một vài con trỏ tại đầu danh sách. Kết luận Lý giải.
B. O(N), vì cần duyệt qua tất cả các nút.
C. O(log N), nếu danh sách được sắp xếp.
D. O(N^2).
14. Nếu ta muốn xây dựng một hàng đợi (queue) sử dụng danh sách liên kết đơn, thì thao tác "enqueue" (thêm vào cuối) và "dequeue" (lấy ra từ đầu) sẽ tương ứng với những thao tác nào trên danh sách liên kết?
A. Enqueue là thêm vào cuối danh sách, Dequeue là xóa từ đầu danh sách. Kết luận Lý giải.
B. Enqueue là thêm vào đầu danh sách, Dequeue là xóa từ cuối danh sách.
C. Enqueue là thêm vào đầu, Dequeue là xóa từ đầu.
D. Enqueue là thêm vào cuối, Dequeue là xóa từ cuối.
15. Nếu ta muốn xây dựng một ngăn xếp (stack) sử dụng danh sách liên kết đơn, thì thao tác "push" (đẩy vào đỉnh) và "pop" (lấy ra từ đỉnh) sẽ tương ứng với những thao tác nào trên danh sách liên kết?
A. Push là thêm vào đầu danh sách, Pop là xóa từ đầu danh sách. Kết luận Lý giải.
B. Push là thêm vào cuối danh sách, Pop là xóa từ đầu danh sách.
C. Push là thêm vào đầu, Pop là xóa từ cuối.
D. Push là thêm vào cuối, Pop là xóa từ cuối.
16. Trong danh sách liên kết đơn, thao tác thêm một nút mới vào đầu danh sách sẽ tốn bao nhiêu phép toán cơ bản trên con trỏ?
A. 2 phép toán: gán giá trị cho trường dữ liệu của nút mới và gán địa chỉ của nút đầu tiên hiện tại vào trường "next" của nút mới. Sau đó, cập nhật con trỏ đầu danh sách trỏ đến nút mới. Kết luận Lý giải.
B. 1 phép toán: chỉ cần cập nhật con trỏ "next" của nút mới để trỏ tới nút đầu tiên hiện tại.
C. 3 phép toán: gán giá trị, gán địa chỉ nút đầu tiên cũ, và cập nhật con trỏ đầu danh sách.
D. 4 phép toán: bao gồm cả việc cấp phát bộ nhớ cho nút mới.
17. Trong danh sách liên kết kép, việc xóa một nút bất kỳ (biết con trỏ tới nút đó) có độ phức tạp thời gian là bao nhiêu?
A. O(1), vì ta có thể truy cập trực tiếp nút trước và nút sau thông qua con trỏ "previous" và "next". Kết luận Lý giải.
B. O(N), vì cần duyệt từ đầu danh sách.
C. O(log N).
D. O(N^2).
18. Khi thực hiện thao tác xóa một nút khỏi danh sách liên kết đơn, nút bị xóa sẽ được xử lý như thế nào về mặt bộ nhớ?
A. Bộ nhớ của nút đó cần được giải phóng (deallocated/free) để tránh rò rỉ bộ nhớ. Kết luận Lý giải.
B. Bộ nhớ đó sẽ tự động được tái sử dụng cho các nút khác.
C. Bộ nhớ đó sẽ bị "khóa" lại và không thể sử dụng được nữa.
D. Không cần xử lý bộ nhớ cho nút bị xóa.
19. Đâu là một sai lầm phổ biến khi làm việc với danh sách liên kết mà có thể dẫn đến lỗi nghiêm trọng?
A. Quên giải phóng bộ nhớ của các nút đã xóa hoặc không còn sử dụng. Kết luận Lý giải.
B. Luôn bắt đầu duyệt từ con trỏ đầu.
C. Sử dụng con trỏ cuối để thêm phần tử.
D. Kiểm tra con trỏ đầu có bằng NULL trước khi duyệt.
20. Nếu ta có một danh sách liên kết đơn rỗng và thực hiện thao tác xóa phần tử đầu tiên, điều gì sẽ xảy ra?
A. Thao tác này không hợp lệ hoặc cần được xử lý đặc biệt để tránh lỗi, ví dụ như trả về một giá trị lỗi hoặc không thay đổi danh sách. Kết luận Lý giải.
B. Con trỏ đầu sẽ trở thành NULL.
C. Chương trình sẽ bị crash ngay lập tức.
D. Danh sách sẽ tự động bị xóa.
21. Trong cấu trúc danh sách liên kết, mỗi nút thường chứa ít nhất bao nhiêu thành phần?
A. Hai thành phần: dữ liệu và một con trỏ đến nút kế tiếp. Kết luận Lý giải.
B. Chỉ một thành phần: dữ liệu.
C. Ba thành phần: dữ liệu, con trỏ kế tiếp và con trỏ trước đó.
D. Số lượng thành phần tùy thuộc vào loại dữ liệu được lưu trữ.
22. Đâu là hạn chế chính của danh sách liên kết đơn khi thực hiện xóa phần tử cuối cùng?
A. Cần duyệt đến nút thứ hai từ cuối để cập nhật con trỏ "next" của nó thành NULL. Kết luận Lý giải.
B. Không thể xóa phần tử cuối cùng.
C. Thao tác này có độ phức tạp O(1).
D. Cần phải biết trước địa chỉ của nút cuối cùng.
23. Danh sách liên kết kép (doubly linked list) khác với danh sách liên kết đơn ở điểm nào cơ bản nhất?
A. Mỗi nút trong danh sách kép có thêm một con trỏ trỏ về nút đứng trước nó, cho phép duyệt theo cả hai chiều. Kết luận Lý giải.
B. Duyệt danh sách kép chỉ có thể thực hiện theo một chiều từ đầu đến cuối.
C. Danh sách kép không có con trỏ đầu và con trỏ cuối.
D. Danh sách kép chỉ lưu trữ dữ liệu, không có liên kết giữa các nút.
24. Đâu là trường hợp sử dụng danh sách liên kết Circular (danh sách vòng) hiệu quả nhất?
A. Quản lý các tác vụ đang chờ xử lý trong một hệ điều hành, nơi tác vụ cuối cùng có thể quay lại hàng đợi. Kết luận Lý giải.
B. Lưu trữ một tập hợp các phần tử có kích thước cố định.
C. Thực hiện tìm kiếm nhị phân hiệu quả.
D. Xây dựng cấu trúc cây nhị phân.
25. Đâu là một ứng dụng thực tế phổ biến của danh sách liên kết trong phát triển phần mềm?
A. Quản lý bộ nhớ đệm (cache memory) hoặc danh sách các tiến trình đang chạy. Kết luận Lý giải.
B. Lưu trữ dữ liệu trong các bảng băm (hash tables).
C. Thực hiện sắp xếp nhanh (quick sort).
D. Xây dựng cấu trúc đồ thị.
