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

Trong biểu diễn danh sách kề của đồ thị, mỗi đỉnh lưu gì?

1. ATổng số cạnh trong đồ thị
2. BĐường đi ngắn nhất đến mọi đỉnh khác
3. CMột hàng gồm V giá trị Boolean
4. DDanh sách các đỉnh lân cận của nó

Bảng băm lưu dữ liệu dưới dạng:

1. AChỉ một danh sách đã sắp xếp
2. BCác cặp khóa–giá trị được định vị bằng hàm băm
3. CMột chuỗi có độ dài cố định
4. DMột cây có khóa được sắp thứ tự

Một cây có n nút thì có bao nhiêu cạnh?

1. A2n
2. Bn + 1
3. Cn − 1
4. Dn

Ma trận kề của một đồ thị có V đỉnh dùng bao nhiêu bộ nhớ?

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

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

Một cây nhị phân có gốc 1 với con trái 2 và con phải 3; nút 2 có các con 4 (trái) và 5 (phải). Duyệt thứ tự trước là gì?

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D4 5 2 3 1

Độ phức tạp thời gian của decrease-key trong đống nhị phân (biết vị trí phần tử) là:

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

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Để tránh đổi kích thước liên tục khi push và pop xen kẽ gần ranh giới
2. BVì chia đôi ở một nửa sẽ làm mất phần tử
3. CĐể giữ mảng được sắp xếp
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