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

Một cây có n nút thì có bao nhiêu cạnh?

1. An + 1
2. Bn
3. Cn − 1
4. D2n

Cấu trúc dữ liệu nào hoạt động theo nguyên tắc "vào sau, ra trước"?

1. ANgăn xếp (stack)
2. BBảng băm
3. CDanh sách liên kết
4. DHàng đợi (queue)

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. ANhỏ hơn giá trị của nút
2. BBằng 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

Vì sao đống nhị phân có thể lưu trong mảng mà không cần con trỏ?

1. AĐống không bao giờ chứa quá 100 phần tử
2. BMảng tự động giữ các khóa theo thứ tự đã sắp, nên không cần con trỏ
3. CMọi khóa trong đống đều bằng nhau
4. DNó là cây nhị phân đầy đủ, nên các vị trí tuân theo công thức chỉ số đơn giản

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

Độ 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)
2. BO(n log n)
3. CO(1)
4. DO(log n)

Trong bảng băm dùng địa chỉ mở, vì sao việc xóa thường được thực hiện bằng dấu "tombstone"?

1. ALàm trống ô có thể phá vỡ chuỗi dò của các khóa khác
2. BNó làm bảng được sắp xếp
3. CTombstone làm băm nhanh hơn
4. DCác khóa đã xóa phải được giữ mãi vì lý do bảo mật, nên các ô không bao giờ được tái sử dụng

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