Thuật toán tham lam khác quy hoạch động thế nào?

Tham lam chốt một lựa chọn cục bộ và cần chứng minh rằng các lựa chọn ấy giữ được nghiệm tối ưu. Quy hoạch động so sánh phương án qua công thức truy hồi và tái dùng kết quả bài toán con. Tối ưu toàn cục đòi hỏi mô hình và truy hồi đúng, không chỉ nhãn “quy hoạch động”.

Tìm kiếm theo chiều sâu phát hiện chu trình trong đồ thị có hướng thế nào?

DFS đi sâu bằng đệ quy hoặc ngăn xếp tường minh. Cạnh đến đỉnh còn hoạt động trên đường DFS hiện tại là cạnh ngược và chứng minh có chu trình có hướng; cạnh đến một đỉnh đã thăm bất kỳ thì chưa đủ.

WHERE và HAVING khác nhau thế nào trong truy vấn có nhóm?

WHERE lọc hàng đầu vào trước khi nhóm. HAVING lọc các nhóm thu được và có thể dùng điều kiện tổng hợp, như COUNT(*)>1.

Điều gì làm một thuật toán sắp xếp ổn định?

Các phần tử có khóa bằng nhau giữ nguyên thứ tự tương đối ban đầu. Sắp xếp trộn có thể ổn định bằng cách lấy phần tử bên trái trước khi bằng khóa; quicksort tại chỗ thông thường thường không ổn định. Tính ổn định phụ thuộc cách cài đặt.

Khóa chính và khóa ngoại trong PostgreSQL khác nhau thế nào?

Khóa chính định danh hàng bằng các giá trị duy nhất, không NULL. Khóa ngoại yêu cầu giá trị khớp với khóa được tham chiếu, theo quy tắc NULL của nó. Nó có thể tham chiếu khóa UNIQUE hợp lệ hoặc khóa chính trong cùng bảng hay bảng khác.

Bellman–Ford xử lý cạnh âm và phát hiện chu trình âm tới được như thế nào?

Nới lỏng mọi cạnh tối đa V−1 lần. Nếu còn cải thiện từ một đỉnh tới được, có chu trình âm tới được từ nguồn. Thời gian xấu nhất là O(VE); các đỉnh tới được từ chu trình đó không có chi phí đường đi ngắn nhất hữu hạn.

Ghi nhớ kết quả và quy hoạch động từ dưới lên khác nhau thế nào?

Ghi nhớ kết quả tính bài toán con khi cần, thường bằng đệ quy, rồi lưu kết quả. Quy hoạch động từ dưới lên tính trạng thái theo thứ tự mà các trạng thái phụ thuộc đã có, thường bằng cách điền bảng.

Đọc bẩn là gì và mức cô lập chuẩn thấp nhất nào ngăn nó?

Đọc dữ liệu chưa commit của giao dịch khác, dù giao dịch đó có hoàn tác về sau hay không. READ COMMITTED và các mức cô lập chuẩn mạnh hơn cấm đọc bẩn.

Tìm kiếm theo chiều rộng tìm đường đi ngắn nhất trong đồ thị không trọng số như thế nào?

BFS dùng hàng đợi FIFO và duyệt đỉnh theo khoảng cách tính bằng số cạnh. Đánh dấu đỉnh lúc đưa vào hàng đợi tránh thăm lặp. Đường đầu tiên được phát hiện đến một đỉnh có thể tới được có số cạnh ít nhất.

WAL của PostgreSQL hỗ trợ tính bền vững thế nào khi commit đồng bộ thông thường?

Các bản ghi nhật ký liên quan phải được ghi vào bộ lưu trữ bền vững trước khi commit được xác nhận và trước khi ghi các trang dữ liệu đã đổi. Sau sự cố, WAL có thể phát lại các thay đổi còn thiếu trong trang dữ liệu. Commit bất đồng bộ có thể làm mất các giao dịch vừa được xác nhận.

Vì sao quy hoạch động hữu ích cho nhiều bài toán tối ưu?

Cấu trúc con tối ưu cho phép biểu diễn nghiệm tối ưu qua nghiệm tối ưu của bài toán con. Khi bài toán con trùng lặp, lưu kết quả tránh làm lại. Định nghĩa trạng thái và công thức truy hồi phải thể hiện đúng bài toán gốc.

Thứ tự tô pô là gì và thuật toán Kahn tìm nó thế nào?

