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ố 3

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 đề.

Danh sách câu hỏi

20/50 câuCòn 30
1Consider the following function:4 lựa chọncó code
Đề bài
void fun(int n)
   {if(n > 0)
     {System.out.print(" " + n );
      fun(n-2);
     }
   }

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

A1 3 5 7 9
B9 7 5 3
C9 7 5 3 1
D7 5 3 1
Lời giải
Đáp án đúng: "9 7 5 3 1". Thân hàm in giá trị n rồi mới gọi lại chính nó với n-2, nên mỗi lần in xảy ra trước khi lún sâu thêm một tầng: fun(9) in 9 rồi gọi fun(7), fun(7) in 7 rồi gọi fun(5), tiếp tục in 5, in 3, in 1, và tới fun(-1) thì điều kiện n lớn hơn 0 không còn đúng nên dừng mà không in gì. Vậy màn hình nhận đủ năm số lẻ giảm dần từ 9 tới 1. Dãy "1 3 5 7 9" là thứ tự ngược lại, nó ứng với việc đặt lệnh in sau lời gọi fun(n-2) để mỗi tầng chỉ in lúc quay về. Dãy "9 7 5 3" dừng sớm một bước, tức điều kiện là n lớn hơn 1 chứ không phải n lớn hơn 0, nên mất lần in 1. Dãy "7 5 3 1" thiếu số 9 ở đầu, như thể tầng đầu tiên chỉ gọi tiếp mà không in, trong khi fun(9) in ngay 9 trước đã.
Mở trang câu hỏi này →
AMulti-programming.
BEvaluating arithmetic expressions.
CUndo sequence in a text editor.
DKeeping track of local variables at run time.
Lời giải
Đáp án đúng: "Multi-programming.". Đa chương trình là bài toán của hệ điều hành: nhiều tiến trình cùng chờ CPU và được chọn theo lát thời gian hoặc theo độ ưu tiên, nên cấu trúc phù hợp là hàng đợi hoặc hàng đợi ưu tiên với kỷ luật vào trước ra trước, trái hẳn với kỷ luật vào sau ra trước của ngăn xếp; điều phối theo kiểu ngăn xếp sẽ bỏ đói tiến trình đến sớm nhất. "Evaluating arithmetic expressions." đúng là việc của ngăn xếp: đổi trung tố sang hậu tố cần một ngăn xếp toán tử để so độ ưu tiên, còn tính biểu thức hậu tố cần ngăn xếp toán hạng, lấy hai phần tử trên đỉnh mỗi khi gặp toán tử. "Undo sequence in a text editor." cũng vậy: thao tác vừa làm phải được hoàn tác trước nhất, đúng thứ tự vào sau ra trước. "Keeping track of local variables at run time." chính là mô tả của ngăn xếp lời gọi: mỗi lần gọi hàm đẩy thêm một khung chứa biến cục bộ, hàm trả về thì lấy khung trên đỉnh ra.
Mở trang câu hỏi này →
3Consider the following function:4 lựa chọncó code
Đề bài
void fun(int n)
  {int m = n/2;
   int k = n%2;
   if (m > 0)
    {fun(m);
    }
   System.out.print(k + " ");
  }

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

