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. AChỉ dữ liệu
2. BDữ liệu và một tham chiếu đến nút kế tiếp
3. CDữ liệu và một chỉ số
4. DDữ liệu và tham chiếu đến mọi nút khác

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

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

Hệ số tải (load factor) của bảng băm là gì?

1. ASố ngăn chia cho độ dài trung bình của các khóa được lưu
2. BSố phần tử đang lưu chia cho số ngăn
3. CSố va chạm cho đến hiện tại
4. DThời gian cần để tải bảng từ đĩa

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(1)
2. BO(n)
3. CO(n²)
4. DO(log n)

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

Mục đích của nút lính canh (sentinel, nút giả) trong danh sách liên kết là gì?

1. ALàm cho danh sách được sắp xếp
2. BĐơn giản hóa mã bằng cách loại bỏ các trường hợp đặc biệt ở đầu hoặc cuối
3. CLưu số phần tử
4. DNgăn danh sách phát triển vượt quá một số nút tối đa cố định

Mảng động nhân đôi khi đầy. Vì sao nhiều cách cài đặt chỉ thu nhỏ nó khi đầy một phần tư, không phải một nửa?

1. AĐể giữ mảng được sắp xếp
2. BĐể tránh đổi kích thước liên tục khi push và pop xen kẽ gần ranh giới
3. CVì chia đôi ở một nửa sẽ làm mất phần tử
4. DVì bộ cấp phát bộ nhớ chỉ có thể giải phóng bộ nhớ theo phần tư của một khối

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 đống min chứa tất cả n giá trị, từ đó k giá trị nhỏ nhất được lấy ra ở cuối
4. DMột hàng đợi FIFO gồm k giá trị cuối