Trong DAG, mỗi cạnh u→v yêu cầu u đứng trước v. Liên tục xuất một đỉnh có bậc vào bằng không rồi xóa các cạnh đi ra, đưa những đỉnh mới có bậc vào bằng không vào hàng đợi. Nếu xuất ít hơn V đỉnh, đồ thị có hướng có chu trình.

INNER JOIN và LEFT JOIN khác nhau thế nào?

INNER JOIN trả về các tổ hợp hàng thỏa điều kiện nối. LEFT JOIN còn giữ mỗi hàng bên trái không khớp, điền NULL cho các cột bên phải. Nhiều hàng bên phải khớp có thể tạo nhiều hàng kết quả cho một hàng bên trái.

Sắp xếp chèn hoạt động thế nào và điều gì quyết định thời gian với dữ liệu gần được sắp xếp?

Nó chèn từng phần tử vào một tiền tố đã sắp xếp. Bản thông thường dịch chuyển hoặc đổi chỗ các phần tử kề nhau tốn Θ(n+I), với I là số nghịch thế. Thời gian tuyến tính khi I=O(n); dữ liệu nhỏ tự nó không đổi cận xấu nhất Θ(n²).

Tìm kiếm nhị phân đòi hỏi gì và khi nào chạy trong thời gian O(log n)?

Nó liên tục chia đôi khoảng tìm kiếm trong dữ liệu đã được sắp theo thứ tự so sánh. Trên mảng có truy cập theo chỉ số O(1) và phép so sánh thời gian hằng số, tìm trong n phần tử tốn O(log n) thời gian.

Hai pha của khóa hai pha, 2PL, là gì?

Pha tăng trưởng: lấy khóa mà không nhả khóa. Pha thu hẹp: nhả khóa mà không lấy khóa mới. Với các khóa đọc/ghi xung đột phù hợp, 2PL bảo đảm lịch khả tuần tự theo xung đột, nhưng bế tắc vẫn có thể xảy ra.

Vì sao cây B+ hữu ích cho chỉ mục cơ sở dữ liệu và truy vấn khoảng?

Số nhánh lớn giữ cây nông, giảm truy cập trang. Khóa có thứ tự và các lá liên kết hỗ trợ quét khoảng. Chỉ mục băm hướng tới tìm kiếm bằng nhau, không tự cung cấp cách truy cập khoảng có thứ tự tương tự.

Dạng chuẩn thứ nhất, thứ hai và thứ ba yêu cầu gì?

1NF: giá trị thuộc tính nguyên tử. 2NF: đạt 1NF và không thuộc tính không khóa nào phụ thuộc vào một phần thực sự của bất kỳ khóa ứng viên nào. 3NF: đạt 1NF và với mọi phụ thuộc không tầm thường X→A, X là siêu khóa hoặc A là thuộc tính khóa. Thuộc tính khóa thuộc ít nhất một khóa ứng viên.

Khi nào thuật toán Dijkstra đúng và cận thường dùng với heap là gì?

Với trọng số cạnh không âm, nó liên tục chốt đỉnh có khoảng cách tạm thời nhỏ nhất. Cài đặt bằng danh sách kề và min-heap nhị phân tốn O((V+E) log V). Cạnh âm có thể làm lập luận về khoảng cách đã chốt không còn đúng.

Thuật toán Kruskal và Prim dựng cây khung nhỏ nhất như thế nào?

Với đồ thị liên thông, vô hướng, có trọng số, Kruskal xét cạnh theo trọng số tăng dần và dùng Union–Find để loại chu trình. Prim phát triển một cây bằng cách liên tục chọn cạnh nhẹ nhất nối cây với một đỉnh ngoài cây.

Đọc không lặp lại là gì và mức cô lập chuẩn nào ngăn nó?

Đọc lại một hàng thấy dữ liệu đã đổi hoặc hàng biến mất sau khi giao dịch khác commit cập nhật hay xóa. REPEATABLE READ và SERIALIZABLE cấm hiện tượng này.

Các thuộc tính giao dịch ACID có nghĩa gì?

Nguyên tử: tác động tất cả hoặc không gì cả. Nhất quán: giao dịch đúng giữ các ràng buộc và bất biến ứng dụng. Cô lập: hoạt động đồng thời tuân theo mức cô lập đã chọn. Bền vững: tác động đã commit tồn tại qua các lỗi thuộc phạm vi bảo đảm được cấu hình của cơ sở dữ liệu.

Thứ tự xử lý lôgic giản lược của truy vấn SQL SELECT là gì?