A1 0 0 1
B1 0 1 1
C1 0 1 0
D1 1 0 1
Lời giải
Đáp án đúng: "1 0 1 1". Hàm gọi đệ quy TRƯỚC khi in, nên các chữ số dư được in theo thứ tự ngược với lúc sinh ra, đúng bằng cách đổi 11 sang hệ hai. Chạy tay: fun(11) có m = 11/2 = 5 và k = 11%2 = 1, m lớn hơn 0 nên gọi fun(5); fun(5) có m = 2, k = 1, gọi fun(2); fun(2) có m = 1, k = 0, gọi fun(1); fun(1) có m = 0, k = 1, m không lớn hơn 0 nên dừng rồi in 1. Khi các lời gọi lần lượt trở về, màn hình nhận thêm 0 của fun(2), rồi 1 của fun(5), rồi 1 của fun(11), cho dãy 1 0 1 1 — chính là biểu diễn hệ hai của 11. "1 1 0 1" là dãy dư theo chiều sinh ra, chỉ xảy ra nếu đặt lệnh in trước lời gọi đệ quy. "1 0 0 1" là hệ hai của 9 và "1 0 1 0" là hệ hai của 10, đều không khớp với 11.
Mở trang câu hỏi này →
A85
B80
C81
D84
Lời giải
Đáp án đúng: "84". Phép băm gấp biên chia khoá 44-65-76-8 thành bốn nhóm 44, 65, 76 và 8 rồi lật ngược chữ số của các nhóm xen kẽ trước khi cộng, vì mép giấy bị gập phải đọc theo chiều ngược: 44 giữ nguyên, 65 lật thành 56, 76 giữ nguyên, 8 chỉ một chữ số nên không đổi; tổng 44 + 56 + 76 + 8 = 184 và 184 chia 100 dư 84. So sánh cho rõ: gấp dịch không lật nhóm nào, cộng thẳng 44 + 65 + 76 + 8 = 193 và cho 93. Vì vậy "85" sai vì nó đòi tổng 185, "80" sai vì nó đòi tổng 180, còn "81" sai vì nó đòi tổng 181; mà mọi cách lật của bốn nhóm này chỉ sinh được các tổng 175, 184 hoặc 193, tức số dư chỉ có thể là 75, 84 hoặc 93.
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 11 6 4 30 8 2
B7 11 6 30 9 8 2
C7 11 6 4 30 9 2
D7 11 4 30 9 8 2
E11 6 4 30 9 8 2
Lời giải
Đáp án đúng: "7 11 6 4 30 8 2". Đoạn mã chỉ nối lại con trỏ chứ không cấp phát nút mới: p trỏ vào nút 30 nên p1 = p.next là nút 9 và p2 = p1.next là nút 8; lệnh p.next = p2 cho nút 30 trỏ thẳng sang 8, còn p2.prev = p cho 8 quay lại 30, nên nút 9 không còn ai trỏ tới và rơi khỏi danh sách, để lại 7 11 6 4 30 8 2. Dãy "7 11 6 30 9 8 2" xoá nút 4 đứng trước 30, muốn vậy phải sửa p.prev chứ không phải p.next. Dãy "7 11 6 4 30 9 2" xoá nút 8, tức bỏ chính p2, muốn vậy phải gán p1.next = p2.next. Dãy "7 11 4 30 9 8 2" xoá nút 6, cách 30 hai bước về phía đầu, vùng mà đoạn mã không hề chạm tới. Dãy "11 6 4 30 9 8 2" xoá nút đầu 7, muốn vậy phải dịch chính biến head.
Mở trang câu hỏi này →
6Consider 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(-3)?

A5
B12
C2
D4
E10
Lời giải
Đáp án đúng: "2". Lời gọi fun(-3) rơi vào nhánh n < 0 nên hàm tự gọi lại với -(-3) = 3; ở lời gọi thứ hai n = 3 thoả điều kiện n < 5 nên hàm trả về ngay hằng 2 và dãy đệ quy dừng, không bao giờ chạm tới nhánh lấy n nhân với fun(n/2). Giá trị 2 ra tới ngoài nguyên vẹn vì nhánh n < 0 chỉ viết return(fun(-n)) chứ không nhân hay cộng thêm gì. Phương án "12" ứng với việc tưởng nhánh cuối được dùng, kiểu lấy 3 nhân fun(1) rồi còn nhân tiếp, nhưng với n = 3 thì điều kiện n < 5 đã chặn trước khi tới đó. Phương án "4" ứng với việc cộng dồn hai lần giá trị dừng 2, trong khi mỗi lời gọi chỉ trả về một lần. Phương án "5" là chính ngưỡng dừng n < 5 bị chép lại thành kết quả, còn hàm thì trả về hằng 2 chứ không trả về ngưỡng. Phương án "10" là 5 nhân 2, tức lấy ngưỡng nhân với giá trị cơ sở, một phép tính không có trong mã. Bẫy của câu này nằm ở dấu âm: hàm đổi dấu trước rồi mới so sánh, nên fun(-3) và fun(3) cho cùng một kết quả.
Mở trang câu hỏi này →
7Consider the following function:4 lựa chọncó code
Đề bài
void fun(int n)
   {System.out.print(" " + n % 5);
     fun(n/3);
   }

