Phiếu bài tập Cấu trúc dữ liệu có đáp án

Trong danh sách liên kết đơn, con trỏ next của nút cuối chứa gì?

1. ASố nút trong danh sách
2. BĐịa chỉ của nút đầu tiên
3. CĐịa chỉ của nút trước
4. DNull (không có nút)

Tính chất đống max là gì?

1. AMọi lá đều chứa khóa lớn nhất
2. BKhóa của mỗi nút cha lớn hơn hoặc bằng khóa của các con
3. CKhóa của mỗi con trái lớn hơn hoặc bằng khóa của anh em bên phải của nó
4. DCác khóa được sắp từ trái sang phải

Trong một cây, các nút anh em (sibling) là gì?

1. ACác nút không có con
2. BCác nút cùng độ sâu ở những cây con khác nhau
3. CMột nút và cha của nó
4. DCác nút có chung một nút cha

Cây AVL duy trì điều kiện cân bằng nào tại mọi nút?

1. AMọi lá ở cùng một độ sâu chính xác
2. BChiều cao của cây con trái và phải chênh lệch tối đa 1
3. CCả hai cây con của mọi nút chứa đúng cùng số nút
4. DMỗi nút được tô đỏ hoặc đen

Trong đống nhị phân lưu trong mảng bắt đầu từ chỉ số 0, cha của nút ở chỉ số i nằm ở đâu?

1. AỞ chỉ số ⌊(i − 1) / 2⌋
2. BỞ chỉ số 2i + 1
3. CỞ chỉ số ⌊i / 2⌋ + 1
4. DỞ chỉ số i − 1

Trong đống nhị phân min lưu trong mảng (chỉ số bắt đầu từ 0), các con của nút ở chỉ số i nằm ở:

1. Ai/2 và i/2 + 1
2. B2i và 2i + 1
3. C2i + 1 và 2i + 2
4. Di + 1 và i + 2

Một đối tượng được lưu làm khóa trong bản đồ băm, rồi một trường được hàm băm của nó sử dụng bị thay đổi. Kết quả có khả năng nhất là gì?

1. ABản đồ tự động chuyển khóa sang ngăn mới
2. BTra cứu đối tượng có thể thất bại vì nó nằm trong ngăn ứng với giá trị băm cũ
3. CBản đồ ném lỗi ngay lúc trường thay đổi
4. DKhông có gì thay đổi, vì giá trị băm của khóa chỉ được tính một lần khi chương trình khởi động

Cây cơ số (radix tree, trie nén) cải thiện trie thông thường như thế nào?

1. ANó lưu mỗi từ trong một bảng băm ở gốc thay vì trong các nút riêng
2. BNó chỉ giữ chữ cái đầu của mỗi từ
3. CNó sắp các con của mỗi nút theo tần suất
4. DNó gộp các chuỗi nút một con thành một cạnh được gắn nhãn bằng một xâu