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

Mỗi nút trong danh sách liên kết đôi chứa gì?

1. AHai bản sao dữ liệu và một con trỏ
2. BDữ liệu và hai con trỏ, một tới nút kế tiếp và một tới nút đứng sau nút đó
3. CDữ liệu, một con trỏ tới nút kế tiếp và một con trỏ tới nút trước
4. DDữ liệu và chỉ một con trỏ tới nút kế tiếp

Thao tác peek (hoặc top) trên ngăn xếp làm gì?

1. ATrả về phần tử đỉnh mà không lấy nó ra
2. BXóa tất cả phần tử khỏi ngăn xếp
3. CLấy phần tử đỉnh ra và trả về nó
4. DTrả về phần tử đáy của ngăn xếp

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

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

Các khóa 50, 30, 70, 20, 40 được chèn theo thứ tự này vào một cây tìm kiếm nhị phân rỗng. Con trái của 30 là gì?

1. A50
2. B20
3. C70
4. D40

Chi phí chèn một phần tử vào giữa mảng n phần tử là bao nhiêu?

1. AO(log n), nhờ tìm kiếm nhị phân
2. BO(n²), vì mỗi phần tử di chuyển n lần
3. CO(1), vì đã biết chỉ số
4. DO(n), vì các phần tử phía sau phải dịch chuyển

Trong bảng băm dùng địa chỉ mở, hệ số tải tối đa có thể là bao nhiêu?

1. A0,5
2. B1
3. CKhông có mức tối đa
4. D2

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

Cây Fenwick (cây chỉ mục nhị phân) trên một mảng n số hỗ trợ những thao tác nào trong O(log n)?

1. ASắp xếp mảng và tìm kiếm nhị phân
2. BTruy vấn tổng tiền tố và cập nhật một phần tử
3. CTìm trung vị trong O(1)
4. DChèn phần tử vào vị trí bất kỳ