What will happen if the statement fun(21); is run?

AThe operating system detects the infinite recursion because of the "repeated state"
BThe run-time stack overflows, halting the program
CThe program keeps running until you press Ctrl-C
DThe results are nondeterministic
Lời giải
Đáp án đúng: "The run-time stack overflows, halting the program". Hàm fun không có nhánh dừng nào: với n = 21 nó in 21%5 = 1 rồi gọi fun(7) in 2, gọi fun(2) in 2, rồi gọi fun(0); từ đó 0/3 vẫn bằng 0 nên fun(0) tự gọi fun(0) mãi mãi, mỗi lời gọi chiếm thêm một khung trên ngăn xếp cho tới khi máy ảo hết vùng ngăn xếp, ném StackOverflowError và chương trình dừng. Phương án "The operating system detects the infinite recursion because of the 'repeated state'" sai vì không hệ điều hành nào theo dõi việc tham số lặp lại trạng thái; máy ảo chỉ biết ngăn xếp đã chạm giới hạn chứ không nhận ra n đứng mãi ở 0. "The program keeps running until you press Ctrl-C" sai vì chương trình tự chết do tràn ngăn xếp sau hữu hạn lời gọi, không cần người dùng ngắt. "The results are nondeterministic" sai vì cả dãy in ra lẫn thời điểm vỡ đều xác định: cùng một giới hạn ngăn xếp luôn cho cùng một kết quả.
Mở trang câu hỏi này →
Đề bài
while(S is not empty)

{ch = top element of the stack S if ch is isolated then remove it from the stack and put it to E

Đề bài
else

select the first vertex Y (by alphabet order), which is adjacent to ch,push Y to S and remove the edge (ch,Y) from the graph

Đề bài
}

the last array E obtained is an Euler cycle of the graph Suppose a multigraph G is given below (view picture). Which of the followings is the Euler cycle from the vertex B, created by above algorithm?

AB, A, B, D, C, B
BB, A, B, D, C
CB, D, C, B, A, B
DB, A, B, C, D, B
Lời giải
Đáp án đúng: "B, D, C, B, A, B". Đồ thị có hai cạnh song song giữa A với đỉnh B, thêm cạnh B–C, cạnh B–D, cạnh C–D, tổng 5 cạnh và mọi đỉnh đều bậc chẵn. Chạy từ B, mỗi bước lấy đỉnh trên đỉnh ngăn xếp, chọn láng giềng đầu theo thứ tự chữ cái rồi xoá cạnh vừa dùng, nên thứ tự đẩy vào ngăn xếp đúng là "B, A, B, C, D, B": B sang A, A trở về B, B sang C, C sang D, D trở về B, lúc đó 5 cạnh đã hết. Sau đó các đỉnh lần lượt thành cô lập và bị lấy ra để nối vào mảng kết quả, vì vậy mảng Euler là dãy đẩy vào đọc ngược. Chính vì thế "B, A, B, C, D, B" là thứ tự vào ngăn xếp chứ không phải mảng mà thuật toán trả về. Dãy "B, A, B, D, C, B" chỉ xuất hiện nếu ở lần quay lại B thuật toán chọn D trước C, trái luật lấy láng giềng nhỏ nhất theo chữ cái. Dãy "B, A, B, D, C" liệt kê 5 đỉnh và không kết thúc ở B, mà một chu trình qua 5 cạnh phải gồm 6 đỉnh với đỉnh đầu trùng đỉnh cuối.
Mở trang câu hỏi này →
Đề bài
int x = 17;
Node q = new Node(x);
q.prev=null;
q.next = head;
head.prev = q;
head = q;
A7 11 6 4 32 13 8 2 17
B7 11 6 4 32 13 8 17 2
C7 11 6 4 32 13 17 8 2
D7 17 11 6 4 32 13 8 2
E17 7 11 6 4 32 13 8 2
Lời giải
Đáp án đúng: "17 7 11 6 4 32 13 8 2". Bốn lệnh cuối chỉ chạm vào đầu danh sách: q.prev=null và q.next=head cho nút mới trỏ tới nút 7 đang đứng đầu, head.prev=q nối lại chiều ngược, rồi head=q đưa chính nút 17 lên làm nút đầu; tham chiếu p tới nút 13 không được dùng lần nào nên khúc giữa giữ nguyên. "7 11 6 4 32 13 8 2 17" là kết quả của phép thêm vào cuối, muốn vậy phải đi tới tail và gán tail.next, đoạn mã không làm thế. "7 11 6 4 32 13 8 17 2" đặt 17 vào giữa 8 và 2, cần một tham chiếu tới nút 8 hoặc nút 2 mà mã không có. "7 11 6 4 32 13 17 8 2" là chèn ngay sau nút 13, tức phải gán q.next=p.next rồi p.next=q, trong khi mã lại gán q.next=head. "7 17 11 6 4 32 13 8 2" là chèn sau nút đầu, cần head.next trong hai phép gán thay vì head.
Mở trang câu hỏi này →
10Consider 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<10)
      System.out.println(n);
        else
        {fun(n/10);
         System.out.println(n%10);
        }
  }

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

