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

Trong đồ thị, chu trình là gì?

1. AMột đường đi bắt đầu và kết thúc tại cùng một đỉnh
2. BMột đỉnh không có cạnh
3. CMột cạnh có trọng số bằng không
4. DMột đường đi thăm mọi đỉnh

Ánh xạ (map, từ điển) lưu gì?

1. AChỉ các giá trị theo thứ tự chèn
2. BCác giá trị sắp theo kích thước
3. CCác cặp khóa bằng nhau
4. DCác cặp khóa-giá trị với khóa duy nhất

Trong một cây, các nút anh em (sibling) là gì?

1. ACác nút không có con
2. BCác nút cùng độ sâu ở những cây con khác nhau
3. CCác nút có chung một nút cha
4. DMột nút và cha của nó

Một bảng băm kích thước 7 dùng h(k) = k mod 7 và dò tuyến tính. Sau khi chèn 10, 17 được lưu ở đâu?

1. AChỉ số 3
2. BChỉ số 4
3. CChỉ số 0
4. DChỉ số 6

Giá trị của biểu thức hậu tố 3 4 + 2 * là bao nhiêu?

1. A10
2. B11
3. C14
4. D24

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)

Ưu điểm chính của skip list so với danh sách liên kết đã sắp xếp là gì?

1. ANó lưu khóa không có thứ tự
2. BNó không dùng thêm bộ nhớ
3. CTìm kiếm O(1) được đảm bảo vì mỗi nút lưu một con trỏ tới mọi nút khác
4. DTìm kiếm kỳ vọng O(log n) nhờ dùng nhiều tầng con trỏ tiế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