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

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

1. An − 1
2. B2n
3. Cn
4. Dn + 1

Chiều cao của một cây thường được định nghĩa là:

1. ASố lá trong cây
2. BSố con của gốc
3. CTổng số nút trong cây, tính cả gốc và mọi lá
4. DSố cạnh trên đường đi dài nhất từ gốc đến một lá

Trong danh sách liên kết đơn, mỗi nút chứa:

1. ADữ liệu và một chỉ số
2. BDữ liệu và tham chiếu đến mọi nút khác
3. CChỉ dữ liệu
4. DDữ liệu và một tham chiếu đến nút kế tiếp

Một mạng lưới đường có 100,000 giao lộ, mỗi giao lộ nối với khoảng 4 giao lộ khác. Cách biểu diễn nào phù hợp nhất?

1. AMột mảng đỉnh đã sắp xếp đơn lẻ
2. BDanh sách kề
3. CMa trận kề
4. DMột đống nhị phân các cạnh

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. A4 2 5 1 3
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D1 2 3 4 5

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

Các khóa 5, 3, 8, 1 được chèn theo thứ tự này vào đống min nhị phân dùng mảng rỗng. Mảng cuối cùng là gì?

1. A[1, 3, 5, 8]
2. B[3, 1, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]

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ì 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
3. CVì chia đôi ở một nửa sẽ làm mất phần tử
4. DĐể giữ mảng được sắp xếp