*Một cơ sở dữ liệu gồm 1 triệu bản ghi.
Nếu mỗi bản ghi có khóa duy nhất thì cấu trúc dữ liệu nào dưới đây giúp tìm kiếm hiệu quả nhất?

A. Danh sách liên kết
B. Mảng chưa sắp xếp
C. Cây nhị phân cân bằng
D. Danh sách tuần tự

Gthich một cách logic , rõ ràng , dễ hiểu.

Question

*Một cơ sở dữ liệu gồm 1 triệu bản ghi.
Nếu mỗi bản ghi có khóa duy nhất thì cấu trúc dữ liệu nào dưới đây giúp tìm kiếm hiệu quả nhất?

A. Danh sách liên kết
B. Mảng chưa sắp xếp
C. Cây nhị phân cân bằng
D. Danh sách tuần tự

Gthich một cách logic , rõ ràng , dễ hiểu.

drained · Accepted Answer

{"userId":5035057,"userName":"NAKSU"}

Danh sách liên kết / Danh sách tuần tự không sắp xếp: Để tìm kiếm 1 bản ghi, bạn phải duyệt tuần tự từ đầu đến khi tìm thấy khóa khớp, độ phức tạp thời gian trung bình là O(n) với n = 1 triệu phần tử, rất chậm.

Mảng chưa sắp xếp: Cũng phải duyệt tuần tự toàn bộ dữ liệu, độ phức tạp cũng làO(n).

Cây nhị phân cân bằng (ví dụ cây AVL, cây đỏ-đen):

Đối với dữ liệu có khóa duy nhất, bạn có thể sắp xếp theo khóa và xây dựng cây nhị phân cân bằng. Thời gian tìm kiếm một phần tử chỉ là O(log 2n). Với 1 triệu bản ghi, chỉ cần khoảng 20 bước so sánh là đủ, đây là phương pháp hiệu quả nhất trong các lựa chọn.

=> chọn C

Timi · Answer

Để tìm kiếm hiệu quả nhất trong một cơ sở dữ liệu gồm 1 triệu bản ghi, mỗi bản ghi có khóa duy nhất, ta phân tích các cấu trúc dữ liệu được đề cập như sau:

A. Danh sách liên kết (Linked List):
- Tìm kiếm trong danh sách liên kết phải duyệt từng phần tử từ đầu đến cuối.
- Thời gian tìm kiếm trung bình là O(n), với n là số phần tử.
- Với 1 triệu bản ghi, tìm kiếm sẽ rất chậm.

B. Mảng chưa sắp xếp (Unsorted Array):
- Tương tự danh sách liên kết, phải duyệt từng phần tử để tìm khóa.
- Thời gian tìm kiếm trung bình cũng là O(n).
- Không hiệu quả với dữ liệu lớn.

C. Cây nhị phân cân bằng (Balanced Binary Search Tree):
- Cây nhị phân cân bằng như AVL, Red-Black Tree đảm bảo chiều cao cây là O(log n).
- Tìm kiếm trong cây nhị phân cân bằng có thời gian O(log n).
- Với 1 triệu bản ghi, log2(1,000,000) ≈ 20, tức là chỉ cần khoảng 20 bước để tìm kiếm.
- Rất hiệu quả cho tìm kiếm.

D. Danh sách tuần tự (Sequential List):
- Nếu danh sách tuần tự là mảng đã sắp xếp, có thể dùng tìm kiếm nhị phân O(log n).
- Nếu không sắp xếp, tìm kiếm vẫn O(n).
- Câu hỏi không nói rõ danh sách tuần tự có sắp xếp hay không, nên không chắc chắn.

Kết luận: Trong các lựa chọn, cây nhị phân cân bằng (C) là cấu trúc dữ liệu giúp tìm kiếm hiệu quả nhất với thời gian O(log n), phù hợp với cơ sở dữ liệu lớn như 1 triệu bản ghi.

**Đáp án đúng: C. Cây nhị phân cân bằng**

Katiee ୨୧ · Answer

{"userId":5035057,"userName":"NAKSU"}

$C.$

$-$ Để tìm kiếm hiệu quả nhất trong 1 triệu bản ghi, ta so sánh độ phức tạp thời gian của các cấu trúc dữ liệu

$-$ Mảng chưa sắp xếp $/$ Danh sách liên kết $/$ Danh sách tuần tự

$+$ Phải tìm kiếm tuần tự từ đầu đến cuối. Nếu không may bản ghi nằm ở cuối, ta phải duyệt qua cả 1 triệu phần tử. Thời gian tìm kiếm trung bình là tỷ lệ thuận với số phần tử $O(n)$

$-$ Cây nhị phân cân bằng

$+$ Dữ liệu được tổ chức theo dạng phân cấp. Mỗi lần so sánh khóa, ta sẽ loại bỏ được ngay một nửa số lượng bản ghi không phù hợp. Thời gian tìm kiếm cực kỳ nhanh, theo hàm logarit $O(\log n)$

*Một cơ sở dữ liệu gồm 1 triệu bản ghi. Nếu mỗi bản ghi có khóa duy nhất thì cấu trúc dữ liệu nào dưới đây giúp tìm kiếm hiệu quả nhất? A. Danh sách liên kết B. Mảng chưa sắp xếp C. Cây nhị phân cân b...