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

Thao tác ngăn xếp thêm một phần tử vào đỉnh có tên là gì?

1. APush
2. BPop
3. CPeek
4. DEnqueue

Duyệt thứ tự trước (preorder) của cây nhị phân thăm các nút theo thứ tự nào?

1. ACây con trái, rồi cây con phải, rồi nút
2. BCây con trái, rồi nút, rồi cây con phải
3. CTừng mức từ trên xuống
4. DNút, rồi cây con trái, rồi cây con phải

Các phần tử của mảng được lưu trong bộ nhớ như thế nào?

1. ATrong một khối liên tục, nối tiếp nhau
2. BTrong một cây các trang bộ nhớ
3. CRải rác, liên kết bằng con trỏ
4. DỞ các vị trí ngẫu nhiên do hàm băm chọn

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

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. BHàng đợi ưu tiên min
3. CMột tập không có thứ tự
4. DNgăn xếp

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

Các quy tắc cây đỏ-đen đảm bảo điều gì về chiều cao của cây có n khóa?

1. AChiều cao tối đa là log₂ n + 1
2. BChiều cao tối đa là n / 2
3. CChiều cao chính xác là log₂ n
4. DChiều cao tối đa là 2 log₂(n + 1)

Với băm đồng nhất đơn giản, thời gian kỳ vọng của một lần tìm kiếm trong bảng băm xâu chuỗi, với n khóa và m ngăn, là bao nhiêu?

1. AO(n)
2. BO(log n)
3. CO(m)
4. DO(1 + α), với α = n / m