Danh sách câu hỏi của đề

Câu hỏi: CSD201 Cấu trúc dữ liệu và giải thuật – Bộ ôn tập cuối kỳ số 4

50 câu trắc nghiệm kèm lời giải của môn CSD201 - Cấu trúc dữ liệu và giải thuật, xếp đúng thứ tự trong đề. Trang 2/3 — câu 21–40.

Danh sách câu hỏi

40/50 câuCòn 10
Đề bài
int x = 9;
Node f = head;
while(f.next != tail) f = f.next;
Node q = new Node(x);
q.next = tail;
f.next = q;
A7 1 6 4 3 12 8 2 9
B7 1 6 4 3 12 8 9 2
C7 1 6 4 3 12 9 8 2
D7 9 1 6 4 3 12 8 2
E9 7 1 6 4 3 12 8 2
Lời giải
Đáp án đúng: "7 1 6 4 3 12 8 9 2". Vòng lặp chạy tới khi f.next bằng tail nên f dừng ở nút 8, tức nút liền trước phần tử cuối. Nút mới mang 9 được nối next vào tail rồi f.next trỏ sang nó, vậy 9 nằm giữa 8 với nút cuối là 2, mọi liên kết phía trước không đổi. Dãy "7 1 6 4 3 12 8 2 9" đặt 9 sau 2, muốn vậy phải đi tới khi f chính là tail rồi gán next của tail, khác với điều kiện dừng f.next bằng tail. Dãy "7 1 6 4 3 12 9 8 2" đặt 9 trước 8, nghĩa là f phải dừng sớm hơn một nút, tại 12. Dãy "7 9 1 6 4 3 12 8 2" chèn 9 vào sau nút đầu, chỉ xảy ra nếu gán next của head mà không đi dọc danh sách. Dãy "9 7 1 6 4 3 12 8 2" đặt 9 lên đầu, đó là phép chèn ở head kèm việc dời biến head, không liên quan tới f.
Mở trang câu hỏi này →
A95
B90
C91
D93
Lời giải
Đáp án đúng: "93". Hàm băm gấp dịch cắt khoá theo các dấu gạch thành các nhóm rồi cộng chúng như những số nguyên độc lập, không đảo chữ số của nhóm nào: 44 cộng 65 cộng 76 cộng 8 bằng 193, lấy phần dư với TSize là 100 được 93. "95" ứng với tổng 195, "91" ứng với tổng 191 và "90" ứng với tổng 190, không con số nào trong ba tổng đó dựng được từ bốn nhóm 44, 65, 76 và 8, nên chúng không thể là phần dư của tổng thật. Điểm cần phân biệt: gấp dịch cộng các nhóm theo đúng chiều đọc, còn gấp biên mới đảo chữ số của những nhóm ở vị trí xen kẽ trước khi cộng, và khi đó tổng sẽ khác 193.
Mở trang câu hỏi này →
A101
B001
C100
D01
Lời giải
Đáp án đúng: "100". Dựng cây Huffman bằng cách ghép hai tần số nhỏ nhất, luôn đặt nút tần số lớn hơn sang trái, nhánh trái mang bit 0 và nhánh phải mang bit 1. Hai nhỏ nhất là E 6% và D 16%, ghép thành nút 22% với D bên trái, E bên phải. Hai nhỏ nhất kế tiếp là F 18% và nút 22%, ghép thành nút 40% với nút 22% bên trái vì 22 lớn hơn 18, F bên phải. Còn lại B 32% và C 28% ghép thành nút 60% với B bên trái. Cuối cùng ghép 60% bên trái với 40% bên phải. Lần đường từ gốc tới D: sang phải tới nút 40% được 1, sang trái tới nút 22% được 0, sang trái tới D được 0, vậy D = 100. "101" là mã của E, lá còn lại dưới nút 22%. "01" là mã của C và chỉ dài hai bit; D có tần số 16% thấp hơn C 28% nên không thể được mã ngắn bằng C. "001" đòi D treo dưới nút mang mã 00, nhưng 00 đã là lá B.
Mở trang câu hỏi này →
Đề bài
int h(int n)
  {if (n == 0 || n==1)
      return(1);
       else
        return(h(n-1)+h(n-2));
  }
