[Cánh diều] Trắc nghiệm 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. Trong danh sách liên kết đơn, mỗi nút (node) chứa hai thành phần chính là gì?
A. Con trỏ đến nút tiếp theo và địa chỉ của nút trước đó.
B. Dữ liệu và con trỏ đến nút tiếp theo.
C. Dữ liệu và giá trị kích thước của nút.
D. Con trỏ đến dữ liệu và con trỏ đến nút cuối cùng.
2. Thao tác xóa một nút khỏi danh sách liên kết đơn yêu cầu phải biết con trỏ đến nút nào?
A. Chỉ cần biết con trỏ đến nút sẽ bị xóa.
B. Cần biết con trỏ đến nút đứng trước nút sẽ bị xóa.
C. Cần biết con trỏ đến nút đầu tiên và nút cuối cùng.
D. Không cần biết con trỏ nào, chỉ cần giá trị của nút đó.
3. Đâu là đặc điểm nổi bật nhất của danh sách liên kết so với mảng tĩnh (array) về khả năng thay đổi kích thước?
A. Danh sách liên kết yêu cầu bộ nhớ liên tục, còn mảng tĩnh thì không.
B. Danh sách liên kết có thể dễ dàng thêm hoặc xóa phần tử mà không cần cấp phát lại bộ nhớ lớn.
C. Mảng tĩnh có thể truy cập phần tử theo chỉ số nhanh hơn danh sách liên kết.
D. Cả hai đều có khả năng thay đổi kích thước linh hoạt như nhau.
4. Trong danh sách liên kết đơn, nếu muốn xóa nút đầu tiên (head), điều gì cần được thực hiện sau khi cập nhật con trỏ `head`?
A. Giải phóng bộ nhớ của nút mới.
B. Giải phóng bộ nhớ của nút đầu tiên đã bị xóa.
C. Cập nhật con trỏ của nút cuối cùng.
D. Không cần làm gì thêm sau khi cập nhật `head`.
5. Đâu là một ứng dụng phổ biến của danh sách liên kết trong thực tế?
A. Lưu trữ dữ liệu cố định, không thay đổi.
B. Quản lý hàng đợi (queue) trong hệ điều hành hoặc các hệ thống xử lý tác vụ.
C. Thực hiện truy cập ngẫu nhiên nhanh chóng đến mọi phần tử.
D. Tối ưu hóa việc tìm kiếm phần tử dựa trên chỉ số.
6. Nếu `prev` là con trỏ trỏ đến nút đứng trước nút `current` trong danh sách liên kết đơn, và ta muốn xóa `current`, thì thao tác cập nhật con trỏ của `prev` là gì?
A. `prev.next = current.next`
B. `prev.next = current`
C. `prev = current.next`
D. `current.next = prev.next`
7. Khi thực hiện thao tác thêm một nút mới vào cuối danh sách liên kết đơn (không có con trỏ `tail`), bạn cần làm gì trước tiên?
A. Cấp phát bộ nhớ cho nút mới.
B. Tìm nút cuối cùng của danh sách.
C. Cập nhật con trỏ `head`.
D. Kiểm tra xem danh sách có rỗng không.
8. Tại sao việc chèn hoặc xóa phần tử ở cuối danh sách liên kết đơn lại có độ phức tạp O(n) nếu không có con trỏ `tail`?
A. Vì cần duyệt qua tất cả các nút để tìm ra nút cuối cùng.
B. Vì cần cập nhật con trỏ `head`.
C. Vì việc cấp phát bộ nhớ cho nút mới tốn thời gian.
D. Vì thao tác này làm tăng độ phức tạp của danh sách.
9. Danh sách liên kết đôi (Doubly Linked List) có sự khác biệt cơ bản nào so với danh sách liên kết đơn?
A. Mỗi nút chỉ chứa dữ liệu và con trỏ đến nút tiếp theo.
B. Mỗi nút chứa dữ liệu, con trỏ đến nút tiếp theo và con trỏ đến nút trước đó.
C. Danh sách liên kết đôi không có nút đầu và nút cuối.
D. Danh sách liên kết đôi chỉ cho phép truy cập từ cuối về đầu.
10. Nếu một danh sách liên kết đơn chỉ có một nút duy nhất, thì con trỏ `head` và con trỏ `next` của nút đó sẽ có mối quan hệ như thế nào?
A. `head` trỏ đến nút đó, và `head.next` cũng trỏ đến nút đó.
B. `head` trỏ đến nút đó, và `head.next` là NULL.
C. `head` là NULL, và nút đó có con trỏ `next` trỏ đến chính nó.
D. `head` trỏ đến nút đó, và nút đó không có con trỏ `next`.
11. Đâu là một nhược điểm chính của danh sách liên kết so với mảng?
A. Khó khăn trong việc thêm hoặc xóa phần tử.
B. Không thể lưu trữ các kiểu dữ liệu khác nhau.
C. Tốn nhiều bộ nhớ hơn cho mỗi phần tử do phải lưu trữ thêm con trỏ.
D. Truy cập phần tử theo chỉ số không hiệu quả.
12. Nếu `current` là con trỏ trỏ đến nút hiện tại trong quá trình duyệt danh sách liên kết đơn, và ta muốn di chuyển sang nút tiếp theo, ta sẽ thực hiện phép toán nào?
A. `current = current.previous`
B. `current = current.data`
C. `current = current.next`
D. `current = NULL`
13. Khi duyệt một danh sách liên kết đơn, nếu gặp phải trường hợp con trỏ `next` của một nút là NULL, điều đó có nghĩa là gì?
A. Đó là nút đầu tiên của danh sách.
B. Đó là nút cuối cùng của danh sách.
C. Danh sách bị lỗi và cần được kiểm tra lại.
D. Nút đó chứa dữ liệu rỗng.
14. Khi thực hiện thao tác tìm kiếm một phần tử trong danh sách liên kết, điều kiện dừng của vòng lặp tìm kiếm thường là gì?
A. Khi con trỏ hiện tại trỏ đến NULL hoặc khi tìm thấy phần tử.
B. Chỉ khi con trỏ hiện tại trỏ đến NULL.
C. Chỉ khi tìm thấy phần tử.
D. Khi duyệt qua một số lượng nút cố định.
15. Khi xem xét hiệu quả của việc tìm kiếm một phần tử trong danh sách liên kết, trường hợp xấu nhất xảy ra khi nào?
A. Phần tử cần tìm nằm ở đầu danh sách.
B. Phần tử cần tìm nằm ở cuối danh sách hoặc không có trong danh sách.
C. Danh sách liên kết là danh sách liên kết đôi.
D. Danh sách liên kết có kích thước rất nhỏ.
16. Nếu bạn cần một cấu trúc dữ liệu cho phép chèn và xóa phần tử ở cả hai đầu một cách hiệu quả (O(1)), bạn nên chọn 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 đôi.
C. Danh sách liên kết vòng.
D. Cả danh sách liên kết đôi và danh sách liên kết vòng đều phù hợp.
17. Trong một bài toán cần lưu trữ một danh sách các sinh viên, trong đó thường xuyên thêm mới và xóa bỏ sinh viên khỏi danh sách, cấu trúc dữ liệu nào sau đây là phù hợp nhất về hiệu quả thay đổi kích thước?
A. Mảng tĩnh (Static Array)
B. Danh sách liên kết (Linked List)
C. Mảng động (Dynamic Array) có khả năng co giãn.
D. Cả Mảng động và Danh sách liên kết đều phù hợp như nhau.
18. Trong danh sách liên kết vòng (Circular Linked List), nút cuối cùng sẽ trỏ đến đâu?
A. NULL
B. Nút đầu tiên (head) của danh sách.
C. Nút đứng trước nó.
D. Một giá trị ngẫu nhiên.
19. Ưu điểm của danh sách liên kết vòng so với danh sách liên kết đơn thông thường là gì?
A. Cho phép truy cập mọi phần tử với độ phức tạp O(1).
B. Giúp việc duyệt danh sách trở nên liên tục và có thể quay vòng.
C. Giảm đáng kể dung lượng bộ nhớ sử dụng.
D. Loại bỏ hoàn toàn khả năng xảy ra lỗi con trỏ NULL.
20. Nếu `head` là con trỏ trỏ đến nút đầu tiên của danh sách liên kết đơn, và `newNode` là con trỏ trỏ đến nút mới cần chèn vào đầu danh sách, thì thao tác nào sau đây là đúng để chèn `newNode` vào đầu?
A. `newNode.next = head; head = newNode;`
B. `head.next = newNode;`
C. `newNode.next = head.next; head = newNode;`
D. `head = newNode; newNode.next = head;`
21. Trong lập trình hướng đối tượng, một "class" định nghĩa cấu trúc của một nút trong danh sách liên kết sẽ chứa các thuộc tính (attributes) nào?
A. Chỉ thuộc tính `next`.
B. Thuộc tính `data` và thuộc tính `next`.
C. Thuộc tính `data`, `next`, và `previous`.
D. Thuộc tính `head` và thuộc tính `tail`.
22. Ưu điểm của danh sách liên kết đôi so với danh sách liên kết đơn khi thực hiện thao tác xóa một nút là gì?
A. Không cần biết con trỏ đến nút đứng trước nút cần xóa.
B. Có thể xóa nút bất kỳ chỉ với con trỏ trỏ đến nút đó.
C. Luôn truy cập nhanh hơn đến nút cần xóa.
D. Giảm thiểu số lượng thao tác cập nhật con trỏ.
23. Khi thực hiện thao tác chèn một nút mới vào đầu danh sách liên kết đơn, bước đầu tiên cần làm là gì?
A. Cập nhật con trỏ của nút cuối cùng trỏ đến nút mới.
B. Cấp phát bộ nhớ cho nút mới và đặt dữ liệu vào nút đó.
C. Tìm nút cuối cùng của danh sách.
D. Cập nhật con trỏ của nút hiện tại trỏ sang nút mới.
24. Trong các thao tác với danh sách liên kết, thao tác nào thường có độ phức tạp thời gian cao nhất (O(n))?
A. Truy cập phần tử đầu tiên.
B. Chèn một phần tử vào đầu danh sách.
C. Tìm kiếm một phần tử hoặc chèn/xóa một phần tử ở vị trí bất kỳ.
D. Xóa phần tử đầu tiên.
25. Trong việc triển khai thuật toán sắp xếp như Bubble Sort hoặc Insertion Sort bằng cách sử dụng danh sách liên kết, thao tác nào thường là chậm nhất?
A. So sánh hai phần tử liền kề.
B. Truy cập phần tử đầu tiên.
C. Hoán đổi vị trí hai phần tử không liền kề.
D. Truy cập phần tử thứ k.
