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

Đặc điểm xác định của tập hợp (set) như một kiểu dữ liệu trừu tượng là gì?

1. ANó lưu các cặp khóa-giá trị
2. BNó lưu các phần tử không trùng lặp
3. CNó lưu các phần tử theo thứ tự đã sắp
4. DNó chỉ cho phép truy cập ở một đầu

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

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

Cấu trúc dữ liệu nào được dùng để duyệt cây theo mức (level-order)?

1. AHàng đợi
2. BHàng đợi ưu tiên
3. CNgăn xếp
4. DBảng băm

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

1. A10
2. B11
3. C24
4. D14

Một hàng đợi được cài đặt bằng hai ngăn xếp: đẩy vào ngăn xếp "vào", và lấy ra từ ngăn xếp "ra", nạp lại từ "vào" khi nó rỗng. Chi phí khấu hao mỗi thao tác là bao nhiêu?

1. AO(n²)
2. BO(1)
3. CO(log n)
4. DO(n)

Extract-min hoạt động thế nào trong đống min nhị phân?

1. AXóa phần tử cuối của mảng
2. BChuyển phần tử cuối lên gốc và đẩy xuống
3. CTìm trong tất cả các lá giá trị nhỏ nhất mới
4. DXóa gốc và dịch tất cả phần tử sang trái một vị trí

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

Cấu trúc dữ liệu nào hỗ trợ bộ nhớ đệm LRU (ít được dùng gần đây nhất) với get và put O(1)?

1. AMột bảng băm kết hợp với danh sách liên kết đôi
2. BChỉ một ngăn xếp
3. CChỉ một cây tìm kiếm nhị phân
4. DMột mảng đã sắp xếp đơn lẻ