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 thi lại số 2

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
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 "Goo**dMor****ning**"?

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

For the call fun(3, 3), how many calls to fun will be made, including the original call?

A2
B3
C9
D8
Lời giải
Đáp án đúng: "3". Mỗi lời gọi chỉ sinh đúng một lời gọi con với tham số n/2 chia nguyên, và dừng khi n bằng 0, nên số lời gọi bằng số lần chia 3 cho 2 để về 0, cộng thêm lời gọi ban đầu. Chuỗi cụ thể: fun(3, 3) gọi fun(3, 1) vì 3/2 = 1; fun(3, 1) gọi fun(3, 0) vì 1/2 = 0; fun(3, 0) gặp n == 0 nên trả 1 ngay và không gọi thêm. Đếm cả lời gọi đầu tiên được 3. "2" dừng đếm ở fun(3, 1), quên rằng 1 vẫn chưa phải điều kiện dừng nên còn một lời gọi nữa. "8" là 2 lũy thừa 3, tức số lời gọi của một hàm mỗi lần sinh hai lời gọi con qua ba mức; hàm này chỉ sinh một lời gọi con mỗi lần. "9" là 3 nhân 3, một kết quả trung gian của phép lũy thừa chứ không phải số lời gọi, và giá trị hàm trả về ở đây còn là 27.
Mở trang câu hỏi này →
23Consider the following function:4 lựa chọncó code
Đề bài
int fun(int a, int n)
  { if(n == 0) return(1);
     int t =fun(a,n/2);
     if(n%2==0)
         return(t*t);
          else
            return(t*t*a);
 }

What is the value of fun(3, 2)?

A6
B5
C9
D8
Lời giải
Đáp án đúng: "9". Hàm là luỹ thừa nhanh: nó tính t bằng fun(a, n/2) rồi trả t nhân t khi n chẵn, trả t nhân t nhân a khi n lẻ, tức dựng a mũ n từ a mũ n/2. Lần theo lời gọi fun(3, 2): n bằng 2 khác 0 nên gọi fun(3, 1); trong đó n bằng 1 khác 0 nên gọi fun(3, 0) trả về 1, rồi vì 1 là số lẻ nên trả 1 × 1 × 3 = 3; quay về mức ngoài với t bằng 3, n bằng 2 là số chẵn nên kết quả là 3 × 3 = 9, đúng bằng 3 mũ 2. Vì vậy "6" sai vì nó là 3 × 2, tức đọc hàm như một phép nhân hai tham số thay vì luỹ thừa; "8" sai vì nó là 2 mũ 3, tức đảo vai trò cơ số và số mũ; "5" sai vì trong toàn bộ dấu vết chỉ xuất hiện các giá trị 1, 3 và 9, không bước nào cho ra 5.
Mở trang câu hỏi này →
24Consider the following function:4 lựa chọncó code
Đề bài
void quiz(int n)
  {if (n > 1)
      {quiz(n);
        quiz(n);
      }
      System.out.print("*  ");
  }

What will happen if the statement quiz(5); is run?

AThe program keeps running until you press Ctrl-C
BThe run-time stack overflows, halting the program
CThe operating system detects the infinite recursion because of the "repeated state"
DThe results are nondeterministic
Lời giải
Đáp án đúng: "The run-time stack overflows, halting the program". Lời gọi bên trong truyền đúng n chứ không phải n-1, nên điều kiện n lớn hơn 1 mãi đúng và không trường hợp cơ sở nào được tới; mỗi lượt gọi lại đặt thêm một khung lên ngăn xếp thời gian chạy, mà ngăn xếp có dung lượng giới hạn, nên máy ảo ném lỗi tràn ngăn xếp rồi dừng chương trình, thường chỉ sau một phần nhỏ của giây. Phương án "The program keeps running until you press Ctrl-C" hình dung một vòng lặp vô hạn không tốn bộ nhớ, nhưng đệ quy thì tiêu ngăn xếp mỗi lượt nên không thể chạy mãi. Phương án "The operating system detects the infinite recursion" gán cho hệ điều hành khả năng phân tích chuỗi lời gọi để nhận ra trạng thái lặp lại, điều không hệ nào làm; giới hạn duy nhất là dung lượng ngăn xếp. Phương án "The results are nondeterministic" sai vì hành vi lặp lại y nguyên mỗi lần chạy, kết cục luôn là tràn ngăn xếp.
Mở trang câu hỏi này →
25Consider the following function:4 lựa chọncó code
Đề bài
void fun(int n)
  {if (n < 0)
    {System.out.println(“-“);
     fun(-n);
    }
    else if(n<24)
      System.out.println(n);
        else
        {fun(n/24);
         System.out.println(n%15);
        }
  }

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

