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

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

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

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

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

Hệ số tải (load factor) của bảng băm là gì?

1. ASố va chạm cho đến hiện tại
2. BThời gian cần để tải bảng từ đĩa
3. CSố phần tử đang lưu chia cho số ngăn
4. DSố ngăn chia cho độ dài trung bình của các khóa được lưu

Tìm một từ có độ dài L trong trie với bảng chữ cái cố định mất bao lâu?

1. AO(n), với n là số từ
2. BO(log n), với n là số từ
3. CO(L), không phụ thuộc số từ được lưu
4. DO(L × n)

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. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

Trong hàng đợi vòng lưu trong mảng có sức chứa n, vị trí kế tiếp sau chỉ số i được tính thế nào?

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

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(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α), với α = n / m

Thời gian chạy của tìm kiếm theo chiều rộng trên đồ thị có V đỉnh được lưu bằng ma trận kề là bao nhiêu?

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