while(there are more characters in the word to read)
{read a character
if a character is '*' then
pop the stack
Đề bài
else
push the character into the stack
}while(the stack is not empty)
pop and write the poped character to the screen
What is written to the screen for the input "Good**Morn**in***gSir" ?
AriSgMoG
BriSgMoo
CGoMg
DriSgMor
Lời giải
Đáp án đúng: "riSgMoG". Ngăn xếp lấy ra phần tử mới nhất. Nạp G, o, o, d rồi hai dấu sao lấy ra d và o, còn G, o; nạp M, o, r, n rồi hai dấu sao lấy ra n và r, còn G, o, M, o; nạp i, n rồi ba dấu sao lấy ra n, i, o, còn G, o, M; nạp g, S, i, r nên ngăn xếp từ đáy lên là G, o, M, g, S, i, r. Vòng cuối lấy ra và in từ đỉnh xuống đáy, cho r, i, S, g, M, o, G, tức riSgMoG. Dãy "riSgMoo" cần đáy là hai chữ o, nhưng chữ o thứ hai đã bị dấu sao thứ hai trong Good lấy ra. Dãy "riSgMor" kết thúc bằng r, trong khi r vừa được in đầu tiên vì nó ở đỉnh, không thể đồng thời nằm ở đáy. Dãy "GoMg" đọc từ đáy lên và rụng mất bốn ký tự, đó là trật tự của hàng đợi chứ không phải ngăn xếp.
Đáp án đúng: "C, B, D, A, E, F, G, H". Các cạnh là C–B, C–D, B–A, B–E, A–E, A–G, E–G, G–F, D–F, còn H không nối với đỉnh nào. Duyệt theo chiều rộng từ C, ưu tiên thứ tự chữ cái khi ngang nhau: thăm C rồi nạp B và D; mở B được A và E; mở D được F; mở A được G; mở E thì B, A, G đã có cả; mở F và G không thêm gì mới. Dãy thu được là C, B, D, A, E, F, G, rồi H được thăm sau cùng vì nó nằm ở thành phần liên thông riêng và phép duyệt phải quét hết các đỉnh còn lại. Phương án "C, B, D, A, E, F, G" đúng phần chứa C nhưng bỏ hẳn H. Phương án "C, B, D, A, G, E, F, H" đưa G lên trước E, nhưng E được phát hiện khi mở B còn G chỉ xuất hiện khi mở A. Phương án "C, B, D, A, E, G, F, H" xếp G trước F, trong khi F được nạp lúc mở D mà D được mở trước A.
Đáp án đúng: "6, 2, 7, 1, 4, 8, 3, 5". Chèn 3 theo đường tìm kiếm: 3 nhỏ hơn 6 nên sang trái tới 2, lớn hơn 2 nên sang phải tới 5, nhỏ hơn 5 nên sang trái tới 4, nhỏ hơn 4 nên thành con trái của 4. Lúc này nút 5 có cây con trái cao hai mức gồm 4 và 3 mà không có con phải, hệ số cân bằng bằng 2 nên mất cân bằng; vì điểm chèn nằm ở nhánh trái của con trái nên chỉ cần một phép quay phải tại 5: nút 4 lên thay chỗ, giữ 3 làm con trái và nhận 5 làm con phải, rồi 4 trở thành con phải của 2. Cây sau quay có gốc 6 với hai con 2 và 7; 2 có con 1 và 4; 7 có con phải 8; 4 có con 3 và 5. Duyệt theo bề rộng cho 6, rồi 2 và 7, rồi 1, 4, 8, cuối cùng 3 và 5. "6, 2, 7, 1, 3, 4, 8, 5" sai vì nó đưa 3 lên cùng mức với 4 và 8, trong khi 3 là con của 4. "6, 2, 7, 1, 3, 5, 8, 4" sai vì nó cho 3 lên làm gốc cây con sau phép quay, tức quay quanh nút 4 thay vì quanh nút 5. "6, 2, 7, 1, 5, 8, 3, 4" sai vì đó là cây chưa quay, vẫn để 5 ở mức ba với hệ số cân bằng 2, vi phạm điều kiện AVL.
{ Node p = root;while(p!=null && p.info != x){if(x<p.info) p = p.left;
else p=p.right;}return(p);}". Phép và trong Java chỉ xét vế phải khi vế trái còn đúng, nên viết p khác null trước rồi mới đọc p.info bảo đảm không bao giờ truy cập trường của một tham chiếu rỗng; nhờ vậy khi x không có trong cây thì vòng lặp thoát với p bằng null và hàm trả về null một cách hợp lệ. Cách viết "Node search(int x){ Node p = root;while(p.info != x && p!=null){if(x<p.info) p = p.left;
else p=p.right;}return(p);}" đảo thứ tự hai điều kiện, lần so sánh đầu đã đọc p.info nên ngay khi đi xuống hết nhánh và p thành null thì chương trình đổ vì truy cập trên tham chiếu rỗng. Cách viết "Node search(int x){ Node p = root;while(p.info != x){if(x<p.info) p = p.left;
else p=p.right;}return(p);
}" bỏ hẳn việc kiểm tra null, nó chỉ chạy đúng với những khoá chắc chắn có trong cây, còn khoá không tồn tại thì vòng lặp đi quá lá rồi đọc trường của null.
Đáp án đúng: "True". Mã hoá theo độ dài loạt đúng là phép nén không mất dữ liệu: nó thay một loạt ký tự giống nhau liền nhau bằng chính ký tự đó kèm số lần lặp, và từ cặp ký tự với số đếm ta dựng lại được loạt gốc nguyên vẹn, chẳng hạn AAAA thành A4 rồi giải nén trở lại đúng AAAA, không ký tự nào bị làm tròn hay bỏ bớt như trong các phép nén ảnh và âm thanh có mất dữ liệu. "False" chỉ đúng nếu phép nén làm mất thông tin, hoặc nếu mô tả trong câu không phải mô tả của mã hoá theo độ dài loạt; cả hai điều đều không xảy ra, vì mô tả khớp đúng định nghĩa và phép giải nén là ánh xạ ngược chính xác của phép nén. Lưu ý thực tế duy nhất là với dữ liệu ít lặp, kết quả có thể dài hơn bản gốc, nhưng dài hơn vẫn là không mất dữ liệu.
int x =15;
Node f = p.prev;//prev is a link to predecessor node
Node q = new Node(x);
q.prev = f; q.next = p;
f.next = q; p.prev = q;
A7 11 6 4 13 12 8 2 15
B7 11 6 4 13 15 12 8 2
C7 11 6 4 13 12 15 8 2
D7 5 11 6 4 13 12 8 2
E15 7 11 6 4 13 12 8 2
Lời giải
Đáp án đúng: "7 11 6 4 13 15 12 8 2". Nhờ danh sách liên kết đôi, p.prev cho ngay nút đứng trước p, tức f là nút 13. Nút mới q mang 15 được khâu vào giữa f và p bằng bốn lệnh gán: q.prev = f cùng q.next = p nối q sang hai bên, f.next = q cùng p.prev = q để hai bên nhận lại q. Kết quả 15 nằm giữa 13 và 12, cho 7 11 6 4 13 15 12 8 2. "7 11 6 4 13 12 15 8 2" đặt 15 sau 12, tức khâu vào phía p.next thay vì p.prev. "7 11 6 4 13 12 8 2 15" là thêm vào cuối danh sách, không dùng tới p. "15 7 11 6 4 13 12 8 2" thêm vào đầu danh sách, cũng không liên quan tới vị trí của p. "7 5 11 6 4 13 12 8 2" chèn số 5 ở chỗ thứ hai, trong khi giá trị được chèn là x = 15 và chỗ chèn hoàn toàn do p quyết định.
AEvery recursive function must have exactly one base case.
BEvery recursive function must have at least one base case.
CIn recursive function the base cases may be absent.
DIn recursive function only the general (recursive) case must be appeared.
Lời giải
Đáp án đúng: "Every recursive function must have at least one base case.". Trường hợp cơ sở là chỗ chuỗi lời gọi chạm đáy và trả về mà không gọi tiếp; thiếu nó thì mỗi lần gọi lại sinh một lần gọi nữa và ngăn xếp lời gọi tràn. Cụm at least one đặt đúng chỗ vì có hàm cần nhiều điểm dừng, ví dụ hàm kiểu Fibonacci phải chặn cả n bằng 0 và n bằng 1 mới đủ để hai nhánh đệ quy n-1 và n-2 cùng dừng được. Vì vậy "Every recursive function must have exactly one base case." sai vì nó buộc đúng một điểm dừng, loại bỏ chính những hàm hai điểm dừng vừa nói; "In recursive function the base cases may be absent." sai vì không có điểm dừng là đệ quy vô hạn, chương trình chết vì tràn ngăn xếp chứ không trả kết quả; "In recursive function only the general (recursive) case must be appeared." sai vì chỉ có nhánh tổng quát cũng chính là không có điểm dừng nào.
Đáp án đúng: "6, 1, 7, 2, 8, 4, 5". Cây có gốc 6, nhánh trái 3 với hai con 1 và 4, dưới 1 là con phải 2, dưới 4 là con phải 5, nhánh phải 7 với con phải 8. Xoá 3 bằng cách nối: nhánh trái của 3 lên thế chỗ nên 1 thành con trái của 6, còn nhánh phải của 3 treo vào nút cực phải của nhánh trái, đi từ 1 sang 2 mà 2 không có con phải nên 2 nhận 4 làm con phải. Cây mới có 6 ở mức một; 1 và 7 ở mức hai; 2 là con phải của 1 và 8 là con phải của 7 ở mức ba; 4 ở mức bốn; 5 ở mức năm. Duyệt theo chiều rộng cho 6, 1, 7, 2, 8, 4, 5. Dãy "6, 1, 7, 2, 8, 5, 4" đổi chỗ 4 với 5, nhưng 4 là con của 2 còn 5 là con của 4 nên 4 nằm cạn hơn một mức. Dãy "6, 2, 7, 1, 4, 8, 5" là kết quả xoá bằng cách sao chép, tức thay giá trị 3 bằng tiền nhiệm 2 rồi bỏ nút 2. Dãy "6, 2, 7, 1, 4, 5, 8" cũng theo lối sao chép và còn xếp 5 trước 8, dù 8 là con của 7 ở mức ba còn 5 nằm ở mức bốn.
Đáp án đúng: "2, 1, 4, 3, 8, 7, 9". Cây có gốc 5, con trái 2 với hai con 1 và 4, con trái của 4 là 3; con phải của 5 là 8 với hai con 7 và 9. Xoá 5 theo kiểu hợp nhất: nhánh trái leo lên làm gốc mới, rồi nhánh phải được treo vào nút phải nhất của nhánh trái. Nút phải nhất của nhánh trái là 4, vì từ 2 sang con phải 4 rồi 4 không có con phải; nên cây gốc 8 thành con phải của 4. Cây mới: gốc 2 với hai con 1 và 4; 4 có con trái 3 và con phải 8; 8 có hai con 7 và 9. Các lớp là 2; rồi 1, 4; rồi 3, 8; rồi 7, 9. Phương án "2, 1, 4, 3, 7, 8, 9" xếp 7 cùng lớp với 3, nhưng sau hợp nhất 7 là con của 8 nên tụt xuống lớp thứ tư. Phương án "2, 1, 4, 3, 8, 9, 7" đảo hai con của 8, trong khi duyệt theo lớp đọc con trái 7 trước con phải 9. Phương án "4, 2, 8, 1, 3, 7, 9" lấy nút phải nhất 4 lên làm gốc, đó là kiểu xoá sao chép.
Đáp án đúng: "(4)", tức bảng có 65 ở ô 5, 76 ở ô 6, 96 ở ô 7 và 205 ở ô 9, các ô khác rỗng. Dò bậc hai thử lần lượt các vị trí (h(x) + i^2)%10 với i = 1, 2, 3: 65 vào ô 5, 76 vào ô 6; 96 băm về ô 6 đã kín nên i = 1 cho (6+1)%10 = 7 và nằm ở ô 7; 205 băm về ô 5 kín, i = 1 cho ô 6 cũng kín, i = 2 cho (5+4)%10 = 9 còn rỗng. "(1)" sai vì nó đặt 96 ở ô 8, tức cộng thêm 2 vốn không phải số chính phương, và đưa 205 về ô 1 ứng với i = 4 dù ô 9 ở bước i = 2 đã rỗng. "(2)" sai vì cho 205 xuống ô 0, ứng với i = 5, cũng bỏ qua ô rỗng tìm được sớm hơn. "(3)" sai vì xếp 205 vào ô 8: đó là kết quả của dò tuyến tính, khi các ô 5, 6, 7 kín thì lấy ngay ô 8, chứ bước nhảy bậc hai không bao giờ cho khoảng cách 3.
Đáp án đúng: "False". Trong danh sách liên kết vòng, nút cuối trỏ về nút đầu nên từ một tham chiếu duy nhất ta đi được tới mọi nút. Cách cài phổ biến là chỉ giữ một tham chiếu tới nút cuối: nút đầu lấy ngay bằng liên kết next của nó, nhờ đó cả việc thêm vào đầu lẫn thêm vào cuối đều tốn thời gian hằng số mà không cần biến thứ hai. Vì vậy mệnh đề đòi luôn phải khai cả hai đầu là không đúng. Trả lời "True" chỉ hợp khi người ta tự chọn lưu cả hai tham chiếu cho tiện, chẳng hạn để đọc thẳng phần tử đầu mà không qua một bước liên kết; đó là tuỳ chọn cài đặt chứ không phải điều kiện bắt buộc của cấu trúc vòng.
int x =9;
Node p1, p2;
p1 = new Node(x);
p2 = p.next;
p.next = p1; p1.prev = p;
p1.next = p2; p2.prev = p1;
A7 11 6 4 3 10 8 2 9
B7 11 6 4 3 9 10 8 2
C7 11 6 4 3 10 9 8 2
D7 9 11 6 4 3 10 8 2
E9 7 11 6 4 3 10 8 2
Lời giải
Đáp án đúng: "7 11 6 4 3 10 9 8 2". Đoạn mã tạo nút p1 chứa 9 rồi lấy p2 là nút đứng sau p, tức nút 8. Bốn phép gán p.next=p1, p1.prev=p, p1.next=p2 và p2.prev=p1 khâu đủ hai chiều, đặt nút 9 vào ngay sau nút 10 và trước nút 8. "7 11 6 4 3 10 8 2 9" là thêm vào cuối danh sách, phải đi qua tail chứ không phải qua p. "7 11 6 4 3 9 10 8 2" là chèn trước p, muốn vậy phải dùng p.prev để nối với nút 3 chứ không phải p.next. "7 9 11 6 4 3 10 8 2" là chèn sau nút đầu, cần một tham chiếu tới head. "9 7 11 6 4 3 10 8 2" là chèn vào đầu danh sách và bắt buộc phải gán lại head, mà đoạn mã không chạm tới head.
Node f = p.prev;// prev is a link to predecessor node
Node q = new Node(x);
q.prev = f; q.next = p;
f.next = q; p.prev = q;
AIt inserts new node with value x before the node p.
BIt inserts new node with value x after the node p.
CIt replaces the node p with new node with value x.
DIt creates new node with value x at the end of the list.
Lời giải
Đáp án đúng: "It inserts new node with value x before the node p.". Đoạn mã lấy f = p.prev, nghĩa là nút đứng ngay trước p, việc chỉ danh sách liên kết đôi làm được trong một bước. Sau đó nút mới q mang giá trị x được nối hai chiều vào khoảng giữa f và p: q.prev = f cùng q.next = p cho q biết hai láng giềng, f.next = q cùng p.prev = q cho f và p biết q. Không liên kết nào của p.next bị đổi và không nút nào bị tách ra, nên hiệu quả đúng là chèn x vào trước p với chi phí O(1). "It inserts new node with value x after the node p." phải lấy mốc là p.next chứ không phải p.prev. "It replaces the node p with new node with value x." sai vì p vẫn nằm trong chuỗi, chỉ có liên kết lùi của nó chuyển sang q. "It creates new node with value x at the end of the list." sai vì vị trí chèn do p quyết định; nó chỉ trùng cuối danh sách trong trường hợp riêng p là nút cuối, mà ngay cả khi ấy x vẫn đứng trước p.
AIn chaining, some positions of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys
BIn this method, the table can never overflow if free memory is available, because the linked list is extendible.
CIn chaining, the linked-list is used instead of array for a hash table
DNone of others
Lời giải
Đáp án đúng: "In this method, the table can never overflow if free memory is available, because the linked list is extendible.". Trong phương pháp nối kết, mỗi ô của bảng giữ đầu một danh sách liên kết, nên số khoá dồn vào một ô không bị chặn bởi kích thước bảng: chèn thêm chỉ là cấp một nút mới và móc vào dây, vì vậy bảng không bao giờ tràn khi còn bộ nhớ trống, khác hẳn địa chỉ mở nơi bảng đầy là hết chỗ chèn. Vì vậy "In chaining, some positions of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys" sai ở chữ some: mọi ô của bảng đều là đầu một dây, dây có thể rỗng chứ không phải chỉ một số ô mới có dây. "In chaining, the linked-list is used instead of array for a hash table" sai vì bảng vẫn phải là mảng để nhảy trực tiếp tới ô h(x) trong thời gian hằng, danh sách liên kết chỉ nối thêm vào từng ô; thay mảng bằng danh sách là mất luôn khả năng truy cập theo chỉ số. "None of others" sai vì đã có một phát biểu đúng nằm trong các lựa chọn.
Đáp án đúng: "(1)", tức bảng có 21 ở ô 1, 203 ở ô 3, 64 ở ô 4, 95 ở ô 5, 44 ở ô 6 và 144 ở ô 7. Hàm băm lấy số dư cho 10 nên 95 vào ô 5, 64 vào ô 4, 21 vào ô 1, 203 vào ô 3, các ô này đều trống nên nhận ngay. Khoá 44 băm về ô 4 đã có 64, dò tuyến tính sang ô 5 cũng đầy vì có 95, sang ô 6 trống nên dừng ở đó. Khoá 144 cũng băm về ô 4, dò qua ô 5, ô 6 rồi đậu ở ô 7. Bảng "(2)" đổi chỗ 44 với 144, nhưng 44 được chèn trước nên chính nó mới chiếm ô trống gần nhất là ô 6. Bảng "(3)" để trống ô 6 và ô 7 rồi đặt 44 ở ô 8, trái với dò tuyến tính vì phép dò này luôn nhận ô trống đầu tiên về phía sau. Bảng "(4)" vừa bỏ qua hai ô trống đó vừa đảo thứ tự hai khoá, sai cả bước dò lẫn trình tự chèn.
BIn the worst case the selection sort is O(n^2), in the best case it is O(n).
CIn the worst case the selection sort is O(n^2), in the best case it is O(nlog n).
DIn the average case the selection sort is O(n^2), in the best case it is O(nlog n).
Lời giải
Đáp án đúng: "In all cases the selection sort is O(n^2).". Sắp xếp chọn luôn chạy hai vòng lặp lồng cố định: lượt thứ i quét toàn bộ phần chưa sắp để tìm phần tử nhỏ nhất, nên số phép so sánh là n−1 cộng n−2 cộng tiếp tới 1, bằng n(n−1)/2 bất kể dữ liệu ra sao. Nó không có cơ chế nào phát hiện mảng đã sắp để dừng sớm, vì phải quét hết mới biết đâu là nhỏ nhất; số phép đổi chỗ thì ít, chỉ cỡ n, nhưng phép so sánh mới chi phối chi phí. Phương án "In the worst case the selection sort is O(n^2), in the best case it is O(n)." mô tả sắp xếp nổi bọt có cờ kiểm tra hoán vị, loại dừng ngay khi một lượt không đổi gì, hoặc sắp xếp chèn trên mảng đã sắp. Phương án "In the worst case the selection sort is O(n^2), in the best case it is O(nlog n)." gán cho trường hợp tốt mức chi phí của sắp xếp trộn hay sắp xếp nhanh, hai thuật toán chia để trị. Phương án "In the average case the selection sort is O(n^2), in the best case it is O(nlog n)." đúng ở phần trung bình nhưng vẫn gán sai cho trường hợp tốt, vốn cũng là n(n−1)/2 phép so sánh.
Đáp án đúng: "AABBBCAB". Đọc cây mã trước: nhánh 1 từ gốc tới ngay lá A nên A = 1; nhánh 0 dẫn vào một nút trong, từ đó 0 tới B và 1 tới C, nên B = 00 và C = 01. Vì đây là mã tiền tố, cứ đọc bit từ trái và dừng ngay khi tới lá: 1 cho A, 1 cho A, 00 cho B, 00 cho B, 00 cho B, 01 cho C, 1 cho A, 00 cho B, vừa hết 13 bit của 1100000001100 và cho AABBBCAB. "CAABBBBA" sai vì nó mở đầu bằng C = 01 trong khi bit đầu của chuỗi là 1, mã tiền tố không cho phép đọc lệch như vậy. "AABBBBBA" sai vì nó đọc cặp bit thứ chín và mười, vốn là 01, thành thêm một B, tức bỏ qua nhánh 1 dẫn tới lá C. "AABBABAB" sai vì chuỗi bit của nó chỉ dài 12 bit và chèn một A vào giữa dải bit 0 liền nhau, không khớp với dữ liệu cần giải mã.
AThe best case is O(n), and the worst case is O(n^2)
BThe best case is O(n), and the worst case is O(nlogn)
CBest case is O(nlogn) , the worst case is O(n^2)
DBoth best and worst cases are O(nlogn)
Lời giải
Đáp án đúng: "Both best and worst cases are O(nlogn)". Sắp xếp vun đống luôn gồm hai phần cố định: dựng đống từ n phần tử rồi lặp n lần việc lấy phần tử lớn nhất ở gốc, đưa về cuối và vun lại. Mỗi lần vun lại đi dọc một đường từ gốc xuống lá nên tốn cỡ log n, lặp n lần cho n log n, và không có dạng dữ liệu nào cắt bớt được các lần vun ấy, kể cả mảng đã sắp xếp sẵn. Mức "The best case is O(n), and the worst case is O(nlogn)" cho trường hợp tốt nhất là tuyến tính, nhưng dù mảng đã có thứ tự thì thuật toán vẫn phải vun lại sau từng lần lấy gốc nên không xuống được mức n. Mức "The best case is O(n), and the worst case is O(n^2)" vừa nêu trường hợp tốt nhất tuyến tính vừa cho trường hợp xấu nhất bình phương, đó là dáng của sắp xếp chèn có kiểm tra mảng đã xong. Mức "Best case is O(nlogn) , the worst case is O(n^2)" cho trường hợp xấu nhất bình phương, đó là dáng của sắp xếp nhanh khi chốt chọn lệch, còn vun đống không phụ thuộc việc chọn chốt.
void fun(int n){if(n ==0)
System.out.println("That's all!");
else
{for(int i =1; i <= n; i++)
System.out.print("*");
System.out.println();fun(n -1);}}
What is the output when the statement fun(3) is run?
AThat's all!
***
**
*
BThat's all!
*
**
***
C***
**
*
That's all!
D*
**
***
That's all!
Lời giải
Đáp án đúng: "*** ** * That's all!", tức ba dấu sao ở dòng đầu, rồi hai, rồi một, cuối cùng mới tới dòng chữ. Hàm in trước rồi mới gọi đệ quy: với n bằng 3, vòng for in ba dấu sao rồi xuống dòng, sau đó gọi fun(2) in hai dấu sao, rồi fun(1) in một dấu sao, rồi fun(0) rơi vào nhánh đầu và in dòng chữ rồi dừng. Vì vậy số dấu sao giảm dần và dòng chữ luôn nằm cuối. Dãy "That's all! *** ** *" đặt dòng chữ lên đầu, điều đó chỉ xảy ra nếu lệnh in dòng chữ đứng trước phần đệ quy, trong khi nó nằm ở nhánh n bằng 0 và chỉ chạy sau ba lần gọi. Dãy "That's all! * ** ***" vừa đưa dòng chữ lên đầu vừa cho số dấu sao tăng dần, sai cả hai chỗ. Dãy "* ** *** That's all!" đúng chỗ dòng chữ nhưng số dấu sao tăng dần, chiều này chỉ xảy ra nếu hàm gọi đệ quy trước rồi mới chạy vòng for.
Đáp án đúng: "1, 2, 4, 5, 7, 3, 6, 8". Duyệt trước thăm gốc rồi đi hết nhánh trái mới sang nhánh phải. Cây gốc 1 có con trái 2 (con trái 4, con phải 5, mà 5 chỉ có con trái 7) và con phải 3 (chỉ có con phải 6, mà 6 chỉ có con trái 8). Chạy dãy: thăm 1; sang nhánh trái thăm 2, rồi 4 là lá, rồi 5 và con trái của 5 là 7, được 2, 4, 5, 7; sang nhánh phải thăm 3, 3 không có con trái nên xuống 6, rồi con trái của 6 là 8, được 3, 6, 8. "1, 2, 4, 7, 5, 3, 6, 8" đặt 7 trước 5 dù 7 là con của 5, mà duyệt trước luôn thăm cha trước con. "1, 2, 4, 5, 7, 3, 8, 6" mắc đúng lỗi đó ở nhánh phải, đưa 8 lên trước cha của nó là 6. "4, 2, 7, 5, 1, 8, 6, 3" mở đầu bằng lá 4, điều không thể có ở duyệt trước vì phần tử đầu tiên bắt buộc là gốc; dãy đó đi theo lối thăm con trái trước gốc.
