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. CNull (không có nút)
4. DĐịa chỉ của nút trước

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

1. AKhó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ó
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. CMọi lá đều chứa khóa lớn nhất
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 cùng độ sâu ở những cây con khác nhau
2. BMột nút và cha của nó
3. CCác nút có chung một nút cha
4. DCác nút không có con

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. BỞ chỉ số 2i + 1
3. CỞ chỉ số ⌊i / 2⌋ + 1
4. DỞ chỉ số ⌊(i − 1) / 2⌋

Một phần tử mới được chèn vào đống nhị phân như thế nào?

1. AĐặt nó ở cuối mảng và đẩy lên trong khi nó vi phạm tính chất đống
2. BĐặt nó ở gốc và đẩy xuống
3. CXây lại toàn bộ đống từ đầu
4. DChèn nó vào vị trí đã sắp bằng cách dịch tất cả các phần tử lớn hơn sang phải một vị trí

Vì sao đống nhị phân có thể lưu trong mảng mà không cần con trỏ?

1. AĐống không bao giờ chứa quá 100 phần tử
2. BMọi khóa trong đống đều bằng nhau
3. CMảng tự động giữ các khóa theo thứ tự đã sắp, nên không cần con trỏ
4. DNó là cây nhị phân đầy đủ, nên các vị trí tuân theo công thức chỉ số đơn giản

Cặp phép duyệt nào luôn xác định duy nhất một cây nhị phân có các khóa phân biệt?

1. AThứ tự trước và thứ tự sau
2. BThứ tự trước và thứ tự giữa
3. CChỉ thứ tự trước
4. DChỉ duyệt theo mức

Bạn phải giữ k giá trị nhỏ nhất từ một luồng n số bằng bộ nhớ O(k). Cách nào chạy trong thời gian O(n log k)?

1. AMột hàng đợi FIFO gồm k giá trị cuối
2. BMột đống min chứa tất cả n giá trị, từ đó k giá trị nhỏ nhất được lấy ra ở cuối
3. CMột mảng đã sắp xếp chứa tất cả n giá trị
4. DMột đống max kích thước k, thay gốc của nó khi có giá trị nhỏ hơn đến