An < 0
Bn < 24
Cn >= 0 && n<24
Dn >= 24
Lời giải
Đáp án đúng: "n >= 0 && n<24". Hàm có ba nhánh nối nhau bằng if và else: nhánh n < 0 in dấu rồi gọi lại với -n nên là bước quy giản; nhánh n < 24 in n và kết thúc mà không gọi lại, đây mới là trường hợp cơ sở; nhánh cuối gọi fun(n/24) nên cũng quy giản. Vì nhánh thứ hai chỉ được xét sau khi điều kiện n < 0 đã sai, nó thực sự chạy với n không âm và nhỏ hơn 24, tức miền n >= 0 và n < 24. Phương án "n < 24" đọc điều kiện tách rời khỏi chuỗi if và else, bỏ qua việc mọi n âm đã bị nhánh trước bắt lấy và đẩy sang lời gọi đệ quy. Phương án "n < 0" chính là nhánh chứa lời gọi đệ quy nên không thể là điểm dừng. Phương án "n >= 24" là nhánh gọi fun(n/24) rồi in n%15, cũng đệ quy chứ không dừng.
Mở trang câu hỏi này →
26Consider 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(6)?

A5
B12
C2
D4
E11
Lời giải
Đáp án đúng: "12". Với n = 6 thì 6 không âm nên bỏ nhánh fun(-n), lại không nhỏ hơn 5 nên bỏ nhánh trả về 2, hàm chạy nhánh cuối và trả về 6 nhân fun(6/2) = 6 nhân fun(3). Lời gọi fun(3) thoả 3 < 5 nên trả về 2 ngay, vậy kết quả là 6 nhân 2 = 12. "2" sai vì 2 chỉ là giá trị của nhánh dừng, nó là đáp số khi đối số nằm trong khoảng từ 0 đến 4. "4" sai vì 4 là 2 nhân 2, ứng với việc nhân hai lần giá trị nhánh dừng thay vì nhân chính n với fun(n/2). "5" sai vì 5 là ngưỡng trong điều kiện n < 5, không phải giá trị trả về của bất kỳ nhánh nào. "11" sai vì chuỗi lời gọi chỉ có một phép nhân duy nhất là 6 nhân 2, không bước nào sinh ra 11.
Mở trang câu hỏi này →
27Consider the following function:4 lựa chọncó code
Đề bài
void foo(int n)
  {int m = n/2;
   int k = n%2;
   if (m > 0)
    {foo(m);
    }
   System.out.print(k + " ");
  }

What is the output when the statement foo(13); is run?

A1 0 0 1
B1 0 1 0
C1 0 1 1
D1 1 0 1
Lời giải
Đáp án đúng: "1 1 0 1". Mỗi tầng tính m bằng n/2, k bằng n%2, gọi foo(m) khi m còn lớn hơn 0 rồi mới in k, nên các chữ số dư được in theo chiều quay về, từ tầng sâu nhất ra ngoài. foo(13) có k bằng 1 và gọi foo(6); foo(6) có k bằng 0 và gọi foo(3); foo(3) có k bằng 1 và gọi foo(1); foo(1) có m bằng 0 nên dừng rồi in 1. Quay về in tiếp 1 của foo(3), 0 của foo(6), 1 của foo(13), đúng là biểu diễn nhị phân của 13. Dãy "1 0 1 1" chính là thứ tự các dư lúc được sinh ra, tức kết quả nếu in trước khi gọi đệ quy, và nó đọc ra số 11. Dãy "1 0 0 1" đọc ra số 9, ứng với chuỗi chia đôi 9, 4, 2, 1 chứ không phải của 13. Dãy "1 0 1 0" đọc ra số 10, ứng với chuỗi 10, 5, 2, 1, cũng không khớp với 13, 6, 3, 1.
Mở trang câu hỏi này →
28Consider the following function:5 lựa chọncó code
Đề bài
void fun(int n)
   {int m = n/3;
    int k = n%3;
    System.out.print(k + " ");
    if(m > 0)
     {fun(m);
     }
   }

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