A2
B3
C4
D5
Lời giải
Đáp án đúng: "5". Hàm dừng khi n bằng 0 hoặc 1, còn lại tự gọi hai lần với n-1 và n-2, nên phải đếm từng lời gọi chứ không phải từng giá trị khác nhau của n. Mở cây lời gọi cho h(3): h(3) gọi h(2) và h(1); h(2) lại gọi h(1) và h(0); h(1) và h(0) là trường hợp cơ sở nên không gọi thêm. Liệt kê ra có h(3), h(2), h(1) sinh từ h(3), h(1) sinh từ h(2) và h(0), cộng cả lời gọi gốc là 5. Vì vậy "2" sai vì nó chỉ đếm hai lời gọi con trực tiếp của h(3); "3" sai vì nó đếm theo đối số khác nhau là 3, 2, 1 và bỏ qua việc h(1) bị gọi tới hai lần ở hai nhánh khác nhau cùng với h(0); "4" sai vì nó bỏ đúng một trong hai lần gọi h(1), và đây chính là chỗ làm đệ quy kiểu Fibonacci tốn kém: cùng một đối số bị tính lại nhiều lần.
Mở trang câu hỏi này →
ANo matter how many data items there are, insertion and searching (and sometimes deletion) always take constant time: O(1).
BIf the chaining method is used for collision resolution, insertion and searching (and sometimes deletion) can take constant time: O(1).
CThe expected complexity of hashing algorithm is O(1). However by the collision resolution, sometimes it may take O(n).
DIf the coalesced method is used for collision resolution, insertion and searching (and sometimes deletion) always take constant time: O(1).
Lời giải
Đáp án đúng: "The expected complexity of hashing algorithm is O(1). However by the collision resolution, sometimes it may take O(n).". Hàm băm tốt rải khoá đều nên trung bình mỗi ô chỉ giữ rất ít phần tử và chi phí chèn hay tìm là hằng số; nhưng khi nhiều khoá cùng rơi một ô, mọi cách giải va chạm đều phải lần theo cụm hoặc theo chuỗi, và trong trường hợp cực đoan mọi khoá đụng nhau thì phép tìm quét qua cả n phần tử. Phương án "No matter how many data items there are, insertion and searching (and sometimes deletion) always take constant time: O(1)." bỏ qua va chạm, nên chữ always không đứng vững. Phương án "If the chaining method is used for collision resolution, insertion and searching (and sometimes deletion) can take constant time: O(1)." chỉ đúng cho phép chèn vào đầu chuỗi; phép tìm vẫn phải đi hết chuỗi, dài tới n nếu mọi khoá cùng ô. Phương án "If the coalesced method is used for collision resolution, insertion and searching (and sometimes deletion) always take constant time: O(1)." cũng vậy, cách gộp chuỗi ngay trong bảng vẫn bắt phải dò theo con trỏ qua nhiều ô.
Mở trang câu hỏi này →
Đề bài
Node p1,p2; p1 = p.next;
 p2 = p1.next;
 p.next = p2;
