Đề thi, bài tập trắc nghiệm online Cấu trúc dữ liệu và giải thuật – Đề 6

Trong trường hợp tốt nhất và trung bình, tìm kiếm trong bảng băm có độ phức tạp thời gian là O(1) khi hàm băm phân phối các khóa đều và xung đột được giải quyết tốt. Trong trường hợp xấu nhất (tất cả khóa băm vào cùng một vị trí), nó có thể trở thành O(n).

Sắp xếp nổi bọt (Bubble Sort) là một giải thuật sắp xếp tại chỗ (in-place), nghĩa là nó không yêu cầu thêm không gian bộ nhớ đáng kể ngoài mảng đầu vào. Độ phức tạp không gian của nó là O(1) vì nó chỉ sử dụng một vài biến phụ trợ.

Ngăn xếp (Stack) hoạt động theo nguyên tắc LIFO, nghĩa là phần tử cuối cùng được thêm vào sẽ là phần tử đầu tiên được lấy ra. Hàng đợi (Queue) hoạt động theo FIFO, danh sách liên kết và cây nhị phân không bị ràng buộc bởi nguyên tắc LIFO hoặc FIFO.

Trong trường hợp tốt nhất, khi mảng đầu vào đã được sắp xếp, giải thuật sắp xếp chèn (Insertion Sort) chỉ cần duyệt qua mảng một lần để xác nhận rằng nó đã được sắp xếp, do đó độ phức tạp thời gian tốt nhất là O(n).

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp theo kiểu chia để trị, hoạt động bằng cách đệ quy chia mảng thành các nửa nhỏ hơn cho đến khi mỗi nửa chỉ chứa một phần tử, sau đó trộn các nửa đã sắp xếp lại để tạo thành mảng đã sắp xếp.

Giải thuật Dijkstra là giải thuật kinh điển để tìm đường đi ngắn nhất trong đồ thị có trọng số không âm. BFS tìm đường đi ngắn nhất trong đồ thị vô hướng hoặc có trọng số bằng nhau. DFS không đảm bảo tìm đường đi ngắn nhất. Sắp xếp tô pô dùng cho đồ thị có hướng không chu trình.

Đồ thị (Graph) là cấu trúc dữ liệu mạnh mẽ để mô hình hóa các mối quan hệ mạng lưới hoặc không tuần tự giữa các đối tượng. Các nút (vertices) đại diện cho đối tượng, và các cạnh (edges) đại diện cho mối quan hệ giữa chúng. Cây mô hình hóa mối quan hệ thứ bậc, danh sách và mảng mô hình hóa mối quan hệ tuyến tính/tuần tự.

Giải thuật Dijkstra là một ví dụ điển hình của giải thuật tham lam. Nó đưa ra lựa chọn tối ưu cục bộ (chọn nút gần nhất chưa được thăm) tại mỗi bước với hy vọng tìm ra đường đi ngắn nhất toàn cục. Các giải thuật khác không thuộc loại tham lam.

Giải thuật tìm kiếm theo chiều rộng (BFS) sử dụng hàng đợi (Queue) để quản lý các nút cần thăm. BFS thăm các nút theo từng mức, bắt đầu từ nút gốc, thăm tất cả các nút lân cận trước khi chuyển sang mức tiếp theo. Hàng đợi FIFO đảm bảo thứ tự thăm theo chiều rộng.

Sắp xếp chèn (Insertion Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2), xảy ra khi mảng đầu vào đã được sắp xếp ngược lại. Sắp xếp trộn và sắp xếp vun đống có độ phức tạp O(n log n) trong mọi trường hợp. Sắp xếp nhanh có thể đạt O(n^2) trong trường hợp xấu nhất nhưng thường tránh được trong thực tế bằng cách chọn pivot ngẫu nhiên.

Mục đích chính của việc cân bằng cây nhị phân là để đảm bảo rằng cây không bị lệch quá nhiều, duy trì chiều cao của cây ở mức logarit so với số lượng nút. Điều này đảm bảo rằng các thao tác như tìm kiếm, thêm, xóa có độ phức tạp thời gian O(log n) trong trường hợp xấu nhất.

Sắp xếp tô pô (Topological Sort) là giải thuật để tạo ra một thứ tự tuyến tính của các đỉnh trong đồ thị có hướng không chu trình (DAG) sao cho với mọi cạnh có hướng từ đỉnh u đến đỉnh v, đỉnh u luôn xuất hiện trước đỉnh v trong thứ tự đó. Nó thường được dùng trong các bài toán phụ thuộc công việc.

Nút gốc (root) trong cây là nút duy nhất không có nút cha. Tất cả các nút khác đều là con cháu của nút gốc. Nút không có nút con là nút lá, không phải nút gốc.

Ma trận kề (Adjacency Matrix) là một cách biểu diễn đồ thị, trong đó phần tử ở hàng i, cột j là 1 (hoặc true) nếu có cạnh nối nút i và nút j, và 0 (hoặc false) nếu không có cạnh. Nó thể hiện sự tồn tại của cạnh giữa các cặp nút.

Tìm kiếm nhị phân (Binary Search) chỉ hoạt động trên dữ liệu đã được sắp xếp. Giải thuật này dựa vào việc so sánh phần tử cần tìm với phần tử ở giữa mảng và loại bỏ một nửa không gian tìm kiếm ở mỗi bước. Dữ liệu không sắp xếp sẽ không đảm bảo tính đúng đắn của giải thuật.

