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

Mỗi nút trong danh sách liên kết đôi chứa gì?

1. ADữ liệu, một con trỏ tới nút kế tiếp và một con trỏ tới nút trước
2. BHai bản sao dữ liệu và một con trỏ
3. CDữ liệu và chỉ một con trỏ tới nút kế tiếp
4. DDữ liệu và hai con trỏ, một tới nút kế tiếp và một tới nút đứng sau nút đó

Thao tác peek (hoặc top) trên ngăn xếp làm gì?

1. ALấy phần tử đỉnh ra và trả về nó
2. BXóa tất cả phần tử khỏi ngăn xếp
3. CTrả về phần tử đỉnh mà không lấy nó ra
4. DTrả về phần tử đáy của ngăn xếp

Trong đồ thị vô hướng, bậc của một đỉnh là gì?

1. ASố cạnh nối với nó
2. BĐộ dài đường đi dài nhất từ nó
3. CVị trí của nó trong danh sách kề
4. DSố đỉnh trong đồ thị

Bạn có một tham chiếu đến một nút ở giữa danh sách. Trong danh sách nào bạn có thể xóa nó trong O(1)?

1. ADanh sách liên kết đơn
2. BDanh sách liên kết đôi
3. CMảng đã sắp xếp
4. DMảng động

Trong đống nhị phân min lưu trong mảng (chỉ số bắt đầu từ 0), các con của nút ở chỉ số i nằm ở:

1. Ai + 1 và i + 2
2. B2i + 1 và 2i + 2
3. C2i và 2i + 1
4. Di/2 và i/2 + 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 log n)
2. BO(log n)
3. CO(n)
4. DO(1)

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(log n)
4. DO(1)

Cấu trúc union-find (tập rời nhau) với hợp theo hạng và nén đường đi có chi phí khấu hao mỗi thao tác là:

1. AChính xác O(log n)
2. BO(n²)
3. CO(n)
4. DO(α(n)), hàm Ackermann ngược, thực tế gần như hằng số