Cấu trúc Dữ liệu, Phân tích Độ phức tạp (Big-O) và Thuật toán Cốt lõi

Ôn tập trình độ đại học, yêu cầu kiến thức lập trình cơ bản: 32 thẻ về mảng, danh sách, băm, cây, heap, trie, Union–Find, bộ lọc Bloom và độ phức tạp.

Category
Computer Science
Level
basic
Languages
vi → vi
Cards
32
Markdown
Cấu trúc Dữ liệu, Phân tích Độ phức tạp (Big-O) và Thuật toán Cốt lõi (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Trie là gì và khi nào tìm khóa dài L ký tự mất O(L)?Cây tiền tố lưu khóa dọc theo đường đi ký tự và đánh dấu khóa hoàn chỉnh. Tìm kiếm là O(L) nếu mỗi chuyển tiếp đến ký tự sau mất O(1).
2Duyệt trung tự một BST có khóa khác nhau cho kết quả gì?Tất cả khóa theo thứ tự tăng nghiêm ngặt, thăm n nút trong O(n).
3Điều kiện cân bằng AVL là gì?Tại mọi nút, chiều_cao(trái) − chiều_cao(phải) ∈ {−1, 0, 1}. Cây cũng phải thỏa bất biến thứ tự BST.
4Hàm băm cần có đặc tính gì để tra cứu bảng?Phải có tính xác định và phân bố tốt các khóa dự kiến. Băm khóa kích thước cố định có thể là O(1); băm một chuỗi mới dài L ký tự thường là O(L).
5Sửa mất cân bằng trái-phải sau một lần chèn AVL thế nào?Trước tiên xoay con trái sang trái, rồi xoay nút mất cân bằng sang phải.
6Thứ tự duyệt tiền tự, trung tự và hậu tự của cây nhị phân là gì?Tiền tự: nút → trái → phải. Trung tự: trái → nút → phải. Hậu tự: trái → phải → nút.
7Với các hàm không âm f và g, f(n) ∈ O(g(n)) nghĩa là gì?Có các hằng số c > 0 và n₀ ≥ 0 sao cho f(n) ≤ c·g(n) với mọi n ≥ n₀.
8Duyệt theo mức thăm cây nhị phân thế nào?Dùng hàng đợi FIFO để thăm từng mức độ sâu. Đưa con trái vào trước con phải để có thứ tự từ trái sang phải.
9Chi phí chèn, xóa gốc và xem gốc của heap nhị phân là gì?Lần lượt O(log n), O(log n) và O(1) nếu không cần đổi kích thước mảng. Đổi kích thước có thể tốn O(n).
10Hàng đợi dùng mảng vòng tránh dịch chuyển sau khi lấy phần tử ra thế nào?Chỉ số đầu và cuối quay vòng theo modulo dung lượng. Lấy ra chỉ đẩy chỉ số đầu lên, nên tái sử dụng được ô trống mà không di chuyển phần tử khác.
11Ngăn xếp hoạt động thế nào và khi nào các thao tác là O(1)?LIFO: phần tử vào sau cùng ra trước. Ở đầu danh sách liên kết, thêm, lấy ra và xem đỉnh đều là O(1); đổi kích thước mảng có thể khiến một lần thêm tốn O(n).
12O, Ω và Θ khác nhau thế nào?Lần lượt là cận trên, cận dưới và cận chặt tiệm cận. Chúng mô tả một hàm chi phí xác định; bản thân O không có nghĩa là trường hợp xấu nhất.
13Phương pháp nối chuỗi riêng giải quyết xung đột băm thế nào?Mỗi ngăn chứa tập hợp các mục có chỉ số ngăn đó, thường bằng danh sách liên kết. Các khóa khác nhau cùng ngăn vẫn là các mục riêng biệt.
14Bất biến thứ tự nào xác định cây tìm kiếm nhị phân (BST) với khóa khác nhau?Ở mỗi nút, mọi khóa trong cây con trái đều nhỏ hơn và mọi khóa trong cây con phải đều lớn hơn. Quy tắc áp dụng đệ quy.
15Khi dung lượng được nhân đôi, chi phí khấu hao của việc thêm vào cuối mảng động là bao nhiêu?O(1) mỗi lần thêm. Một lần đổi kích thước có thể tốn O(n), nhưng n lần thêm từ mảng rỗng chỉ tốn tổng cộng O(n).
16Hai tính chất xác định heap nhị phân nhỏ nhất là gì?Đó là cây nhị phân hoàn chỉnh, và khóa của mỗi nút cha không lớn hơn khóa các nút con. Vì vậy gốc chứa một giá trị nhỏ nhất.
17Chi phí kỳ vọng và xấu nhất của bảng băm dùng nối chuỗi riêng là gì?Với tải bị chặn, băm phân bố tốt và thao tác khóa có chi phí hằng số, tìm/xóa có kỳ vọng O(1). Chèn với tăng dung lượng theo cấp số nhân có chi phí khấu hao kỳ vọng O(1). Chuỗi n khóa xung đột có thể làm thao tác thành O(n).
18Bộ lọc Bloom chỉ cho phép chèn có thể trả lời gì?Kết quả âm nghĩa là phần tử chưa được chèn; dương nghĩa là có thể đã được chèn. Các hàm băm đặt bit trong mảng bit: có thể có dương tính giả, nhưng không có âm tính giả nếu trạng thái nguyên vẹn.
19Xây heap từ dưới lên với n phần tử tốn bao nhiêu?O(n). Phần lớn nút gần lá nên cần ít bước đẩy xuống; cộng công việc theo chiều cao nút cho tổng tuyến tính.
20So sánh chèn đầu và truy cập theo chỉ số ở danh sách liên kết đơn và mảng động.Danh sách: chèn đầu O(1), truy cập theo chỉ số O(n). Mảng: chèn đầu O(n), truy cập theo chỉ số O(1); chèn đầu phải dịch các phần tử.
21find và union làm gì trong cấu trúc các tập hợp rời nhau?find(x) trả về đại diện của tập chứa x. union(x,y) hợp nhất hai tập nếu khác nhau; nếu đã cùng tập thì phân hoạch không đổi.
22Nén đường đi, hợp nhất theo hạng và theo kích thước khác nhau thế nào?Nén chuyển các nút đã thăm về gốc. Theo hạng, gốc hạng thấp nối dưới gốc hạng cao; theo kích thước, tập nhỏ nối dưới tập lớn. Hạng không nhất thiết bằng chiều cao hiện tại.
23Vì sao danh sách liên kết đôi xóa được một nút đã cho trong O(1)?Các liên kết trước và sau cho phép nối lại trực tiếp hai nút lân cận. Cập nhật đầu/cuối khi cần; không phải tìm nút đứng trước.
24Trong mảng heap dài n đánh chỉ số từ 0, cha và con của nút i nằm ở đâu?Cha: ⌊(i−1)/2⌋ khi i>0. Con: 2i+1 và 2i+2, chỉ khi các chỉ số này nhỏ hơn n. Chỉ số 0 không có cha.
25Hệ số tải của bảng băm là gì và vì sao bảng có thể đổi kích thước?α = n/m: n mục đã lưu và m ngăn hoặc ô. Vượt ngưỡng của cách cài đặt có thể dẫn đến tăng kích thước và băm lại; 0,75 không phải ngưỡng chung.
26Các quy tắc màu nào giữ BST đỏ-đen cân bằng?Nút có màu đỏ hoặc đen; gốc và lá NIL màu đen. Nút đỏ không có con đỏ. Mọi đường từ một nút đến lá NIL hậu duệ có cùng số nút đen. Các quy tắc này chặn chiều cao ở O(log n).
27Chi phí khấu hao của union/find với nén đường đi và hợp nhất theo hạng là gì?O(α(n)) mỗi thao tác, với α là hàm Ackermann nghịch đảo và n là số phần tử. Khởi tạo tốn O(n); cận áp dụng cho chuỗi thao tác, không khẳng định mỗi lần gọi đều có chi phí xấu nhất hằng số.
28Tìm kiếm, chèn và xóa trong BST phụ thuộc chiều cao h ra sao?Mất O(h). Cây cân bằng có h = O(log n), còn dạng chuỗi có h = O(n). Kỳ vọng O(log n) cần giả định như thứ tự chèn ngẫu nhiên.
29Dò tuyến tính và dò bậc hai trong địa chỉ mở khác nhau thế nào?Các mục vẫn nằm trong mảng. Với kích thước bảng m và chỉ số ban đầu h, lần lượt dò (h+i) mod m hoặc (h+c₁i+c₂i²) mod m. Dò bậc hai cần tham số phù hợp.
30Quy tắc truy cập và chi phí thao tác thường gặp của hàng đợi là gì?FIFO: thêm ở cuối, lấy ở đầu. Cả hai là O(1) với liên kết đầu/cuối hoặc bộ đệm vòng có dung lượng cố định; dịch mảng làm thao tác lấy ra thành O(n).
31Xếp các tốc độ tăng từ chậm đến nhanh khi n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.Về tiệm cận: 1 < log n < n < n log n < n² < 2ⁿ < n!.
32Vì sao truy cập theo chỉ số trong mảng kích thước cố định là O(1)?Các ô có cùng kích thước nằm liên tiếp: địa_chỉ(i) = địa_chỉ_gốc + i·kích_thước_ô. Giả định việc tính địa chỉ mất thời gian hằng số.