if(p2!=null) p2.prev=p;
A7 9 6 4 3 10 2
B7 9 6 4 3 10 8
C7 9 6 4 3 8 2
D7 9 6 4 10 8 2
E9 6 4 3 10 8 2
Lời giải
Đáp án đúng: "7 9 6 4 3 10 2". Danh sách là 7, 9, 6, 4, 3, 10, 8, 2 và p trỏ vào nút 10. Đoạn mã lấy p1 = p.next tức nút 8, rồi p2 = p1.next tức nút 2; lệnh p.next = p2 nối 10 thẳng sang 2 và p2.prev = p vá chiều ngược lại, nên nút 8 bị bỏ khỏi cả hai chiều liên kết. Kết quả là 7, 9, 6, 4, 3, 10, 2. Phương án "7 9 6 4 3 10 8" là kết quả của việc xoá nút cuối 2, nhưng mã không gán tail cũng không cắt liên kết sau nút 8. Phương án "7 9 6 4 3 8 2" ứng với xoá chính nút p là 10, trong khi p vẫn còn và còn là nơi phát ra liên kết mới. Phương án "7 9 6 4 10 8 2" ứng với xoá nút đứng trước p là 3, mà mã không chạm tới p.prev chút nào. Phương án "9 6 4 3 10 8 2" là kết quả xoá đầu danh sách, việc đó đòi gán lại head và mã không làm.
Mở trang câu hỏi này →
Ainfinity
B3
C20
D15
Lời giải
Đáp án đúng: "3". Dijkstra cố định A với nhãn 0 rồi gán nhãn tạm B = 2, E = 5, C = 10, D = 20. Nhãn nhỏ nhất là B = 2 nên cố định B, và cung B→D = 1 hạ nhãn của D từ 20 xuống 2 + 1 = 3. Tiếp đó cố định D = 3 và cung D→C = 4 hạ nhãn C xuống 7; rồi cố định E = 5 và cung E→C = 1 hạ nhãn C xuống 6. Khi C được cố định với 6 thì D đã mang nhãn cuối cùng từ trước, bằng 3. "20" sai vì đó chỉ là nhãn tạm ban đầu theo cung A→D và bị thay ngay ở bước cố định B. "15" sai vì 15 là chi phí của đường A→E→D, bằng 5 cộng 10, dài hơn đường A→B→D nên không bao giờ thành nhãn của D. "infinity" sai vì D kề thẳng A qua cung trọng số 20, nên nó có nhãn hữu hạn ngay sau bước đầu tiên.
Mở trang câu hỏi này →
28Consider the following function:4 lựa chọncó code
Đề bài
int fun(int n)
  {if (n < 0)
      return(fun(-n));
       else if(n<4)
        return(2);
          else
          return(n*fun(n/2));
  }

What values of n are directly handled by the stopping (base) case?

An < 0
Bn < 4
Cn > = 4
Dn >= 0 && n<4
Lời giải
Đáp án đúng: "n >= 0 && n<4". Hàm có ba nhánh: n âm thì gọi lại chính nó với -n, n nhỏ hơn 4 thì trả về 2 ngay, còn lại trả về n nhân fun(n/2). Chỉ nhánh giữa kết thúc mà không sinh thêm lời gọi nào nên đó là trường hợp dừng; nhưng nhánh ấy chỉ tới được khi điều kiện n âm đã sai, nghĩa là n không âm. Ghép hai điều đó thì những giá trị được trường hợp dừng xử lý trực tiếp đúng là n từ 0 tới 3. Điều kiện "n < 0" là một nhánh đệ quy: với n âm hàm còn phải gọi fun(-n) rồi mới có cơ hội dừng. Điều kiện "n < 4" bao cả số âm, mà số âm phải đi qua lời gọi đổi dấu trước đã nên không được xử lý trực tiếp. Điều kiện "n > = 4" là nhánh nhân rồi chia đôi, càng không phải chỗ dừng vì nó luôn sinh thêm một lời gọi nữa.
Mở trang câu hỏi này →
Đề bài
while(there are more characters in the word to read)

{read a character if a character is '*' then dequeue the queue

Đề bài
else
enqueue the character into the queue
}

How the queue looks like after processing the input "Hello∗∗∗Worl***d*"?

A(1)
B(2)
C(4)
D(3)
Lời giải
Đáp án đúng: "(4)", tức mảng vòng có r ở ô 1, l ở ô 2, d ở ô 3 và ba ô 0, 4, 5 để rỗng. Chạy tay trên mảng sáu ô: H, e, l, l, o vào các ô 0 đến 4; ba dấu sao lấy ra H, e, l nên đầu hàng đợi dời tới ô 3; W vào ô 5, rồi o, r, l quay vòng về các ô 0, 1, 2 và hàng đợi đầy; ba dấu sao tiếp lấy ra l, o, W nên đầu hàng dời tới ô 0; d vào ô 3; dấu sao cuối lấy ra o ở ô 0. Còn đúng r ở ô 1, l ở ô 2, d ở ô 3. "(1)" đặt d ở ô 0 cùng r ở ô 4 và l ở ô 5, tức đầu hàng đợi lệch một ô so với vị trí thật. "(2)" đặt l ở ô 0, d ở ô 1 và r ở ô 5, phá cả thứ tự r trước l trước d. "(3)" dồn r, l, d về ba ô đầu, đó là hình ảnh của mảng bị dịch dồn sau mỗi phép lấy ra, còn mảng vòng không dịch phần tử mà chỉ dời chỉ số đầu hàng.
Mở trang câu hỏi này →
30Consider the following function:4 lựa chọncó code
Đề bài
int fun(int n)
   {if(n<=0) return(1);
      return(2*fun(n-2));
   }

