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

Sự khác biệt chính giữa mảng tĩnh và mảng động là gì?

1. AMảng tĩnh cho phép truy cập chỉ số chậm hơn
2. BMảng tĩnh chỉ có thể lưu số
3. CMảng động có thể tăng bằng cách chuyển sang một khối bộ nhớ lớn hơn
4. DMảng động lưu các phần tử trong các nút liên kết để có thể tăng từng phần tử một

Hàm băm làm gì trong bảng băm?

1. AMã hóa các giá trị trong bảng
2. BĐếm số khóa đang được lưu
3. CÁnh xạ một khóa tới một chỉ số trong bảng
4. DSắp xếp các khóa trong bảng

Trong một cây, lá là gì?

1. ANút không có cha
2. BNút có đúng một con
3. CNút có giá trị lớn nhất
4. DNút không có con

Một ứng dụng cần tra cứu nhanh, đồng thời cần liệt kê khóa theo thứ tự đã sắp và trả lời các truy vấn khoảng. Cấu trúc nào phù hợp nhất?

1. ADanh sách liên kết không sắp xếp
2. BCây tìm kiếm nhị phân cân bằng
3. CBảng băm
4. DNgăn xếp

Kiểm tra cạnh (u, v) có tồn tại hay không bằng ma trận kề mất bao lâu?

1. AO(1)
2. BO(E)
3. CO(log V)
4. DO(V)

Một hàng đợi được cài đặt bằng hai ngăn xếp: đẩy vào ngăn xếp "vào", và lấy ra từ ngăn xếp "ra", nạp lại từ "vào" khi nó rỗng. Chi phí khấu hao mỗi thao tác là bao nhiêu?

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(1)

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

Phát biểu nào về heapsort là đúng?

1. ANó cần một cây tìm kiếm nhị phân làm bộ nhớ phụ, nên dùng thêm O(n) bộ nhớ
2. BNó ổn định và cần O(n) bộ nhớ thêm
3. CNó sắp xếp tại chỗ trong thời gian O(n log n) trường hợp xấu nhất nhưng không ổn định
4. DNó chạy trong thời gian O(n) với mọi đầu vào