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

Trong cây tìm kiếm nhị phân, các giá trị ở cây con bên trái của một nút:

1. ABằng giá trị của nút
2. BNhỏ hơn giá trị của nút
3. CTheo thứ tự ngẫu nhiên
4. DLớn hơn giá trị của nút

Trong đồ thị vô hướng, bậc của một đỉnh là gì?

1. ASố đỉnh trong đồ thị
2. BĐộ dài đường đi dài nhất từ nó
3. CVị trí của nó trong danh sách kề
4. DSố cạnh nối với nó

Deque (hàng đợi hai đầu) là gì?

1. AHai hàng đợi riêng biệt dùng chung một mảng
2. BMột hàng đợi chỉ cho phép xóa ở cuối
3. CMột hàng đợi được sắp theo ưu tiên
4. DMột cấu trúc cho phép chèn và xóa ở cả hai đầu

Trong hàng đợi vòng lưu trong mảng có sức chứa n, vị trí kế tiếp sau chỉ số i được tính thế nào?

1. Ai + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. D2i + 1

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

1. AChè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í
2. BĐặt nó ở gốc và đẩy xuống
3. CĐặt nó ở cuối mảng và đẩy lên trong khi nó vi phạm tính chất đống
4. DXây lại toàn bộ đống từ đầu

Các khóa 50, 30, 70, 20, 40 được chèn theo thứ tự này vào một cây tìm kiếm nhị phân rỗng. Con trái của 30 là gì?

1. A40
2. B50
3. C70
4. D20

Tính chất nào mà cây đỏ-đen phải thỏa mãn?

1. AMọi nút phải là đỏ
2. BMọi nút đỏ phải có các con màu đỏ, nên các nút đỏ luôn tạo thành chuỗi liền mạch đến các lá
3. CMọi đường đi từ một nút đến các lá hậu duệ có cùng số nút đen
4. DGốc phải là đỏ

Ư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. ATì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
2. BTìm kiếm kỳ vọng O(log n) nhờ dùng nhiều tầng con trỏ tiến
3. CNó lưu khóa không có thứ tự
4. DNó không dùng thêm bộ nhớ