What is the output when the statement:

Đề bài
System.out.println(fun(5));

is run?

A8
B7
C9
D10
Lời giải
Đáp án đúng: "8". Hàm trả 1 khi n không dương, còn lại trả 2 nhân kết quả của fun(n-2), nên giá trị cuối là 2 lũy thừa số lần đệ quy. Chuỗi lời gọi: fun(5) cần fun(3), fun(3) cần fun(1), fun(1) cần fun(-1); tới fun(-1) thì n không lớn hơn 0 nên trả 1 và dừng. Trả ngược lên: fun(1) = 2×1 = 2, fun(3) = 2×2 = 4, fun(5) = 2×4 = 8, đúng ba lần nhân với 2. "7" và "9" không phải lũy thừa của 2 nên không thể là kết quả của một chuỗi chỉ gồm các phép nhân với 2 bắt đầu từ 1. "10" là 2×5, tức lầm rằng hàm nhân với chính n; thân hàm chỉ nhân với hằng số 2, còn n chỉ đóng vai đếm số bước đệ quy.
Mở trang câu hỏi này →
AA, B, C, E, G, F, D, H
BA, B, E, G, F, D, C, H
CA, B, E, G, C, F, D, H
DA, B, E, G, C, F, D
Lời giải
Đáp án đúng: "A, B, E, G, C, F, D, H". Duyệt theo bề rộng dùng hàng đợi nên phải vét hết các đỉnh kề của A trước khi sang tầng sau. Với các cạnh A–B, A–E, A–G, B–C, B–E, E–G, C–D, D–F, F–G và đỉnh H cô lập: thăm A rồi nạp B, E, G theo thứ tự chữ cái; lấy B ra, nạp thêm C; lấy E ra, các đỉnh kề của nó là A, B, G đều đã gặp; lấy G ra, nạp thêm F; lấy C ra, nạp thêm D; lấy F rồi D ra, không còn đỉnh mới; H không nối với ai nên được thăm khi thuật toán khởi động lại ở thành phần liên thông còn lại. Vì vậy "A, B, C, E, G, F, D, H" sai vì nó thăm C ngay sau B, trong khi E và G đã nằm trong hàng đợi trước C; "A, B, E, G, F, D, C, H" sai vì C được nạp khi đang xét B, sớm hơn F được nạp khi đang xét G, nên C phải ra trước; "A, B, E, G, C, F, D" sai vì bỏ sót H, mà một lần duyệt đầy đủ phải khởi động lại ở mọi đỉnh chưa thăm.
Mở trang câu hỏi này →
A2, 1, 4, 7, 8, 3, 9
B4, 2, 7, 1, 8, 3, 9
C2, 1, 4, 3, 7, 8, 9
D4, 2, 7, 1, 3, 8, 9
Lời giải
Đáp án đúng: "4, 2, 7, 1, 3, 8, 9". Cây có gốc 5, nhánh trái 2 với hai con 1 và 4, dưới 4 là con trái 3, nhánh phải 7 với con phải 8 và dưới 8 là con phải 9. Xoá bằng cách sao chép lấy nút cực phải của nhánh trái làm giá trị thay thế: đi từ 2 sang 4, mà 4 không có con phải nên 4 chính là tiền nhiệm trung tố; gán 4 cho gốc rồi tháo nút 4 cũ, con trái 3 của nó lên thế chỗ làm con phải của 2. Cây mới có gốc 4, nhánh trái 2 với hai con 1 và 3, nhánh phải vẫn là 7, 8, 9. Duyệt theo chiều rộng cho 4, rồi 2 và 7, rồi 1, 3, 8, rồi 9. Dãy "4, 2, 7, 1, 8, 3, 9" xếp 8 trước 3 ở cùng mức, nhưng duyệt chiều rộng đọc từ trái sang phải nên 3 nằm dưới 2 phải đứng trước 8 nằm dưới 7. Dãy "2, 1, 4, 7, 8, 3, 9" đưa 2 lên làm gốc, đó là lối xoá bằng cách nối chứ không phải sao chép. Dãy "2, 1, 4, 3, 7, 8, 9" cũng nâng 2 lên gốc và treo nhánh phải xuống dưới 4, vẫn là phép nối cây chứ không phải thay giá trị gốc.
Mở trang câu hỏi này →
Đề bài
int x = 5;
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 5 3 9 8 2
B7 11 6 4 3 5 9 8 2
C7 11 6 4 3 9 8 2 5
D7 5 11 6 4 3 9 8 2
E7 11 6 4 3 9 8 5 2
Lời giải