A2 0 2 1
B2 2 1
C1 0 0 1
D1 2 2
E2 0 1
Lời giải
Đáp án đúng: "2 2 1". Hàm lấy m bằng n chia nguyên cho 3 và k bằng n chia 3 lấy dư, in k trước rồi mới gọi đệ quy với m, nên chuỗi in ra là các chữ số dư của phép đổi 17 sang cơ số 3 đọc từ thấp lên cao. Gọi fun(17): m bằng 5, k bằng 2, in 2; fun(5): m bằng 1, k bằng 2, in 2; fun(1): m bằng 0, k bằng 1, in 1, và vì m không lớn hơn 0 nên dừng. "2 0 2 1" chèn thêm một chữ số 0, chỉ có nếu một lần gọi nào đó cho dư 0, nhưng ba lần gọi cho dư lần lượt 2, 2, 1. "1 0 0 1" có bốn chữ số nên cần bốn lần chia, trong khi 17 chia cho 3 ba lần đã về 0, và dư đầu tiên của 17 là 2 chứ không phải 1. "1 2 2" là kết quả đọc ngược, chỉ xảy ra nếu lệnh in đặt sau lời gọi đệ quy. "2 0 1" dừng sớm một bước so với điều kiện m lớn hơn 0.
Mở trang câu hỏi này →
A18, 10, 23, 6, 15, 20, 3
B18, 10, 23, 6, 15, 3, 20
C18, 10, 23, 6, 3, 15, 20
D18, 10, 23, 6, 20, 3, 15
Lời giải
Đáp án đúng: "18, 10, 23, 6, 15, 20, 3". Chèn lần lượt 18, 10, 6, 3, 15, 23, 20 vào cây tìm kiếm nhị phân: 18 làm gốc; 10 nhỏ hơn 18 nên sang trái; 6 nhỏ hơn 18 và nhỏ hơn 10 nên là con trái của 10; 3 xuống tiếp làm con trái của 6; 15 nhỏ hơn 18 nhưng lớn hơn 10 nên là con phải của 10; 23 lớn hơn 18 nên là con phải của gốc; 20 lớn hơn 18 nhưng nhỏ hơn 23 nên là con trái của 23. Duyệt theo chiều rộng đọc từng mức từ trái sang phải: 18; rồi 10 và 23; rồi 6, 15 và 20; mức cuối chỉ có 3. "18, 10, 23, 6, 15, 3, 20" đặt 3 trước 20 dù 3 nằm sâu hơn 20 một mức. "18, 10, 23, 6, 3, 15, 20" đọc 3 ngay sau 6 như đi theo chiều sâu, trong khi 15 cùng mức với 6 nên phải đọc trước. "18, 10, 23, 6, 20, 3, 15" vừa sai mức của 3 vừa đẩy 15 xuống cuối dù 15 là con phải của 10.
Mở trang câu hỏi này →
30Given a search() method in a binary search tree:4 lựa chọncó code
Đề bài
Node search(int x)
   { Node p = root;
      while(p!=null && p.info != x)
        { if(x<p.info)  p = p.left;
           else   p=p.right;
         }
      return(p);
    }

The complexity of this algorithm is:

