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

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

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

Đồ thị có trọng số là gì?

1. AĐồ thị trong đó mỗi cạnh có một giá trị số như chi phí hoặc khoảng cách
2. BĐồ thị được lưu trên đĩa
3. CĐồ thị có nhiều cạnh hơn đỉnh
4. DĐồ thị trong đó một số đỉnh nặng hơn các đỉnh khác vì có nhiều cạnh hơn

Cấu trúc dữ liệu nào hoạt động theo nguyên tắc "vào sau, ra trước"?

1. ABảng băm
2. BHàng đợi (queue)
3. CNgăn xếp (stack)
4. DDanh sách liên kết

Cây nhị phân hoàn hảo có chiều cao h, với chiều cao tính bằng cạnh, có bao nhiêu nút?

1. A2^h+1 − 1
2. B2^h
3. Ch²
4. D2h + 1

Độ phức tạp thời gian của việc tìm một khóa trong cây tìm kiếm nhị phân cân bằng là bao nhiêu?

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

Điều nào đúng với ma trận kề của một đồ thị vô hướng?

1. ANó luôn là ma trận tam giác trên
2. BNó đối xứng qua đường chéo chính
3. CMỗi hàng có đúng một số 1
4. DĐường chéo chính của nó luôn chứa các số một

Thuật toán Kahn cho sắp xếp tô-pô liên tục loại bỏ các đỉnh có bậc vào 0. Cấu trúc nào chứa các đỉnh đó?

1. AMột đống max sắp theo bậc ra
2. BMột hàng đợi (hoặc bất kỳ tập hợp nào) các đỉnh có bậc vào 0
3. CMột ma trận kề ghi lại những đỉnh đã bị loại
4. DMột ngăn xếp gồm mọi cạnh đã thăm

Nếu không có hợp theo hạng hay nén đường đi, chi phí trường hợp xấu nhất của một lần find trong cấu trúc union-find với n phần tử là bao nhiêu?

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