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, mỗi nút chứa:

1. ADữ liệu và tham chiếu đến mọi nút khác
2. BChỉ dữ liệu
3. CDữ liệu và một chỉ số
4. DDữ liệu và một tham chiếu đến nút kế tiếp

Đồ thị gồm:

1. AChỉ khóa và giá trị băm
2. BHàng và cột
3. CCác đỉnh (nút) được nối bởi các cạnh
4. DChỉ một gốc và các lá

Thao tác hàng đợi lấy phần tử ở đầu ra có tên là gì?

1. ADequeue
2. BPush
3. CEnqueue
4. DInsert

Đ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 hiện có được sắp xếp tại chỗ
3. CChỉ các khóa va chạm được chuyển sang một danh sách tràn mới ở cuối bảng
4. DCác khóa cũ nhất bị xóa để lấy chỗ

Thuật toán Dijkstra dùng kiểu dữ liệu trừu tượng nào để chọn đỉnh kế tiếp cần xử lý?

1. AHàng đợi FIFO
2. BNgăn xếp
3. CHàng đợi ưu tiên min
4. DMột tập không có thứ tự

Extract-min hoạt động thế nào trong đống min nhị phân?

1. AChuyển phần tử cuối lên gốc và đẩy xuống
2. BXóa phần tử cuối của mảng
3. CTìm trong tất cả các lá giá trị nhỏ nhất mới
4. DXóa gốc và dịch tất cả phần tử sang trái một vị trí

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 max kích thước k, thay gốc của nó khi có giá trị nhỏ hơn đến
3. CMột mảng đã sắp xếp chứa tất cả n giá trị
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

Băm kép chủ yếu giảm vấn đề nào của dò tuyến tính?

1. AHiện tượng gom cụm sơ cấp, khi các dãy ô bị chiếm dài ra
2. BChi phí O(n) để đọc giá trị của một khóa
3. CNhu cầu lưu khóa trong bảng
4. DNhu cầu có hàm băm