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

Thao tác nào là O(1) với mảng nhưng O(n) với danh sách liên kết đơn?

1. ATruy cập phần tử ở chỉ số i
2. BXóa phần tử đầu
3. CĐọc phần tử đầu tiên
4. DChèn vào đầu

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

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

Sự khác biệt chính giữa mảng tĩnh và mảng động là gì?

1. AMảng tĩnh chỉ có thể lưu số
2. BMảng tĩnh cho phép truy cập chỉ số chậm hơn
3. CMảng động lưu các phần tử trong các nút liên kết để có thể tăng từng phần tử một
4. DMảng động có thể tăng bằng cách chuyển sang một khối bộ nhớ lớn hơn

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

Cây AVL và cây đỏ-đen đảm bảo:

1. ACác khóa được lưu theo thứ tự chèn
2. BKhông nút nào có hai con
3. CTìm kiếm thời gian hằng số trong mọi trường hợp
4. DChiều cao O(log n) nhờ cân bằng lại

Thuật toán Dijkstra dùng kiểu dữ liệu trừu tượng nào để chọn đỉnh kế tiếp cần xử lý?

1. AHàng đợi FIFO
2. BNgăn xếp
3. CMột tập không có thứ tự
4. DHàng đợi ưu tiên min

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

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