Trắc Nghiệm Tin Học 11 Cánh Diều Khoa Học Máy Tính Chủ đề FCS Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng là nội dung thuộc môn Tin học, được xây dựng dưới dạng đề ôn tập tham khảo dành cho học sinh lớp 11 theo chương trình sách giáo khoa Cánh Diều. Bộ đề tập trung vào kiến thức chuyên sâu của cấu trúc dữ liệu danh sách liên kết, bao gồm khái niệm nút (node), con trỏ liên kết, cách tạo – duyệt – chèn – xoá phần tử và ứng dụng danh sách liên kết trong xử lý dữ liệu. Nội dung mở đầu có sử dụng định dạng trắc nghiệm Tin học 11 Khoa học máy tính Cánh Diều, được biên soạn năm 2024 bởi thầy Nguyễn Hoàng Long – giáo viên Tin học Trường THPT Tôn Đức Thắng (TP. Buôn Ma Thuột). Tài liệu được đăng tải trên detracnghiem.edu.vn, giúp học sinh ôn tập thuận tiện và bám sát sách giáo khoa.
Trắc nghiệm môn Tin học 11 ở bài học này bao gồm hệ thống câu hỏi từ cơ bản đến nâng cao, hỗ trợ học sinh hiểu rõ nguyên lý hoạt động của danh sách liên kết, phân biệt các loại danh sách (đơn, đôi, vòng), đồng thời biết ứng dụng chúng trong bài toán quản lý dữ liệu và thuật toán. Khi luyện tập qua detracnghiem.edu.vn, học sinh có thể xem lời giải chi tiết, theo dõi tiến độ học tập và nâng cao kỹ năng lập trình theo từng chủ đề. Bộ đề này là tài liệu hữu ích giúp học sinh sẵn sàng cho các bài kiểm tra định kỳ và phát triển tư duy thuật toán Trắc nghiệm lớp 11.
Trắc Nghiệm Tin Học 11 Cánh Diều Khoa Học Máy Tính
Chủ đề FCS: Giải quyết vấn đề với sự trợ giúp của máy tính
Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng
Câu 1: Danh sách liên kết (Linked List) được cấu tạo từ các thành phần cơ bản nào?
A. Các chỉ số (Index) và giá trị.
B. Các mảng con (Sub-array).
C. Các nút (Node) liên kết với nhau.
D. Các từ điển (Dictionary).
Câu 2: Mỗi nút (Node) trong danh sách liên kết đơn bao gồm hai thành phần chính là:
A. Tên nút và địa chỉ nút.
B. Phần dữ liệu và phần chỉ số.
C. Phần dữ liệu (Data) và con trỏ tham chiếu (Next).
D. Phần đầu (Head) và phần đuôi (Tail).
Câu 3: Nút cuối cùng trong một danh sách liên kết đơn thường trỏ tới đâu?
A. Trỏ về nút đầu tiên (Head).
B. Trỏ về chính nó.
C. Trỏ tới giá trị None (hoặc Null).
D. Trỏ tới một địa chỉ ngẫu nhiên.
Câu 4: Khác biệt lớn nhất về mặt bộ nhớ giữa Mảng (Array) và Danh sách liên kết (Linked List) là gì?
A. Mảng tốn ít bộ nhớ hơn danh sách liên kết.
B. Danh sách liên kết lưu trữ các phần tử liên tiếp nhau.
C. Mảng lưu trữ các phần tử rải rác trong bộ nhớ.
D. Danh sách liên kết có thể lưu trữ các phần tử rải rác.
Câu 5: Để tạo một nút mới trong Python (giả sử đã có lớp Node), câu lệnh nào sau đây là đúng?
A. new_node = list(value)
B. new_node = [value, None]
C. new_node = Node(value)
D. new_node = create(value)
Câu 6: Trong danh sách liên kết, con trỏ Head đóng vai trò gì?
A. Lưu trữ số lượng phần tử của danh sách.
B. Đánh dấu phần tử cuối cùng.
C. Quản lý địa chỉ của nút đầu tiên.
D. Lưu trữ dữ liệu của toàn bộ danh sách.
Câu 7: Thao tác thêm một nút mới vào đầu danh sách liên kết có độ phức tạp thời gian là bao nhiêu?
A. O(1)
B. O(n)
C. O(log n)
D. O(n²)
Câu 8: Để duyệt qua toàn bộ danh sách liên kết đơn, ta cần sử dụng cấu trúc điều khiển nào?
A. Vòng lặp for với chỉ số i từ 0 đến n.
B. Vòng lặp while kiểm tra con trỏ khác None.
C. Câu lệnh if-else kiểm tra từng nút.
D. Sử dụng hàm len() để lấy kích thước.
Câu 9: Cho một danh sách liên kết đang rỗng (Head = None). Sau lệnh thêm nút có giá trị 10 vào đầu, giá trị của Head.data là:
A. None
B. 0
C. 10
D. Một địa chỉ bộ nhớ.
Câu 10: Muốn xóa nút đầu tiên của danh sách liên kết (giả sử danh sách không rỗng), ta thực hiện lệnh nào?
A. Head = None
B. Head.next = None
C. Head = Head.next
D. del Head
Câu 11: Để chèn một nút mới P vào sau nút Q trong danh sách liên kết, trình tự lệnh nào là đúng?
A. Q.next = P; P.next = Q.next
B. P.next = Q; Q.next = P
C. Q.next = P.next; P = Q
D. P.next = Q.next; Q.next = P
Câu 12: Khi tìm kiếm một giá trị x trong danh sách liên kết đơn, trường hợp xấu nhất tốn bao nhiêu bước?
A. 1 bước.
B. n bước (với n là số nút).
C. log n bước.
D. n/2 bước.
Câu 13: Ưu điểm của danh sách liên kết so với danh sách (list/array) trong Python khi thực hiện chèn/xóa phần tử ở đầu là gì?
A. Tốn ít bộ nhớ lưu trữ hơn.
B. Truy cập ngẫu nhiên nhanh hơn.
C. Không phải dời chỗ các phần tử còn lại.
D. Mã lệnh cài đặt đơn giản hơn.
Câu 14: Cho danh sách liên kết: 1 → 2 → 3. Sau khi thực hiện thao tác xóa nút số 2, liên kết sẽ thay đổi thế nào?
A. Nút 1 trỏ tới None, nút 3 trỏ tới None.
B. Nút 1 trỏ trực tiếp tới nút 3.
C. Nút 3 trỏ ngược về nút 1.
D. Danh sách bị đứt đoạn, mất nút 3.
Câu 15: Đoạn mã sau dùng để làm gì?
curr = Head
while curr != None:
print(curr.data)
curr = curr.next
A. Xóa toàn bộ danh sách.
B. Tìm phần tử cuối cùng.
C. In giá trị các nút trong danh sách.
D. Đảo ngược danh sách.
Câu 16: Trong Python, nếu ta để mất con trỏ trỏ tới một nút giữa danh sách (không còn ai tham chiếu tới nó), điều gì sẽ xảy ra?
A. Nút đó vẫn tồn tại mãi mãi trong RAM.
B. Chương trình báo lỗi và dừng lại.
C. Bộ thu gom rác (Garbage Collector) sẽ thu hồi bộ nhớ.
D. Nút đó tự động nối vào cuối danh sách.
Câu 17: Để thêm nút vào cuối danh sách liên kết đơn (không có con trỏ Tail), độ phức tạp thời gian là:
A. O(1)
B. O(n)
C. O(log n)
D. O(n²)
Câu 18: Danh sách liên kết thường được ứng dụng để cài đặt cấu trúc dữ liệu nào sau đây một cách hiệu quả nhất?
A. Mảng hai chiều tĩnh.
B. Bảng băm (Hash Table).
C. Ngăn xếp (Stack) và Hàng đợi (Queue).
D. Cây nhị phân tìm kiếm đầy đủ.
Câu 19: Nếu biến Head trỏ đến None, điều này biểu thị trạng thái gì của danh sách?
A. Danh sách bị lỗi.
B. Danh sách đầy bộ nhớ.
C. Danh sách có 1 phần tử rỗng.
D. Danh sách rỗng (không có phần tử).
Câu 20: Cho nút A đang trỏ tới nút B. Lệnh A.next = B.next có tác dụng gì?
A. Nối thêm một nút mới sau B.
B. Đổi chỗ vị trí của A và B.
C. Tách nút B ra khỏi danh sách (xóa B).
D. Sao chép dữ liệu từ B sang A.
Câu 21: Trong bài toán quản lý danh sách bài hát (Playlist), tại sao Danh sách liên kết lại phù hợp hơn Mảng?
A. Vì bài hát có dung lượng lớn.
B. Vì thường xuyên thêm/xóa bài hát và phát tuần tự.
C. Vì cần truy cập ngẫu nhiên bài hát thứ 100 ngay lập tức.
D. Vì tên bài hát là chuỗi ký tự.
Câu 22: Khuyết điểm lớn nhất của danh sách liên kết đơn so với mảng là:
A. Kích thước cố định không thay đổi được.
B. Khó cài đặt hơn mảng rất nhiều.
C. Không thể truy cập trực tiếp phần tử qua chỉ số (index).
D. Không lưu trữ được số nguyên.
Câu 23: Giả sử cần lưu trữ đa thức P(x) = 3x^5 + 2x^2 + 1. Mỗi nút trong danh sách liên kết cần lưu trữ thông tin gì?
A. Chỉ lưu hệ số (3, 2, 1).
B. Chỉ lưu số mũ (5, 2, 0).
C. Lưu cả hệ số và số mũ tương ứng.
D. Lưu giá trị x và kết quả P(x).
Câu 24: Cho đoạn mã thêm vào đầu:
node = Node(x)
node.next = Head
Head = node
Thứ tự 3 dòng lệnh này có quan trọng không?
A. Không, viết thứ tự nào cũng được.
B. Có, dòng 3 phải viết trước dòng 2.
C. Có, phải gán next trước khi cập nhật Head.
D. Có, phải cập nhật Head ngay dòng đầu tiên.
Câu 25: Để đếm số lượng phần tử trong danh sách liên kết, ta cần làm gì?
A. Lấy sizeof(Head).
B. Dùng hàm len() có sẵn của Python.
C. Truy cập Head.count.
D. Duyệt từ đầu đến cuối và tăng biến đếm.
Câu 26: Danh sách liên kết đôi (Doubly Linked List) khác danh sách liên kết đơn ở điểm nào?
A. Có hai con trỏ Head.
B. Mỗi nút có thêm con trỏ trỏ về nút trước nó (Prev).
C. Mỗi nút chứa hai giá trị dữ liệu.
D. Tốc độ truy cập chậm hơn liên kết đơn.
Câu 27: Ứng dụng nút Back (Quay lại) và Forward (Tiến lên) trên trình duyệt web có thể được mô hình hóa tốt nhất bằng:
A. Một danh sách liên kết đơn.
B. Một mảng một chiều.
C. Một danh sách liên kết đôi.
D. Một cây nhị phân.
Câu 28: Cho danh sách A → B → C. Muốn chèn nút X vào giữa A và B. Các thao tác gán con trỏ nào là đúng?
A. A.next = X; X.next = B
B. X.next = A.next; A.next = X
C. X.next = B; B.next = A
D. A.next = X; B.next = X
Câu 29: Để đảo ngược (Reverse) một danh sách liên kết đơn, ta cần sử dụng bao nhiêu con trỏ phụ trong quá trình duyệt?
A. 1 con trỏ.
B. 2 con trỏ (curr, next).
C. 3 con trỏ (prev, curr, next).
D. Không cần con trỏ phụ nào.
Câu 30: Phát hiện chu trình (cycle) trong danh sách liên kết (ví dụ nút cuối trỏ ngược lại nút giữa) thường dùng thuật toán nào?
A. Duyệt trâu (Brute-force).
B. Tìm kiếm nhị phân.
C. Thuật toán Rùa và Thỏ (Floyd’s Cycle Finding).
D. Sắp xếp danh sách trước.
