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. BTheo thứ tự ngẫu nhiên
3. CLớn hơn giá trị của nút
4. DNhỏ hơn giá trị của nút

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. BNgăn xếp
3. CHàng đợi ưu tiên
4. DBảng băm

Đặ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ó chỉ cho phép truy cập ở một đầu
4. DNó lưu các phần tử theo thứ tự đã sắp

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

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

Bộ đệm vòng (circular buffer, ring buffer) thường được dùng để cài đặt:

1. AHàng đợi kích thước cố định
2. BHàm băm
3. CPhép duyệt đồ thị
4. DCây tìm kiếm nhị phân

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

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

Một nút AVL mất cân bằng vì cây con phải của con trái nó trở nên quá cao (trường hợp trái-phải). Cách sửa nào được áp dụng?

1. AMột phép xoay trái đơn tại nút
2. BXoay trái tại con trái, rồi xoay phải tại nút
3. CXoay phải tại con trái, rồi xoay trái tại nút
4. DMột phép xoay phải đơn tại nút

Cây Fenwick (cây chỉ mục nhị phân) trên một mảng n số hỗ trợ những thao tác nào trong O(log n)?

1. ASắp xếp mảng và tìm kiếm nhị phân
2. BTruy vấn tổng tiền tố và cập nhật một phần tử
3. CTìm trung vị trong O(1)
4. DChèn phần tử vào vị trí bất kỳ