An < 0
Bn < 10
Cn >= 0 && n<10
Dn > = 10
Lời giải
Đáp án đúng: "n >= 0 && n<10". Trường hợp dừng là nhánh không còn gọi lại chính nó, ở đây chỉ có nhánh else if(n<10) in ngay n rồi kết thúc. Nhưng nhánh đó chỉ được xét sau khi điều kiện n < 0 đã sai, nghĩa là n đang không âm, nên tập giá trị được xử lý trực tiếp là các n thoả cả hai điều kiện: không nhỏ hơn 0 và nhỏ hơn 10, tức các số một chữ số. "n < 0" không phải điểm dừng, vì thân nhánh ấy in dấu trừ rồi gọi tiếp fun(-n), vẫn là bước đệ quy. "n < 10" bỏ qua việc các số âm đã bị nhánh đầu chặn lại, nên nó gộp cả số âm vào trường hợp dừng dù số âm phải đi qua một lời gọi nữa. "n > = 10" là nhánh else cuối, nơi hàm gọi fun(n/10) rồi in n%10, tức nhánh sinh đệ quy chứ không phải nhánh kết thúc.
Mở trang câu hỏi này →
A88
B90
C91
D86
Lời giải
Đáp án đúng: "88". Khoá 45-65-79-8 được tách thành bốn nhóm 45, 65, 79 và 8; phép gấp biên lật chữ số của các nhóm xen kẽ rồi mới cộng: 45 giữ nguyên, 65 lật thành 56, 79 giữ nguyên, 8 một chữ số nên không đổi, tổng 45 + 56 + 79 + 8 = 188 và 188 chia 100 dư 88. Gấp dịch thì khác, nó cộng thẳng 45 + 65 + 79 + 8 = 197 và cho 97, nên phải đọc đúng tên phép băm trước khi tính. Vì vậy "90" sai vì nó đòi tổng 190, "91" sai vì nó đòi tổng 191, còn "86" sai vì nó đòi tổng 186; liệt kê mọi cách lật của bốn nhóm này chỉ có các tổng 188, 197, 206, 215 và 224, không có tổng nào kết thúc bằng 90, 91 hay 86.
Mở trang câu hỏi này →
ABoth best and worst cases are O(n^2)
BThe best case is O(n), and the worst case is O(n^2)
CThe best case is O(n), and the worst case is O(nlogn)
DThe best case is O(nlogn), and the worst case is O(n^2)
Lời giải
Đáp án đúng: "The best case is O(n), and the worst case is O(n^2)". Bubble sort chuẩn có cờ đánh dấu đã xảy ra đổi chỗ hay chưa: với mảng đã sắp sẵn, lượt quét đầu làm n-1 phép so sánh mà không đổi chỗ lần nào nên thuật toán dừng ngay, cho O(n); với mảng sắp ngược, mỗi lượt chỉ đưa được một phần tử về chỗ nên phải chạy n-1 lượt với tổng khoảng n(n-1)/2 phép so sánh và đổi chỗ, cho O(n^2). Phương án "Both best and worst cases are O(n^2)" chỉ đúng với bản viết không kiểm cờ đổi chỗ, tức luôn chạy đủ n-1 lượt bất kể dữ liệu, điều kiện mà câu hỏi không nêu. Phương án "The best case is O(n), and the worst case is O(nlogn)" sai ở trường hợp xấu: thuật toán chỉ so sánh các cặp kề nhau nên không có cách nào hạ xuống nlogn. Phương án "The best case is O(nlogn), and the worst case is O(n^2)" sai ở trường hợp tốt: một lượt quét sạch đã đủ kết luận, tốn đúng n-1 phép so sánh.
Mở trang câu hỏi này →
AO(n^2)
BO(n)
CO(log n)
DO(1)
Lời giải
Đáp án đúng: "O(n)". Danh sách liên kết đơn chỉ cho phép đi từ một nút sang nút kế tiếp qua con trỏ next, không có phép tính địa chỉ như mảng, nên muốn tới phần tử ở giữa phải xuất phát từ head và nhảy khoảng n/2 lần; chi phí n/2 bước tỉ lệ thuận với n, tức O(n). Phương án "O(1)" chỉ đúng với mảng hoặc cấu trúc có truy cập ngẫu nhiên, vì ở đó địa chỉ phần tử thứ i tính được bằng một phép nhân và một phép cộng; danh sách liên kết không lưu gì cho phép tính như vậy. Phương án "O(log n)" là chi phí của tìm nhị phân hay của việc đi trên cây cân bằng, cả hai đòi hỏi nhảy thẳng vào giữa đoạn trong một bước, điều mà con trỏ next không làm được, và cũng chính vì thế không thể tìm nhị phân trên danh sách liên kết. Phương án "O(n^2)" cao hơn hẳn thực tế: ta chỉ đi một lượt qua nửa danh sách, không có vòng lặp nào lồng trong vòng lặp.
Mở trang câu hỏi này →
A36
B37
C35
D39
Lời giải
Đáp án đúng: "37". Shift folding cắt khoá thành các nhóm rồi cộng thẳng các nhóm lại, không đảo nhóm nào, sau đó lấy phần dư với kích thước bảng: K = 43-35-59 cho 43 + 35 + 59 = 137, nên h(K) = 137 % 100 = 37, nằm đúng trong vùng chỉ số hợp lệ 0 đến 99. Với TSize = 100, mẹo kiểm tra nhanh là chỉ cần đọc hai chữ số cuối của tổng ba nhóm. "35" sai vì đó là nhóm giữa được chép lại nguyên vẹn, tức bỏ hẳn bước cộng ba nhóm vốn là trọng tâm của phép gấp. "36" sai vì muốn ra 36 thì tổng ba nhóm phải là 136 hoặc 36, trong khi ba nhóm của khoá này cộng lại đúng bằng 137. "39" sai vì nó ứng với tổng 139, nhiều hơn tổng thật hai đơn vị, thường xuất hiện khi cộng nhầm một nhóm.
Mở trang câu hỏi này →
A2, 3, 5, 11, 10, 8, 12, 16, 8, 6
B2, 5, 16, 11, 10, 8, 12, 3, 8, 6
C2, 5, 11, 10, 8, 12, 3, 8, 6, 16
D2, 3, 16, 11, 10, 8, 12, 5, 8, 6
Lời giải
Đáp án đúng: "2, 5, 16, 11, 10, 8, 12, 3, 8, 6". Sắp xếp chèn giữ một đoạn đầu đã có thứ tự rồi mỗi bước lấy phần tử kế tiếp chèn vào đúng chỗ trong đoạn đó, các phần tử phía sau không bị động tới. Bước thứ nhất lấy 5 chèn vào đoạn chỉ có 16, cho 5, 16; bước thứ hai lấy 2 chèn vào đoạn 5, 16, cho 2, 5, 16, nên bảy phần tử cuối vẫn y nguyên như lúc đầu. Dãy "2, 3, 16, 11, 10, 8, 12, 5, 8, 6" là trạng thái sau hai lượt sắp xếp chọn, tức đổi chỗ 2 với 16 rồi đổi chỗ 3 với 5, vì thế 5 bị bắn về chỗ của 3. Dãy "2, 3, 5, 11, 10, 8, 12, 16, 8, 6" là sau ba lượt sắp xếp chọn, đã đưa cả 2, 3, 5 về đầu và đẩy 16 vào giữa mảng, đi xa hơn hẳn hai bước được hỏi. Dãy "2, 5, 11, 10, 8, 12, 3, 8, 6, 16" mang 16 ra hẳn cuối mảng, đó là dấu vết của một lượt nổi bọt, còn phép chèn không hề dồn phần tử lớn nhất về cuối chỉ sau hai bước.
Mở trang câu hỏi này →
A001
B100
C101
D111
Lời giải
Đáp án đúng: "101". Huffman luôn gộp hai tần số nhỏ nhất: D 15 phần trăm với E 5 phần trăm thành nút 20, nút nặng hơn đứng bên trái nên D nhận nhánh 0 và E nhận nhánh 1. Hai nhỏ nhất kế tiếp là C 19 và nút 20, gộp thành 39 với nút 20 bên trái, C bên phải. Rồi B 25 với A 36 thành nút 61, A bên trái, B bên phải. Cuối cùng 61 và 39 thành gốc 100, nhánh 0 về phía 61 vì nó nặng hơn, nhánh 1 về phía 39. Đường đi từ gốc tới E vì vậy là 1 rồi 0 rồi 1. "001" chỉ xuất hiện nếu nhánh chứa D và E bị treo bên trái của gốc, trái với quy ước nhánh nặng hơn nằm bên trái. "100" đúng là mã của D, tức nhầm nhánh ở bước tách D với E. "111" không ứng với đường đi nào: sau hai nhánh 1 ta đã tới lá C nên không còn nhánh nào để đi bit thứ ba, mã của C chỉ dài hai bit.
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 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***g" ?

