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

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

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

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

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

Đồ thị có trọng số là gì?

1. AĐồ thị trong đó một số đỉnh nặng hơn các đỉnh khác vì có nhiều cạnh hơn
2. BĐồ thị trong đó mỗi cạnh có một giá trị số như chi phí hoặc khoảng cách
3. CĐồ thị có nhiều cạnh hơn đỉnh
4. DĐồ thị được lưu trên đĩa

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ự sau là gì?

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

Điều nào đúng với ma trận kề của một đồ thị vô hướng?

1. AĐường chéo chính của nó luôn chứa các số một
2. BNó đối xứng qua đường chéo chính
3. CMỗi hàng có đúng một số 1
4. DNó luôn là ma trận tam giác trên

Danh sách kề dùng bao nhiêu bộ nhớ cho đồ thị có V đỉnh và E cạnh?

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

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

Cấu trúc nào cho phép tính giá trị lớn nhất của mọi cửa sổ kích thước k trong mảng với tổng thời gian O(n)?

1. AMột deque giữ các chỉ số theo thứ tự giá trị giảm dần
2. BMột đống min được xây lại cho mỗi cửa sổ
3. CMột danh sách liên kết đơn gồm các phần tử của cửa sổ
4. DMột mảng đã sắp xếp được cập nhật bằng dịch chuyển