Tìm kiếm theo chiều sâu (DFS) là một giải thuật hiệu quả để phát hiện chu trình trong đồ thị. Trong quá trình DFS, nếu gặp lại một nút đã được thăm trong cùng một nhánh đệ quy, điều đó chứng tỏ có chu trình. BFS cũng có thể được sử dụng nhưng DFS thường đơn giản hơn cho việc phát hiện chu trình.

Tuyến tính hóa (Linear Probing) là một phương pháp giải quyết xung đột trong bảng băm, trong đó khi có xung đột, giải thuật sẽ tìm kiếm vị trí trống kế tiếp một cách tuần tự để chèn khóa mới. Các phương pháp khác không phải là phương pháp giải quyết xung đột phổ biến hoặc hiệu quả.

Tìm kiếm một nút trong cây nhị phân tìm kiếm cân bằng có độ phức tạp thời gian trung bình là O(log n) vì mỗi bước tìm kiếm giảm một nửa không gian tìm kiếm. Các thao tác duyệt cây thường có độ phức tạp O(n) vì cần truy cập tất cả các nút.

Cây nhị phân tìm kiếm trở thành cây suy biến (skewed tree) khi các nút được thêm vào theo thứ tự đã sắp xếp (tăng dần hoặc giảm dần). Trong trường hợp này, cây trở nên giống như danh sách liên kết, và độ phức tạp thời gian cho các thao tác tìm kiếm, thêm, xóa trở thành O(n), kém hiệu quả nhất.

Hàm băm (hash function) trong bảng băm có vai trò quan trọng là tính toán địa chỉ lưu trữ (vị trí index) cho mỗi khóa. Hàm băm lý tưởng sẽ phân phối các khóa đều khắp bảng để giảm thiểu xung đột và đảm bảo hiệu suất tìm kiếm gần O(1).

Danh sách liên kết đôi cho phép duyệt cả về phía trước và phía sau do mỗi nút chứa con trỏ đến nút trước đó. Danh sách liên kết đơn chỉ cho phép duyệt một chiều. Các ưu điểm khác không phải là ưu điểm chính của danh sách liên kết đôi so với đơn.

Mảng (Array) cho phép truy cập phần tử ngẫu nhiên (tức là truy cập phần tử tại một chỉ số cụ thể) với độ phức tạp thời gian O(1) vì vị trí bộ nhớ của mỗi phần tử có thể được tính toán trực tiếp dựa trên chỉ số của nó. Các cấu trúc dữ liệu khác không có tính chất này.

Heap (đặc biệt là binary heap) là cấu trúc dữ liệu hiệu quả nhất để cài đặt hàng đợi ưu tiên vì nó cho phép các thao tác thêm và loại bỏ phần tử ưu tiên cao nhất với độ phức tạp thời gian O(log n). Mảng và danh sách liên kết có thể cài đặt hàng đợi ưu tiên nhưng kém hiệu quả hơn.

Sắp xếp nhanh (Quick Sort) có độ phức tạp thời gian trung bình là O(n log n) và thường nhanh hơn các giải thuật sắp xếp O(n log n) khác trong thực tế do hệ số hằng số nhỏ hơn. Các giải thuật còn lại thường có độ phức tạp O(n^2) hoặc kém hiệu quả hơn trong trường hợp trung bình.

Sắp xếp trộn (Merge Sort) không phải là giải thuật sắp xếp tại chỗ (in-place). Nó cần không gian bộ nhớ phụ trợ để trộn các nửa mảng đã sắp xếp. Độ phức tạp không gian của nó là O(n) vì nó cần một mảng tạm thời có kích thước tương đương với mảng đầu vào trong quá trình trộn.

Ngăn xếp (Stack) là cấu trúc dữ liệu lý tưởng để kiểm tra tính hợp lệ của dấu ngoặc. Khi gặp dấu mở ngoặc, đẩy nó vào stack. Khi gặp dấu đóng ngoặc, kiểm tra stack có rỗng không và có dấu mở ngoặc tương ứng trên đỉnh stack không. Nếu cuối cùng stack rỗng, dấu ngoặc hợp lệ.

Cây (Tree) là cấu trúc dữ liệu tự nhiên để biểu diễn quan hệ 'cha-con' hoặc hệ thống phân cấp. Mỗi nút (ngoại trừ nút gốc) có một nút cha và có thể có nhiều nút con. Cây thư mục, cây tổ chức, cây quyết định đều là ví dụ điển hình.

Khi thêm hoặc xóa phần tử ở giữa danh sách, danh sách liên kết (Linked List) hiệu quả hơn mảng (Array). Trong mảng, cần dịch chuyển các phần tử phía sau vị trí thêm/xóa, tốn thời gian O(n). Trong danh sách liên kết, chỉ cần thay đổi con trỏ của các nút lân cận, tốn thời gian O(1) sau khi tìm được vị trí.

Sắp xếp nổi bọt (Bubble Sort) hoạt động bằng cách lặp đi lặp lại qua danh sách, so sánh các cặp phần tử liền kề và 'nổi' phần tử lớn hơn (hoặc nhỏ hơn) lên vị trí đúng của nó ở mỗi lần lặp. Đây là một giải thuật đơn giản nhưng kém hiệu quả cho dữ liệu lớn.

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp ổn định và hiệu quả với dữ liệu lớn, đặc biệt là dữ liệu không thể chứa hết trong bộ nhớ chính (external sorting). Tính ổn định (giữ nguyên thứ tự tương đối của các phần tử bằng nhau) và hiệu suất O(n log n) trong mọi trường hợp làm cho nó phù hợp cho các ứng dụng này.