AgMoG
BgMoo
CGoMg
DgMor
Lời giải
Đáp án đúng: "gMoG". Mỗi dấu sao lấy bỏ một ký tự ở đỉnh ngăn xếp mà không in, các ký tự khác được đẩy vào; vòng cuối lấy ra lần lượt nên in theo thứ tự ngược với lúc nạp. Chạy tay theo đúng thứ tự ký tự của từ: nạp G, o, o, d rồi hai dấu sao lấy bỏ d và o, còn G, o; nạp M, o, r, n rồi hai dấu sao bỏ n và r, còn G, o, M, o; nạp i, n rồi ba dấu sao bỏ n, i và o, còn G, o, M; nạp g thành G, o, M, g. Vòng xả cho g, M, o, G. "gMoo" giả định ba dấu sao liền nhau chỉ lấy bỏ hai ký tự nên chữ o đẩy vào sau M vẫn còn; đếm đủ thì nó đã bị lấy. "gMor" giữ lại r, nhưng r đã bị dấu sao thứ tư lấy bỏ từ trước. "GoMg" chính là thứ tự nạp vào, trong khi ngăn xếp xả ra theo chiều vào sau ra trước.
Mở trang câu hỏi này →
A3, 5, 9, 8, 1, 0, 2, 6, 4, 10
B3, 5, 9, 1, 8, 0, 2, 6, 4, 10
C3, 5, 9, 1, 8, 0, 2, 4, 6, 10
D3, 5, 9, 0, 1, 8, 2, 6, 4, 10
Lời giải
Đáp án đúng: "3, 5, 9, 1, 8, 0, 2, 6, 4, 10". Một lượt của vòng for i = 0 đến n-2 chỉ so từng cặp kề nhau đúng một lần từ đầu tới cuối, nên tác dụng duy nhất là đẩy phần tử lớn nhất về cuối. Chạy tay trên 5, 3, 9, 10, 1, 8, 0, 2, 6, 4: cặp 5 và 3 đổi cho 3, 5; 5 với 9 rồi 9 với 10 đều đúng thứ tự nên giữ nguyên; từ đó 10 là phần tử đang được mang đi và lần lượt đổi với 1, 8, 0, 2, 6, 4 nên trôi hẳn về cuối, mỗi phần tử bị 10 vượt qua chỉ dịch trái đúng một ô. Vì vậy "3, 5, 9, 8, 1, 0, 2, 6, 4, 10" sai vì nó đổi 1 với 8 dù 1 nhỏ hơn 8; "3, 5, 9, 1, 8, 0, 2, 4, 6, 10" sai vì nó đổi thêm 6 với 4, nhưng khi 10 đã vượt qua 6 thì chỉ số i đã đi quá cặp đó và một lượt không quay lại; "3, 5, 9, 0, 1, 8, 2, 6, 4, 10" sai vì 0 nhảy trái hai ô, trong khi một lượt chỉ kéo được một phần tử nhỏ sang trái đúng một ô.
Mở trang câu hỏi này →
A7
B9
C6
D8
Lời giải
Đáp án đúng: "8". Gốc tính là mức 1 nên cây cao 4 có bốn mức; định nghĩa đòi các mức 1, 2, 3 phải đầy, cho 1 + 2 + 4 = 7 nút, và mức 4 phải có ít nhất một lá, nếu không cây chỉ cao 3. Vậy số nút ít nhất là 7 + 1 = 8, với lá duy nhất của mức cuối nằm sát bên trái. Con số "7" là tổng của ba mức đầy nhưng mức 4 rỗng, tức cây cao 3 chứ không phải 4. Con số "9" ứng với hai lá ở mức cuối, vẫn hợp lệ nhưng chưa ít nhất vì bớt một lá cây vẫn còn cao 4. Con số "6" không đủ cho ba mức đầu đầy, mức 3 sẽ thiếu nút nên vi phạm điều kiện đầy ở mọi mức trước mức cuối.
Mở trang câu hỏi này →
20Consider the following function:4 lựa chọncó code
Đề bài
void fun(int n)
   {int m = n/2;
    int k = n%2;
    System.out.print(k + " ");
    if (m > 0)
     {fun(m);
     }
   }

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