Đáp án đúng: "7 11 6 4 5 3 9 8 2". Danh sách là 7, 11, 6, 4, 3, 9, 8, 2 và p trỏ vào nút 3. Vòng while(f.next != p) f = f.next; chạy từ head và dừng khi f là nút 4, tức nút đứng ngay trước p. Sau đó q = new Node(x) với x = 5, q.next = p nối nút mới vào trước 3, rồi f.next = q cho 4 trỏ sang 5. Nút 5 do đó nằm giữa 4 và 3, cho dãy 7, 11, 6, 4, 5, 3, 9, 8, 2. Phương án "7 11 6 4 3 5 9 8 2" là kết quả của chèn SAU p, muốn vậy phải viết q.next = p.next; p.next = q;. Phương án "7 11 6 4 3 9 8 2 5" là chèn vào cuối, cần đi tới tail chứ không dừng ở nút trước p. Phương án "7 5 11 6 4 3 9 8 2" là chèn ngay sau head, tức vòng lặp không chạy lần nào. Phương án "7 11 6 4 3 9 8 5 2" chèn trước nút cuối, không khớp với điều kiện dừng neo vào p.

Mở trang câu hỏi này →
A19, 11, 23, 6, 3, 15, 20
B19, 11, 23, 6, 15, 4, 20
C19, 11, 23, 6, 15, 20, 4
D19, 11, 23, 6, 20, 4, 15
Lời giải
Đáp án đúng: "19, 11, 23, 6, 15, 20, 4". Chèn lần lượt: 19 làm gốc; 11 nhỏ hơn 19 nên sang trái; 6 nhỏ hơn cả 19 và 11 nên thành con trái của 11; 4 nhỏ hơn 6 nên thành con trái của 6; 15 nhỏ hơn 19 nhưng lớn hơn 11 nên thành con phải của 11; 23 lớn hơn 19 nên sang phải; 20 lớn hơn 19 và nhỏ hơn 23 nên thành con trái của 23. Duyệt theo bề rộng đọc từng mức: 19, rồi 11 và 23, rồi 6, 15, 20, cuối cùng 4 nằm một mình ở mức bốn. "19, 11, 23, 6, 15, 4, 20" sai vì nó in 4 trước 20, trong khi 4 sâu hơn 20 đúng một mức. "19, 11, 23, 6, 20, 4, 15" sai vì nó đẩy 15 xuống sau 4, dù 15 là con của 11 nên cùng mức với 20. "19, 11, 23, 6, 3, 15, 20" sai vì nó chứa khoá 3 không có trong dãy chèn và làm mất khoá 4.
Mở trang câu hỏi này →
35Consider the following function:4 lựa chọncó code
Đề bài
void fun(int n)
    {if(n > 0)
      { n = n/5;
        fun(n);
        System.out.print("  " + n);
      }
    }

What is the output when the statement fun(23); is run?

