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

Cấu trúc dữ liệu nào được dùng để duyệt cây theo mức (level-order)?

1. ANgăn xếp
2. BBảng băm
3. CHàng đợi
4. DHàng đợi ưu tiên

Thao tác nào chậm trong mảng nhưng nhanh ở đầu danh sách liên kết?

1. AChèn vào đầu
2. BĐọc phần tử cuối theo chỉ số
3. CTruy cập phần tử thứ 5
4. DTìm độ dài của mảng cố định

Điều gì định nghĩa một cây nhị phân?

1. AMỗi nút có tối đa hai con
2. BCây có đúng hai mức
3. CMỗi nút lưu một số nhị phân
4. DMỗi nút có đúng hai con

Điều gì xảy ra khi bảng băm băm lại (rehash) sau khi hệ số tải vượt ngưỡng?

1. AMột bảng lớn hơn được cấp phát và mọi khóa được chèn lại
2. BCác khóa cũ nhất bị xóa để lấy chỗ
3. CCác khóa hiện có được sắp xếp tại chỗ
4. DChỉ các khóa va chạm được chuyển sang một danh sách tràn mới ở cuối bảng

Chiều cao trong trường hợp xấu nhất của cây tìm kiếm nhị phân có n nút là bao nhiêu nếu các khóa được chèn theo thứ tự đã sắp xếp?

1. A√n
2. Bn (nó trở thành danh sách liên kết)
3. C1
4. Dlog₂ n

Bộ đệm vòng (circular buffer, ring buffer) thường được dùng để cài đặt:

1. APhép duyệt đồ thị
2. BHàng đợi kích thước cố định
3. CHàm băm
4. DCây tìm kiếm nhị phân

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. ATruy vấn tổng tiền tố và cập nhật một phần tử
2. BTìm trung vị trong O(1)
3. CSắp xếp mảng và tìm kiếm nhị phân
4. DChèn phần tử vào vị trí bất kỳ

Cấu trúc union-find (tập rời nhau) với hợp theo hạng và nén đường đi có chi phí khấu hao mỗi thao tác là:

1. AChính xác O(log n)
2. BO(n²)
3. CO(α(n)), hàm Ackermann ngược, thực tế gần như hằng số
4. DO(n)