AO(n^2)
BO(n).
CO(log n).
DO(nlog n)
Lời giải
Đáp án đúng: "O(log n).". Thân vòng while chỉ làm một việc là so x với p.info rồi chuyển p sang p.left hoặc p.right, tức mỗi lượt đi xuống đúng một tầng và cắt bỏ trọn một cây con, nên số lượt lặp nhiều nhất bằng chiều cao cây. Với cây tìm kiếm nhị phân có chiều cao tối ưu trên n nút thì chiều cao xấp xỉ log2 của n, nên chi phí tìm là O(log n), và đó cũng chính là lý do người ta phải cân bằng cây. Vì vậy "O(n^2)" sai vì không có vòng lặp lồng nhau nào, thân vòng chỉ gồm một phép so sánh và một phép gán; "O(nlog n)" sai vì đó là cấp của các thuật toán sắp xếp dựa trên so sánh phải chạm mọi phần tử, còn ở đây ta chỉ đi một đường từ gốc xuống; riêng "O(n)." chỉ đúng khi cây suy biến thành dạng xương sống, mỗi nút một con và chiều cao bằng số nút, tức trường hợp xấu nhất mà câu hỏi không nêu, nên nó không phải cấp đặc trưng được gán cho phép tìm trên cây tìm kiếm.
Mở trang câu hỏi này →
AThe tree is both full and complete.
BThe tree is full but not complete.
CThe tree is neither complete nor full.
DThe tree is complete but not full.
Lời giải
Đáp án đúng: "The tree is both full and complete.". Cây có gốc 40 với hai con 25 và 50; 25 có hai con 15 và 35; 15 có hai con 10 và 20; 50 có hai con 45 và 55; các nút 35, 10, 20, 45, 55 là lá. Kiểm tính đầy: mọi nút trong là 40, 25, 15, 50 đều có đúng hai con và mọi nút khác không có con nào, nên cây đầy. Kiểm tính đủ: mức một có 40, mức hai có 25 và 50, mức ba có 15, 35, 45, 55 tức đã kín, mức cuối chỉ có 10 và 20 là hai con của 15 mà 15 là nút ngoài cùng bên trái của mức ba, nên các lá cuối nằm sát bên trái và cây đủ. Phương án "The tree is full but not complete." bỏ qua chi tiết 10 và 20 treo đúng ở nhánh trái nhất, nơi tính đủ yêu cầu. Phương án "The tree is complete but not full." sai vì không tìm được nút trong nào chỉ có một con. Phương án "The tree is neither complete nor full." trái cả hai phép kiểm vừa chạy.
Mở trang câu hỏi này →
A40, 35, 15, 50, 45, 30
B40, 15, 50, 35, 45, 30
C15, 40, 35, 50, 45, 30
D40, 30, 15, 50, 35, 45
Lời giải
Đáp án đúng: "40, 15, 50, 35, 45, 30". Cây có gốc 40, con trái 25 với con trái 15 và con phải 35, con trái của 35 là 30, còn 50 có con trái 45. Xoá 25 theo kiểu hợp nhất nghĩa là cho nhánh trái của nó leo lên thay chỗ, rồi treo nhánh phải của nó vào nút phải nhất của nhánh trái. Nhánh trái của 25 chỉ có một nút 15, nên 15 lên làm con trái của 40 và cây gốc 35 trở thành con phải của 15. Cây mới: 40 có hai con 15 và 50; 15 có con phải 35; 50 có con trái 45; 35 có con trái 30. Duyệt theo lớp cho 40; rồi 15, 50; rồi 35, 45; rồi 30. Phương án "40, 35, 15, 50, 45, 30" đưa 35 lên thay 25, đó là lấy nút phải nhất của nhánh trái làm nút thay thế, tức kiểu xoá sao chép. Phương án "15, 40, 35, 50, 45, 30" đặt 15 trước 40 nên không còn là duyệt theo lớp tính từ gốc. Phương án "40, 30, 15, 50, 35, 45" cho 30 làm con của 40, nhưng 30 vẫn nằm sâu dưới 35 sau khi hợp nhất.
Mở trang câu hỏi này →
A2, 1, 4, 3, 7, 8, 6
B2, 1, 4, 3, 7, 6, 8
C4, 2, 7, 1, 3, 6, 8
D2, 1, 4, 3, 6, 7, 8
Lời giải
Đáp án đúng: "4, 2, 7, 1, 3, 6, 8". Xoá bằng sao chép nghĩa là chép khoá liền trước nút bị xoá theo thứ tự giữa, tức nút phải nhất của cây con trái, rồi xoá chính nút nguồn đó. Cây con trái của 5 là 2 với con phải 4, mà 4 không có con phải nên 4 là khoá liền trước; chép 4 lên gốc rồi bỏ nút 4, con trái 3 của nó nối lên làm con phải của 2. Cây còn lại có gốc 4, con trái 2 với hai con 1 và 3, con phải 7 với hai con 6 và 8, nên duyệt theo bề rộng cho 4, rồi 2 và 7, rồi 1, 3, 6, 8. "2, 1, 4, 3, 7, 6, 8" sai vì đó là kết quả của xoá bằng hợp nhất, khi 2 lên gốc và cây con phải 7 được treo dưới nút phải nhất là 4. "2, 1, 4, 3, 7, 8, 6" sai vì ngoài việc dùng cách hợp nhất nó còn in 8 trước 6 ở mức cuối. "2, 1, 4, 3, 6, 7, 8" sai vì nó đưa 6 lên cùng mức với cha của nó là 7, mà duyệt theo mức không bao giờ in con trước cha.
Mở trang câu hỏi này →
Avoid preOrder(Node p) { if (p != null) { visit(p); preOrder(p.left); preOrder(p.right); } }
Bvoid preOrder(Node p) { if (p != null) { preOrder(p.left); visit(p); preOrder(p.right); } }
Cvoid preOrder(Node p) { if (p == null) { visit(p); preOrder(p.left); preOrder(p.right); } }
Dvoid preOrder(Node p) { visit(p); preOrder(p.left); preOrder(p.right); }
Lời giải