Với truy vấn không có CTE, hàm cửa sổ hay phép toán tập hợp: FROM/JOIN → WHERE → GROUP BY và tổng hợp → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Đây là mô hình lôgic, không nhất thiết là thứ tự thực thi vật lý của bộ tối ưu.

Công thức quy hoạch động cho độ dài dãy con chung dài nhất, LCS, là gì?

Gọi L[i,j] là độ dài LCS của các tiền tố dài i,j. Đặt L[0,j]=L[i,0]=0. Nếu ký tự cuối giống nhau, L[i,j]=1+L[i−1,j−1]; nếu không, L[i,j]=max(L[i−1,j],L[i,j−1]). Toàn bộ bảng dùng O(mn) thời gian và bộ nhớ.

Đọc bóng ma là gì và được ngăn như thế nào?

Lặp lại truy vấn theo một vị từ cho tập hàng khớp khác sau khi giao dịch khác commit thay đổi. SERIALIZABLE ngăn bóng ma trong mô hình chuẩn; một số cài đặt, gồm PostgreSQL REPEATABLE READ, cũng ngăn ở mức thấp hơn.

Chỉ mục rowstore có cụm và không có cụm trong SQL Server khác nhau thế nào?

Chỉ mục có cụm lưu các hàng bảng theo thứ tự khóa nên một bảng có tối đa một chỉ mục như vậy. Chỉ mục không có cụm có khóa và bộ định vị hàng riêng, có thể chứa thêm cột. Thuật ngữ và cách lưu trữ thay đổi giữa các hệ quản trị.

Sắp xếp trộn chuẩn trên mảng hoạt động thế nào, với cận thời gian và bộ nhớ nào?

Nó sắp xếp đệ quy hai nửa rồi trộn chúng trong thời gian tuyến tính. Bản chuẩn tốn Θ(n log n) thời gian và O(n) bộ nhớ phụ, giả sử phép so sánh có thời gian hằng số.

Công thức truy hồi chuẩn cho bài toán ba lô 0/1 với sức chứa nguyên W là gì?

Gọi D[i,w] là giá trị tốt nhất khi dùng i đồ vật đầu với sức chứa w và trọng lượng nguyên dương wᵢ. Đặt D[0,w]=0. Nếu wᵢ>w, sao chép D[i−1,w]; nếu không, lấy max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Thời gian O(NW) là giả đa thức.

Vì sao quicksort có thể tốn Θ(n²) thời gian và ngẫu nhiên hóa giúp thế nào?

Phân hoạch liên tục rất mất cân bằng, như luôn chọn khóa nhỏ nhất khi các khóa phân biệt, gây lượng công việc bậc hai. Với khóa phân biệt hoặc xử lý khóa trùng phù hợp, chọn chốt ngẫu nhiên cho thời gian kỳ vọng O(n log n). Chọn trung vị của ba là mẹo hữu ích, không bảo đảm cho trường hợp xấu nhất.

Ma trận kề và danh sách kề thông thường khác nhau thế nào?

Với V đỉnh và E cạnh, ma trận dùng O(V²) bộ nhớ và kiểm tra cạnh trong O(1). Danh sách dùng O(V+E) bộ nhớ; tìm cạnh (u,v) trong danh sách chưa sắp xếp tốn O(deg(u)), với deg(u) là độ dài danh sách đó.

Khi nào sắp xếp đếm hoặc sắp xếp cơ số có thời gian tuyến tính?

Sắp xếp đếm tốn O(n+k) cho n khóa trong miền k giá trị. Sắp xếp cơ số với d lượt sắp chữ số ổn định và cơ số b tốn O(d(n+b)). Chúng chỉ tuyến tính khi các tham số cho phép; chúng dùng cấu trúc khóa ngoài phép so sánh.

Heapsort tại chỗ có cận thời gian xấu nhất và bộ nhớ phụ nào?

Dựng heap tốn O(n), sau đó các lần lấy phần tử tốn tổng cộng O(n log n). Nếu thao tác vun xuống được cài đặt lặp ngay trên mảng đầu vào, heapsort tốn O(n log n) thời gian xấu nhất và O(1) bộ nhớ phụ.

Thuật toán, đồ thị, quy hoạch động và cơ sở dữ liệu quan hệ

32 thẻ ôn tập bậc đại học về sắp xếp, thuật toán đồ thị, quy hoạch động, SQL, chỉ mục và giao dịch. Cần kiến thức cơ bản về lập trình, cấu trúc dữ liệu và SQL.