A4 1
B4 0
C1 4
D0 4
Lời giải
Đáp án đúng: "0 4". Trong thân hàm, n bị gán lại bằng n/5 trước khi gọi đệ quy, và lệnh in đứng sau lời gọi nên mỗi tầng chỉ in khi đã quay về, lại in giá trị n đã bị chia. fun(23) đổi n thành 4 rồi gọi fun(4); fun(4) đổi n thành 0 rồi gọi fun(0); fun(0) không vào thân vì điều kiện n lớn hơn 0 sai. Trên đường quay về, tầng của fun(4) in 0 rồi tầng của fun(23) in 4. Dãy "4 0" là thứ tự in khi đặt lệnh in trước lời gọi đệ quy, lúc đó 4 ra trước 0. Dãy "4 1" dùng 1 thay cho 0, nhưng 4 chia 5 trong phép chia nguyên bằng 0 chứ không phải 1. Dãy "1 4" sai cả giá trị lẫn thứ tự, nó giả định tầng sâu in 1 rồi tầng ngoài in 4, trong khi tầng sâu giữ n bằng 0.
Mở trang câu hỏi này →
A6, 2, 7, 1, 4, 8, 5
B6, 1, 7, 2, 8, 5, 4
C6, 1, 8, 2, 7, 4, 5
D6, 2, 8, 1, 4, 7, 5
Lời giải
Đáp án đúng: "6, 1, 8, 2, 7, 4, 5". Cây có gốc 6 với con trái 3 và con phải 8; nút 3 có con trái 1 và con phải 4; nút 1 có con phải 2; nút 4 có con phải 5; nút 8 có con trái 7. Xoá bằng cách trộn là bỏ hẳn nút 3, đưa nhánh trái của nó lên thay chỗ và treo nhánh phải vào nút phải nhất của nhánh trái: nút phải nhất của nhánh 1 là 2, nên nhánh gồm 4 và 5 thành con phải của 2, còn 1 lên làm con trái của 6. Đọc theo mức: 6; rồi 1 và 8; rồi 2 và 7; rồi 4; rồi 5. "6, 2, 8, 1, 4, 7, 5" là kết quả của cách xoá bằng cách thế, tức đưa 2 lên đúng vị trí nút 3 và giữ nguyên hai nhánh, nên 1 và 4 cùng ở mức ba. "6, 2, 7, 1, 4, 8, 5" còn kéo 7 lên mức hai, nhưng 7 là con của 8 nên phải nằm dưới 8. "6, 1, 7, 2, 8, 5, 4" cũng kéo 7 lên mức hai và đẩy 8 xuống mức ba, trong khi phép xoá này không chạm gì tới nhánh phải của gốc.
Mở trang câu hỏi này →
37Consider the following function:5 lựa chọncó code
Đề bài
int fun(int n)
  {if (n < 0)
      return(fun(-n));
       else if(n<5)
        return(2);
          else
          return(n*fun(n-2));
  }

What is the value of fun(5)?

A5
B12
C2
D4
E10
Lời giải
Đáp án đúng: "10". Hàm có ba nhánh: n âm thì đổi dấu rồi gọi lại, n nhỏ hơn 5 thì trả 2, còn lại trả n nhân fun(n-2). Với n = 5: 5 không âm và cũng không nhỏ hơn 5, nên vào nhánh cuối và cần fun(3); 3 nhỏ hơn 5 nên fun(3) = 2 và dừng tại đó. Vậy fun(5) = 5 × 2 = 10. "2" chính là giá trị của fun(3), tức dừng ở lời gọi con mà quên nhân với 5. "5" đòi fun(3) phải bằng 1, nhưng nhánh dừng của hàm trả 2 chứ không trả 1. "4" là 2×2, như thể cả fun(5) và fun(3) đều rơi vào nhánh dừng, trong khi 5 không nhỏ hơn 5. "12" không phải bội của 5, mà phép cuối bắt buộc là 5 nhân với kết quả của fun(3), nên mọi giá trị trả về đều phải chia hết cho 5.
Mở trang câu hỏi này →
Đề bài
Integer fun()
  {if (isEmpty())  return(null);
    Integer x = tail.info;
    if (head == tail)
      head = tail = null;
       else
      {Node p1,p; p1=null;p=head;
        while(p!=tail) {p1=p;p=p.next;}
        p1.next=null; tail=p1;
       }
    return(x);
  }

Specify the correct statement about the fun() method in the code above (choose the most suitable one).

