C.Số mili-giây thuật toán chạy trên một máy cụ thể
D.Lượng RAM tối đa tiến trình được phép cấp phát
Đáp án: B
Big-O mô tả tốc độ tăng của chi phí theo kích thước đầu vào n, không phải thời gian chạy tuyệt đối. Nói một hàm là O(n) nghĩa là khi n tăng gấp đôi thì chi phí tăng khoảng gấp đôi. Đây là cách so sánh thuật toán mà không phụ thuộc máy, ngôn ngữ hay chất lượng trình biên dịch.
Hai vòng lặp lồng nhau, mỗi vòng chạy hết mảng n phần tử, có độ phức tạp thời gian là gì?
javascript
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
check(a[i], a[j])
}
}
A.O(n)
B.O(n²)
C.O(2n)
D.O(n log n)
Đáp án: B
O(n²). Vòng ngoài chạy n lần, mỗi lần vòng trong chạy thêm n lần, nên check được gọi n × n lần. Dấu hiệu nhận biết: vòng lặp lồng mà cả hai đều phụ thuộc n. Nếu vòng trong chạy số lần cố định thì vẫn là O(n).
Câu 3·Mảng & chuỗi
Vì sao chèn phần tử vào đầu mảng tốn O(n) còn thêm vào cuối chỉ tốn O(1)?
A.Chèn đầu buộc mọi phần tử sau dịch một ô
B.Vì chèn đầu phải tính lại hàm băm của mảng
C.Vì thêm vào cuối được lưu đệm và ghi sau
D.Vì phần đầu mảng nằm ở vùng nhớ chỉ đọc
Đáp án: A
Mảng lưu các phần tử liền nhau và truy cập bằng công thức địa chỉ = gốc + chỉ số × kích thước. Chèn vào đầu làm chỉ số của mọi phần tử cũ tăng 1, nên phải dịch n phần tử. Thêm vào cuối chỉ ghi một ô còn trống nên là O(1) khấu hao.
Câu 4·Mảng & chuỗi
Nối chuỗi bằng s += x trong vòng lặp n lần ở ngôn ngữ có chuỗi bất biến dẫn tới điều gì?
A.Chi phí O(n) vì trình biên dịch luôn gộp các phép nối lại
B.Rò rỉ bộ nhớ vì các chuỗi trung gian không được giải phóng
C.Lỗi thời gian chạy khi chuỗi vượt quá dung lượng ban đầu
D.Chi phí O(n²) do mỗi lần nối tạo chuỗi mới và sao chép lại
Đáp án: D
O(n²). Chuỗi bất biến nghĩa là s += x tạo ra một chuỗi mới và sao chép lại toàn bộ nội dung cũ, nên lần thứ i tốn khoảng i bước. Tổng 1 + 2 + … + n là O(n²). Cách đúng là gom các mảnh vào mảng rồi join một lần, hoặc dùng bộ dựng chuỗi của ngôn ngữ.
Câu 5·Hash map & set
Vì sao tra cứu theo khoá trong hash map thường là O(1)?
A.Các khoá được giữ sắp xếp nên tìm kiếm nhị phân rất nhanh
B.Vì mỗi ô chỉ chứa đúng một khoá nên không bao giờ phải so sánh
C.Hàm băm biến khoá thành chỉ số ô để truy cập thẳng
D.Toàn bộ bảng được nạp sẵn vào cache của CPU
Đáp án: C
Hàm băm biến khoá thành một số, lấy dư theo số ô là ra vị trí cần tìm, nên không phải duyệt phần tử nào. Chi phí gồm tính băm cộng vài phép so sánh trong ô, không phụ thuộc n. Đây là trung bình, không phải bảo đảm cho mọi trường hợp.
Câu 6·Hai con trỏ & cửa sổ trượt
Trên mảng đã sắp xếp tăng dần, hai con trỏ ở hai đầu tìm cặp có tổng bằng đích. Khi tổng hiện tại nhỏ hơn đích thì làm gì?
A.Dịch con trỏ trái sang phải một bước
B.Bắt đầu lại từ đầu với con trỏ phải mới
C.Dịch cả hai con trỏ vào giữa cùng lúc
D.Dịch con trỏ phải sang trái một bước
Đáp án: A
Dịch con trỏ trái sang phải. Vì mảng tăng dần, chỉ có tăng đầu trái mới làm tổng lớn lên. Ngược lại, tổng lớn hơn đích thì lùi con trỏ phải. Mỗi bước loại bỏ chắc chắn một khả năng, nên toàn bộ chạy trong O(n) với O(1) bộ nhớ.
Câu 7·Ngăn xếp & hàng đợi
Kiểm tra chuỗi ngoặc có cân bằng hay không thì ngăn xếp phù hợp vì sao?
A.Ngoặc đóng phải khớp ngoặc mở gần nhất chưa đóng
B.Ngăn xếp đếm được số ngoặc mở mà không cần lưu chúng
C.Ngăn xếp cho phép truy cập phần tử bất kỳ trong O(1)
D.Ngăn xếp giữ các ngoặc theo thứ tự đã sắp xếp
Đáp án: A
Vì quy tắc ngoặc là vào sau ra trước: một ngoặc đóng phải khớp với ngoặc mở gần nhất còn chưa đóng, đúng ngữ nghĩa của ngăn xếp. Gặp ngoặc mở thì đẩy vào, gặp ngoặc đóng thì lấy đỉnh ra so khớp. Chuỗi hợp lệ khi không lệch giữa chừng và ngăn xếp rỗng lúc kết thúc.
Câu 8·Tìm kiếm nhị phân
Điều kiện bắt buộc để áp dụng tìm kiếm nhị phân là gì?
A.Mảng phải nằm liên tục trong bộ nhớ vật lý
B.Dữ liệu phải nằm trong mảng có kích thước là luỹ thừa của hai
C.Không gian tìm kiếm phải có tính đơn điệu rõ ràng
D.Các phần tử phải khác nhau đôi một
Đáp án: C
Không gian tìm kiếm phải đơn điệu: sau mỗi phép so sánh phải kết luận chắc chắn đáp án nằm ở nửa nào. Dãy sắp xếp là trường hợp quen thuộc nhất, nhưng điều kiện thật sự là tính đơn điệu của vị từ, chứ không phải bản thân việc dữ liệu được sắp xếp.
Quicksort trung bình là O(n log n) nhưng xấu nhất là O(n²). Trường hợp xấu nhất xảy ra khi nào?
A.Khi số phần tử không phải luỹ thừa của hai
B.Khi mảng quá lớn để nằm vừa trong cache CPU
C.Khi chốt luôn là phần tử nhỏ nhất hoặc lớn nhất
D.Khi mảng có nhiều phần tử trùng giá trị nhau
Đáp án: C
Khi mọi lần phân hoạch đều lệch tối đa: chốt là phần tử nhỏ nhất hoặc lớn nhất, nên một bên rỗng và bên kia còn n − 1 phần tử. Độ sâu đệ quy thành n, tổng chi phí O(n²). Chọn chốt cố định ở đầu mảng gặp đúng trường hợp này khi dữ liệu đã sắp xếp sẵn.
Câu 10·Sắp xếp
Cần sắp danh sách nhân viên theo phòng ban tăng dần, cùng phòng thì lương giảm dần. Cách gọn nhất là gì?
A.Ghép phòng ban và lương thành chuỗi rồi sắp theo chuỗi đó
B.Nhóm theo phòng ban rồi sắp từng nhóm bằng thuật toán riêng
C.Sắp theo phòng ban trước rồi sắp lại toàn bộ theo lương
D.Một hàm so sánh: so phòng ban trước, bằng nhau so lương
Đáp án: D
Viết một hàm so sánh nhiều khoá: trả về kết quả so phòng ban trước, chỉ khi bằng nhau mới so lương theo chiều ngược. Một lượt sắp xếp là đủ và thứ tự ưu tiên nằm ngay trong mã. Nếu ngôn ngữ bảo đảm sắp xếp ổn định thì cách sắp hai lần từ khoá phụ tới khoá chính cũng đúng.
Câu 11·Cây & BST
Cây tìm kiếm nhị phân cho tra cứu O(log n), nhưng có trường hợp thành O(n). Khi nào?
A.Khi số nút vượt quá dung lượng cache của CPU
B.Khi cây có nhiều lá hơn nút trong
C.Khi cây chứa nhiều giá trị âm lẫn giá trị dương
D.Khi cây suy biến thành một chuỗi thẳng đứng
Đáp án: D
Khi cây suy biến thành chuỗi thẳng. Chèn 1, 2, 3, … theo thứ tự tăng dần khiến mọi nút chỉ có con phải, chiều cao bằng n, và tra cứu thành duyệt tuyến tính. Chi phí BST là O(chiều cao), chỉ bằng O(log n) khi cây được giữ cân bằng.
Câu 12·Đồ thị
Tìm đường đi ít cạnh nhất giữa hai đỉnh trên đồ thị không trọng số thì dùng gì?
A.Duyệt theo chiều sâu và ghi lại đường ngắn nhất tìm được
B.Duyệt theo chiều rộng từ đỉnh xuất phát
C.Sắp xếp tô-pô rồi lấy hiệu vị trí hai đỉnh
D.Thuật toán Dijkstra với priority queue
Đáp án: B
BFS. Vì queue thăm các đỉnh theo thứ tự khoảng cách tăng dần, lần đầu chạm tới đích chính là đường ít cạnh nhất. Chi phí O(V + E). Muốn dựng lại đường đi thì lưu thêm đỉnh cha của mỗi đỉnh rồi lần ngược từ đích.
Câu 13·Đệ quy & quay lui
Thành phần nào bắt buộc phải có trong mọi hàm đệ quy?
A.Một tham số đếm số lần đã gọi
B.Một cấu trúc phụ để lưu kết quả trung gian
C.Giá trị trả về khác kiểu với tham số đầu vào
D.Trường hợp cơ sở dừng lại mà không gọi tiếp
Đáp án: D
Trường hợp cơ sở: một nhánh trả về ngay mà không gọi đệ quy nữa. Ngoài ra mỗi lần gọi phải tiến gần trường hợp cơ sở hơn. Đủ cả hai thì hàm dừng; thiếu một trong hai thì chương trình chạy tới khi tràn ngăn xếp.
Câu 14·Heap & hàng đợi ưu tiên
Trong một min-heap nhị phân, chi phí lấy phần tử nhỏ nhất và chi phí xoá nó là bao nhiêu?
A.Đọc O(log n), xoá O(n)
B.Đọc O(log n), xoá O(log n)
C.Đọc O(1), xoá O(log n)
D.Đọc O(1), xoá O(1)
Đáp án: C
Đọc là O(1) vì phần tử nhỏ nhất luôn nằm ở gốc. Xoá là O(log n): đưa phần tử cuối lên gốc rồi vun xuống theo chiều cao cây. Chèn cũng O(log n). Đổi lại, heap không cho tìm một phần tử bất kỳ nhanh, việc đó vẫn là O(n).
Khác biệt cốt lõi giữa mảng và danh sách liên kết khi lấy phần tử thứ k là gì?
A.Danh sách liên kết nhanh hơn vì không cần tính địa chỉ
B.Mảng lấy được ngay, danh sách liên kết phải đi qua k nút
C.Khác nhau tuỳ ngôn ngữ, không có quy tắc chung
D.Cả hai đều lấy được ngay, chỉ khác nhau ở cách cấp phát bộ nhớ bên dưới
Đáp án: B
Mảng lưu các phần tử liên tiếp nên địa chỉ phần tử thứ k tính được bằng base + k * size — một phép nhân, O(1). Danh sách liên kết rải rác trong bộ nhớ, mỗi nút chỉ biết nút kế tiếp, nên muốn tới phần tử thứ k phải đi lần lượt qua k nút — O(k). Đây là lý do gốc của mọi đánh đổi còn lại giữa hai cấu trúc.
Duyệt hết một danh sách liên kết đơn cần điều kiện dừng nào?
javascript
let cur = head
while (/* ??? */) {
visit(cur.value)
cur = cur.next
}
A.cur !== head
B.cur.value !== null
C.cur.next !== null
D.cur !== null
Đáp án: D
Điều kiện đúng là cur !== null. Trong danh sách liên kết đơn, nút cuối có next = null, nên khi cur nhận giá trị null là đã đi hết. Dùng cur.next !== null là lỗi off-by-one kinh điển: vòng lặp dừng ở nút cuối và bỏ sót chính nó.
Câu 17·Danh sách liên kết
Trong danh sách liên kết vòng, dấu hiệu nào cho biết đã duyệt hết một lượt?
A.Giá trị nút bắt đầu lặp lại
B.Con trỏ quay lại đúng nút xuất phát
C.Con trỏ nhận giá trị null
D.Gặp một nút có next trỏ vào chính nó
Đáp án: B
Khi con trỏ quay về đúng nút xuất phát. Danh sách vòng không có null ở đâu cả, nên điều kiện cur !== null sẽ chạy mãi. Mẫu chuẩn là dùng vòng lặp kiểm tra sau: thăm nút, dời con trỏ, rồi lặp lại chừng nào cur !== start.
Câu 18·Danh sách đặc & mảng
Danh sách đặc khác danh sách liên kết ở điểm nào về mặt lưu trữ?
A.Phần tử luôn được giữ ở trạng thái đã sắp xếp
B.Mỗi phần tử giữ thêm con trỏ tới phần tử kế tiếp
C.Các phần tử được cấp phát rời rạc rồi nối lại với nhau bằng chỉ số
D.Các phần tử nằm liên tiếp nhau trong một vùng nhớ duy nhất
Đáp án: D
Danh sách đặc lưu các phần tử liên tiếp trong một vùng nhớ, thường là mảng. Vị trí phần tử thứ i suy ra được bằng công thức từ chỉ số nên truy cập là O(1). Đổi lại, chèn hay xóa ở giữa buộc phải dịch chuyển các phần tử phía sau để giữ tính liên tiếp.
Câu 19·Đệ quy & quay lui
Với bài toán tính n giai thừa bằng đệ quy, trường hợp suy biến là gì?
A.n = 0, trả về 1 mà không gọi tiếp
B.Khi n đã giảm xuống bằng một nửa giá trị ban đầu của nó
C.n âm, vì phép tính vô nghĩa
D.n = 1, vì nhân với 1 thì không làm giá trị thay đổi nữa
Đáp án: A
Trường hợp suy biến là n = 0, trả về 1. Đây là giá trị biết trước mà không phải gọi đệ quy nữa, nhờ đó chuỗi lời gọi có điểm kết thúc. Chọn n = 1 cũng chạy đúng với mọi n dương nhưng làm hàm sai với đầu vào n = 0, vốn là một giá trị hợp lệ.
Câu 20·Đệ quy & quay lui
Hàm đệ quy thiếu điều kiện dừng thì chương trình kết thúc thế nào?
A.Trình biên dịch phát hiện và từ chối biên dịch chương trình
B.Chạy mãi không dừng
C.Tràn ngăn xếp lời gọi
D.Hàm tự trả về giá trị mặc định của kiểu dữ liệu sau một số vòng
Đáp án: C
Chương trình dừng vì tràn ngăn xếp — StackOverflowError trong Java, RangeError: Maximum call stack size exceeded trong JavaScript, RecursionError trong Python. Mỗi lời gọi chưa trả về đều chiếm một khung trên ngăn xếp lời gọi; ngăn xếp có kích thước hữu hạn nên chuỗi lời gọi vô hạn sẽ chạm trần.
Câu 21·Đệ quy & quay lui
Cùng một thuật toán, vì sao bản đệ quy thường chạy chậm hơn bản vòng lặp?
A.Vì trình biên dịch không tối ưu được phần thân của hàm đệ quy
B.Vì đệ quy luôn tính lại
C.Vì đệ quy bắt buộc phải cấp phát bộ nhớ động cho từng lời gọi
D.Mỗi lời gọi tốn chi phí lập và gỡ khung ngăn xếp
Đáp án: D
Vì chi phí gọi hàm. Mỗi lời gọi phải đẩy tham số, lưu địa chỉ trở về, lập khung mới, rồi khi trả về phải gỡ khung và khôi phục trạng thái. Vòng lặp chỉ có một phép nhảy và một phép so sánh. Chênh lệch này là hằng số, không đổi bậc độ phức tạp, nhưng đo được rõ khi số lời gọi lớn.
Câu 22·Ngăn xếp & hàng đợi
Ngăn xếp và hàng đợi khác nhau ở nguyên tắc lấy phần tử ra như thế nào?
A.Ngăn xếp lấy phần tử vào sau cùng, hàng đợi lấy phần tử vào đầu tiên
B.Ngăn xếp có giới hạn số phần tử, còn hàng đợi thì không bị giới hạn nào
C.Ngăn xếp cho phép lấy ở cả hai đầu, hàng đợi chỉ cho lấy ở một đầu
D.Ngăn xếp lấy phần tử nhỏ nhất, còn hàng đợi lấy phần tử lớn nhất hiện có
Đáp án: A
Ngăn xếp là LIFO — vào sau ra trước, lấy phần tử ở đỉnh. Hàng đợi là FIFO — vào trước ra trước, lấy phần tử ở đầu. Cả hai đều chỉ cho thao tác ở đầu quy định sẵn; chính ràng buộc đó khiến mọi thao tác giữ được O(1) và làm cấu trúc dễ suy luận.
Câu 23·Ngăn xếp & hàng đợi
Ngăn xếp "cạn" (underflow) xảy ra khi nào?
A.Khi gọi lấy phần tử ra trong lúc ngăn xếp đang rỗng
B.Khi ngăn xếp đã đầy
C.Khi số phần tử trong ngăn xếp tụt xuống dưới một nửa sức chứa tối đa
D.Khi phần tử ở đỉnh ngăn xếp mang giá trị rỗng hoặc null
Đáp án: A
Khi gọi pop hoặc top trên một ngăn xếp rỗng. Cặp thuật ngữ đối xứng: tràn (overflow) là đẩy vào khi đã đầy, cạn (underflow) là lấy ra khi đang rỗng. Vì vậy cài đặt đúng luôn phải có hai hàm kiểm tra trạng thái rỗng và đầy trước khi thao tác.
Câu 24·Ngăn xếp & hàng đợi
Tính năng hoàn tác nhiều bước trong trình soạn thảo hợp với cấu trúc dữ liệu nào nhất?
A.Ngăn xếp
B.Bảng băm
C.Cây tìm kiếm
D.Hàng đợi
Đáp án: A
Ngăn xếp. Hoàn tác luôn nhắm vào thao tác gần nhất, đúng nguyên tắc LIFO. Mỗi thao tác được đẩy vào khi thực hiện, và hoàn tác chỉ là lấy phần tử ở đỉnh ra rồi đảo ngược nó. Muốn có cả làm lại thì cần hai ngăn xếp.
Câu 25·Ngăn xếp & hàng đợi
Ngoài cấu trúc do lập trình viên tự tạo, chương trình nào cũng đang chạy sẵn một ngăn xếp. Đó là gì?
A.Cache CPU
B.Ngăn xếp lời gọi hàm
C.Hàng chờ các tiến trình đang đợi được hệ điều hành cấp thời gian chạy
D.Vùng nhớ động, nơi các đối tượng được cấp phát trong lúc chạy
Đáp án: B
Ngăn xếp lời gọi hàm. Mỗi lần gọi hàm đẩy một khung chứa tham số, biến cục bộ và địa chỉ trở về; khi hàm kết thúc, khung được lấy ra. Đây là lý do vết lỗi in ra khi chương trình sập được gọi là "stack trace" — nó chính là ảnh chụp ngăn xếp lời gọi tại thời điểm lỗi.
Câu 26·Sắp xếp
Sắp xếp nổi bọt trên mảng đã sắp xếp sẵn, có cờ kiểm tra hoán vị, tốn bao nhiêu?
C.O(n), vì lượt duyệt đầu không có hoán vị nào nên dừng luôn
D.O(1), vì thuật toán nhận ra ngay từ đầu là không cần làm gì cả
Đáp án: C
O(n). Bản nổi bọt có cờ sẽ quét một lượt, thấy không thực hiện hoán vị nào và thoát ngay. Đây là trường hợp tốt nhất của thuật toán. Bản không có cờ vẫn chạy đủ n−1 lượt nên luôn là O(n²) bất kể dữ liệu.
Câu 27·Sắp xếp
Vì sao sắp xếp chèn được coi là lựa chọn tốt cho mảng gần như đã sắp xếp?
A.Vì nó chia mảng thành các đoạn nhỏ rồi sắp xếp riêng từng đoạn một
B.Vì nó dùng tìm kiếm nhị phân để định vị chỗ chèn
C.Vì nó bỏ qua hẳn các phần tử đã nằm đúng vị trí
D.Mỗi phần tử chỉ dịch đúng bằng số phần tử đứng sai chỗ trước nó
Đáp án: D
Vì chi phí của nó tỉ lệ với số cặp nghịch thế — số cặp phần tử đang đứng sai thứ tự tương đối. Mảng gần như đã sắp xếp có rất ít cặp như vậy, nên mỗi phần tử chỉ phải dịch một vài bước. Trường hợp tốt nhất là mảng đã sắp xếp hoàn toàn, chi phí O(n).
Câu 28·Tìm kiếm
Tìm kiếm tuần tự trên mảng n phần tử, trường hợp trung bình phải so sánh bao nhiêu lần?
A.Khoảng n/4 vì thuật toán có thể dừng sớm ở nhiều tình huống khác nhau
B.Khoảng n/2 khi phần tử cần tìm có mặt trong mảng
C.Khoảng log n lần
D.Luôn đúng n lần với mọi trường hợp
Đáp án: B
Khoảng n/2 khi phần tử có trong mảng. Nếu vị trí của nó phân bố đều thì kỳ vọng số phép so sánh là (n+1)/2. Khi phần tử không có trong mảng thì luôn phải quét hết n lần. Cả hai đều là O(n).
Câu 29·Tìm kiếm
Áp dụng tìm kiếm nhị phân lên mảng chưa sắp xếp thì chuyện gì xảy ra?
A.Kết quả vẫn luôn đúng nhưng thời gian chạy tăng lên thành tuyến tính
B.Chương trình báo lỗi ngay khi bắt đầu tìm kiếm
C.Vòng lặp chạy mãi không dừng
D.Vòng lặp vẫn kết thúc nhưng kết quả có thể sai mà không báo lỗi gì
Đáp án: D
Thuật toán vẫn kết thúc bình thường nhưng kết quả có thể sai, và không có gì báo lỗi. Tìm nhị phân dựa vào giả thiết đã sắp xếp để quyết định loại nửa nào; giả thiết sai thì nó loại nhầm nửa chứa đáp án và báo không tìm thấy dù phần tử vẫn nằm trong mảng.
Câu 30·Cây & BST
Duyệt tiền tự (NLR) một cây nhị phân thăm các nút theo thứ tự nào?
A.Hai cây con trước theo thứ tự trái phải, rồi mới tới nút gốc
B.Lần lượt từng mức của cây, mỗi mức đi từ trái sang phải
C.Toàn bộ cây con trái trước, rồi nút gốc, rồi tới cây con phải
D.Nút gốc trước, rồi toàn bộ cây con trái, rồi cây con phải
Đáp án: D
Nút gốc → cây con trái → cây con phải. Ba chữ N-L-R chính là thứ tự: Node, Left, Right. Đổi chỗ chữ N cho ra hai kiểu còn lại — LNR là trung tự, LRN là hậu tự. Cả ba đều duyệt theo chiều sâu, chỉ khác thời điểm thăm nút cha.
Câu 31·Ký pháp hậu tố & cây biểu thức
Ký pháp hậu tố đặt toán tử ở đâu so với hai toán hạng của nó?
A.Vị trí thay đổi tuỳ theo độ ưu tiên của chính toán tử đó
B.Sau cả hai toán hạng
C.Trước hai toán hạng
D.Ở giữa hai toán hạng, giống hệt cách viết toán thông thường
Đáp án: B
Sau cả hai toán hạng. Ba cách viết cho cùng phép cộng: trung tốa + b, tiền tố+ a b, hậu tốa b +. Hậu tố còn được gọi là ký pháp Ba Lan ngược, đặt theo tên nhà logic học Jan Łukasiewicz.
Câu 32·Độ phức tạp
Sắp xếp các bậc sau theo thứ tự tăng dần: O(n log n), O(1), O(2ⁿ), O(n), O(log n), O(n²).
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Hai chỗ hay nhầm: log n nhỏ hơn n chứ không lớn hơn, và n log n nhỏ hơn n² vì log n tăng chậm hơn n rất nhiều. Ngoài ra hàm mũ luôn vượt mọi đa thức khi n đủ lớn.
Câu 33·Độ phức tạp
Nói một thao tác là O(1) nghĩa là gì?
A.Chi phí không tăng khi dữ liệu lớn dần lên
B.Thao tác đó nhanh hơn mọi thao tác có bậc khác
C.Thao tác đó chỉ đọc đúng một phần tử của dữ liệu
D.Thao tác đó chạy xong trong đúng một chu kỳ máy
Đáp án: A
Chi phí không phụ thuộc n. Dữ liệu có 10 phần tử hay 10 triệu thì thao tác vẫn tốn chừng ấy. Điểm hay bị hiểu sai: O(1) không có nghĩa là nhanh. Một thao tác O(1) tốn 5 mili-giây vẫn là O(1), và vẫn chậm hơn một thao tác O(log n) tốn vài micro-giây.
Câu 34·Đồ thị
Đồ thị vô hướng đơn có n đỉnh thì có tối đa bao nhiêu cạnh?
A.n(n−1)/2
B.n(n−1)
C.n² + n
D.2(n−1)
Đáp án: A
n(n−1)/2 cạnh. Mỗi cặp đỉnh khác nhau nối được đúng một cạnh, và số cặp là tổ hợp chập hai của n. Đồ thị đạt số cạnh này gọi là đồ thị đầy đủ. Với đồ thị có hướng thì con số là n(n−1) vì mỗi cặp có hai chiều.
Câu 35·Tổng quan & ADT
Kiểu dữ liệu trừu tượng (ADT) được định nghĩa bằng gì?
A.Ngôn ngữ lập trình và thư viện chuẩn được dùng để hiện thực hoá kiểu đó
B.Tập thao tác và ý nghĩa của chúng, không nói cách lưu trữ
C.Số byte mà mỗi phần tử của kiểu đó chiếm khi được cấp phát trong bộ nhớ
D.Cách bố trí dữ liệu trong bộ nhớ
Đáp án: B
Bằng tập thao tác và ý nghĩa của chúng, hoàn toàn không nói tới cách lưu trữ. Ngăn xếp là một ADT: nó hứa push, pop, top với quy tắc vào sau ra trước. Dùng mảng hay danh sách liên kết để hiện thực đều được, người dùng không cần biết và không nên phụ thuộc vào điều đó.
Câu 36·Tổng quan & ADT
Đẳng thức nổi tiếng của Niklaus Wirth về mối quan hệ giữa cấu trúc dữ liệu và giải thuật là gì?
A.Cấu trúc dữ liệu + Ngôn ngữ lập trình = Giải thuật
B.Cấu trúc dữ liệu + Giải thuật = Chương trình
C.Cấu trúc dữ liệu = Chương trình − Giải thuật
D.Giải thuật + Chương trình = Cấu trúc dữ liệu
Đáp án: B
Cấu trúc dữ liệu + Giải thuật = Chương trình, nhan đề cuốn sách Wirth xuất bản năm 1976. Ý của nó: một chương trình cần cả hai vế, và chúng ràng buộc lẫn nhau — chọn cấu trúc dữ liệu nào sẽ quyết định thuật toán nào khả thi, và ngược lại.
Bước đầu tiên nên làm khi chọn cấu trúc dữ liệu cho một bài toán là gì?
A.Chọn cấu trúc có độ phức tạp tốt nhất trong bảng tra cứu
B.Liệt kê các thao tác cần dùng và tần suất của từng thao tác
C.Ước lượng lượng bộ nhớ mà chương trình sẽ được phép sử dụng tối đa
D.Xem thư viện chuẩn của ngôn ngữ đang dùng có sẵn những cấu trúc nào
Đáp án: B
Liệt kê các thao tác cần dùng kèm tần suất. Cần tra theo khoá không, có duyệt theo thứ tự không, chèn xóa ở đâu và nhiều tới mức nào. Trả lời xong thì lựa chọn thường chỉ còn một hai phương án, và bảng độ phức tạp lúc đó mới dùng được.
Câu 38·Quy hoạch động
Leo cầu thang n bậc, mỗi lần bước 1 hoặc 2 bậc. Số cách leo thoả hệ thức nào?
A.f(n) = f(n−1) + 1
B.f(n) = f(n−1) × f(n−2)
C.f(n) = 2·f(n−1)
D.f(n) = f(n−1) + f(n−2)
Đáp án: D
f(n) = f(n−1) + f(n−2) — chính là dãy Fibonacci. Lập luận: bước cuối cùng để lên bậc n hoặc là từ bậc n−1 bước 1 bậc, hoặc từ bậc n−2 bước 2 bậc. Hai nhóm này không giao nhau và phủ hết mọi cách, nên cộng lại.
Câu 39·Heap & hàng đợi ưu tiên
Bất biến của một min-heap nhị phân là gì?
A.Mỗi mức của cây chứa các giá trị đều nhỏ hơn mọi giá trị ở mức nằm ngay dưới nó
B.Nút bên trái nhỏ hơn nút gốc và nút bên phải lớn hơn nút gốc
C.Mỗi nút cha có giá trị nhỏ hơn hoặc bằng cả hai nút con của nó
D.Toàn bộ các nút của cây được sắp xếp tăng dần theo thứ tự duyệt trung tự
Đáp án: C
Mỗi nút cha nhỏ hơn hoặc bằng cả hai con của nó. Bất biến chỉ ràng buộc theo chiều dọc, nên giá trị nhỏ nhất chắc chắn nằm ở gốc. Hai nút anh em hoàn toàn không có quan hệ thứ tự nào, và hai nút ở khác nhánh cũng vậy.
Mức Trung bình — 130 câu Thuật toán & CTDL
Câu 1·Độ phức tạp
Vì sao 3n² + 500n + 20 được viết gọn thành O(n²)?
A.Vì cộng các số hạng lại luôn cho bậc của số hạng đầu tiên
B.Vì Big-O chỉ chấp nhận một số hạng duy nhất trong biểu thức
C.Vì 500n và 20 chỉ ảnh hưởng tới bộ nhớ chứ không tới thời gian
D.Khi n đủ lớn, số hạng bậc cao nhất áp đảo phần còn lại
Đáp án: D
Vì Big-O xét hành vi khi n tiến ra vô cùng. Tại n = 1.000.000, 3n² là 3×10¹², còn 500n chỉ là 5×10⁸, nhỏ hơn khoảng 6000 lần. Hằng số và số hạng bậc thấp bị bỏ vì chúng không đổi được hình dạng đường cong tăng trưởng.
Câu 2·Độ phức tạp
Một hàm đệ quy duyệt danh sách liên kết n nút, không cấp phát thêm mảng nào, tốn bao nhiêu bộ nhớ phụ?
A.O(1), vì không có cấu trúc dữ liệu nào được tạo
B.O(n), do n khung hàm nằm trên ngăn xếp gọi
C.O(log n), vì đệ quy luôn chia đôi bài toán
D.Không tốn gì, trình biên dịch luôn khử được đệ quy
Đáp án: B
O(n). Mỗi lần gọi đệ quy đẩy một khung hàm lên ngăn xếp và các khung chỉ được gỡ khi lần gọi sâu nhất trả về, nên độ sâu n đồng nghĩa với n khung cùng tồn tại. Với danh sách đủ dài, đây chính là nguyên nhân gây tràn ngăn xếp.
Câu 3·Độ phức tạp
Thêm phần tử vào cuối mảng động được nói là "O(1) khấu hao". Điều đó nghĩa là gì?
A.Chi phí là O(1) khi mảng còn trống và O(n) khi mảng đã đầy
B.Trình thu gom rác trả lại chi phí cấp phát về sau
C.Mọi lần thêm đều tốn đúng một số bước cố định
D.Một số lần thêm tốn O(n) nhưng trung bình vẫn là O(1)
Đáp án: D
Khi hết chỗ, mảng cấp phát vùng nhớ mới gấp đôi rồi sao chép, tốn O(n). Nhưng lần nhân đôi tiếp theo chỉ xảy ra sau n lần thêm rẻ nữa, nên tổng chi phí của n lần thêm là O(n), trung bình O(1) mỗi lần. Bảo đảm này áp dụng cho chuỗi thao tác, không cho từng lần riêng lẻ.
Cần trả lời rất nhiều truy vấn "tổng các phần tử từ chỉ số i đến j" trên một mảng không đổi. Kỹ thuật phù hợp là gì?
A.Dựng mảng tổng tiền tố, mỗi truy vấn là một phép trừ
B.Băm mỗi cặp (i, j) rồi lưu đệm kết quả đã tính
C.Duyệt lại từ i đến j cho mỗi truy vấn, đã là tối ưu
D.Sắp xếp mảng trước rồi tìm kiếm nhị phân hai đầu mút
Đáp án: A
Tổng tiền tố. Dựng prefix[k] = a[0] + … + a[k−1] một lần với chi phí O(n), sau đó tổng đoạn [i, j] là prefix[j+1] − prefix[i], mỗi truy vấn O(1). Đổi O(n) bộ nhớ phụ lấy thời gian trả lời hằng số.
Câu 5·Mảng & chuỗi
So với mảng, danh sách liên kết đơn có ưu thế rõ nhất ở thao tác nào?
A.Truy cập phần tử thứ i theo chỉ số
B.Duyệt tuần tự toàn bộ phần tử
C.Tìm giá trị lớn nhất trong cấu trúc
D.Chèn hoặc xoá khi đã có con trỏ
Đáp án: D
Chèn và xoá tại một vị trí đã cầm con trỏ: chỉ cần nối lại liên kết, O(1), trong khi mảng phải dịch phần tử nên O(n). Đổi lại danh sách liên kết mất khả năng truy cập theo chỉ số ở O(1) và kém thân thiện với cache.
Câu 6·Hash map & set
Trường hợp xấu nhất của tra cứu hash map là O(n). Điều gì gây ra nó?
A.Bảng có quá nhiều ô trống nên phải quét tìm ô có dữ liệu
B.Khoá quá dài nên hàm băm phải chạy nhiều vòng lặp
C.Nhiều khoá cùng rơi vào một ô, tạo ra danh sách dài
D.Bảng bị cấp phát lại quá thường xuyên khi thêm phần tử
Đáp án: C
Va chạm dồn cục. Nếu hàm băm phân tán kém, hoặc dữ liệu bị chọn có chủ đích, mọi khoá rơi vào cùng một ô và ô đó thành danh sách n phần tử, nên tra cứu phải duyệt hết. Cài đặt hiện đại chống việc này bằng băm có mầm ngẫu nhiên và chuyển ô đông thành cây cân bằng.
Câu 7·Hash map & set
Cho mảng số và một giá trị đích, tìm hai phần tử có tổng bằng đích. Cách nào chạy một lượt O(n)?
A.Duyệt một lượt, tra hash map tìm phần bù của số
B.Duyệt mọi cặp chỉ số và kiểm tra tổng của từng cặp
C.Sắp xếp mảng rồi dùng hai con trỏ từ hai đầu
D.Chia đôi mảng rồi giải đệ quy từng nửa
Đáp án: A
Duyệt một lượt và dùng hash map làm bộ nhớ: tại mỗi phần tử x, kiểm tra target − x đã nằm trong map chưa; nếu rồi thì trả về cặp, nếu chưa thì lưu x cùng chỉ số của nó. Mỗi phần tử tra và ghi đúng một lần nên tổng là O(n) thời gian, O(n) bộ nhớ.
Câu 8·Hash map & set
Dùng một đối tượng có thể thay đổi làm khoá hash map, rồi sửa nó sau khi đã chèn. Chuyện gì xảy ra?
A.Chương trình báo lỗi ngay khi khoá bị sửa
B.Mục bị xoá khỏi bảng để giữ tính nhất quán
C.Mục cũ gần như không tìm lại được vì băm đã đổi
D.Bảng tự động dời mục sang ô đúng khi khoá thay đổi
Đáp án: C
Mục trở thành rác không truy cập được. Bảng đã đặt mục vào ô tính theo giá trị băm cũ; sau khi khoá đổi, lần tra sau tính ra ô mới và không thấy gì ở đó, dù mục vẫn chiếm bộ nhớ. Vì vậy khoá phải bất biến trong suốt thời gian nằm trong bảng.
Câu 9·Hai con trỏ & cửa sổ trượt
Tìm chuỗi con dài nhất không có ký tự lặp. Cửa sổ trượt xử lý thế nào khi gặp ký tự đã có trong cửa sổ?
A.Giữ nguyên cửa sổ và bỏ qua ký tự đang xét
B.Lùi biên phải lại một bước rồi thử ký tự kế tiếp
C.Đặt lại cửa sổ về rỗng rồi bắt đầu từ ký tự hiện tại
D.Đẩy biên trái tới ngay sau lần xuất hiện trước
Đáp án: D
Đẩy biên trái tới ngay sau vị trí xuất hiện trước đó của ký tự vừa gặp, lấy từ một map ký tự đến chỉ số. Cửa sổ luôn giữ bất biến "không có ký tự lặp", còn biên phải chỉ tiến, nên mỗi ký tự vào và ra tối đa một lần: O(n).
Câu 10·Hai con trỏ & cửa sổ trượt
Cửa sổ trượt có hai vòng lặp lồng nhau nhưng vẫn được tính là O(n). Vì sao?
A.Mỗi phần tử chỉ vào và rời khỏi cửa sổ đúng một lần
B.Vì biên trái được tính lại bằng công thức chứ không lặp
C.Vòng trong luôn chạy đúng một lần với mọi đầu vào
D.Vì cửa sổ có kích thước cố định nên vòng trong là hằng số
Đáp án: A
Vì phải đếm tổng số bước chứ không nhân số vòng. Biên phải đi tối đa n bước, biên trái cũng chỉ đi tối đa n bước và không bao giờ lùi, nên tổng công việc bị chặn bởi 2n. Vòng lồng nhau không tự động có nghĩa là O(n²).
Câu 11·Hai con trỏ & cửa sổ trượt
Kỹ thuật hai con trỏ nhanh và chậm phát hiện chu trình trong danh sách liên kết dựa trên điều gì?
A.Hai con trỏ luôn gặp nhau đúng ở nút bắt đầu chu trình
B.Nếu có chu trình, con trỏ nhanh sẽ đuổi kịp con chậm
C.Con trỏ nhanh gặp lại nút đầu danh sách sau đúng một vòng
D.Con trỏ chậm ghi lại các nút đã thăm để so sánh
Đáp án: B
Con trỏ chậm đi một bước, con trỏ nhanh đi hai bước. Nếu có chu trình, cả hai đều mắc trong vòng và khoảng cách giữa chúng giảm đúng một đơn vị mỗi bước, nên chắc chắn về 0. Không có chu trình thì con trỏ nhanh chạm null và dừng. Chi phí O(n) thời gian, O(1) bộ nhớ.
Với mỗi phần tử của mảng, tìm phần tử lớn hơn đầu tiên đứng sau nó. Cách nào cho O(n)?
A.Với mỗi phần tử, quét tiếp phần đuôi cho tới khi gặp số lớn hơn
B.Dựng mảng tổng tiền tố rồi so sánh các hiệu liên tiếp
C.Sắp xếp mảng giảm dần rồi ghép lại theo chỉ số gốc
D.Duyệt một lượt với ngăn xếp giữ các chỉ số giảm dần
Đáp án: D
Ngăn xếp đơn điệu. Duyệt trái sang phải, giữ ngăn xếp các chỉ số có giá trị giảm dần; khi gặp phần tử lớn hơn đỉnh thì lấy đỉnh ra và ghi nhận phần tử hiện tại là đáp án của nó, lặp tới khi đỉnh lớn hơn. Mỗi chỉ số vào ra một lần nên O(n).
Câu 13·Ngăn xếp & hàng đợi
Trong duyệt đồ thị, thay queue bằng ngăn xếp làm thay đổi điều gì?
A.Chuyển từ duyệt theo chiều rộng sang theo chiều sâu
B.Giảm độ phức tạp thời gian từ O(V + E) xuống O(V)
C.Làm thuật toán tìm được đường đi ngắn nhất chính xác hơn
D.Cho phép bỏ tập đỉnh đã thăm khi đồ thị có chu trình
Đáp án: A
Đổi thứ tự duyệt: queue cho BFS, đi hết các đỉnh cùng mức trước; ngăn xếp cho DFS, đi sâu hết một nhánh rồi mới quay lại. Cùng độ phức tạp O(V + E), nhưng chỉ BFS bảo đảm tìm được đường ít cạnh nhất trên đồ thị không trọng số.
Câu 14·Ngăn xếp & hàng đợi
Mô phỏng queue bằng hai ngăn xếp: thao tác lấy ra khỏi hàng có chi phí thế nào?
A.O(log n) do phải cân bằng lại hai ngăn xếp
B.O(1) trường hợp xấu nhất vì đỉnh luôn sẵn sàng
C.O(n) cho mọi lần lấy ra không có ngoại lệ
D.O(1) khấu hao, dù một lần ra có thể tốn O(n)
Đáp án: D
O(1) khấu hao. Thao tác vào luôn đẩy vào ngăn xếp in. Thao tác ra lấy đỉnh của ngăn xếp out; nếu out rỗng thì đổ toàn bộ in sang out, việc này đảo thứ tự đúng một lần. Mỗi phần tử chỉ chuyển một lần trong đời nên tổng n thao tác là O(n).
Câu 15·Tìm kiếm nhị phân
Vì sao nhiều tài liệu khuyên viết mid = lo + (hi - lo) / 2 thay vì mid = (lo + hi) / 2?
A.Tránh tràn số khi lo và hi đều lớn với số nguyên cố định
B.Vì cách viết kia không hoạt động khi mảng có số phần tử lẻ
C.Vì cách viết kia luôn làm lệch điểm giữa sang bên phải
D.Vì phép trừ chạy nhanh hơn phép cộng trên hầu hết CPU
Đáp án: A
Để tránh tràn số. Với kiểu số nguyên cố định, lo + hi có thể vượt giá trị lớn nhất khi cả hai đều lớn, cho ra chỉ số âm và làm chương trình sai hoặc lỗi. Dạng lo + (hi - lo) / 2 luôn nằm trong khoảng hợp lệ vì hiệu không bao giờ lớn hơn hi.
Câu 16·Tìm kiếm nhị phân
Mảng đã sắp xếp có nhiều giá trị trùng nhau. Cần tìm vị trí đầu tiên của một giá trị thì sửa gì?
A.Sắp xếp lại mảng theo cặp giá trị và chỉ số trước khi tìm
B.Gặp giá trị đúng vẫn thu hẹp sang nửa trái thay vì dừng
C.Dừng ngay khi gặp giá trị đúng rồi lùi tuyến tính về đầu dãy
D.Đổi điều kiện vòng lặp từ nhỏ hơn bằng thành nhỏ hơn
Đáp án: B
Không dừng khi trùng khớp. Ghi nhận mid là ứng viên rồi đặt hi = mid - 1 để tiếp tục tìm phía trái. Vòng lặp kết thúc với ứng viên cuối cùng chính là vị trí đầu tiên. Vẫn O(log n), trong khi lùi tuyến tính sau khi tìm thấy có thể thành O(n).
Câu 17·Sắp xếp
Một thuật toán sắp xếp "ổn định" nghĩa là gì, và khi nào tính chất đó quan trọng?
A.Không cấp phát thêm bộ nhớ trong quá trình sắp xếp
B.Luôn chạy đúng O(n log n) bất kể dữ liệu đầu vào
C.Cho kết quả giống nhau ở mọi lần chạy với cùng đầu vào
D.Giữ nguyên thứ tự tương đối của các khoá bằng nhau
Đáp án: D
Ổn định nghĩa là hai phần tử có khoá bằng nhau giữ nguyên thứ tự tương đối như trước khi sắp. Nhờ đó, muốn sắp theo nhiều tiêu chí thì chỉ cần sắp lần lượt từ tiêu chí phụ tới tiêu chí chính. Merge sort và Timsort ổn định; quicksort và heapsort thì không.
Vì sao merge sort thường được chọn để sắp xếp danh sách liên kết còn quicksort thì không?
A.Danh sách liên kết luôn gần như đã sắp xếp sẵn
B.Quicksort không hoạt động khi số phần tử chưa biết trước
C.Merge sort không cần so sánh phần tử nên chạy tuyến tính
D.Trộn hai danh sách chỉ cần nối lại con trỏ là xong
Đáp án: D
Merge sort chỉ cần đi tuần tự và nối con trỏ, đúng với thao tác mà danh sách liên kết làm tốt, và trên danh sách nó còn không cần O(n) bộ nhớ phụ. Quicksort dựa vào truy cập ngẫu nhiên để chọn chốt và phân hoạch tại chỗ, thứ mà danh sách liên kết không cung cấp ở O(1).
Câu 19·Sắp xếp
Sắp xếp 10 triệu số nguyên trong khoảng 0 đến 100. Cách nào nhanh hơn O(n log n)?
A.Dùng quicksort với chốt chọn ngẫu nhiên cho từng đoạn
B.Đếm số lần xuất hiện rồi ghi lại theo thứ tự tăng
C.Chia mảng ra nhiều thread rồi trộn kết quả lại
D.Sắp xếp trên đĩa theo từng khối rồi trộn ngoài
Đáp án: B
Counting sort: đếm số lần xuất hiện của từng giá trị vào mảng 101 ô, rồi ghi ra theo thứ tự tăng dần. Chi phí O(n + k) với k là kích thước miền giá trị. Cách này vượt được chặn dưới n log n vì không so sánh phần tử với nhau mà dùng giá trị làm chỉ số.
Câu 20·Cây & BST
Duyệt trung tự (in-order) một cây tìm kiếm nhị phân cho ra điều gì?
A.Dãy bắt đầu từ nút gốc rồi tới các nhánh
B.Dãy các lá theo thứ tự từ trái sang phải
C.Dãy giá trị theo từng mức từ trên xuống
D.Dãy giá trị tăng dần
Đáp án: D
Dãy tăng dần. Trung tự đi trái, rồi gốc, rồi phải; kết hợp với bất biến của BST là con trái nhỏ hơn và con phải lớn hơn, kết quả là các giá trị được liệt kê theo thứ tự. Đây cũng là cách kiểm tra một cây có đúng là BST hay không.
Câu 21·Cây & BST
Cây đỏ đen và AVL đều tự cân bằng. Khác biệt thực tế giữa chúng là gì?
A.AVL dùng cho dữ liệu trên đĩa còn đỏ đen dùng trong bộ nhớ
B.Đỏ đen giữ thứ tự các khoá còn AVL thì không
C.AVL cho O(log n) còn đỏ đen chỉ cho O(n) ở trường hợp xấu nhất
D.AVL cân bằng chặt hơn nên đọc nhanh, đỏ đen ghi rẻ
Đáp án: D
Cùng bảo đảm O(log n), khác ở chỗ đánh đổi. AVL giữ chênh lệch chiều cao hai cây con tối đa 1 nên cây thấp hơn và tra cứu nhanh hơn, đổi lại phải quay nhiều hơn khi ghi. Cây đỏ đen cho phép mất cân bằng nhiều hơn nên chèn và xoá rẻ hơn, phù hợp khi tỉ lệ ghi cao.
Câu 22·Cây & BST
In các nút của cây nhị phân theo từng mức, mỗi mức một dòng. Cần thêm gì so với BFS thông thường?
A.Ghi lại số nút đang có trong queue trước mỗi mức
B.Duyệt cây hai lần, một lần đếm mức và một lần in ra
C.Đổi queue thành ngăn xếp để phân biệt các mức
D.Lưu chiều sâu vào từng nút của cây trước khi duyệt
Đáp án: A
Chụp lại kích thước queue ngay đầu mỗi vòng lặp. Con số đó đúng bằng số nút của mức hiện tại, nên lấy ra đúng chừng đó nút, in một dòng, rồi đẩy con của chúng vào cho mức sau. Vẫn O(n) thời gian và O(chiều rộng) bộ nhớ.
Câu 23·Đồ thị
DFS đệ quy trên đồ thị có chu trình mà quên tập đỉnh đã thăm sẽ dẫn tới điều gì?
A.Mỗi đỉnh được thăm đúng một lần nhờ ngăn xếp gọi
B.Kết quả đúng nhưng chậm hơn bản có tập đã thăm
C.Đệ quy vô hạn cho tới khi tràn ngăn xếp
D.Bỏ sót một số đỉnh nhưng vẫn kết thúc bình thường
Đáp án: C
Đệ quy chạy vô hạn quanh chu trình cho tới khi tràn ngăn xếp. Tập đỉnh đã thăm là thứ bảo đảm mỗi đỉnh chỉ được mở rộng một lần, đồng thời kéo độ phức tạp về O(V + E). Trên cây thì không cần vì cây không có chu trình.
Câu 24·Đồ thị
Vì sao Dijkstra cho kết quả sai khi đồ thị có cạnh trọng số âm?
A.Vì tổng đường đi có thể tràn số khi cộng nhiều số âm
B.Nó chốt đỉnh là tối ưu ngay khi lấy ra khỏi queue
C.Vì thuật toán bắt buộc mọi đỉnh phải liên thông với nhau
D.Vì priority queue không lưu được số âm
Đáp án: B
Dijkstra tham lam: khi lấy đỉnh có khoảng cách nhỏ nhất ra khỏi queue, nó chốt đỉnh đó là đã tối ưu. Lập luận này dựa vào giả định đường đi không bao giờ ngắn lại khi thêm cạnh. Cạnh âm phá vỡ giả định nên một đỉnh đã chốt vẫn có thể được cải thiện sau đó. Trường hợp có cạnh âm dùng Bellman-Ford.
Cần xác định thứ tự chạy các tác vụ có ràng buộc "A phải xong trước B". Thuật toán nào phù hợp?
A.Dijkstra với trọng số là thời lượng của mỗi tác vụ
B.Duyệt theo chiều rộng từ tác vụ đầu tiên trong danh sách
C.Sắp xếp tô-pô trên đồ thị phụ thuộc có hướng
D.Sắp xếp các tác vụ theo số phụ thuộc rồi chạy lần lượt
Đáp án: C
Sắp xếp tô-pô. Dựng đồ thị có hướng với cạnh A→B nghĩa là A phải xong trước B, rồi lặp: lấy ra các đỉnh bậc vào bằng 0, giảm bậc vào của các đỉnh kề. Nếu còn đỉnh chưa lấy được thì có phụ thuộc vòng. Chi phí O(V + E).
Đồ thị 100.000 đỉnh nhưng chỉ 300.000 cạnh. Nên lưu bằng danh sách kề hay ma trận kề?
A.Ma trận kề, vì kiểm tra hai đỉnh có kề nhau là O(1)
B.Cả hai như nhau vì cùng độ phức tạp O(V + E)
C.Ma trận kề, vì duyệt các đỉnh kề nhanh hơn
D.Danh sách kề, vì bộ nhớ tỉ lệ với số cạnh có thật
Đáp án: D
Danh sách kề. Ma trận cần V² = 10¹⁰ ô, không khả thi, trong khi danh sách chỉ tốn O(V + E) tức khoảng 400.000 mục. Đồ thị thưa thì luôn chọn danh sách kề; ma trận chỉ đáng dùng khi đồ thị dày hoặc cần kiểm tra kề nhau ở O(1) rất nhiều lần.
Câu 27·Đệ quy & quay lui
Trong thuật toán quay lui, vì sao phải hoàn tác thay đổi sau khi gọi đệ quy trở về?
A.Để trình thu gom rác giải phóng được bộ nhớ đã cấp
B.Để bảo đảm các lời giải được sinh theo thứ tự tăng dần
C.Để giảm độ phức tạp từ hàm mũ xuống đa thức
D.Để nhánh kế tiếp bắt đầu từ trạng thái ban đầu
Đáp án: D
Vì trạng thái được dùng chung giữa các nhánh. Sau khi thử một lựa chọn và đệ quy xong, nếu không gỡ nó ra thì nhánh kế tiếp bắt đầu với trạng thái đã bị bẩn và sinh ra lời giải sai. Khuôn mẫu là: chọn, đệ quy, bỏ chọn.
Câu 28·Đệ quy & quay lui
Hàm Fibonacci đệ quy thuần chạy O(2ⁿ). Ghi nhớ kết quả đã tính đưa nó về bậc nào?
A.O(n log n), do chi phí tra cứu cache
B.O(n), vì mỗi giá trị chỉ được tính đúng một lần
C.Vẫn O(2ⁿ) nhưng với hằng số nhỏ hơn nhiều
D.O(n²), vì vẫn phải duyệt lại các giá trị nhỏ hơn
Đáp án: B
O(n) thời gian và O(n) bộ nhớ. Cây gọi của bản thuần lặp lại cùng những bài toán con vô số lần; ghi nhớ khiến mỗi giá trị từ 0 tới n chỉ được tính một lần, các lần sau trả về ngay. Bản lặp từ dưới lên còn hạ bộ nhớ xuống O(1) nếu chỉ giữ hai giá trị liền trước.
Câu 29·Quy hoạch động· chọn nhiều đáp án
Hai điều kiện nào cho biết một bài toán giải được bằng quy hoạch động?
A.Kích thước đầu vào đủ nhỏ để duyệt toàn bộ
B.Dữ liệu đầu vào đã được sắp xếp sẵn
C.Các bài toán con gối lên nhau và lặp lại
D.Lời giải tối ưu ghép từ lời giải tối ưu của bài toán con
Đáp án: C, D
Cần cả hai: bài toán con gối nhau (cùng bài toán con xuất hiện nhiều lần, nên lưu lại có lợi) và cấu trúc con tối ưu (lời giải tối ưu tổng thể ghép được từ lời giải tối ưu của các phần). Thiếu điều kiện đầu thì ghi nhớ vô ích; thiếu điều kiện sau thì công thức truy hồi sai.
Câu 30·Quy hoạch động
Quy hoạch động từ trên xuống (ghi nhớ) khác gì từ dưới lên (điền bảng)?
A.Từ trên xuống không cần công thức truy hồi
B.Từ dưới lên luôn cho độ phức tạp thời gian tốt hơn
C.Từ trên xuống chỉ tính những trạng thái thật sự cần
D.Từ dưới lên chỉ áp dụng được khi trạng thái là một chiều
Đáp án: C
Từ trên xuống là đệ quy cộng cache, chỉ tính những trạng thái thật sự chạm tới và giữ nguyên hình dạng bài toán. Từ dưới lên điền bảng theo thứ tự nên tránh được chi phí gọi hàm và mở đường tối ưu bộ nhớ, nhưng phải tính cả những trạng thái không cần và phải tự xác định thứ tự tính.
Câu 31·Heap & hàng đợi ưu tiên
Tìm 10 phần tử lớn nhất trong dòng dữ liệu 100 triệu số không giữ được hết trong bộ nhớ. Cách nào phù hợp?
A.Giữ một min-heap 10 phần tử, thay gốc khi gặp số lớn hơn
B.Chia dòng thành khối, lấy số lớn nhất mỗi khối rồi so sánh
C.Giữ một max-heap chứa toàn bộ phần tử rồi lấy ra 10 lần
D.Sắp xếp toàn bộ dòng dữ liệu rồi lấy 10 phần tử cuối
Đáp án: A
Min-heap kích thước k = 10. Duyệt một lượt: heap chưa đủ 10 thì thêm vào; đủ rồi thì so với gốc, lớn hơn thì thay gốc và vun lại. Gốc luôn là phần tử nhỏ nhất trong nhóm dẫn đầu hiện tại. Chi phí O(n log k) thời gian và O(k) bộ nhớ.
Câu 32·Heap & hàng đợi ưu tiên
Dựng heap từ một mảng n phần tử có sẵn tốn bao nhiêu, so với chèn lần lượt từng phần tử?
A.Dựng trực tiếp là O(n log n), chèn lần lượt là O(n)
B.Cả hai đều là O(n log n) vì cùng phải vun n lần
C.Dựng trực tiếp là O(n), chèn lần lượt là O(n log n)
D.Cả hai đều là O(n) vì mỗi phần tử chỉ chạm một lần
Đáp án: C
Dựng trực tiếp bằng cách vun từ dưới lên là O(n), còn chèn lần lượt là O(n log n). Lý do là một nửa số nút nằm ở đáy và không phải vun bước nào; chỉ vài nút gần gốc mới tốn log n. Tổng lại hội tụ về tuyến tính.
Câu 33·Danh sách liên kết
Đã có con trỏ tới nút p, chèn một nút mới ngay sau p tốn bao nhiêu thời gian?
A.Tuỳ vị trí của p trong danh sách
B.O(1)
C.O(log n)
D.O(n)
Đáp án: B
O(1). Toàn bộ việc cần làm là node.next = p.next rồi p.next = node — hai phép gán, không phụ thuộc n. Điểm dễ nhầm: chi phí O(n) mà giáo trình hay nhắc là chi phí đi tìm vị trí chèn. Khi đề bài đã cho sẵn con trỏ tới p thì phần tìm kiếm đó không còn.
Câu 34·Danh sách liên kết
Chỉ cầm con trỏ tới nút p ở giữa một danh sách liên kết đơn, làm sao xóa được p?
A.Gán p = p.next là xong
B.Gán p = null để cắt nút khỏi danh sách
C.Không có cách nào, bắt buộc phải duyệt lại từ head
D.Chép dữ liệu của p.next vào p rồi xóa nút p.next
Đáp án: D
Chép giá trị của p.next đè lên p, rồi nối p.next = p.next.next để bỏ nút kế tiếp. Kết quả: giá trị tại vị trí p biến mất khỏi danh sách trong O(1), dù ô nhớ bị giải phóng lại là ô của nút sau. Mẹo này chỉ dùng được khi p không phải nút cuối — nút cuối không có gì để chép sang.
Danh sách liên kết đôi trả giá thêm bộ nhớ để đổi lấy điều gì?
A.Giảm hẳn số lần cache miss khi duyệt danh sách tuần tự
B.Truy cập phần tử thứ k trong O(1)
C.Tìm kiếm một giá trị trong O(log n)
D.Xóa nút đã cầm con trỏ trong O(1) và duyệt ngược
Đáp án: D
Mỗi nút giữ thêm con trỏ prev, đổi lại hai thứ: xóa nút trong O(1) khi đã cầm con trỏ tới nó, và duyệt ngược từ đuôi về đầu. Danh sách đơn muốn xóa nút p phải tìm nút đứng trước p, tức O(n). Giá phải trả là bộ nhớ mỗi nút tăng và mỗi thao tác phải cập nhật hai chiều thay vì một.
Câu 36·Danh sách liên kết
Xóa nút thứ n tính từ cuối danh sách liên kết đơn, chỉ được duyệt đúng một lượt. Làm thế nào?
A.Đưa toàn bộ các nút vào một mảng phụ rồi truy cập theo chỉ số để xóa
B.Đảo ngược danh sách, xóa nút thứ n kể từ đầu, rồi đảo ngược lại lần nữa
C.Cho một con trỏ đi trước n bước, rồi hai con cùng tiến tới hết
D.Duyệt một lượt để đếm độ dài, rồi duyệt tiếp tới vị trí cần xóa và cắt liên kết
Đáp án: C
Dùng hai con trỏ cách nhau đúng n bước. Cho con trỏ nhanh đi trước n bước, rồi cho cả hai cùng tiến từng bước cho tới khi con nhanh chạm cuối. Lúc đó con chậm đứng ngay trước nút cần xóa. Một lượt duyệt, O(1) bộ nhớ.
Đảo ngược danh sách liên kết đơn tại chỗ cần giữ tối thiểu mấy con trỏ?
A.Một, vì chỉ cần đổi chiều trường next
B.Bốn, cần thêm một con trỏ giữ lại head cũ ban đầu
C.Ba: nút trước, nút hiện tại, nút kế tiếp
D.Hai: nút hiện tại và nút kế tiếp
Đáp án: C
Ba con trỏ: prev, cur, next. Mỗi vòng lặp làm đúng bốn việc theo thứ tự — lưu next = cur.next, bẻ cur.next = prev, dời prev = cur, dời cur = next. Con trỏ next bắt buộc phải có vì ngay khi ghi đè cur.next là mất đường đi tới phần còn lại của danh sách.
constbuild = (arr) => arr.reduceRight((next, value) => ({ value, next }), null)
functionreverse(head) {
let prev = nulllet cur = head
while (cur) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}
const out = []
for (let n = reverse(build([1, 2, 3, 4])); n; n = n.next) out.push(n.value)
console.log(out.join(','))
A.1,2,3,4
B.3,4,1,2
C.2,1,4,3
D.4,3,2,1
Đáp án: D
In ra 4,3,2,1. build dựng danh sách 1→2→3→4, reverse bẻ ngược từng liên kết và trả về prev — chính là nút cuối cũ, tức nút 4. Duyệt từ đó ra thứ tự ngược.
Câu 39·Danh sách liên kết
Nút giả (dummy head) đặt trước danh sách nhằm mục đích gì?
A.Tăng tốc truy cập phần tử thứ k
B.Khử trường hợp đặc biệt khi chèn hoặc xóa ở đầu danh sách
C.Lưu số lượng phần tử hiện có của danh sách
D.Đánh dấu điểm kết thúc để vòng lặp biết chính xác khi nào nên dừng
Đáp án: B
Nút giả biến "chèn/xóa ở đầu" thành một trường hợp bình thường. Không có nó, mọi hàm sửa danh sách phải viết riêng nhánh if (node === head) để cập nhật biến head. Có nó, mọi nút thật đều có nút đứng trước, nên chỉ còn một đường xử lý — code ngắn hơn và bớt hẳn nhóm lỗi biên.
Câu 40·Danh sách liên kết
Tìm nút giữa danh sách liên kết chỉ với một lượt duyệt thì làm thế nào?
A.Duyệt một lượt đếm n, rồi duyệt tiếp n/2 bước
B.Đưa toàn bộ các nút vào một mảng phụ rồi lấy phần tử nằm chính giữa
C.Đảo danh sách rồi lấy nút đầu tiên
D.Một con trỏ đi 1 bước, một con đi 2 bước, tới khi con nhanh chạm cuối
Đáp án: D
Vẫn là hai con trỏ nhanh và chậm, nhưng lần này đọc kết quả ở con chậm. Khi con nhanh chạm cuối, con chậm đứng đúng giữa vì đã đi được nửa quãng đường. Một lượt duyệt, O(1) bộ nhớ.
Câu 41·Danh sách liên kết
Cùng là O(n), vì sao duyệt mảng thường nhanh hơn duyệt danh sách liên kết?
A.Vì danh sách liên kết luôn phải cấp phát thêm bộ nhớ trong lúc duyệt
B.Vì mảng có ít phép so sánh hơn trong vòng lặp
C.Phần tử mảng nằm cạnh nhau nên một lần nạp cache dùng được nhiều
D.Vì O(n) của danh sách liên kết thực chất là O(n log n)
Đáp án: C
Do cache locality. CPU không đọc từng byte mà nạp cả cache line khoảng 64 byte. Với mảng, một lần nạp mang về luôn nhiều phần tử kế tiếp. Với danh sách liên kết, các nút nằm rải rác nên mỗi bước có thể là một cache miss, và một lần chờ bộ nhớ chính đắt gấp hàng chục lần một lệnh tính toán.
Câu 42·Danh sách liên kết
Trộn hai danh sách liên kết đã sắp xếp thành một danh sách sắp xếp tốn bao nhiêu?
A.O(n + m) thời gian, O(1) bộ nhớ phụ nếu nối lại con trỏ
B.O(n + m) thời gian nhưng bắt buộc O(n + m) bộ nhớ phụ
C.O(n · m) vì mỗi nút phải so với mọi nút của danh sách kia
D.O((n + m) log(n + m)) vì phải sắp xếp lại kết quả
Đáp án: A
O(n + m) thời gian và O(1) bộ nhớ phụ. Luôn so hai nút đang đứng đầu, lấy nút nhỏ hơn nối vào kết quả rồi đẩy con trỏ của danh sách đó lên. Mỗi nút được xét đúng một lần. Vì chỉ đổi trường next chứ không tạo nút mới nên không tốn thêm bộ nhớ.
Danh sách đặc đang có 10 phần tử ở các vị trí 1..10. Chèn một phần tử vào vị trí 4 phải dịch bao nhiêu phần tử?
A.10
B.4
C.7
D.6
Đáp án: C
Bảy phần tử. Muốn giải phóng ô số 4, mọi phần tử từ vị trí 4 tới vị trí 10 phải lùi sang phải một ô — đúng 10 − 4 + 1 = 7 phần tử. Ba phần tử đầu giữ nguyên. Vòng lặp dịch phải chạy từ cuối về vị trí chèn, nếu chạy xuôi sẽ ghi đè mất dữ liệu.
Câu 44·Danh sách đặc & mảng
Vẫn danh sách đặc 10 phần tử ở vị trí 1..10. Xóa phần tử ở vị trí 4 phải dịch bao nhiêu phần tử?
A.6
B.4
C.5
D.7
Đáp án: A
Sáu phần tử. Các phần tử ở vị trí 5 tới 10 tiến lên một ô để lấp chỗ trống, tức 10 − 4 = 6. Chú ý lệch một so với bài chèn: khi chèn thì phần tử tại vị trí i cũng phải dịch, khi xóa thì phần tử tại i biến mất nên chỉ phần đuôi dịch. Vòng lặp lần này chạy xuôi từ i tới n − 1.
Câu 45·Danh sách đặc & mảng
Truy cập a[i] trong mảng là O(1) nhờ đâu?
A.Trình biên dịch lưu sẵn một bảng địa chỉ cho mọi phần tử của mảng
B.Địa chỉ tính được từ địa chỉ gốc, chỉ số và kích thước phần tử
C.CPU giữ toàn bộ mảng trong thanh ghi
D.Mảng luôn được sắp xếp nên tìm bằng chia đôi
Đáp án: B
Nhờ công thức địa chỉ = base + i × size. Vì mọi phần tử cùng kích thước và nằm liên tiếp, vị trí phần tử thứ i là một phép nhân cộng — chi phí không đổi bất kể mảng dài bao nhiêu. Mất một trong hai điều kiện đó là mất luôn O(1).
Câu 46·Danh sách đặc & mảng
Mảng động hết chỗ thì cấp phát vùng mới gấp đôi thay vì cộng thêm một hằng số. Vì sao?
A.Nhân đôi cho O(1) khấu hao, còn cộng hằng số cho O(n)
B.Vì bộ nhớ chỉ cấp phát được theo lũy thừa của hai
C.Vì sao chép vùng nhớ lớn nhanh hơn sao chép nhiều vùng nhỏ
D.Để mảng luôn vừa khít một cache line
Đáp án: A
Vì tổng chi phí sao chép. Nhân đôi khiến các lần cấp phát lại thưa dần theo cấp số nhân: sao chép 1 + 2 + 4 + … + n < 2n, chia đều cho n phần tử ra O(1) khấu hao. Nếu chỉ cộng thêm k phần tử mỗi lần, số lần cấp phát lại là n/k và tổng sao chép là O(n²), tức O(n) cho mỗi lần thêm.
Câu 47·Danh sách đặc & mảng
Mảng hai chiều lưu theo hàng. Vì sao duyệt theo hàng nhanh hơn duyệt theo cột?
A.Vì số phép nhân khi tính địa chỉ theo hàng ít hơn
B.Vì trình biên dịch tự chuyển vòng lặp cột thành vòng lặp hàng
C.Theo hàng đọc ô liền kề, theo cột mỗi bước nhảy cả một hàng
D.Vì số vòng lặp khi duyệt theo hàng ít hơn
Đáp án: C
Vì thứ tự truy cập khớp hay không khớp với thứ tự lưu. Lưu theo hàng nghĩa là cả hàng nằm liên tiếp trong bộ nhớ. Duyệt theo hàng đi tuần tự nên mỗi cache line nạp về phục vụ được nhiều ô. Duyệt theo cột thì mỗi bước nhảy qua độ dài một hàng, thường rơi vào cache line khác — có thể một cache miss cho mỗi ô.
Câu 48·Danh sách đặc & mảng
Xóa phần tử ở vị trí i khỏi một mảng không cần giữ thứ tự thì làm cách nào rẻ nhất?
A.Chép phần tử cuối đè lên vị trí i rồi giảm độ dài đi một
B.Tạo một mảng mới rồi chép sang toàn bộ trừ phần tử thứ i
C.Gán null vào vị trí i và giữ nguyên độ dài
D.Dịch mọi phần tử sau i lên một ô rồi giảm độ dài
Đáp án: A
Chép phần tử cuối cùng đè lên vị trí i rồi giảm độ dài — thường gọi là swap-remove, chi phí O(1). Đánh đổi là thứ tự các phần tử bị xáo. Cách này chỉ dùng khi mảng đóng vai trò tập hợp không thứ tự; nếu thứ tự có ý nghĩa thì phải chấp nhận dịch chuyển O(n).
Câu 49·Đệ quy & quay lui
Máy dùng cấu trúc dữ liệu nào để ghi nhớ chỗ quay về giữa các lời gọi đệ quy?
A.Hàng đợi
B.Bảng băm
C.Danh sách
D.Ngăn xếp
Đáp án: D
Ngăn xếp lời gọi. Mỗi lời gọi đẩy một khung chứa tham số, biến cục bộ và địa chỉ trở về; khi hàm kết thúc, khung được lấy ra và thread thực thi quay về đúng chỗ. Thứ tự vào sau ra trước khớp chính xác với thứ tự kết thúc của các lời gọi lồng nhau.
Câu 50·Đệ quy & quay lui
Bài toán Tháp Hà Nội với n đĩa cần tối thiểu bao nhiêu lần chuyển đĩa?
A.n·log n
B.n² − n
C.2ⁿ − 1
D.n × 2ⁿ
Đáp án: C
Cần đúng 2ⁿ − 1 lần chuyển. Lời giải đệ quy: chuyển n−1 đĩa trên sang cọc phụ, chuyển đĩa lớn nhất sang cọc đích, rồi chuyển n−1 đĩa từ cọc phụ sang cọc đích. Hệ thức truy hồi T(n) = 2·T(n−1) + 1 với T(1) = 1 cho nghiệm 2ⁿ − 1, và đây cũng là số lần tối thiểu.
Đoạn code đếm số lời gọi của Fibonacci đệ quy sau in ra gì?
javascript
let calls = 0functionfib(n) {
calls++
if (n < 2) return n
returnfib(n - 1) + fib(n - 2)
}
const value = fib(6)
console.log(value, calls)
A.8 25
B.8 15
C.13 25
D.8 13
Đáp án: A
In ra 8 25. Dãy Fibonacci bắt đầu 0, 1, 1, 2, 3, 5, 8 nên fib(6) = 8. Số lời gọi thoả hệ thức C(n) = C(n−1) + C(n−2) + 1 với C(0) = C(1) = 1, cho C(6) = 25. Công thức gọn là C(n) = 2·fib(n+1) − 1.
Câu 52·Đệ quy & quay lui
Đệ quy đuôi là dạng đệ quy như thế nào?
A.Lời gọi đệ quy nằm ở dòng cuối cùng trong thân hàm khi đọc mã nguồn
B.Hàm gọi chính nó đúng một lần duy nhất trong toàn bộ thân hàm
C.Hàm xử lý phần tử cuối của cấu trúc dữ liệu trước rồi lùi dần về đầu
D.Lời gọi đệ quy là việc cuối cùng, kết quả trả thẳng ra không tính thêm
Đáp án: D
Lời gọi đệ quy là việc cuối cùng hàm làm, và kết quả của nó được trả thẳng ra ngoài. return f(n - 1, acc * n) là đệ quy đuôi; return n * f(n - 1) thì không, vì sau khi f trả về vẫn còn một phép nhân. Khi không còn việc gì sau lời gọi, khung ngăn xếp hiện tại có thể tái sử dụng.
Câu 53·Đệ quy & quay lui
Muốn viết lại một hàm đệ quy thành vòng lặp thì cần bổ sung thứ gì?
A.Một ngăn xếp tường minh do mình tự quản lý
B.Một bảng ghi nhớ
C.Một biến đếm giữ số lần hàm đã tự gọi lại chính nó
D.Một hàng đợi để lưu các trạng thái còn phải xử lý về sau
Đáp án: A
Một ngăn xếp tường minh. Đệ quy vốn chạy trên ngăn xếp lời gọi của máy; khử đệ quy chỉ là chuyển ngăn xếp ẩn đó thành một ngăn xếp mình tự đẩy và lấy ra. Mỗi phần tử lưu đúng những gì một khung lời gọi từng lưu: tham số và điểm đang xử lý dở.
Câu 54·Đệ quy & quay lui
Quay lui khác vét cạn thuần tuý ở điểm nào?
A.Quay lui duyệt các phương án theo thứ tự ngược lại so với vét cạn
B.Quay lui bỏ sớm cả nhánh khi biết chắc nhánh đó không dẫn tới lời giải
C.Quay lui dùng vòng lặp còn vét cạn thì bắt buộc phải viết bằng đệ quy
D.Quay lui luôn cho ra độ phức tạp đa thức còn vét cạn thì luôn là mũ
Đáp án: B
Quay lui cắt nhánh: ngay khi một lời giải dở dang đã vi phạm ràng buộc, toàn bộ nhánh con phía dưới bị bỏ mà không cần dựng ra. Vét cạn thuần tuý sinh đủ mọi phương án rồi mới kiểm tra. Cả hai cùng bậc mũ ở trường hợp xấu, nhưng quay lui thường nhanh hơn nhiều lần trên dữ liệu thật.
Câu 55·Đệ quy & quay lui
Một hàm đệ quy cộng dồn mảng n phần tử, mỗi lời gọi xử lý một phần tử. Bộ nhớ phụ là bao nhiêu?
A.O(n²)
B.O(log n)
C.O(n)
D.O(1)
Đáp án: C
O(n). Dù hàm không cấp phát mảng nào, mỗi lời gọi vẫn chiếm một khung trên ngăn xếp và có tới n khung tồn tại cùng lúc trước khi lời gọi sâu nhất bắt đầu trả về. Ngăn xếp lời gọi là bộ nhớ thật, phải tính vào độ phức tạp không gian.
Câu 56·Đệ quy & quay lui
Đệ quy tuyến tính khác đệ quy nhị phân ở chỗ nào về số lời gọi?
A.Tuyến tính sinh n² lời gọi vì mỗi mức phải quét lại toàn bộ dữ liệu
B.Tuyến tính sinh n lời gọi, nhị phân có thể sinh tới cỡ 2ⁿ lời gọi
C.Cả hai đều sinh đúng n lời gọi, chỉ khác nhau ở thứ tự thực thi
D.Nhị phân sinh log n lời gọi vì mỗi bước chia đôi kích thước bài toán
Đáp án: B
Đệ quy tuyến tính gọi chính nó một lần mỗi mức, tổng cộng n lời gọi và độ sâu n. Đệ quy nhị phân gọi hai lần mỗi mức, nên cây lời gọi nhân đôi theo mức và tổng có thể lên tới cỡ 2ⁿ, dù độ sâu vẫn chỉ là n. Đây là lý do bộ nhớ và thời gian của hai dạng lệch nhau rất xa.
Câu 57·Ngăn xếp & hàng đợi
Hàng đợi cài trên mảng thẳng gặp vấn đề gì mà hàng đợi vòng khắc phục được?
A.Chỗ trống ở đầu mảng bị bỏ phí sau nhiều lần lấy ra
B.Không biết đâu là đầu hàng
C.Thao tác thêm vào cuối hàng đợi trở thành O(n) thay vì O(1)
D.Các phần tử mất thứ tự sau khi hàng đợi đã đầy rồi lại vơi đi
Đáp án: A
Không gian ở đầu mảng bị bỏ phí. Mỗi lần lấy ra, chỉ số đầu tiến lên một và không bao giờ lùi lại, nên các ô phía trước dù đã trống vẫn không dùng lại được. Sau đủ số lần, chỉ số đuôi chạm cuối mảng và hàng đợi báo đầy trong khi nửa mảng đang rỗng. Hàng đợi vòng cho hai chỉ số quay lại đầu bằng phép chia lấy dư.
Câu 58·Ngăn xếp & hàng đợi
Cài ngăn xếp bằng mảng động so với bằng danh sách liên kết khác nhau thế nào?
A.Mảng cho thao tác đẩy vào và lấy ra là O(n), danh sách liên kết thì O(1)
B.Chỉ có bản cài bằng mảng mới giữ được đúng nguyên tắc vào sau ra trước
C.Danh sách liên kết tốn ít bộ nhớ hơn
D.Mảng nhanh hơn nhờ cache nhưng đôi lúc phải trả giá cấp phát lại
Đáp án: D
Về bậc thì tương đương, khác ở hằng số và ở độ ổn định. Mảng động cho đẩy vào O(1) khấu hao — thỉnh thoảng phải cấp phát lại và sao chép — nhưng phần tử nằm liên tiếp nên tận dụng cache tốt. Danh sách liên kết cho O(1) đều đặn, không có lần chậm đột biến, đổi lại mỗi nút tốn thêm con trỏ và duyệt gây cache miss.
Câu 59·Ngăn xếp & hàng đợi
Đoạn code thao tác ngăn xếp sau in ra gì?
javascript
const s = []
for (const ch of'ABCD') s.push(ch)
s.pop()
s.push('E')
s.pop()
s.pop()
console.log(s.join('') + '|' + s.length)
A.ABE|3
B.AB|2
C.AC|2
D.ABC|3
Đáp án: B
In ra AB|2. Diễn biến: đẩy A, B, C, D vào; pop bỏ D còn ABC; push('E') thành ABCE; pop bỏ E còn ABC; pop bỏ C còn AB. Độ dài cuối là 2.
Câu 60·Ngăn xếp & hàng đợi
Hàng đợi ưu tiên khác hàng đợi thường ở điểm nào?
A.Lấy ra phần tử có độ ưu tiên cao nhất chứ không phải phần tử vào sớm nhất
B.Chỉ cho phép thêm phần tử vào đúng vị trí đã được sắp xếp sẵn từ trước
C.Chỉ chứa được các phần tử là số, còn hàng đợi thường chứa mọi kiểu
D.Có sức chứa cố định trong khi hàng đợi thường thì mở rộng tuỳ ý
Đáp án: A
Thứ tự lấy ra do độ ưu tiên quyết định chứ không do thời điểm vào. Hàng đợi thường là FIFO thuần; hàng đợi ưu tiên luôn trả phần tử có khoá nhỏ nhất hoặc lớn nhất. Cài bằng heap nhị phân cho thêm vào và lấy ra đều O(log n), còn xem phần tử ở đỉnh là O(1).
Câu 61·Ngăn xếp & hàng đợi
Deque cho phép làm gì mà ngăn xếp và hàng đợi đều không làm được?
A.Thêm và lấy phần tử ở cả hai đầu, đều với chi phí O(1)
B.Truy cập phần tử giữa theo chỉ số
C.Tự động giữ các phần tử bên trong ở trạng thái đã được sắp xếp
D.Cho phép nhiều thread cùng thao tác mà không cần khoá đồng bộ
Đáp án: A
Thêm và lấy ở cả hai đầu, đều O(1). Deque là hàng đợi hai đầu, nên dùng được như ngăn xếp nếu chỉ thao tác một đầu, hoặc như hàng đợi nếu thêm ở đầu này lấy ở đầu kia. Vì vậy nhiều thư viện chuẩn chỉ cung cấp deque rồi để người dùng tự chọn cách dùng.
Câu 62·Ngăn xếp & hàng đợi
Vì sao duyệt đồ thị theo chiều rộng bắt buộc dùng hàng đợi?
A.Để mọi đỉnh cách nguồn k bước được xử lý hết trước lớp k cộng một
B.Vì chỉ hàng đợi mới cho thêm và lấy phần tử với chi phí không đổi
C.Vì hàng đợi tốn ít bộ nhớ hơn ngăn xếp khi số đỉnh của đồ thị lớn
D.Để tránh thăm lại một đỉnh đã được xử lý ở bước trước đó
Đáp án: A
Vì FIFO giữ đúng thứ tự theo lớp. Hàng đợi đảm bảo mọi đỉnh cách nguồn k bước được lấy ra hết trước bất kỳ đỉnh nào cách k+1 bước. Chính tính chất đó khiến lần đầu chạm tới một đỉnh cũng là đường đi ngắn nhất theo số cạnh. Thay bằng ngăn xếp là thành duyệt theo chiều sâu và mất luôn bảo đảm này.
Câu 63·Ngăn xếp & hàng đợi
Bài tìm giá trị lớn nhất của mọi cửa sổ trượt kích thước k đạt O(n) nhờ đâu?
A.Sắp xếp trước toàn bộ mảng rồi lấy phần tử lớn nhất của từng đoạn
B.Deque giữ chỉ số theo giá trị giảm dần, mỗi phần tử vào ra đúng một lần
C.Duyệt lại từng cửa sổ nhưng bỏ qua các phần tử đã biết là nhỏ hơn
D.Dùng một hàng đợi ưu tiên giữ đúng k phần tử đang nằm trong cửa sổ
Đáp án: B
Nhờ deque đơn điệu. Deque lưu chỉ số sao cho giá trị tương ứng giảm dần. Trước khi thêm phần tử mới, loại khỏi đuôi mọi phần tử nhỏ hơn nó — chúng không bao giờ còn cơ hội làm lớn nhất. Đồng thời loại khỏi đầu chỉ số đã trôi khỏi cửa sổ. Đầu deque luôn là đáp án, và mỗi phần tử vào ra đúng một lần nên tổng là O(n).
Trong ba thuật toán O(n²) quen thuộc, thuật toán nào thực hiện ít phép hoán vị nhất?
A.Cả ba bằng nhau, vì cùng thuộc nhóm O(n²)
B.Sắp xếp chọn, đúng n−1 lần hoán vị bất kể dữ liệu vào
C.Sắp xếp nổi bọt, vì mỗi lượt chỉ đẩy đúng một phần tử về cuối
D.Sắp xếp chèn, vì nó chỉ dịch chuyển chứ không thực sự hoán vị
Đáp án: B
Sắp xếp chọn, đúng n−1 lần hoán vị bất kể dữ liệu. Mỗi lượt nó quét tìm phần tử nhỏ nhất trong phần còn lại rồi hoán vị đúng một lần. Nổi bọt và chèn thì số phép ghi phụ thuộc dữ liệu và có thể lên tới O(n²).
Câu 65·Sắp xếp
Merge sort trên mảng cần bao nhiêu bộ nhớ phụ, và vì sao không tránh được?
A.O(n), vì bước trộn phải ghi kết quả ra vùng khác rồi mới chép về
B.O(1), vì thuật toán trộn tại chỗ ngay trên mảng gốc
C.O(log n), đúng bằng độ sâu của cây đệ quy
D.O(n log n), vì mỗi mức của cây đệ quy lại cần một vùng đệm riêng
Đáp án: A
O(n). Bước trộn đọc hai đoạn đã sắp xếp và ghi ra dãy kết quả; nếu ghi thẳng đè lên mảng gốc sẽ phá mất phần tử chưa đọc tới. Cách chuẩn là cấp một mảng đệm bằng kích thước mảng gốc và dùng chung cho mọi mức đệ quy, vì các mức không chạy cùng lúc.
Câu 66·Sắp xếp
Heapsort có O(n log n) ở trường hợp xấu nhất và sắp xếp tại chỗ. Vì sao vẫn ít được chọn làm mặc định?
A.Vì nó cần thêm một vùng nhớ phụ có kích thước bằng chính mảng đầu vào
B.Vì trường hợp xấu nhất của nó thực ra là O(n²)
C.Nó truy cập bộ nhớ nhảy cóc nên tận dụng cache kém, và không ổn định
D.Vì nó chỉ chạy đúng với dữ liệu là số nguyên
Đáp án: C
Vì cache và tính ổn định. Heapsort nhảy giữa chỉ số i và 2i+1, khoảng cách lớn dần nên mỗi bước vun đống thường rơi vào cache line khác. Quicksort quét tuần tự nên nhanh hơn đáng kể trên thực tế dù xấu nhất tệ hơn. Heapsort cũng không ổn định.
Câu 67·Sắp xếp
Đoạn code sắp xếp mảng số sau in ra gì?
javascript
const a = [10, 9, 100, 1, 25]
console.log(a.sort().join(','))
A.1,10,100,25,9
B.9,10,25,100,1
C.10,9,100,1,25
D.1,9,10,25,100
Đáp án: A
In ra 1,10,100,25,9. Array.prototype.sort() không có tham số sẽ chuyển mọi phần tử thành chuỗi rồi so sánh theo mã UTF-16, tức thứ tự từ điển. Chuỗi "10" đứng trước "9" vì ký tự "1" nhỏ hơn "9". Muốn đúng thứ tự số phải viết a.sort((x, y) => x - y).
Câu 68·Sắp xếp
Thế nào là một thuật toán sắp xếp "tại chỗ"?
A.Sắp xếp xong ngay trong một lượt duyệt duy nhất qua toàn bộ mảng
B.Không tạo ra bất kỳ biến tạm nào trong suốt quá trình chạy
C.Không hoán vị các phần tử mà chỉ đọc rồi ghi lại đúng chỗ cũ
D.Chỉ dùng thêm một lượng bộ nhớ hằng số ngoài mảng đầu vào
Đáp án: D
Thuật toán chỉ dùng thêm O(1) bộ nhớ ngoài mảng đầu vào. Vài biến tạm để hoán vị hay giữ chỉ số là hợp lệ; điều kiện là lượng đó không tăng theo n. Sắp xếp chèn, chọn, nổi bọt và heapsort đều tại chỗ. Merge sort trên mảng thì không, vì cần vùng đệm O(n).
Câu 69·Sắp xếp
Sắp xếp theo cơ số (radix sort) đạt được bậc dưới O(n log n) nhờ đâu?
A.Nó bỏ qua các phần tử trùng nhau để giảm số phép so sánh
B.Nó dùng nhiều thread để xử lý song song các đoạn của mảng
C.Nó phân loại theo từng chữ số thay vì so sánh các phần tử với nhau
D.Nó sắp xếp trước một mẫu nhỏ rồi suy ra thứ tự cho phần còn lại
Đáp án: C
Vì nó không so sánh phần tử với nhau. Cận dưới Ω(n log n) chỉ áp dụng cho thuật toán dựa trên so sánh. Radix sort phân loại theo từng chữ số, chạy d lượt với mỗi lượt là O(n + k) — trong đó d là số chữ số, k là số giá trị mỗi chữ số — cho tổng O(d·(n + k)).
Câu 70·Sắp xếp
Số lần hoán vị của sắp xếp nổi bọt trên một mảng bằng đúng đại lượng nào?
A.Số cặp nghịch thế, tức số cặp phần tử đang đứng sai thứ tự tương đối
B.Đúng n(n−1)/2 với mọi mảng đầu vào
C.Số lượt duyệt mà thuật toán phải thực hiện trước khi mảng được sắp xong
D.Số phần tử đang nằm sai vị trí cuối cùng của chúng
Đáp án: A
Bằng số cặp nghịch thế của mảng. Nổi bọt chỉ hoán vị hai phần tử kề nhau, và mỗi lần hoán vị như vậy loại bỏ đúng một cặp nghịch thế. Mảng đã sắp xếp có 0 cặp nên không hoán vị lần nào; mảng sắp xếp ngược có n(n−1)/2 cặp, là trường hợp xấu nhất.
Câu 71·Sắp xếp
Mảng chỉ gồm ba giá trị 0, 1 và 2. Sắp xếp trong một lượt duyệt và O(1) bộ nhớ thì làm thế nào?
A.Duyệt mảng và hoán vị mỗi cặp kề nhau đang đứng sai thứ tự cho tới khi hết
B.Ba con trỏ chia mảng thành vùng số 0, vùng số 1 và vùng số 2
C.Đếm số lần xuất hiện của từng giá trị rồi ghi đè lại mảng theo đúng số đếm
D.Gọi thuật toán sắp xếp nhanh với phần tử chốt được chọn ngẫu nhiên mỗi lần
Đáp án: B
Dùng phân hoạch ba đường của Dijkstra, quen gọi là bài toán quốc kỳ Hà Lan. Giữ ba con trỏ: low là biên phải của vùng số 0, high là biên trái của vùng số 2, và mid đang quét. Gặp 0 thì đổi với low và tiến cả hai; gặp 2 thì đổi với high và lùi high; gặp 1 thì chỉ tiến mid.
Kỹ thuật lính canh trong tìm kiếm tuần tự loại bỏ được phép kiểm tra nào?
A.Phép so sánh giữa phần tử hiện tại và giá trị cần tìm
B.Phép kiểm tra xem mảng đầu vào có đang rỗng hay không trước khi quét
C.Phép kiểm tra xem chỉ số đã vượt quá cuối mảng hay chưa
D.Phép tăng chỉ số sau mỗi vòng lặp
Đáp án: C
Bỏ được phép kiểm tra biêni < n. Cách làm: đặt chính giá trị cần tìm vào ô ngay sau phần tử cuối. Vòng lặp khi đó chắc chắn dừng vì luôn tìm thấy ít nhất một lần khớp. Sau vòng lặp chỉ cần xem chỉ số dừng có phải vị trí lính canh hay không để biết là tìm thấy thật hay không.
Câu 73·Tìm kiếm nhị phân
Tìm kiếm nhị phân trên mảng n phần tử cần tối đa bao nhiêu vòng lặp?
A.Khoảng √n
B.Phụ thuộc vào vị trí thực tế của phần tử cần tìm trong mảng đầu vào
C.Khoảng n/2 vì mỗi bước bỏ đi một nửa số phần tử
D.Khoảng log₂n, làm tròn lên
Đáp án: D
Khoảng log₂n vòng, chính xác là ⌈log₂(n+1)⌉. Mỗi vòng lặp loại bỏ một nửa khoảng còn lại, nên từ n phần tử phải chia đôi log₂n lần mới còn một. Với một triệu phần tử chỉ cần khoảng 20 vòng; với một tỉ là khoảng 30.
Câu 74·Tìm kiếm nhị phân
Đoạn tìm kiếm nhị phân sau in ra gì?
javascript
const a = [2, 5, 8, 12, 16, 23, 38, 56]
let lo = 0let hi = a.length - 1let steps = 0while (lo <= hi) {
steps++
const mid = (lo + hi) >> 1if (a[mid] === 23) { console.log(mid, steps); break }
if (a[mid] < 23) lo = mid + 1else hi = mid - 1
}
A.5 2
B.5 3
C.6 2
D.23 2
Đáp án: A
In ra 5 2. Vòng 1: lo=0, hi=7, mid=3, a[3]=12 nhỏ hơn 23 nên lo=4. Vòng 2: lo=4, hi=7, mid=5, a[5]=23 khớp và thoát. Vậy chỉ số là 5 và số vòng lặp là 2.
Câu 75·Tìm kiếm nhị phân
Mảng đã sắp xếp bị xoay vòng tại một vị trí không biết trước. Còn tìm nhị phân được không?
A.Được, vì mỗi lần chia luôn có ít nhất một nửa đang đúng thứ tự
B.Được, nhưng độ phức tạp tăng lên thành O(n)
C.Được, nhưng phải sắp xếp lại mảng về đúng thứ tự trước khi tìm kiếm
D.Không, vì mảng không còn được sắp xếp nữa
Đáp án: A
Được, vẫn O(log n). Mấu chốt: khi chia tại mid, luôn có ít nhất một trong hai nửa đang đúng thứ tự liền mạch. So a[lo] với a[mid] là biết nửa nào; nếu giá trị cần tìm nằm trong khoảng của nửa liền mạch đó thì tìm ở đó, ngược lại tìm ở nửa kia.
Cần tìm phần tử nhỏ thứ k trong mảng chưa sắp xếp. Cách nào cho O(n) trung bình?
A.Sắp xếp mảng rồi lấy phần tử ở vị trí thứ k
B.Quickselect, phân hoạch như quicksort nhưng chỉ đệ quy vào một phía
C.Dựng cây nhị phân tìm kiếm rồi duyệt giữa tới nút thứ k
D.Duyệt mảng k lượt, mỗi lượt tìm và loại bỏ phần tử nhỏ nhất còn lại
Đáp án: B
Quickselect. Phân hoạch mảng quanh một chốt như quicksort, nhưng sau đó chỉ đệ quy vào phía chứa vị trí k thay vì cả hai. Chi phí trung bình n + n/2 + n/4 + … hội tụ về khoảng 2n, tức O(n). Trường hợp xấu nhất vẫn là O(n²) khi chốt liên tục lệch.
Câu 77·Tìm kiếm
Tìm kiếm nội suy có thể nhanh hơn tìm nhị phân với điều kiện nào?
A.Khi mảng có kích thước nhỏ, dưới khoảng vài chục phần tử
B.Khi mảng chưa được sắp xếp theo thứ tự nào
C.Khi mảng chứa nhiều giá trị trùng nhau
D.Khi các giá trị trong mảng phân bố tương đối đều nhau
Đáp án: D
Khi các giá trị phân bố tương đối đều. Thay vì luôn lấy điểm giữa, nội suy ước lượng vị trí theo tỉ lệ giá trị — giống cách người ta lật từ điển: tìm chữ bắt đầu bằng "v" thì mở gần cuối chứ không mở giữa. Với dữ liệu đều, chi phí trung bình là O(log log n).
Câu 78·Tìm kiếm
Khi nào bảng băm là lựa chọn tốt hơn mảng đã sắp xếp kèm tìm nhị phân?
A.Khi tập dữ liệu nhỏ và hầu như không thay đổi
B.Khi chỉ cần tra chính xác một khoá và không cần duyệt theo thứ tự
C.Khi cần lấy ra các khoá nằm trong một khoảng giá trị
D.Khi cần tìm khoá nhỏ nhất hoặc lớn nhất trong toàn bộ tập dữ liệu
Đáp án: B
Khi chỉ cần tra chính xác một khoá và không quan tâm thứ tự. Bảng băm cho O(1) trung bình so với O(log n) của tìm nhị phân, và thêm hay xóa cũng O(1) thay vì O(n). Đổi lại nó mất hoàn toàn thứ tự khoá, nên không làm được truy vấn khoảng, tìm cực trị hay duyệt tăng dần.
Câu 79·Tìm kiếm
Mảng nhỏ khoảng 20 phần tử chưa sắp xếp, chỉ tra cứu đúng một lần. Nên dùng cách nào?
A.Sắp xếp rồi tìm nhị phân
B.Quét tuần tự, vì sắp xếp trước còn đắt hơn chính lần tra cứu đó
C.Dựng cây nhị phân tìm kiếm rồi tra trên cây
D.Dựng một bảng băm từ mảng rồi tra cứu khoá trong bảng đó
Đáp án: B
Quét tuần tự. Sắp xếp tốn O(n log n) và dựng bảng băm tốn O(n) — cả hai đều đắt hơn hoặc bằng chính lần quét O(n) mà chúng định thay thế. Chi phí chuẩn bị chỉ đáng bỏ ra khi được chia đều cho nhiều lần tra cứu về sau.
Câu 80·Cây & BST
Một cây nhị phân có tối đa bao nhiêu nút ở mức thứ k, tính gốc là mức 0?
A.k²
B.2^k
C.2^k − 1
D.2k
Đáp án: B
Tối đa 2^k nút. Mức 0 có 1 nút là gốc, mức 1 có tối đa 2, mức 2 có tối đa 4 — mỗi mức nhân đôi vì mỗi nút sinh tối đa hai con. Từ đó suy ra tổng số nút của cây có chiều cao h là tối đa 2^(h+1) − 1.
Câu 81·Cây & BST
Cây nhị phân hoàn chỉnh lưu bằng mảng, gốc ở chỉ số 0. Hai con của nút i nằm ở đâu?
A.i/2 và i/2+1
B.2i+1 và 2i+2
C.2i và 2i+1
D.i+1 và i+2
Đáp án: B
Con trái ở 2i+1, con phải ở 2i+2, và cha của nút j ở ⌊(j−1)/2⌋. Nhờ ba công thức này mà cây hoàn chỉnh lưu được trong mảng phẳng, không cần con trỏ nào. Nếu đặt gốc ở chỉ số 1 thì công thức gọn hơn: con là 2i và 2i+1, cha là ⌊j/2⌋.
Câu 82·Cây & BST
Chèn một khoá mới vào cây tìm kiếm nhị phân, nút mới luôn xuất hiện ở đâu?
A.Ở vị trí một nút lá
B.Ở vị trí gốc
C.Ở mức nông nhất còn chỗ trống, để giữ cho cây luôn cân bằng
D.Ở giữa cây, ngay tại chỗ mà giá trị khoá rơi vào theo thứ tự
Đáp án: A
Luôn ở vị trí một nút lá. Thuật toán đi từ gốc, so khoá mới với từng nút để rẽ trái hoặc phải, cho tới khi gặp một liên kết rỗng — nút mới treo vào chính chỗ đó. Vì vậy hình dạng cây phụ thuộc hoàn toàn vào thứ tự chèn.
Câu 83·Cây & BST
Xóa một nút có đủ hai con trong cây tìm kiếm nhị phân thì thay nó bằng nút nào?
A.Nút nhỏ nhất của cây con phải, hoặc lớn nhất của cây con trái
B.Nút con trái của nó, còn cây con phải được treo vào cuối nhánh trái
C.Nút gốc của cả cây, rồi toàn bộ cây được dựng lại từ đầu
D.Nút lá nằm sâu nhất trong cây, để giữ cho chiều cao không tăng thêm
Đáp án: A
Thay bằng nút kế vị trung tự — nút nhỏ nhất của cây con phải — hoặc đối xứng là nút tiền nhiệm, nút lớn nhất của cây con trái. Hai nút này đứng ngay cạnh nút bị xóa trong dãy trung tự, nên đưa chúng lên thay thì mọi quan hệ thứ tự vẫn giữ nguyên.
In ra 1 2 3 4 5 6. Lệnh out.push nằm giữa hai lời gọi đệ quy, tức duyệt trung tự. Vì cây này là một BST hợp lệ nên trung tự cho ra đúng dãy khoá tăng dần.
Câu 85·Cây & BST
Cây AVL thực hiện phép xoay khi nào?
A.Khi có một khoá bị xóa khỏi cây, còn khi chèn thì không cần xoay
B.Khi chênh lệch chiều cao hai cây con của một nút vượt quá một
C.Khi số nút của cây vượt quá một ngưỡng đã được đặt sẵn từ trước
D.Khi cây con trái và cây con phải có số lượng nút chênh nhau quá nhiều
Đáp án: B
Khi hệ số cân bằng của một nút — chiều cao cây con trái trừ chiều cao cây con phải — ra ngoài khoảng [−1, 1]. Sau mỗi lần chèn hoặc xóa, thuật toán đi ngược từ chỗ vừa sửa lên gốc, cập nhật chiều cao và xoay ngay nút đầu tiên vi phạm.
Câu 86·Cây & BST
Tìm tổ tiên chung gần nhất của hai nút trong một cây tìm kiếm nhị phân thì tận dụng được gì?
A.Nút đầu tiên có giá trị nằm giữa hai khoá chính là đáp án
B.Phải duyệt toàn bộ cây rồi ghi lại đường đi từ gốc xuống cả hai nút
C.Duyệt trung tự rồi lấy nút nằm chính giữa hai vị trí của hai khoá
D.Tổ tiên chung gần nhất của hai nút bất kỳ trong BST luôn chính là nút gốc
Đáp án: A
Tận dụng tính chất thứ tự. Đi từ gốc: nếu cả hai khoá đều nhỏ hơn nút hiện tại thì rẽ trái, cả hai lớn hơn thì rẽ phải. Nút đầu tiên mà hai khoá rẽ về hai phía khác nhau — hoặc nút trùng với một trong hai khoá — chính là tổ tiên chung gần nhất. Chi phí O(chiều cao), không cần bộ nhớ phụ.
Câu 87·Cây & BST
Heap và cây tìm kiếm nhị phân đều là cây nhị phân. Ràng buộc thứ tự của chúng khác nhau thế nào?
A.Heap chỉ ràng buộc cha với con, BST ràng buộc trái nhỏ hơn phải
B.Heap ràng buộc mọi nút phải khác giá trị nhau, còn BST thì cho phép trùng
C.Cả hai ràng buộc giống nhau, chỉ khác nhau ở cách lưu trữ bên dưới
D.Heap ràng buộc theo chiều cao còn BST ràng buộc theo số lượng nút mỗi nhánh
Đáp án: A
Heap chỉ đảm bảo quan hệ cha với con — cha luôn nhỏ hơn cả hai con ở min-heap. Hai nút anh em không có thứ tự nào. BST ràng buộc theo phương ngang: mọi nút bên trái nhỏ hơn nút gốc, mọi nút bên phải lớn hơn. Vì vậy BST có thứ tự toàn cục còn heap chỉ có thứ tự dọc theo mỗi đường từ gốc xuống.
Câu 88·Cây & BST
Duyệt hậu tự phù hợp nhất với loại công việc nào?
A.Việc cần lấy các khoá của cây tìm kiếm nhị phân theo thứ tự tăng dần
B.Việc cần ghi cây ra chuỗi để lưu rồi dựng lại đúng hình dạng ban đầu
C.Việc cần kết quả của các con trước khi xử lý được nút cha
D.Việc cần tìm đường đi ngắn nhất tính theo số cạnh giữa hai nút bất kỳ
Đáp án: C
Việc mà nút cha phụ thuộc kết quả của các con. Tính kích thước thư mục phải cộng xong các thư mục con; giải phóng bộ nhớ phải xóa con trước rồi mới xóa cha; đánh giá cây biểu thức phải có giá trị hai toán hạng rồi mới áp dụng toán tử. Hậu tự đảm bảo đúng thứ tự đó.
Câu 89·Cây & BST
Cây nhị phân đầy đủ, tức mọi nút có 0 hoặc 2 con, có L nút lá thì có bao nhiêu nút trong?
A.2L − 1
B.L
C.L + 1
D.L − 1
Đáp án: D
Đúng L − 1 nút trong, và tổng số nút của cây là 2L − 1. Chứng minh bằng quy nạp: cây một nút có L = 1 và 0 nút trong. Mỗi lần biến một lá thành nút trong bằng cách thêm hai con, số nút trong tăng 1 còn số lá tăng 1, nên hiệu luôn giữ nguyên.
Câu 90·Cây & BST
Duyệt cây theo mức cần cấu trúc gì, và tách được từng mức riêng bằng cách nào?
A.Hàng đợi, và ghi lại số phần tử đang có trước khi xử lý mỗi mức
B.Hàng đợi, và chèn thêm một phần tử đánh dấu vào giữa hai mức liền nhau
C.Ngăn xếp, và đếm số nút đã lấy ra để biết khi nào sang mức kế tiếp
D.Hàng đợi ưu tiên, xếp các nút theo độ sâu của chúng trong cây
Đáp án: A
Cần hàng đợi. Mẹo tách mức: ngay đầu mỗi vòng lặp ngoài, ghi lại size = queue.length — đó chính là số nút của mức hiện tại. Lấy ra đúng size nút, xử lý chúng và đẩy con của chúng vào; khi vòng trong kết thúc là hết một mức.
Câu 91·Ký pháp hậu tố & cây biểu thức
Biểu thức trung tố a + b * c chuyển sang hậu tố là gì?
A.a b + c *
B.a b c * +
C.b c * a +
D.a + b c *
Đáp án: B
a b c * +. Vì phép nhân ưu tiên cao hơn phép cộng nên b * c được nhóm trước, cho b c *; sau đó cộng với a cho a b c * +. Kiểm tra bằng cách đánh giá: gặp * thì lấy b và c nhân lại, gặp + thì lấy a và kết quả vừa có.
Câu 92·Ký pháp hậu tố & cây biểu thức
Đánh giá một biểu thức đã ở dạng hậu tố cần cấu trúc dữ liệu nào?
A.Hàng đợi
B.Ngăn xếp
C.Cây nhị phân
D.Bảng băm
Đáp án: B
Ngăn xếp. Quét biểu thức từ trái sang phải: gặp toán hạng thì đẩy vào ngăn xếp; gặp toán tử thì lấy ra hai giá trị, tính, rồi đẩy kết quả trở lại. Hết biểu thức thì giá trị duy nhất còn lại trên ngăn xếp chính là đáp án.
Câu 93·Ký pháp hậu tố & cây biểu thức
Đoạn code đánh giá biểu thức hậu tố sau in ra gì?
javascript
functionevalPostfix(expr) {
const st = []
for (const t of expr.split(' ')) {
if (!'+-*/'.includes(t)) { st.push(Number(t)); continue }
const b = st.pop()
const a = st.pop()
st.push(t === '+' ? a + b : t === '-' ? a - b : t === '*' ? a * b : a / b)
}
return st.pop()
}
console.log(evalPostfix('5 1 2 + 4 * + 3 -'))
A.14
B.-2
C.11
D.20
Đáp án: A
In ra 14. Lần theo ngăn xếp: đẩy 5, 1, 2 → gặp + lấy 1 và 2 cho 3, ngăn xếp còn [5, 3] → đẩy 4 → gặp * cho 3×4 = 12, còn [5, 12] → gặp + cho 17 → đẩy 3 → gặp - cho 17 − 3 = 14.
Câu 94·Ký pháp hậu tố & cây biểu thức
Thuật toán shunting-yard lấy một toán tử ra khỏi ngăn xếp khi nào?
A.Chỉ khi quét hết toàn bộ biểu thức và bắt đầu dọn ngăn xếp
B.Khi ngăn xếp đã chứa nhiều hơn hai toán tử cùng lúc
C.Khi gặp một toán hạng mới trong quá trình quét biểu thức trung tố
D.Khi toán tử ở đỉnh có độ ưu tiên lớn hơn hoặc bằng toán tử đang xét
Đáp án: D
Khi toán tử đang ở đỉnh ngăn xếp có độ ưu tiên lớn hơn hoặc bằng toán tử vừa quét được. Lấy ra và đưa thẳng vào kết quả, lặp lại tới khi điều kiện không còn đúng, rồi mới đẩy toán tử mới vào. Dấu ngoặc mở là ngoại lệ: nó chặn việc lấy ra cho tới khi gặp dấu ngoặc đóng.
Câu 95·Ký pháp hậu tố & cây biểu thức
Duyệt tiền tự một cây biểu thức cho ra ký pháp nào?
A.Hậu tố
B.Trung tố
C.Không ký pháp nào
D.Tiền tố
Đáp án: D
Ký pháp tiền tố. Trong cây biểu thức, nút trong là toán tử còn nút lá là toán hạng. Duyệt tiền tự thăm toán tử trước hai toán hạng, đúng dạng + a b. Tương ứng, hậu tự cho hậu tố và trung tự cho trung tố.
Câu 96·Ký pháp hậu tố & cây biểu thức
Vì sao ký pháp hậu tố không cần dấu ngoặc mà vẫn không mơ hồ?
A.Vì các toán hạng luôn được sắp xếp lại theo thứ tự cần tính toán trước
B.Vị trí toán tử đã xác định luôn hai toán hạng nào thuộc về nó
C.Vì mỗi biểu thức hậu tố chỉ được phép chứa nhiều nhất một toán tử duy nhất
D.Vì hậu tố quy định mọi toán tử đều có cùng một mức độ ưu tiên như nhau
Đáp án: B
Vì vị trí của toán tử đã xác định hai toán hạng của nó: luôn là hai kết quả vừa hoàn thành gần nhất. Không có chỗ nào cho phép đọc theo hai cách, nên không cần độ ưu tiên lẫn dấu ngoặc. Trung tố thì a + b * c đọc được hai kiểu nếu không có quy tắc ưu tiên.
Câu 97·Độ phức tạp
Hai đoạn chương trình chạy nối tiếp nhau, một đoạn O(n) và một đoạn O(n²). Tổng là gì?
A.O(n)
B.O(n³)
C.O(n²)
D.O(n² + n)
Đáp án: C
O(n²). Đây là quy tắc cộng: hai đoạn nối tiếp thì lấy bậc lớn hơn, vì khi n đủ lớn số hạng nhỏ hơn không còn ảnh hưởng. Phân biệt với quy tắc nhân: hai vòng lặp lồng nhau mới nhân bậc, cho O(n) × O(n²) = O(n³).
Câu 98·Độ phức tạp
Vòng lặp trong chạy từ 0 tới i, còn vòng ngoài chạy i từ 0 tới n. Tổng số lần lặp là bậc gì?
javascript
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
work()
}
}
A.O(n log n)
B.O(n)
C.O(n²)
D.O(n³)
Đáp án: C
O(n²). Tổng số lần lặp là 0 + 1 + 2 + … + (n−1) = n(n−1)/2, tức khoảng n²/2. Big-O bỏ hằng số 1/2 nên kết quả vẫn là O(n²). Điểm dễ nhầm: thấy vòng trong "chỉ chạy tới i" nên tưởng rẻ hơn, thực ra chỉ rẻ hơn đúng một nửa.
Câu 99·Độ phức tạp
Vòng lặp for (i = 1; i < n; i *= 2) chạy bao nhiêu lần?
A.Khoảng n/2 lần
B.Khoảng √n lần
C.Đúng n lần
D.Khoảng log₂n lần
Đáp án: D
Khoảng log₂n lần. Biến i nhận các giá trị 1, 2, 4, 8, …, 2^k và vòng lặp dừng khi 2^k ≥ n, tức k ≈ log₂n. Với n = 1000 chỉ khoảng 10 lần; với n = một triệu là khoảng 20 lần.
Câu 100·Độ phức tạp
Ký hiệu Θ (theta) khác Big-O ở điểm nào?
A.Θ bỏ hằng số còn O thì giữ lại hằng số nhân
B.Θ tính cả bộ nhớ còn O chỉ tính thời gian chạy
C.Θ dùng cho trường hợp trung bình, O dùng cho trường hợp xấu nhất
D.Θ chặn cả trên lẫn dưới, còn O chỉ chặn trên
Đáp án: D
Θ là chặn hai phía, O chỉ là chặn trên. Nói tìm nhị phân là O(n²) không sai — nó thật sự không chậm hơn n² — nhưng vô ích. Nói Θ(log n) mới là mô tả chính xác. Ω là chặn dưới, và Θ tồn tại khi O và Ω trùng bậc.
Câu 101·Độ phức tạp
Chi phí "trung bình" và chi phí "khấu hao" khác nhau thế nào?
A.Hai khái niệm này thực chất là một, chỉ khác nhau ở cách gọi tên trong tài liệu
B.Khấu hao luôn cho kết quả tốt hơn trung bình
C.Trung bình lấy kỳ vọng trên dữ liệu, khấu hao chia đều trên chuỗi thao tác
D.Trung bình dùng cho thời gian, khấu hao dùng cho bộ nhớ
Đáp án: C
Trung bình là kỳ vọng theo phân bố dữ liệu đầu vào — quicksort O(n log n) trung bình, nhưng đầu vào xấu vẫn cho O(n²). Khấu hao là chi phí chia đều trên một chuỗi thao tác và là bảo đảm chắc chắn: thêm phần tử vào mảng động là O(1) khấu hao, tức n lần thêm luôn tốn O(n), không phụ thuộc may rủi.
Câu 102·Độ phức tạp
Độ phức tạp không gian của một thuật toán có tính luôn cả kích thước dữ liệu đầu vào không?
A.Có, tổng bộ nhớ luôn phải cộng cả phần dữ liệu đầu vào vào kết quả cuối
B.Chỉ tính khi thuật toán có sửa đổi dữ liệu đầu vào
C.Tuỳ ngôn ngữ lập trình được dùng để cài đặt
D.Thường không; người ta báo bộ nhớ phụ, tức phần cấp phát thêm
Đáp án: D
Thường không. Quy ước là báo bộ nhớ phụ — phần cấp phát thêm ngoài đầu vào. Nếu tính cả đầu vào thì mọi thuật toán trên mảng n phần tử đều ít nhất O(n) và con số đó không phân biệt được gì. Nhờ quy ước này mà "sắp xếp tại chỗ" mới có nghĩa là O(1).
Câu 103·Độ phức tạp
Thuật toán A là O(n) với hằng số rất lớn, B là O(n²) với hằng số nhỏ. Chọn cái nào?
A.Luôn chọn B vì hằng số nhỏ thì thực tế bao giờ cũng nhanh hơn
B.Chọn cái nào cũng như nhau vì Big-O đã bỏ hằng số
C.Luôn chọn A vì bậc tuyến tính tốt hơn bậc hai
D.Tuỳ n; phải ước lượng điểm hoà vốn rồi mới quyết định
Đáp án: D
Tuỳ vào n thực tế. Big-O chỉ mô tả xu hướng khi n tiến ra vô cùng; ở vùng n nhỏ thì hằng số chi phối. Cách quyết định đúng là ước lượng điểm hoà vốn — giải c₁·n = c₂·n² — rồi so với khoảng n mà hệ thống thật sự gặp.
Câu 104·Hash map & set
Hai cách xử lý va chạm phổ biến là nối chuỗi và địa chỉ mở. Khác biệt cơ bản là gì?
A.Nối chuỗi cho O(1), địa chỉ mở luôn cho O(n)
B.Nối chuỗi cần hàm băm tốt, địa chỉ mở thì không cần
C.Nối chuỗi dùng cho khoá dạng chuỗi ký tự, còn địa chỉ mở dùng cho khoá dạng số
D.Nối chuỗi để phần tử va chạm ngoài bảng, địa chỉ mở tìm ô trống khác trong bảng
Đáp án: D
Nối chuỗi cho mỗi ô của bảng trỏ tới một danh sách liên kết chứa mọi khoá băm về ô đó. Địa chỉ mở giữ mọi phần tử ngay trong mảng bảng: khi ô đã bị chiếm thì dò tìm theo một quy tắc — tuyến tính, bậc hai, hoặc băm kép — cho tới khi gặp ô trống.
Câu 105·Hash map & set
Hệ số tải của bảng băm là gì, và vượt ngưỡng thì chuyện gì xảy ra?
A.Số va chạm đã xảy ra; vượt ngưỡng thì hàm băm được thay bằng hàm khác
B.Số lần tra cứu mỗi giây; vượt ngưỡng thì các yêu cầu bị xếp hàng chờ
C.Tỉ lệ số phần tử trên số ô; vượt ngưỡng thì bảng được mở rộng và băm lại
D.Số byte trung bình mỗi phần tử chiếm; vượt ngưỡng thì bảng bị nén lại
Đáp án: C
Hệ số tải là số phần tử chia cho số ô của bảng. Càng cao thì va chạm càng nhiều và số lần dò càng tăng. Vượt ngưỡng — thường 0,75 với nối chuỗi và 0,5 tới 0,7 với địa chỉ mở — thì bảng cấp phát mảng lớn hơn, thường gấp đôi, rồi băm lại toàn bộ khoá vào bảng mới.
Câu 106·Hash map & set
Một hàm băm tốt cho bảng băm cần tính chất nào là quan trọng nhất?
A.Chống được việc suy ngược từ giá trị băm ra khoá gốc
B.Không bao giờ sinh ra hai giá trị băm trùng nhau cho hai khoá
C.Cho ra giá trị băm tăng dần theo thứ tự của khoá đầu vào
D.Phân tán khoá đều khắp các ô, kể cả khi khoá đầu vào có quy luật
Đáp án: D
Phân tán đều. Hàm băm phải rải khoá ra khắp các ô, kể cả khi khoá đầu vào có quy luật — chuỗi số tăng dần, tên có tiền tố giống nhau, địa chỉ bộ nhớ cách đều. Phân tán kém thì chuỗi va chạm dài ra và tra cứu tụt từ O(1) về O(n).
Câu 107·Hash map & set
Dò tuyến tính trong bảng băm gặp hiện tượng nào làm hiệu năng xấu đi?
A.Các ô bị chiếm dồn thành cụm liền nhau và cụm lớn dần
B.Giá trị băm bị tràn số khi bảng vượt quá một kích thước nào đó
C.Các khoá bị phân tán quá đều nên mất tính cục bộ của bộ nhớ đệm
D.Bảng phải băm lại sau mỗi lần chèn để giữ cho chuỗi dò ngắn
Đáp án: A
Cụm sơ cấp. Dò tuyến tính đi sang ô kế tiếp khi va chạm, nên các ô bị chiếm dồn thành từng cụm liền nhau. Cụm càng dài thì xác suất một khoá mới rơi vào nó càng cao, và rơi vào là cụm dài thêm. Đây là vòng phản hồi dương làm số lần dò tăng nhanh khi hệ số tải lên cao.
Câu 108·Hash map & set
Vì sao kích thước bảng băm thường được chọn là số nguyên tố?
A.Giảm dồn cụm khi giá trị băm có ước chung với kích thước bảng
B.Số nguyên tố đảm bảo không bao giờ có hai khoá cùng ô
C.Số nguyên tố giúp phép chia lấy dư chạy nhanh hơn trên bộ xử lý
D.Số nguyên tố cho phép bảng mở rộng mà không cần băm lại khoá
Đáp án: A
Để giảm dồn cụm khi giá trị băm có quy luật. Nếu kích thước bảng là 16 thì hash % 16 chỉ dùng bốn bit thấp của giá trị băm; các khoá chỉ khác nhau ở bit cao sẽ đụng nhau hết. Kích thước nguyên tố khiến phép chia dư phụ thuộc toàn bộ các bit, nên trải đều hơn.
Câu 109·Hash map & set
Ghi đè hàm so sánh bằng của một lớp mà quên ghi đè hàm băm dẫn tới hậu quả gì?
A.Hai đối tượng bằng nhau rơi vào hai ô khác nhau nên tra cứu không thấy
B.Chương trình báo lỗi ngay lúc biên dịch vì hai hàm này bắt buộc phải đi thành cặp
C.Mọi đối tượng của lớp đó đều bị coi là bằng nhau
D.Bảng băm tự động dùng hàm so sánh bằng để thay thế
Đáp án: A
Hai đối tượng "bằng nhau" theo logic nghiệp vụ lại có giá trị băm khác nhau, nên rơi vào hai ô khác nhau. Bảng băm định vị ô theo giá trị băm trước rồi mới so bằng trong ô đó — khác ô thì phép so bằng không bao giờ được gọi. Kết quả: chèn một đối tượng rồi tra bằng một đối tượng tương đương sẽ báo không tìm thấy.
Câu 110·Đồ thị
DFS và BFS trên cùng một đồ thị khác nhau thế nào về bộ nhớ cần dùng?
A.BFS tốn ít hơn vì hàng đợi chỉ giữ đúng một đỉnh tại mỗi thời điểm
B.Cả hai luôn tốn đúng O(V) như nhau vì cùng phải lưu tập đã thăm
C.DFS tốn nhiều hơn vì phải lưu toàn bộ các cạnh đã đi qua
D.DFS tốn theo độ sâu, BFS tốn theo bề rộng của lớp lớn nhất
Đáp án: D
DFS tốn O(độ sâu) cho ngăn xếp, BFS tốn O(bề rộng lớp lớn nhất) cho hàng đợi. Với đồ thị phân nhánh rộng và nông thì DFS tiết kiệm hơn nhiều; với đồ thị sâu và hẹp thì ngược lại. Cả hai đều cần thêm O(V) cho tập đỉnh đã thăm.
Câu 111·Đồ thị
Phát hiện chu trình trong đồ thị có hướng khác gì so với đồ thị vô hướng?
A.Phải phân biệt đỉnh đang trong ngăn xếp đệ quy với đỉnh đã xử lý xong
B.Phải bỏ qua cạnh dẫn ngược về đúng đỉnh cha vừa đi tới
C.Phải chạy BFS thay vì DFS vì DFS không phát hiện được chu trình có hướng
D.Không phát hiện được chu trình trong đồ thị có hướng bằng cách duyệt
Đáp án: A
Phải dùng ba trạng thái thay vì hai: chưa thăm, đang trong ngăn xếp đệ quy, và đã xử lý xong. Chu trình tồn tại khi gặp một đỉnh đang trong ngăn xếp. Gặp đỉnh đã xử lý xong chỉ nghĩa là có hai đường cùng dẫn tới đó, hoàn toàn hợp lệ trong đồ thị có hướng.
Câu 112·Đồ thị
Kruskal và Prim cùng tìm cây khung nhỏ nhất. Cách tiếp cận khác nhau ra sao?
A.Kruskal chạy trên đồ thị có hướng, Prim chạy trên đồ thị vô hướng
B.Kruskal xét cạnh theo trọng số tăng dần, Prim lớn dần từ một đỉnh
C.Kruskal cho ra cây khung nhỏ nhất, còn Prim chỉ cho ra một cây khung bất kỳ
D.Kruskal cần trọng số dương còn Prim chấp nhận cả trọng số âm
Đáp án: B
Kruskal sắp xếp mọi cạnh theo trọng số tăng dần rồi lần lượt lấy cạnh nào không tạo chu trình, dùng union-find để kiểm tra. Prim bắt đầu từ một đỉnh và mỗi bước thêm cạnh nhẹ nhất nối cây hiện tại với một đỉnh chưa thuộc cây, dùng hàng đợi ưu tiên.
Câu 113·Đồ thị
Cấu trúc union-find (disjoint set union) giải quyết loại câu hỏi nào?
A.Liệt kê toàn bộ các phần tử đang thuộc về một nhóm cho trước
B.Hai phần tử có thuộc cùng một nhóm không, và gộp hai nhóm lại
C.Sắp xếp các phần tử theo thứ tự tăng dần của khoá
D.Đường đi ngắn nhất giữa hai đỉnh bất kỳ của đồ thị
Đáp án: B
Hai câu hỏi: hai phần tử có cùng nhóm không (find) và gộp hai nhóm lại (union). Với hai tối ưu là nén đường đi và gộp theo hạng, mỗi thao tác gần như O(1) — chính xác là O(α(n)) với α là hàm Ackermann ngược, nhỏ hơn 5 với mọi n thực tế.
Câu 114·Đồ thị
Đếm số thành phần liên thông của một đồ thị vô hướng thì làm thế nào?
A.Duyệt từ mỗi đỉnh chưa thăm, đếm số lần phải khởi động lượt duyệt mới
B.Chạy Dijkstra từ một đỉnh và đếm số đỉnh không tới được
C.Đếm tổng số đỉnh của đồ thị rồi trừ đi tổng số cạnh đang có trong đó
D.Đếm số đỉnh có bậc bằng không trong đồ thị
Đáp án: A
Lặp qua mọi đỉnh; gặp đỉnh chưa thăm thì tăng bộ đếm lên một và chạy DFS hoặc BFS từ đó để đánh dấu toàn bộ vùng liên thông chứa nó. Số lần phải khởi động một lượt duyệt mới chính là số thành phần liên thông. Chi phí O(V + E), một lượt duyệt toàn đồ thị.
Câu 115·Tổng quan & ADT
Một dãy các bước được gọi là thuật toán thì bắt buộc phải thoả tính chất nào?
A.Chạy xong trong thời gian đa thức theo kích thước đầu vào
B.Cho ra cùng một kết quả với mọi bộ dữ liệu đầu vào có thể có
C.Viết được bằng ít nhất một ngôn ngữ lập trình bậc cao
D.Dừng sau hữu hạn bước, mỗi bước xác định rõ ràng không mơ hồ
Đáp án: D
Hai tính chất cốt lõi: tính dừng — kết thúc sau hữu hạn bước — và tính xác định — mỗi bước phải rõ ràng, cùng đầu vào luôn cho cùng chuỗi thao tác. Giáo trình thường liệt kê thêm: có đầu vào, có đầu ra, và mỗi bước phải khả thi để thực hiện.
Câu 116·Tổng quan & ADT
Đánh giá một cấu trúc dữ liệu có tốt hay không thì dựa vào tiêu chí nào?
A.Phản ánh đúng bài toán, thao tác cần dùng đủ nhanh, và tiết kiệm bộ nhớ
B.Được nhắc tới trong giáo trình và các tài liệu tham khảo phổ biến
C.Số dòng code cần viết để cài đặt nó
D.Có sẵn trong thư viện chuẩn của ngôn ngữ lập trình đang được sử dụng
Đáp án: A
Ba tiêu chí giáo trình thường nêu: phản ánh đúng thực tế bài toán, thao tác thường dùng phải đủ nhanh, và tiết kiệm bộ nhớ. Trong ba cái, tiêu chí thứ hai thường quyết định — phải xác định thao tác nào chạy nhiều nhất rồi chọn cấu trúc tối ưu cho đúng thao tác đó.
Câu 117·Tổng quan & ADT
Kiểu dữ liệu cơ bản khác kiểu dữ liệu có cấu trúc ở chỗ nào?
A.Kiểu cơ bản không thể dùng làm khoá trong các cấu trúc dữ liệu tra cứu
B.Kiểu cơ bản do ngôn ngữ định nghĩa sẵn còn kiểu có cấu trúc do lập trình viên tự tạo
C.Kiểu cơ bản chiếm ít bộ nhớ hơn kiểu có cấu trúc
D.Kiểu cơ bản là giá trị đơn không chia nhỏ được, kiểu có cấu trúc gộp nhiều thành phần
Đáp án: D
Kiểu cơ bản mang một giá trị nguyên khối, không truy cập được thành phần bên trong: số nguyên, số thực, ký tự, logic. Kiểu có cấu trúc gộp nhiều thành phần lại và cho phép truy cập từng phần riêng: mảng, bản ghi, chuỗi, tập hợp.
Câu 118·Tổng quan & ADT
Cấu trúc dữ liệu tĩnh khác cấu trúc dữ liệu động ở điểm nào?
A.Tĩnh nằm trên ngăn xếp còn động luôn nằm trên vùng nhớ động của tiến trình
B.Tĩnh không sửa được giá trị phần tử, động thì sửa được
C.Tĩnh cố định kích thước từ lúc khai báo, động cấp phát thêm lúc chạy
D.Tĩnh chỉ chứa được kiểu cơ bản, động chứa được cả kiểu có cấu trúc
Đáp án: C
Cấu trúc tĩnh cố định số phần tử ngay từ lúc khai báo — mảng kích thước cố định là ví dụ chuẩn. Cấu trúc động cấp phát và giải phóng bộ nhớ trong lúc chạy nên co giãn theo nhu cầu thật — danh sách liên kết, cây, mảng động đều thuộc nhóm này.
Câu 119·Tổng quan & ADT
Vì sao khai báo biến theo giao diện thay vì theo lớp cài đặt cụ thể lại có lợi?
A.Đổi cách cài đặt về sau mà không phải sửa code đang dùng nó
B.Chương trình chạy nhanh hơn vì giao diện nhẹ hơn lớp cụ thể
C.Trình biên dịch kiểm tra được nhiều lỗi hơn khi biết chính xác giao diện
D.Tiết kiệm bộ nhớ vì giao diện không mang theo dữ liệu của riêng nó
Đáp án: A
Vì code gọi chỉ phụ thuộc vào hợp đồng chứ không phụ thuộc cách thực hiện. Khai báo List<T> ds = new ArrayList<>() thì sau này đổi sang LinkedList chỉ phải sửa đúng một dòng. Nếu khai báo thẳng ArrayList<T> thì mọi nơi dùng biến đó đều có thể bị ràng buộc vào lớp cụ thể.
Câu 120·Tổng quan & ADT
Con trỏ hoặc tham chiếu đóng vai trò gì trong các cấu trúc dữ liệu động?
A.Nối các vùng nhớ rời rạc lại thành một cấu trúc có quan hệ
B.Giúp truy cập phần tử theo chỉ số nhanh hơn so với dùng mảng
C.Tự động giải phóng bộ nhớ khi phần tử không còn được sử dụng nữa
D.Đảm bảo các phần tử của cấu trúc luôn được cấp phát cạnh nhau trong bộ nhớ
Đáp án: A
Con trỏ mang quan hệ giữa các phần tử. Mảng suy ra quan hệ từ vị trí liên tiếp nên không cần con trỏ. Cấu trúc động cấp phát từng nút rải rác khắp bộ nhớ, nên thứ duy nhất cho biết nút nào nối với nút nào chính là con trỏ lưu trong mỗi nút.
Câu 121·Tổng quan & ADT
Cùng một ADT hàng đợi ưu tiên, cài bằng danh sách đã sắp xếp so với cài bằng heap khác nhau ra sao?
A.Heap chỉ dùng được cho khoá là số còn danh sách sắp xếp nhận mọi kiểu khoá
B.Chỉ heap mới hiện thực đúng được hợp đồng của hàng đợi ưu tiên
C.Danh sách sắp xếp cho kết quả chính xác hơn heap khi có nhiều phần tử cùng độ ưu tiên
D.Danh sách sắp xếp chèn O(n) lấy O(1), heap thì cả hai đều O(log n)
Đáp án: D
Danh sách đã sắp xếp: chèn O(n) vì phải tìm chỗ và dịch phần tử, lấy phần tử ưu tiên nhất O(1) vì nó nằm sẵn ở đầu. Heap: cả chèn lẫn lấy đều O(log n). Cùng một hợp đồng ADT, hai hồ sơ chi phí khác hẳn nhau.
Câu 122·Quy hoạch động
Bài đổi tiền với các mệnh giá bất kỳ, vì sao thuật toán tham lam lấy đồng lớn nhất trước lại sai?
A.Vì tham lam chạy chậm hơn quy hoạch động rất nhiều
B.Vì tham lam không xử lý được trường hợp số tiền cần đổi quá lớn
C.Vì tham lam đòi hỏi các mệnh giá phải được sắp xếp sẵn theo thứ tự tăng dần
D.Lựa chọn tốt nhất tại chỗ có thể chặn mất lời giải tối ưu toàn cục
Đáp án: D
Vì lựa chọn tốt nhất tại chỗ không đảm bảo tối ưu toàn cục. Ví dụ đối chứng gọn nhất: mệnh giá {1, 3, 4}, đổi số tiền 6. Tham lam lấy 4 rồi buộc phải lấy 1 và 1, tổng ba đồng. Lời giải tối ưu là 3 + 3, chỉ hai đồng.
Câu 123·Quy hoạch động
Quy hoạch động khác chia để trị ở điểm cốt lõi nào?
A.Quy hoạch động luôn viết bằng vòng lặp còn chia để trị luôn viết đệ quy
B.Quy hoạch động chỉ giải bài toán tối ưu còn chia để trị giải mọi loại bài
C.Bài toán con của quy hoạch động gối lên nhau nên đáng lưu lại kết quả
D.Chia để trị luôn cho độ phức tạp tốt hơn quy hoạch động trên cùng bài toán
Đáp án: C
Bài toán con của quy hoạch động gối lên nhau, còn của chia để trị thì rời nhau. Merge sort chia mảng thành hai nửa không giao nhau nên lưu kết quả cũng vô ích. Fibonacci hay bài cái túi thì cùng một bài toán con bị hỏi lại nhiều lần, nên lưu lại là tiết kiệm được rất nhiều.
Câu 124·Quy hoạch động
Khoảng cách sửa (edit distance) giữa hai chuỗi độ dài m và n dùng bảng cỡ nào?
A.Bảng một chiều độ dài bằng tổng độ dài của cả hai chuỗi đầu vào
B.Bảng (m+n) × (m+n) để chứa được mọi cặp vị trí có thể xảy ra
C.Bảng m × n, không cần hàng và cột phụ cho chuỗi rỗng
D.Bảng (m+1) × (n+1), mỗi ô là khoảng cách giữa hai tiền tố
Đáp án: D
Bảng (m+1) × (n+1). Ô dp[i][j] là khoảng cách sửa giữa i ký tự đầu của chuỗi thứ nhất và j ký tự đầu của chuỗi thứ hai. Hàng 0 và cột 0 ứng với chuỗi rỗng, điền sẵn 0, 1, 2, … vì phải chèn hoặc xóa toàn bộ. Chi phí O(m·n) cả thời gian lẫn bộ nhớ.
Câu 125·Quy hoạch động
Nguyên lý tối ưu Bellman phát biểu điều gì?
A.Thuật toán tham lam luôn cho kết quả tối ưu nếu bài toán con gối lên nhau
B.Lời giải tối ưu của một bài toán luôn là duy nhất và không có lời giải nào khác cùng giá trị
C.Mọi đoạn con của một lời giải tối ưu cũng phải là tối ưu cho đoạn đó
D.Bài toán tối ưu nào cũng giải được bằng quy hoạch động
Đáp án: C
Rằng mọi đoạn con của lời giải tối ưu cũng phải tối ưu cho chính đoạn đó. Đây là tính chất cấu trúc con tối ưu. Lập luận: nếu một đoạn con chưa tối ưu, thay nó bằng đoạn tốt hơn sẽ cho lời giải tổng thể tốt hơn, mâu thuẫn với giả thiết ban đầu đã tối ưu.
Câu 126·Quy hoạch động
Ghi nhớ kết quả (memoisation) không giúp được gì với thuật toán nào sau đây?
A.Bài cái túi 0/1 giải bằng đệ quy
B.Đếm số đường đi từ góc trên trái xuống góc dưới phải của một lưới ô vuông
C.Merge sort, vì hai nửa mảng của nó không bao giờ trùng nhau
D.Fibonacci đệ quy thuần
Đáp án: C
Merge sort. Nó chia mảng thành hai nửa rời nhau, nên không có bài toán con nào bị hỏi lại lần thứ hai. Bảng nhớ sẽ chỉ tốn bộ nhớ mà không bao giờ trúng. Ghi nhớ chỉ có ích khi các bài toán con gối lên nhau.
Câu 127·Heap & hàng đợi ưu tiên
Chèn một phần tử vào min-heap được thực hiện như thế nào?
A.Thêm vào cuối rồi chạy lại thủ tục dựng heap trên toàn bộ mảng một lần nữa
B.Đặt vào gốc rồi đẩy nút gốc cũ xuống nhánh phù hợp bên dưới
C.Đặt vào vị trí trống cuối cùng rồi đổi dần lên trên khi còn nhỏ hơn cha
D.Tìm vị trí đúng theo giá trị bằng cách đi từ gốc xuống rồi chèn vào đó
Đáp án: C
Đặt phần tử mới vào vị trí trống cuối cùng để giữ cây hoàn chỉnh, rồi vun lên: so với nút cha, nếu nhỏ hơn thì đổi chỗ, lặp lại cho tới khi lớn hơn cha hoặc chạm gốc. Chi phí O(log n) vì đường đi từ lá lên gốc dài bằng chiều cao cây.
Câu 128·Heap & hàng đợi ưu tiên
Vì sao thủ tục dựng heap từ mảng chỉ cần bắt đầu vun từ chỉ số n/2 trở về đầu?
A.Các chỉ số từ n/2 trở đi đều là nút lá nên đã thoả bất biến sẵn
B.Vì vun nửa sau tốn quá nhiều thời gian nên người ta chấp nhận bỏ qua
C.Vì thuật toán chỉ đảm bảo bất biến cho nửa đầu của mảng mà thôi
D.Vì nửa sau của mảng luôn chứa các giá trị lớn hơn nửa đầu
Đáp án: A
Vì mọi chỉ số từ ⌊n/2⌋ trở đi đều là nút lá. Trong cách lưu heap bằng mảng, nút i có con ở 2i+1 và 2i+2; với i ≥ n/2 thì cả hai chỉ số đó đều vượt quá mảng. Nút lá không có con nên tự nó đã thoả bất biến, không cần vun.
Câu 129·Heap & hàng đợi ưu tiên
Dijkstra dùng hàng đợi ưu tiên để làm gì?
A.Sắp xếp các cạnh của đồ thị theo trọng số tăng dần trước khi bắt đầu duyệt
B.Phát hiện chu trình có tổng trọng số âm trong quá trình duyệt đồ thị
C.Luôn lấy ra đỉnh chưa chốt có khoảng cách tạm tính nhỏ nhất
D.Lưu lại toàn bộ các đường đi đã tìm được để so sánh về sau
Đáp án: C
Để luôn lấy ra đỉnh chưa chốt có khoảng cách tạm tính nhỏ nhất. Đây là bước tham lam cốt lõi: đỉnh gần nguồn nhất trong số chưa chốt thì khoảng cách của nó chắc chắn đã tối ưu, vì mọi đường khác tới nó đều phải đi qua một đỉnh xa hơn.
Câu 130·Heap & hàng đợi ưu tiên
Tìm xem một giá trị cụ thể có nằm trong heap hay không tốn bao nhiêu?
A.O(log n) trung bình nhưng có thể lên tới O(n) ở trường hợp xấu nhất
B.O(n), vì phải quét toàn bộ do không có hướng nào để rẽ
C.O(1), vì heap lưu trong mảng nên truy cập trực tiếp được
D.O(log n), đi từ gốc xuống theo so sánh giá trị như cây tìm kiếm
Đáp án: B
O(n) — phải quét toàn bộ. Bất biến heap chỉ nói cha nhỏ hơn con, hoàn toàn không nói giá trị cần tìm nằm ở nhánh trái hay phải. Không có hướng để rẽ nên không tận dụng được cấu trúc cây, khác hẳn cây tìm kiếm nhị phân với O(log n).
Còn 31 câu Thuật toán & CTDL mức Nâng cao
Phần Nâng cao đi vào tình huống chuyên sâu và các bẫy kỹ thuật hay gặp, dành cho thành viên Pro.