Level: basic
Languages: vi → vi
Cards: 32
Markdown: Thuật toán, đồ thị, quy hoạch động và cơ sở dữ liệu quan hệ (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Thuật toán tham lam khác quy hoạch động thế nào?	Tham lam chốt một lựa chọn cục bộ và cần chứng minh rằng các lựa chọn ấy giữ được nghiệm tối ưu. Quy hoạch động so sánh phương án qua công thức truy hồi và tái dùng kết quả bài toán con. Tối ưu toàn cục đòi hỏi mô hình và truy hồi đúng, không chỉ nhãn “quy hoạch động”.
2	Tìm kiếm theo chiều sâu phát hiện chu trình trong đồ thị có hướng thế nào?	DFS đi sâu bằng đệ quy hoặc ngăn xếp tường minh. Cạnh đến đỉnh còn hoạt động trên đường DFS hiện tại là cạnh ngược và chứng minh có chu trình có hướng; cạnh đến một đỉnh đã thăm bất kỳ thì chưa đủ.
3	WHERE và HAVING khác nhau thế nào trong truy vấn có nhóm?	WHERE lọc hàng đầu vào trước khi nhóm. HAVING lọc các nhóm thu được và có thể dùng điều kiện tổng hợp, như COUNT(*)>1.
4	Điều gì làm một thuật toán sắp xếp ổn định?	Các phần tử có khóa bằng nhau giữ nguyên thứ tự tương đối ban đầu. Sắp xếp trộn có thể ổn định bằng cách lấy phần tử bên trái trước khi bằng khóa; quicksort tại chỗ thông thường thường không ổn định. Tính ổn định phụ thuộc cách cài đặt.
5	Khóa chính và khóa ngoại trong PostgreSQL khác nhau thế nào?	Khóa chính định danh hàng bằng các giá trị duy nhất, không NULL. Khóa ngoại yêu cầu giá trị khớp với khóa được tham chiếu, theo quy tắc NULL của nó. Nó có thể tham chiếu khóa UNIQUE hợp lệ hoặc khóa chính trong cùng bảng hay bảng khác.
6	Bellman–Ford xử lý cạnh âm và phát hiện chu trình âm tới được như thế nào?	Nới lỏng mọi cạnh tối đa V−1 lần. Nếu còn cải thiện từ một đỉnh tới được, có chu trình âm tới được từ nguồn. Thời gian xấu nhất là O(VE); các đỉnh tới được từ chu trình đó không có chi phí đường đi ngắn nhất hữu hạn.
7	Ghi nhớ kết quả và quy hoạch động từ dưới lên khác nhau thế nào?	Ghi nhớ kết quả tính bài toán con khi cần, thường bằng đệ quy, rồi lưu kết quả. Quy hoạch động từ dưới lên tính trạng thái theo thứ tự mà các trạng thái phụ thuộc đã có, thường bằng cách điền bảng.
8	Đọc bẩn là gì và mức cô lập chuẩn thấp nhất nào ngăn nó?	Đọc dữ liệu chưa commit của giao dịch khác, dù giao dịch đó có hoàn tác về sau hay không. READ COMMITTED và các mức cô lập chuẩn mạnh hơn cấm đọc bẩn.
9	Tìm kiếm theo chiều rộng tìm đường đi ngắn nhất trong đồ thị không trọng số như thế nào?	BFS dùng hàng đợi FIFO và duyệt đỉnh theo khoảng cách tính bằng số cạnh. Đánh dấu đỉnh lúc đưa vào hàng đợi tránh thăm lặp. Đường đầu tiên được phát hiện đến một đỉnh có thể tới được có số cạnh ít nhất.
10	WAL của PostgreSQL hỗ trợ tính bền vững thế nào khi commit đồng bộ thông thường?	Các bản ghi nhật ký liên quan phải được ghi vào bộ lưu trữ bền vững trước khi commit được xác nhận và trước khi ghi các trang dữ liệu đã đổi. Sau sự cố, WAL có thể phát lại các thay đổi còn thiếu trong trang dữ liệu. Commit bất đồng bộ có thể làm mất các giao dịch vừa được xác nhận.
11	Vì sao quy hoạch động hữu ích cho nhiều bài toán tối ưu?	Cấu trúc con tối ưu cho phép biểu diễn nghiệm tối ưu qua nghiệm tối ưu của bài toán con. Khi bài toán con trùng lặp, lưu kết quả tránh làm lại. Định nghĩa trạng thái và công thức truy hồi phải thể hiện đúng bài toán gốc.
12	Thứ tự tô pô là gì và thuật toán Kahn tìm nó thế nào?	Trong DAG, mỗi cạnh u→v yêu cầu u đứng trước v. Liên tục xuất một đỉnh có bậc vào bằng không rồi xóa các cạnh đi ra, đưa những đỉnh mới có bậc vào bằng không vào hàng đợi. Nếu xuất ít hơn V đỉnh, đồ thị có hướng có chu trình.
13	INNER JOIN và LEFT JOIN khác nhau thế nào?	INNER JOIN trả về các tổ hợp hàng thỏa điều kiện nối. LEFT JOIN còn giữ mỗi hàng bên trái không khớp, điền NULL cho các cột bên phải. Nhiều hàng bên phải khớp có thể tạo nhiều hàng kết quả cho một hàng bên trái.
14	Sắp xếp chèn hoạt động thế nào và điều gì quyết định thời gian với dữ liệu gần được sắp xếp?	Nó chèn từng phần tử vào một tiền tố đã sắp xếp. Bản thông thường dịch chuyển hoặc đổi chỗ các phần tử kề nhau tốn Θ(n+I), với I là số nghịch thế. Thời gian tuyến tính khi I=O(n); dữ liệu nhỏ tự nó không đổi cận xấu nhất Θ(n²).
15	Tìm kiếm nhị phân đòi hỏi gì và khi nào chạy trong thời gian O(log n)?	Nó liên tục chia đôi khoảng tìm kiếm trong dữ liệu đã được sắp theo thứ tự so sánh. Trên mảng có truy cập theo chỉ số O(1) và phép so sánh thời gian hằng số, tìm trong n phần tử tốn O(log n) thời gian.
16	Hai pha của khóa hai pha, 2PL, là gì?	Pha tăng trưởng: lấy khóa mà không nhả khóa. Pha thu hẹp: nhả khóa mà không lấy khóa mới. Với các khóa đọc/ghi xung đột phù hợp, 2PL bảo đảm lịch khả tuần tự theo xung đột, nhưng bế tắc vẫn có thể xảy ra.
17	Vì sao cây B+ hữu ích cho chỉ mục cơ sở dữ liệu và truy vấn khoảng?	Số nhánh lớn giữ cây nông, giảm truy cập trang. Khóa có thứ tự và các lá liên kết hỗ trợ quét khoảng. Chỉ mục băm hướng tới tìm kiếm bằng nhau, không tự cung cấp cách truy cập khoảng có thứ tự tương tự.
18	Dạng chuẩn thứ nhất, thứ hai và thứ ba yêu cầu gì?	1NF: giá trị thuộc tính nguyên tử. 2NF: đạt 1NF và không thuộc tính không khóa nào phụ thuộc vào một phần thực sự của bất kỳ khóa ứng viên nào. 3NF: đạt 1NF và với mọi phụ thuộc không tầm thường X→A, X là siêu khóa hoặc A là thuộc tính khóa. Thuộc tính khóa thuộc ít nhất một khóa ứng viên.
19	Khi nào thuật toán Dijkstra đúng và cận thường dùng với heap là gì?	Với trọng số cạnh không âm, nó liên tục chốt đỉnh có khoảng cách tạm thời nhỏ nhất. Cài đặt bằng danh sách kề và min-heap nhị phân tốn O((V+E) log V). Cạnh âm có thể làm lập luận về khoảng cách đã chốt không còn đúng.
20	Thuật toán Kruskal và Prim dựng cây khung nhỏ nhất như thế nào?	Với đồ thị liên thông, vô hướng, có trọng số, Kruskal xét cạnh theo trọng số tăng dần và dùng Union–Find để loại chu trình. Prim phát triển một cây bằng cách liên tục chọn cạnh nhẹ nhất nối cây với một đỉnh ngoài cây.
21	Đọc không lặp lại là gì và mức cô lập chuẩn nào ngăn nó?	Đọc lại một hàng thấy dữ liệu đã đổi hoặc hàng biến mất sau khi giao dịch khác commit cập nhật hay xóa. REPEATABLE READ và SERIALIZABLE cấm hiện tượng này.
22	Các thuộc tính giao dịch ACID có nghĩa gì?	Nguyên tử: tác động tất cả hoặc không gì cả. Nhất quán: giao dịch đúng giữ các ràng buộc và bất biến ứng dụng. Cô lập: hoạt động đồng thời tuân theo mức cô lập đã chọn. Bền vững: tác động đã commit tồn tại qua các lỗi thuộc phạm vi bảo đảm được cấu hình của cơ sở dữ liệu.
23	Thứ tự xử lý lôgic giản lược của truy vấn SQL SELECT là gì?	Với truy vấn không có CTE, hàm cửa sổ hay phép toán tập hợp: FROM/JOIN → WHERE → GROUP BY và tổng hợp → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Đây là mô hình lôgic, không nhất thiết là thứ tự thực thi vật lý của bộ tối ưu.
24	Công thức quy hoạch động cho độ dài dãy con chung dài nhất, LCS, là gì?	Gọi L[i,j] là độ dài LCS của các tiền tố dài i,j. Đặt L[0,j]=L[i,0]=0. Nếu ký tự cuối giống nhau, L[i,j]=1+L[i−1,j−1]; nếu không, L[i,j]=max(L[i−1,j],L[i,j−1]). Toàn bộ bảng dùng O(mn) thời gian và bộ nhớ.
25	Đọc bóng ma là gì và được ngăn như thế nào?	Lặp lại truy vấn theo một vị từ cho tập hàng khớp khác sau khi giao dịch khác commit thay đổi. SERIALIZABLE ngăn bóng ma trong mô hình chuẩn; một số cài đặt, gồm PostgreSQL REPEATABLE READ, cũng ngăn ở mức thấp hơn.
26	Chỉ mục rowstore có cụm và không có cụm trong SQL Server khác nhau thế nào?	Chỉ mục có cụm lưu các hàng bảng theo thứ tự khóa nên một bảng có tối đa một chỉ mục như vậy. Chỉ mục không có cụm có khóa và bộ định vị hàng riêng, có thể chứa thêm cột. Thuật ngữ và cách lưu trữ thay đổi giữa các hệ quản trị.
27	Sắp xếp trộn chuẩn trên mảng hoạt động thế nào, với cận thời gian và bộ nhớ nào?	Nó sắp xếp đệ quy hai nửa rồi trộn chúng trong thời gian tuyến tính. Bản chuẩn tốn Θ(n log n) thời gian và O(n) bộ nhớ phụ, giả sử phép so sánh có thời gian hằng số.
28	Công thức truy hồi chuẩn cho bài toán ba lô 0/1 với sức chứa nguyên W là gì?	Gọi D[i,w] là giá trị tốt nhất khi dùng i đồ vật đầu với sức chứa w và trọng lượng nguyên dương wᵢ. Đặt D[0,w]=0. Nếu wᵢ>w, sao chép D[i−1,w]; nếu không, lấy max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Thời gian O(NW) là giả đa thức.
29	Vì sao quicksort có thể tốn Θ(n²) thời gian và ngẫu nhiên hóa giúp thế nào?	Phân hoạch liên tục rất mất cân bằng, như luôn chọn khóa nhỏ nhất khi các khóa phân biệt, gây lượng công việc bậc hai. Với khóa phân biệt hoặc xử lý khóa trùng phù hợp, chọn chốt ngẫu nhiên cho thời gian kỳ vọng O(n log n). Chọn trung vị của ba là mẹo hữu ích, không bảo đảm cho trường hợp xấu nhất.
30	Ma trận kề và danh sách kề thông thường khác nhau thế nào?	Với V đỉnh và E cạnh, ma trận dùng O(V²) bộ nhớ và kiểm tra cạnh trong O(1). Danh sách dùng O(V+E) bộ nhớ; tìm cạnh (u,v) trong danh sách chưa sắp xếp tốn O(deg(u)), với deg(u) là độ dài danh sách đó.
31	Khi nào sắp xếp đếm hoặc sắp xếp cơ số có thời gian tuyến tính?	Sắp xếp đếm tốn O(n+k) cho n khóa trong miền k giá trị. Sắp xếp cơ số với d lượt sắp chữ số ổn định và cơ số b tốn O(d(n+b)). Chúng chỉ tuyến tính khi các tham số cho phép; chúng dùng cấu trúc khóa ngoài phép so sánh.
32	Heapsort tại chỗ có cận thời gian xấu nhất và bộ nhớ phụ nào?	Dựng heap tốn O(n), sau đó các lần lấy phần tử tốn tổng cộng O(n log n). Nếu thao tác vun xuống được cài đặt lặp ngay trên mảng đầu vào, heapsort tốn O(n log n) thời gian xấu nhất và O(1) bộ nhớ phụ.