Đáp án đúng: "13, 15, 18, 11, 17, 10, 12, 16, 14, 19". Một lượt của vòng for so sánh từng cặp kề nhau từ đầu tới cuối và đổi chỗ khi phần tử trước lớn hơn, nên phần tử lớn nhất bị đẩy dần về cuối. Chạy trên 15, 13, 18, 19, 11, 17, 10, 12, 16, 14: cặp 15 và 13 đổi chỗ thành 13, 15; cặp 15 với 18 rồi 18 với 19 đều đã đúng thứ tự nên giữ nguyên; từ đó 19 trở thành phần tử đang được mang theo và lần lượt đổi chỗ với 11, 17, 10, 12, 16, 14 để rơi xuống ô cuối. Sau lượt đầu chỉ có 13 lên đầu và 19 về cuối, còn các số bị 19 vượt qua đều dịch lên một chỗ mà giữ nguyên thứ tự tương đối, cho 13, 15, 18, 11, 17, 10, 12, 16, 14, 19. "13, 15, 18, 17, 11, 10, 12, 16, 14, 19" đổi chỗ 11 với 17, nhưng 11 nhỏ hơn 17 nên cặp đó không bị đổi. "13, 15, 18, 11, 17, 10, 12, 14, 16, 19" đã sắp lại 14 với 16, việc chỉ xảy ra ở lượt sau. "13, 15, 18, 10, 11, 17, 12, 16, 14, 19" kéo 10 nhảy ngược qua 11 và 17, trong khi mỗi lượt chỉ dồn một phần tử lớn về cuối.
Đáp án đúng: "dequeue". Hàng đợi là kiểu vào trước ra trước và cũng có cặp tên truyền thống: enqueue đưa phần tử vào cuối hàng, dequeue lấy phần tử ở đầu hàng ra và trả nó về cho người gọi. Vì vậy "peek" sai vì nó chỉ đọc giá trị ở đầu hàng mà không tháo phần tử nào, số phần tử không giảm đi; "delete" sai vì đó là tên chung của phép xoá, không nói gì tới việc trả giá trị về và cũng không ràng buộc phải xoá ở đầu hàng; "remove" sai vì nó là tên quen thuộc trong các lớp danh sách và tập hợp, nơi ta xoá theo chỉ số hoặc theo giá trị bất kỳ, chứ không phải tên truyền thống của phép lấy khỏi đầu hàng đợi.
Đáp án đúng: "7, 6, 2, 5, 1, 3, 8, 4". Duyệt trung tố đi nhánh trái, rồi gốc, rồi nhánh phải. Cây có gốc 1, nhánh trái 2 với hai con 6 và 5, dưới 6 là con trái 7, nhánh phải 3 chỉ có con phải 4, dưới 4 là con trái 8. Trong nhánh trái, nút 6 phải nhường chỗ cho con trái 7 nên ra 7 rồi 6, tiếp đến gốc nhánh là 2, rồi 5, được 7, 6, 2, 5. Gốc 1 ra giữa dãy. Nhánh phải: 3 không có con trái nên ra ngay 3, rồi vào 4 và trong đó 8 ra trước 4, được 3, 8, 4. Dãy "1, 2, 6, 7, 5, 3, 4, 8" là kết quả duyệt tiền tố, nhận ra vì gốc 1 đứng đầu. Dãy "7, 6, 5, 2, 8, 4, 3, 1" là kết quả duyệt hậu tố, nhận ra vì gốc 1 đứng cuối. Dãy "1, 2, 6, 7, 5, 3, 8, 4" cũng bắt đầu bằng gốc như tiền tố, mà trung tố thì gốc chỉ được thăm sau khi in xong toàn bộ nhánh trái.
Đáp án đúng: "1". Đồ thị có các cạnh A–B, A–C, A–D, A–G, B–C, B–E, C–E, D–F, E–F, E–G. Tô màu tuần tự theo thứ tự chữ cái, mỗi đỉnh nhận màu nhỏ nhất chưa bị láng giềng ĐÃ tô dùng: A nhận màu 1; B kề A nên nhận màu 2; C kề A màu 1 và B màu 2 nên nhận màu 3; D kề A màu 1 và kề F chưa tô nên nhận màu 2; tới E, các láng giềng là B, C, F, G, trong đó chỉ B và C đã tô với màu 2 và 3, còn F và G chưa tô nên không chặn gì, mà E không kề A nên màu 1 vẫn trống và E nhận màu 1. Phương án "2" là màu của B và D, nhưng E kề B nên không được lấy 2, và dù sao màu 1 vẫn còn. Phương án "3" là màu của C, mà E kề C nên không được lấy 3. Phương án "4" và phương án "5" đòi E bị chặn ở ba hoặc bốn màu đầu, nhưng lúc tô E chỉ có hai láng giềng đã tô nên nhiều nhất hai màu bị chặn.
(head) 7 21 6 4 23 19 8 12 (tail)
What does the list look like after the following java code snippet is run?
Đề bài
int x =5;
Node f = p.prev;// prev is a link to predecessor node
Node q = new Node(x);// Create new node with value x
q.prev = f; q.next = p;
f.next = q; p.prev = q;
A7 21 6 4 23 5 19 8 12
B5 7 21 6 4 23 19 8 12
C7 21 6 4 23 19 8 12 5
D7 21 6 4 23 19 8 5 12
E7 21 6 4 23 19 5 8 12
Lời giải
Đáp án đúng: "7 21 6 4 23 5 19 8 12". Vì là danh sách liên kết đôi nên lấy được nút trước p chỉ bằng một bước: p trỏ nút 19 nên f = p.prev là nút 23. Nút mới q mang 5 được gắn q.prev = f và q.next = p, rồi f.next = q cùng p.prev = q vá cả hai chiều, đặt q đúng vào khe giữa 23 và 19, tức chèn ngay trước p. "5 7 21 6 4 23 19 8 12" sai vì đoạn mã không chạm head; muốn 5 lên đầu thì p phải là nút đầu tiên. "7 21 6 4 23 19 8 12 5" sai vì chèn vào cuối cần f là nút cuối và q.next phải là null. "7 21 6 4 23 19 8 5 12" sai vì vị trí đó ứng với p trỏ nút 12 chứ không phải nút 19. "7 21 6 4 23 19 5 8 12" sai vì đó là chèn sau p, phải viết q.prev = p và q.next = p.next.
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 "FileComp**ress*ion***" ?
AseroCeli
BseroCeliF
CseroCelFi
DseroCeliFn
EFilreion
Lời giải
Đáp án đúng: "seroCeliF". Dấu sao ở đây chỉ lấy bỏ phần tử trên đỉnh mà không in; chỉ khi đọc hết chuỗi mới lấy ra lần lượt và in, nên kết quả là phần còn lại đọc ngược. Nạp F, i, l, e, C, o, m, p; hai dấu sao bỏ p rồi m. Nạp r, e, s, s; một dấu sao bỏ một chữ s. Nạp i, o, n; ba dấu sao bỏ n, o, i. Ngăn xếp còn F, i, l, e, C, o, r, e, s nên in ngược cho đủ chín ký tự. Chuỗi "seroCeli" rơi mất F ở cuối, nhưng F là ký tự nạp đầu tiên nên nó nằm dưới cùng và được in sau chót. Chuỗi "seroCelFi" đổi chỗ hai ký tự cuối, trong khi i nạp ngay sau F nên i phải ra trước F. Chuỗi "seroCeliFn" chen thêm n vào cuối, mà n đã bị một trong ba dấu sao cuối lấy bỏ. Chuỗi "Filreion" liệt kê theo chiều nạp vào chứ không theo chiều lấy ra, lại còn chứa i, o, n là ba ký tự đã bị loại bỏ.
int x =13;
Node f = head;while(f.next != p) f = f.next;
Node q = new Node(x);
q.next = p;
f.next = q;
A7 11 6 4 3 9 8 21 13
B7 11 6 4 3 13 9 8 21
C7 11 6 4 3 9 13 8 21
D7 13 11 6 4 3 9 8 21
E13 7 11 6 4 3 9 8 21
Lời giải
Đáp án đúng: "7 11 6 4 3 13 9 8 21". Danh sách liên kết đơn chỉ đi được một chiều, nên muốn chèn trước nút p chứa 9 phải dò từ head bằng vòng while cho tới khi f.next bằng p; khi vòng dừng, f đang ở nút 3. Hai phép gán q.next=p rồi f.next=q đặt nút 13 vào đúng giữa 3 và 9, các liên kết khác không đổi. "7 11 6 4 3 9 8 21 13" là thêm vào cuối, phải đi tới nút 21 và gán next của nó. "7 11 6 4 3 9 13 8 21" là chèn ngay sau p, cần q.next=p.next rồi p.next=q. "7 13 11 6 4 3 9 8 21" là chèn sau nút đầu, chỉ xảy ra nếu vòng while dừng ngay tại head, tức p là nút thứ hai. "13 7 11 6 4 3 9 8 21" là chèn vào đầu danh sách, việc đó buộc phải gán lại head mà đoạn mã không chạm tới head.
". Duyệt giữa cần đúng hai điều: trình tự con trái, thăm gốc, con phải; và điều kiện dừng khi gặp cây rỗng, vì mỗi lá vẫn gọi tiếp vào hai liên kết null. Bản này kiểm p khác null trước rồi mới đi xuống nên đệ quy chắc chắn kết thúc. Phương án "
Đáp án đúng: "1, 2, 6, 5, 7, 3, 4, 8". Cây có gốc 1 với con trái 2 và con phải 3; 2 có hai con 6 và 5; 5 có con trái 7; 3 có con phải 4; 4 có con trái 8. Duyệt pre-order in gốc trước, rồi vét trọn nhánh trái, rồi nhánh phải. In 1; vào nhánh trái gặp 2 thì in 2, con trái của 2 là lá 6 nên in 6, sang con phải 5 in 5 rồi con trái của nó là 7; quay sang nhánh phải in 3, mà 3 không có con trái nên xuống 4 in 4, rồi con trái của 4 là 8. Vì vậy "6, 2, 7, 5, 1, 8, 4, 3" sai vì pre-order buộc mở đầu bằng gốc 1, còn dãy bắt đầu bằng 6 mang dáng in-order, và in-order thật của cây này là 6, 2, 7, 5, 1, 3, 8, 4; "1, 2, 6, 5, 7, 3, 8, 4" sai vì 8 là con trái của 4 nên pre-order phải in 4 trước rồi mới tới 8; "1, 2, 6, 7, 5, 3, 4, 8" sai vì 7 là con trái của 5, cũng phải in 5 trước con của nó.
while(there are more characters in the word to read)
{read a character
if a character is '*' then
dequeue and write the dequeued character to the screen
Đề bài
else
enqueue the character into the queue
}
What is written to the screen for the input ""Go*odA**fter****Noo***n" ?
AoAdoretfoo
BGoodAfter
CoodAfteroo
DGoodAfterN
Lời giải
Đáp án đúng: "GoodAfterN". Hàng đợi lấy ra phần tử vào sớm nhất, nên mỗi dấu sao in ra một ký tự theo đúng thứ tự nạp vào. Lần lượt: G và o vào, dấu sao in G; o, d, A vào, hai dấu sao in o rồi o; f, t, e, r vào, bốn dấu sao in d, A, f, t; N, o, o vào, ba dấu sao in e, r, N; cuối cùng n vào mà không còn dấu sao nào. Những ký tự được in là G, o, o, d, A, f, t, e, r, N, tức GoodAfterN, còn o, o, n vẫn nằm trong hàng đợi. Dãy "GoodAfter" dừng sớm một ký tự, bỏ sót chữ N do dấu sao thứ ba của nhóm sau Noo in ra. Dãy "oodAfteroo" mất chữ G ở đầu, nhưng G vào sớm nhất nên phải là ký tự đầu tiên bị lấy ra. Dãy "oAdoretfoo" in ký tự mới vào trước ký tự cũ, đó là hành vi vào sau ra trước của ngăn xếp, không phải của hàng đợi.