Đáp án đúng: "

Lời giải
void preOrder(Node p) {
  if (p != null) {
    visit(p);
    preOrder(p.left);
    preOrder(p.right);
  }
}

". Tiền thứ tự nghĩa là thăm gốc trước rồi mới xuống nhánh trái, sau đó nhánh phải, nên lệnh thăm phải đứng trước cả hai lời gọi đệ quy; thêm vào đó điều kiện p khác null chính là chỗ dừng, nó chặn lời gọi đi vào cây rỗng. Cách viết "

Lời giải
void preOrder(Node p) {
  if (p != null) {
    preOrder(p.left);
    visit(p);
    preOrder(p.right);
  }
}

" đặt lệnh thăm giữa hai lời gọi nên cho ra thứ tự trung tố, với cây tìm kiếm thì in dãy tăng dần chứ không phải tiền thứ tự. Cách viết "

Lời giải
void preOrder(Node p) {
  if (p == null) {
    visit(p);
    preOrder(p.left);
    preOrder(p.right);
  }
}

" đảo điều kiện thành p bằng null, tức chỉ làm việc khi con trỏ rỗng, nên nó thăm một nút không tồn tại và không bao giờ đi xuống cây thật. Cách viết "

Lời giải
void preOrder(Node p) {
  visit(p);
  preOrder(p.left);
  preOrder(p.right);
}

" đúng trật tự thăm nhưng bỏ hẳn chỗ dừng, mỗi lá vẫn gọi tiếp vào hai con rỗng nên đệ quy lún vô hạn và chương trình đổ vì truy cập trên con trỏ rỗng.