AIt returns a node at the end of the list.
BIt removes and returns a node at the beginning of the list
CIt removes and returns a node at the middle of the list
DIt removes and returns a node at the end of the list
Lời giải
Đáp án đúng: "It removes and returns a node at the end of the list". Đọc theo đúng thụt lề: hàm lưu x bằng tail.info trước, nếu danh sách chỉ có một nút thì head và tail cùng về null, ngược lại cho p chạy từ head còn p1 luôn giữ nút liền trước p, vòng while với điều kiện p khác tail dừng đúng lúc p chạm tail nên p1 là nút áp cuối; hai lệnh p1.next bằng null và tail bằng p1 cắt hẳn nút cuối ra khỏi danh sách, rồi hàm trả về giá trị đã lưu. Vì vậy "It returns a node at the end of the list." sai vì nó bỏ mất phần quan trọng là danh sách bị ngắn đi một nút; "It removes and returns a node at the beginning of the list" sai vì head chỉ bị gán lại trong trường hợp danh sách một nút, các trường hợp khác head không hề thay đổi; "It removes and returns a node at the middle of the list" sai vì điều kiện dừng của vòng lặp gắn chặt vào tail nên không bao giờ dừng ở nút giữa.
Mở trang câu hỏi này →
A2, 3, 4, 11, 9, 7, 12, 16, 7, 5
B2, 3, 16, 11, 9, 7, 12, 4, 7, 5
C2, 4, 16, 11, 9, 7, 12, 3, 7, 5
D2, 4, 11, 9, 7, 12, 3, 7, 5, 16
Lời giải
Đáp án đúng: "2, 4, 16, 11, 9, 7, 12, 3, 7, 5". Insertion sort chỉ làm việc trong đoạn đầu đã sắp, phần sau giữ nguyên vị trí ban đầu. Bước i = 1 chèn 4 vào đoạn đã sắp chỉ gồm 16, được 4, 16, 2, 11, 9, 7, 12, 3, 7, 5. Bước i = 2 chèn 2 vào đoạn 4, 16, đẩy cả hai sang phải, được 2, 4, 16, 11, 9, 7, 12, 3, 7, 5; ba ô đầu đã sắp còn bảy ô sau chưa bị chạm tới. Dãy "2, 3, 4, 11, 9, 7, 12, 16, 7, 5" đã lôi số 3 từ ô thứ tám về đầu, việc chỉ xảy ra ở bước i = 7. Dãy "2, 3, 16, 11, 9, 7, 12, 4, 7, 5" hoán vị 3 với 4, tức chọn phần tử nhỏ nhất toàn mảng rồi đổi chỗ, đó là lối của selection sort. Dãy "2, 4, 11, 9, 7, 12, 3, 7, 5, 16" đẩy 16 về cuối mảng, dấu vết của một lượt bubble sort, còn phép chèn không bao giờ đưa phần tử ra khỏi đoạn đã sắp.
Mở trang câu hỏi này →
A(2)
B(4)
C(1)
D(3)
Lời giải
Đáp án đúng: "(3)", tức bảng có 204 ở ô 3, 34 ở ô 4, 65 ở ô 5 và 94 ở ô 8, các ô còn lại rỗng. Với h(x) = x%10 và dò bậc hai (h(x) + i^2)%10: 34 băm về ô 4 đang trống nên vào ô 4; 65 băm về ô 5 và vào ô 5; 94 cũng băm về 4 nhưng ô 4 đã có 34, thử i = 1 được ô 5 đang có 65, thử i = 2 được (4 + 4)%10 = 8 nên 94 nằm ở ô 8; 204 lại băm về 4, i = 1 cho ô 5 và i = 2 cho ô 8 đều kẹt, i = 3 cho (4 + 9)%10 = 3 nên 204 vào ô 3. Phương án "(1)" đặt 94 ở ô 9 thay vì ô 8, chỉ đúng nếu bước i = 2 cộng 5 thay vì cộng 4. Phương án "(2)" đặt 204 ở ô 2, chỉ đúng nếu bước i = 3 cộng 8 thay vì cộng 9. Phương án "(4)" bỏ trống ô 3 và đẩy 204 xuống ô 9, hợp với dò tuyến tính đi liên tiếp 4, 5, 6, 7, 8, 9 chứ không hợp với các bước nhảy 1, 4, 9 của dò bậc hai.
Mở trang câu hỏi này →