A0 0 1 1
B1 0 1 0
C1 1 0 0
D1 0 1 1
Lời giải
Đáp án đúng: "0 0 1 1". Hàm tính m = n/2 theo phép chia nguyên và k = n%2, in k TRƯỚC rồi mới gọi đệ quy khi m > 0, nên các chữ số hiện ra theo chiều từ bit thấp lên bit cao. Chạy fun(12): m = 6, k = 0 nên in 0; fun(6): m = 3, k = 0 nên in 0; fun(3): m = 1, k = 1 nên in 1; fun(1): m = 0, k = 1 nên in 1 rồi m = 0 nên dừng. Dãy in ra là 0 0 1 1. Phương án "1 1 0 0" chính là biểu diễn nhị phân 1100 của 12 đọc theo chiều quen thuộc từ bit cao, tức kết quả nếu lệnh in được đặt SAU lời gọi đệ quy; ở đây in đứng trước nên thứ tự đảo lại. Phương án "1 0 1 0" là dãy số dư của 10 chứ không của 12. Phương án "1 0 1 1" đòi số dư đầu tiên của 12 phải là 1, nhưng 12 chẵn nên 12%2 = 0. Vị trí của lệnh in so với lời gọi đệ quy là điều quyết định ở đây, không phải phép chia.
Mở trang câu hỏi này →