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

Gốc của một cây là gì?

1. ANút trên cùng không có nút cha
2. BNút không có con
3. CNút có giá trị lớn nhất
4. DBất kỳ nút nào ở giữa

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

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

Hàm băm làm gì trong bảng băm?

1. AÁnh xạ một khóa tới một chỉ số trong bảng
2. BMã hóa các giá trị trong bảng
3. CĐếm số khóa đang được lưu
4. DSắp xếp các khóa trong bảng

Phương pháp xử lý va chạm nào lưu các khóa va chạm trong một danh sách ở cùng một ngăn?

1. ABăm kép
2. BDò bậc hai
3. CXâu chuỗi riêng (separate chaining)
4. DDò tuyến tính

Một phần tử mới được chèn vào đống nhị phân như thế nào?

1. AĐặt nó ở gốc và đẩy xuống
2. BXây lại toàn bộ đống từ đầu
3. CĐặt nó ở cuối mảng và đẩy lên trong khi nó vi phạm tính chất đống
4. DChèn nó vào vị trí đã sắp bằng cách dịch tất cả các phần tử lớn hơn sang phải một vị trí

Độ phức tạp thời gian của việc tìm một khóa trong cây tìm kiếm nhị phân cân bằng là bao nhiêu?

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

Chèn một khóa vào cây AVL làm cây con trái của một nút quá cao, và khóa mới đi vào cây con trái của con trái của nó (trường hợp trái-trái). Cách sửa nào được áp dụng?

1. AMột phép xoay phải đơn tại nút mất cân bằng
2. BTô lại màu nút và con của nó
3. CXoay trái tại nút con, rồi xoay phải tại nút
4. DMột phép xoay trái đơn tại nút mất cân bằng

Tìm một khóa tùy ý trong đống min nhị phân n phần tử mất bao lâu?

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