Mở trang câu hỏi này →
A1, 3, 4, 7, 5, 2, 8, 6
B7, 4, 3, 5, 1, 2, 8, 6
C1, 3, 4, 7, 5, 2, 6, 8
D7, 4, 5, 3, 8, 6, 2, 1
Lời giải
Đáp án đúng: "1, 3, 4, 7, 5, 2, 6, 8". Cây có gốc 1 với con trái 3 và con phải 2; nút 3 có con trái 4 và con phải 5; nút 4 có con trái 7; nút 2 chỉ có con phải 6; nút 6 có con trái 8. Duyệt trước in gốc rồi vét hết nhánh trái mới sang nhánh phải: 1, 3, 4, 7, rồi 5 là con phải của 3; sang nhánh phải của gốc được 2, 6, rồi 8 là con trái của 6. "7, 4, 3, 5, 1, 2, 8, 6" là dãy duyệt giữa, nhận ra vì gốc 1 nằm giữa hai nhánh. "7, 4, 5, 3, 8, 6, 2, 1" là dãy duyệt sau, gốc 1 đứng cuối cùng. "1, 3, 4, 7, 5, 2, 8, 6" chỉ khác đáp án ở hai số cuối: nó in 8 trước 6, nhưng 8 là con trái của 6 nên trong duyệt trước cha 6 phải ra trước.
Mở trang câu hỏi này →
A4, 2, 7, 5, 1, 8, 6, 3
B4, 2, 7, 5, 1, 3, 8, 6
C4, 7, 5, 2, 8, 6, 3, 1
D4, 2, 5, 7, 1, 8, 6, 3
Lời giải
Đáp án đúng: "4, 2, 7, 5, 1, 3, 8, 6". Duyệt giữa luôn theo trình tự con trái, gốc, con 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). Nhánh trái: in 4 trước, rồi 2, rồi vào 5 phải xuống 7 trước nên in 7 rồi 5, được 4, 2, 7, 5. Thăm gốc 1. Nhánh phải: 3 không có con trái nên in 3 ngay, rồi vào 6 phải xuống 8 trước nên in 8 rồi 6, được 3, 8, 6. "4, 2, 7, 5, 1, 8, 6, 3" đẩy 3 xuống sau cả 8 và 6, đó là cách duyệt sau xử lý nhánh phải, còn duyệt giữa phải thăm 3 trước con phải của nó. "4, 7, 5, 2, 8, 6, 3, 1" là kết quả duyệt sau, nhận ra vì gốc 1 đứng cuối. "4, 2, 5, 7, 1, 8, 6, 3" in 5 trước con trái 7 của nó, tức làm theo thứ tự gốc rồi con trái.
Mở trang câu hỏi này →
A5, 1, 7, 2, 6, 8, 4
B5, 1, 7, 6, 8, 2, 4
C5, 2, 7, 1, 6, 8, 4
D5, 2, 7, 1, 4, 6, 8
Lời giải
Đáp án đúng: "5, 1, 7, 2, 6, 8, 4". Cây ban đầu có gốc 5, bên trái là 3 với hai con 1 và 4 trong đó 1 chỉ có con phải 2, bên phải là 7 với hai con 6 và 8. Xoá bằng cách nối là tìm nút phải nhất của cây con trái của nút bị xoá, treo cây con phải của nút bị xoá vào đó, rồi đưa cây con trái lên thay chỗ: cây con trái của 3 là 1, đi phải hết cỡ được 2, nên nút 4 trở thành con phải của 2, rồi 1 lên làm con trái của 5. Cây mới có 5 với hai con 1 và 7; 1 có con phải 2; 2 có con phải 4; 7 có hai con 6 và 8. Duyệt bề rộng cho 5, rồi 1 và 7, rồi 2, 6, 8, rồi 4. Vì vậy "5, 1, 7, 6, 8, 2, 4" sai vì 2 là con của 1 nên phải ra khỏi hàng đợi trước các con của 7; "5, 2, 7, 1, 4, 6, 8" sai vì đó là kết quả của phép xoá bằng cách sao chép, nó kéo giá trị 2 lên chỗ nút 3 rồi cắt nút 2; "5, 2, 7, 1, 6, 8, 4" sai vì nó vừa đưa 2 lên làm con trái của 5 vừa treo 4 xuống dưới nút 1, không khớp bước nào của phép nối.
Mở trang câu hỏi này →
A6, 1, 7, 2, 8, 5, 4
B6, 2, 8, 1, 4, 7, 5
C6, 1, 8, 2, 7, 4, 5
D6, 2, 7, 1, 4, 8, 5
Lời giải
Đáp án đúng: "6, 2, 8, 1, 4, 7, 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 8 với con trái 7. Xoá 3 bằng cách sao chép thì lấy nút cực phải của nhánh trái của 3: đi từ 1 sang 2, mà 2 không có con phải nên 2 là tiền nhiệm trung tố; gán 2 vào chỗ của 3 rồi tháo nút 2 cũ, vì 2 là lá nên con phải của 1 thành rỗng. Cây mới có gốc 6, nhánh trái 2 với hai con 1 và 4, dưới 4 vẫn là 5, nhánh phải vẫn là 8 với con trái 7. Duyệt theo chiều rộng cho 6, rồi 2 và 8, rồi 1, 4, 7, rồi 5. Dãy "6, 1, 8, 2, 7, 4, 5" là kết quả xoá bằng cách nối, khi 1 lên thế chỗ 3 và nhánh của 4 treo xuống dưới 2. Dãy "6, 2, 7, 1, 4, 8, 5" đưa 7 lên mức hai, nhưng 7 là con trái của 8 nên 8 vẫn giữ vai con phải của gốc. Dãy "6, 1, 7, 2, 8, 5, 4" vừa nhầm nút thay thế vừa xếp 5 trước 4, dù 4 là cha của 5 nên nằm cạn hơn một mức.
Mở trang câu hỏi này →
AN
Bn-1
Cn+1
D2n
Lời giải
Đáp án đúng: "N". Muốn một đồ thị gắn cả n đỉnh vào một khối thì cần ít nhất n − 1 cạnh, và khi đúng n − 1 cạnh thì nó là cây, mà cây không có chu trình vì giữa hai đỉnh chỉ tồn tại duy nhất một đường đi. Thêm đúng một cạnh nữa, tổng n cạnh, là đủ để đóng một chu trình: chẳng hạn lấy một cây rồi nối hai lá lại với nhau. Vậy n là con số nhỏ nhất. Phương án "n-1" là số cạnh của cây khung, tức mức vừa đủ để nối hết đỉnh mà vẫn chưa có chu trình nào. Phương án "n+1" đủ tạo chu trình nhưng dư một cạnh so với mức cần, nó ứng với đồ thị đã có hai chu trình độc lập hoặc một cạnh thừa. Phương án "2n" dư nhiều hơn nữa, gấp đôi số đỉnh, trong khi n cạnh đã đóng được chu trình nên câu hỏi về mức tối thiểu không thể nhận con số ấy.
Mở trang câu hỏi này →
AC, B, D, F, A, E, G
BC, B, D, A, E, F, G, H
CC, B, D, F, A, E, G, H
DC, B, D, A, E, F, H, G
Lời giải
Đáp án đúng: "C, B, D, F, A, E, G". Duyệt theo bề rộng từ C: thăm C, đưa các đỉnh kề của C theo thứ tự chữ cái vào hàng đợi là B, D, F. Lấy B thì thêm A và E (C, D đã biết); lấy D thì không có đỉnh mới vì B, C, F đã vào; lấy F thì thêm G. Các đỉnh còn lại trong hàng đợi A, E, G không mở ra đỉnh mới, vậy thứ tự thăm là C, B, D, F, A, E, G. Đỉnh H không có cạnh nào nên không bao giờ tới được từ C, phép duyệt một nguồn chỉ phủ thành phần liên thông chứa nguồn. "C, B, D, F, A, E, G, H" sai vì nó gắn thêm H vào dù không có đường nào từ C tới H. "C, B, D, A, E, F, G, H" sai vì vừa thêm H, vừa đẩy F xuống sau A và E dù F kề thẳng C nên thuộc mức một. "C, B, D, A, E, F, H, G" sai vì mắc cả hai lỗi trên và còn đảo thứ tự hai đỉnh cuối.
Mở trang câu hỏi này →