Đây là một đề có 8 câu, mà các ý của nó liên quan đến đề tuyển sinh cao học năm 2011. Đề nghị các members tập làm thành thạo trước khi thi nha.

Câu 1: Danh sách X được tổ chức bởi cấu trúc:
List = ^Element;
Element = Record
          d: Data;
          Next : List;
          End;
Cho danh sách P và Q. Hãy viết thủ tục để:
a. Xóa nút đứng cuối cùng trong danh sách P.
b. Nối danh sách Q vào sau danh sách P.

Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố.Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4

Câu 3: Văn bản T chứa các ký tự a, b, c, d , e , f , g , h, m , n với tần suất xuất hiện: 0.18, 0.06, 0.12, 0.14, 0.08, 0.05, 0.07, 0.12, 0.08, 0,10. Xây dựng bộ mã Huffman cho T. Vẽ cây nhị phân tương ứng. Tính hiệu suất.

Câu 4: Văn bản T chứa n ký tự K(1), K(2)...K(n) có tần suất xuất hiện T(1), T(2)...T(n). Viết thủ tục tạo cây nhị phân Huffman để mã hóa văn bản.

Câu 5: Viết thủ tục HN2P(X: Mảng; d,m, c: Chỉ số, VAR Y: Mảng) có nhiệm vụ tạo mảng Y(d..c) không giảm từ 2 phần của mảng X, biết rằng hai phần của mảng X đã được sắp xếp:
X(d) ≤ X(d + m) ≤ ... ≤ X(m) và X(m + 1) ≥ X(m + 2) ≥ ... ≥ X(c) với d ≤ m ≤ c.

Câu 6: Ma trận A =(A (i, j) ; 1 ≤ i ≤ m, 1 ≤ j ≤ n) được sắp xếp không giảm theo từng hàng và từng cột. Viết giải thuật tạo mảng X (i.. mxn) không giảm từ các phần tử của A. Đánh giá số phép so sánh phải thực hiện.

Câu 7: Đồ thị G có n đỉnh, U1, U2... Un được cho bởi danh sách cạnh
Cạnh = Record
          d, c : Tên đỉnh;
          t: trọng số;
          End;
D (1..m) of Cạnh
Viết chi tiết thuật toán KRUSKAL tìm cây khung bé nhất của G
Áp dụng thuật toán để tìm cây khung bé nhất của đồ thị G vô hướng sau:

1	2	3		5	1	3		9	5	1		7	12	2		3	4	4
2	3	3		6	2	2		10	6	3		12	8	2		5	10	4
1	6	2		7	3	5		6	11	3		9	10	4		7	8	2
2	7	1		8	4	2		6	7	4		10	11	4		4	1	7
3	8	4		5	6	4		11	7	2		11	12	5		12	9	2

Câu 8: Đồ thị G có n đỉnh được đánh số từ 1 đến n lưu trong danh sách kề
V = ARRAY (1..n) of List
List = ^Vertex;
Vertex = Record
          t: Tên đỉnh;
          Next: List;
          End;
Cho đỉnh u. Hãy tính số đỉnh thuộc vùng liên thông chứa u.

Đề Test CTDL & GT năm 2011 đã viết:Câu 1: Danh sách X được tổ chức bởi cấu trúc:
List = ^Element;
          Element = Record
                    d: Data;
                    Next : List;
          End;
Cho danh sách P và Q. Hãy viết thủ tục để:
a. Xóa nút đứng cuối cùng trong danh sách P.
b. Nối danh sách Q vào sau danh sách P.

a)

Xóa nút đứng cuối cùng trong danh sách P:

b)

Nối danh sách Q vào sau danh sách P:

Đề Test CTDL & GT năm 2011 đã viết:Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố. Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4

a)

Viết code:

Đề Test CTDL & GT năm 2011 đã viết:
Câu 5: Viết thủ tục HN2P(X: Mảng; d,m, c: Chỉ số, VAR Y: Mảng) có nhiệm vụ tạo mảng Y(d..c) không giảm từ 2 phần của mảng X, biết rằng hai phần của mảng X đã được sắp xếp:
X(d) ≤ X(d + m) ≤ ... ≤ X(m) và X(m + 1) ≥ X(m + 2) ≥ ... ≥ X(c) với d ≤ m ≤ c.

Viết thuật toán:

Đề TEST 2011 CTDL và GT đã viết:Câu 4: Văn bản T chứa n ký tự K(1), K(2)...K(n) có tần suất xuất hiện T(1), T(2)...T(n). Viết thủ tục tạo cây nhị phân Huffman để mã hóa văn bản.

A) {Khai báo cấu trúc cây nhị phân}
List = ^bg;
          bg = Record
          k : tên ký tự;
          T : tần suất xuất hiện;
          L, R : List;
          End;
X[1...n] of List;
B) {Các bước thực hiện}
1) FOR i := 1 TO n DO
          New(p);
          p^.k := ki;
          p^.T := Ti;
          p^.L:= Nil;
          p^.R := Nil;
X(i):= p;
2) FOR m := n DOWNTO 2 DO
          a) Sắp xếp X(1).T > X(2).T >...> X(m).T {sắp xếp tần suất giảm dần}
          b) New(q);
                    q^.T := X(m)^.T + X(m-1)^.T;
                    q^.R:=X(m);
                    New(G);
                    G:=X(m-1);
                    q^.L:=G;
                    X(m-1):=q;
3) OUTPUT X(1);

Theo tôi nghĩ câu 1 rất dễ nhưng cũng rất dễ điểm. Tôi cũng bị mất điểm câu này.

Không thấy các anh chị chuyên gia ngọ nguậy gì, em mạn phép xin trình bày cách làm Câu 6: Ma trận A =(A (i, j) ; 1 ≤ i ≤ m, 1 ≤ j ≤ n) được sắp xếp không giảm theo từng hàng và từng cột. Viết giải thuật tạo mảng X (i.. mxn) không giảm từ các phần tử của A. Đánh giá số phép so sánh phải thực hiện.
Chọn cách tối ưu nhất có thể có. Em tham khảo 2 cuốn sách sau:
[1] M. Schimmler. Fast Sorting on the Instruction Systolic Array. Bericht Nr. 8709, Institut fr Informatik, Christian-Albrechts-Universitt Kiel (1987).
[2] C.D. Thompson, H.T. Kung. Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM 20, 4, 263-271 (1977).

---

Có nhiều phương pháp sắp xếp. Song, tùy thuộc vào sự tổ chức của dữ liệu, người ta chọn phương pháp sắp xếp sao cho phù hợp. Dưới đây, em xin chia sẻ với anh chị phương pháp sắp xếp hòa nhập bốn đường (4-Way Mergesort) trên mảng 2 chiều. Còn việc áp dụng cụ thể vào bài toán này, xin nhường anh chị, vì nếu em làm luôn, sợ múa rìu qua mắt.... rất nhiều thợ.
1. Thiết kế giải thuật
Định nghĩa:
Một mảng 2 chiều mxn gọi là mảng sắp xếp thô (roughly sorted) nếu ta chỉ cần sắp xếp các dòng của nó thì toàn bộ mảng sẽ được sắp xếp hoàn toàn.
Vậy, trong mảng sắp xếp thô, mỗi phần tử của mảng đã nằm đúng trên dòng của nó.
Ví dụ 1:

[You must be registered and logged in to see this image.]

ý tưởng của sắp xếp hòa nhập bốn đường là hòa nhập bốn mảng sắp xếp thô [You must be registered and logged in to see this image.] lại với nhau để được một mảng sắp xếp thô m x n. (ở đây, ta mặc định là sắp tăng dần)
Procedure Four_Way_Merge (m, n)
Dữ liệu vào:
Mảng m x n thỏa mãn bốn mảng con [You must be registered and logged in to see this image.] của nó là sắp xếp thô.
Dữ liệu ra:
Mảng sắp xếp thô m x n.
Các bước thực hiện:
B1. Sắp xếp các dòng của bốn mảng con theo cách:
- Sắp xếp giảm dần với mảng con có chỉ số nhỏ hơn,
- Sắp xếp tăng dần với mảng con có chỉ số lớn hơn.
B2. Sắp xếp tăng dần các cột của mảng m x n.
B3. Sắp xếp các dòng của mảng m x n theo cách:
- Dòng lẻ thì sắp xếp tăng dần,
- Dòng chẵn thì sắp xếp giảm dần.
B4. Sắp xếp tăng dần các cột của mảng m x n.
Ví dụ 2:
Với m =5 và n =5, mỗi mảng con sắp xếp thô có kích thước là 2 x 2. Các bước thực hiện giải thuật như sau:

[You must be registered and logged in to see this image.]

a) Mảng ban đầu có 4 mảng con sắp xếp thô.
b) Mảng có được sau bước 1.
c) Mảng có được sau bước 2.
d) Mảng có được sau bước 3.
e) Mảng có được sau bước 4. Đây là mảng sắp xếp thô.
f) Mảng đã được sắp xếp hoàn toàn sau khi sắp xếp các dòng.
Minh họa trên cũng cho chúng ta thấy được sự đúng đắn của giải thuật (phần chứng minh tính đúng đắn xin dành cho các anh chị).
Để có được các mảng con sắp xếp thô từ một mảng ban đầu chưa sắp xếp, ta nên dùng chiến lược chia để trị với kĩ thuật đệ quy.

Thuật toán sơ bộ:

Vậy, một mảng m x n được sắp xếp hoàn toàn bằng cách làm cho nó trở thành mảng sắp xếp thô và rồi sắp xếp các dòng của nó.

Procedure Four_Way_ Mergesort (n):

2. Phân tích giải thuật
Ta thử phân tích độ phức tạp của giải thuật khi sắp xếp một mảng n x n.
Ta có thể sắp xếp mỗi một dòng n phần tử theo phương pháp sắp xếp nổi bọt. Vậy, như anh chị đã biết, trong trường hợp xấu nhất ta phải mất thời gian là n(n - 1)/2. Gọi việc sắp xếp một dòng hay một cột là một bước sắp xếp thì việc sắp xếp n dòng hoặc n cột của mảng n x n phải mất n bước. Trong thủ tục Four_Way_Merge, số lượng các bước là:
B1: n/2 bước
B2: n bước
B3: n bước
B4: n/2 bước
Tổng: 3n bước.
Chú ý rằng, B4 chỉ cần n/2 bước bởi vì mỗi cột đã được chia thành 2 phần (trên và dưới) bởi 4 mảng con ban đầu, nên ta chỉ cần sắp xếp trong nội bộ 2 phần của mỗi cột đó.
Việc gọi đệ quy Four_Way_Merge trong Rough_Sort mất 3n+3n/2+3n/4+…+3 ≤ 6n bước. Do vậy, cộng thêm việc sắp xếp các dòng của mảng n x n trong Four_Way_Mergesort ta có tổng thời gian của giải thuật là: T(n) ≤ 7n bước. Mỗi bước mất thời gian ít nhất là n(n - 1)/2 nên T(n) ≤ 7n.2(n - 1)/2. Với kích thước của mảng hai chiều là n x n thì độ phức tạp tính toán của giải thuật là: O(n^3/2).
3. Kết luận
Đến đây, anh chị đã biết được giải thuật sắp xếp hòa nhập bốn đường là gì. Độ phức tạp của nó là chấp nhận được, cụ thể là O(n^3/2). anh chị cũng sẽ biết cách cài đặt giải thuật này một khi anh chị muốn sắp xếp một mảng 2 chiều. Xin góp ý của các anh chị về giải thuật này.

Xóa nút đứng cuối cùng trong danh sách P:
PROC Xóa (P: List);
1) WHILE P^.Next ^.Next ≠ Nil DO
P = P^.Next
2) P^.Next = Nil

Cái P^.next^.next dùng được hả anh. Có lẽ kiến thức em hạn hẹp không biết có cái này

Ban QT: Không hiểu câu hỏi "Cái P^.next^.next dùng được hả anh?"

Đề TEST 2011 CTDL và GT đã viết:Câu 8: Đồ thị G có n đỉnh được đánh số từ 1 đến n lưu trong danh sách kề
V = ARRAY (1..n) of List
List = ^Vertex;
          Vertex = Record
          t: Tên đỉnh;
          Next: List;
End;
Cho đỉnh u. Hãy tính số đỉnh thuộc vùng liên thông chứa u.

Trước khi giải ta hãy xem xét bài tập này một chút.
Ở đây là mảng V có n phần tử. Mỗi phần tử là một đỉnh. Cấu trúc dữ liệu của nó có gì đặc biệt? Đó là mỗi đỉnh lại trỏ vào một đỉnh kề với nó. Nghĩa là nếu bắt đầu là đỉnh a trỏ vào đỉnh b → đỉnh c.... → đỉnh z, khi đỉnh z không trỏ được vào đỉnh nào, nó sẽ phải trỏ vào nil. Đấy là một phần của vùng liên thông. Một phần của vùng liên thông khác cũng bắt đầu từ a phảy lặp lại đúng như vậy.
Cái khó ở đây là chúng ta không thể biết được đỉnh nào là đỉnh bắt đầu. Nghĩa là nếu sắp xếp các đỉnh thành một dãy mà ta duyệt từ một đỉnh a nào đó, thì với cấu trúc dữ liệu dạng này, ta chỉ duyệt được từ đỉnh a đó đến cuối dãy, nếu có đếm thì cũng đếm từ đỉnh a duyệt đến cuối dãy thôi. Vậy ta làm thế nào để biết được đỉnh nào là đầu tiên nhỉ?
Vậy bài toán ở đây đưa ra là cách đánh dấu duyệt và cách đếm thôi.

Giả sử duyệt từ đỉnh 1 đi lòng vòng đến hết vùng liên thông của 1 ta đánh một dấu. Đây là vòng duyệt 1.
Sang đỉnh 2, ta cũng phải làm vòng duyệt 2. Nếu như đỉnh 2 đã được đánh dấu của vòng duyệt 1 rồi thì may quá, nhảy tiếp sang đỉnh kế, còn nó chưa thấy đánh dấu thì cũng phải đánh dấu lại vì có 2 trường hợp:
- Trường hợp 1, nếu nó cũng thuộc vùng liên thông của 1 (nhưng trong dãy nó đứng trước đỉnh 1 thì nó cũng không được đánh dấu ở vòng 1, do vòng 1 chỉ duyệt các đỉnh từ vòng 1 về sau mà). Khi duyệt dần gặp đánh dấu của đỉnh 1 thì ta cũng đếm từ đỉnh 2 này + với đếm của vòng 1. Biết đếm sẽ có khi vô ích, khi mà đến cuối cùng vùng này không chứa u. Nhưng dữ liệu kiểu này đều là nhỡ may mà.
- Nhỡ may đỉnh 2 không cùng vùng liên thông của 1 thì sao. Đương nhiên việc đếm này là độc lập.
Vậy ta phải sử dụng 2 mảng độ dài n, hoặc 1 mảng 2 x n trong đó 1 mảng để đánh dấu đã duyệt đã đếm, còn một mảng thứ 2 để đếm các đỉnh của vùng liên thông của đỉnh đánh dấu đó. uh, mệt thật đấy.

Bây giờ viết lệnh nhé!
Thực ra viết thẳng ra chỉ có ít dòng thôi. Nhưng tôi muốn vừa viết vừa phân tích để những bạn nghỉ học hôm thầy giảng có thể hiểu được, nên các bạn vui lòng xem dài một tý nhé! Ở đây tôi làm 2 mảng song song cho dễ lý giải, bạn cũng có thể dùng một mảng dung lượng gấp đôi cũng được.
PROC DemVungLienThongChua_U (V: list)
I) {Đánh dấu tất cả các đỉnh là số thứ tự đỉnh, mỗi đỉnh là một nhóm, đồng thời đưa số đếm của tất cả các nhóm về 1}
FOR i: = 1 TO n DO
          1) Nhom(i) = i;
          2) Dem(i) = 1;
II) {Duyệt lần lượt các đỉnh cho đến hết, ở đây nếu đã cùng vùng liên thông thì đánh lại nhóm chính là chỉ số của đỉnh bé hơn nha}
A) NEW(P);
B) FOR i = 1 TO n DO
C) Stop = False
D)WHILE !Stop DO
          1) P = V(i) {Dùng biến con trỏ P để duyệt danh sách, duyệt từ đỉnh i}
          2) j = i {Dùng biến j để xử lý nội bộ vòng lặp, tránh ảnh hưởng đến vòng lặp chung này}
          3)WHILE (P^.Next ≠ Nil) &!Stop DO {Lặp các đỉnh là danh sách kề chưa được xét}
                    IF (Nhom(P^.Next.t) = t THEN {Các đỉnh này chưa được xét}
                              i) Dem(j) = Dem(j) + 1 {Tăng biến đếm cho nhóm vì có đỉnh kế}
                              ii) P = P^.Next {Chuyển con trỏ sang đỉnh kế}
                              iii) j = P^.t {Lấy đỉnh kề mới}
                              iv) Nhom (j) = i {Đặt lại các phần tử thuộc vùng liên thông theo tên nhóm là đỉnh thứ i}
                    ELSE {Các đỉnh này đã xét ở vòng FOR i trước rồi, do đã đánh dấu theo đỉnh nhỏ}
                              i) Dem (i) = Dem (i) + Dem (Nhom(P^.Next.t)) {Cộng biến đếm}
                              ii) FOR x = 1 TO n DO
                                        IF Nhom(x) = Nhom(P^.Next.t)) THEN Dem (x) = Dem(i);Nhom(x) = Nhom(i);
                                        {Đặt lại biến đếm và nhóm cho cả nhóm trong mảng theo dõi}
                              iii)Stop = True
III) OUTPUT (Dem (u)) {Xuất ra kết quả đếm đối với đỉnh u, là vùng liên thông chứa u}

Đề TEST 2011 CTDL và GT đã viết:Câu 7: Đồ thị G có n đỉnh, U1, U2... Un được cho bởi danh sách cạnh
          Cạnh = Record
          d, c : Tên đỉnh;
          t: trọng số;
          End;
d (1..m) of Cạnh
Viết chi tiết thuật toán tìm cây khung bé nhất của G

KRUSKAL by LĐS:

KRUSKAL by HTH:

Làm bằng tay phần b)
Đánh dấu tất cả các đỉnh theo tên của nó.
Sắp xếp tăng dần theo trọng số, sau đó lấy các cạnh, đánh dấu các đỉnh được lấy bằng chỉ số đánh dấu của cạnh đầu.
Khi lấy đủ các đỉnh, bài toán hoàn thành.
[You must be registered and logged in to see this image.]

Câu 1 nếu đổi thành danh sách móc nối đơn và mô tả như sau
List = ^LINK;
LINK = record
K : Data;
Next : List;
End;
Và câu hỏi giống y như câu 1 thì lời giải có gì khác không bạn?

Đây là nhận xét của thầy tôi ghi lại để những người vắng rút kinh nghiệm.
- Thứ nhất là yếu về kiến thức cơ bản, sao chép của nhau nhiều, chữ viết cẩu thả, thụt thò không đúng, cách viết chỉ số tùy tiện thiếu nhất quán (chỗ thì ghi là Xj, chỗ thì ghi là X[j]), ký hiệu hỗn độn lẫn lộn chữ hoa và chữ thường (chỗ thì x, chỗ khác lại X...).
- Cây thì vẽ ngang phè, con và cha không rõ ràng.
- Viết các con số liền tù tì (563) lẽ ra phải có dấu cách đủ lớn để phân biệt 5 và 6 và 3, hay 5 và 63, hay 56 và 3.
- Dùng các dấu ngoặc đóng mở không chính xác, không rõ ràng.
- Bài toán tìm cây khung bé nhất không ghi STT bên cạnh các bước, dẫn tới lý giải và khó khăn nhiều cho người chấm theo dõi, rất tối kỵ.
- Cây khung cần có tên nút, nhưng nhiều bài không có tên nút.
- Thiếu không chỉ ra câu "Tập cạnh của cây khung bé nhất là..."
- Nhiều bài thiếu, không khai báo cấu trúc cây khung, trừ đến 0,25 đ.
Cụ thể sai sót đối với từng câu như sau:

Với những câu dễ là câu 2 mất điểm vì:
- Lý luận là x, nhưng push, pop lại là Mi. Nếu dùng x phải có câu "đọc x từ M", nhưng nên dùng Mi để người chấm nhận ra luôn thứ tự của phần tử.
- Câu lệnh FOR i := 1 To /M/ nhưng nhiều người thiếu 2 gạch 2 bên chữ M, nên bị đánh giá không hiểu và trừ điểm nặng.
- Trong vòng lặp làm 2 công việc là pop từ ngăn xếp ra và đưa vào sau N. Càn ghi thụt thò cẩn thận, hoặc ghi trên cùng hàng thì dùng dấu {}, cùng lắm thì mới dùng BEGIN, END cũng thụt thò, nhưng dùng cái này sẽ rối, khiến giáo viên chấm mất tập trung vì loãng nội dung nếu như cứ BEGIN END toàn bài. Nếu chấm khó theo dõi chỉ cần 1 sai sót nhỏ sẽ có cớ để trừ toàn bộ số điểm.
- Lưu ý biểu thức mà không chỉ rõ chứa bên trong là gì thì M, N chấm như nhau.
- Có thể giải quyết vấn đề bằng nhiều cách, không quan trọng, miễn là phải đúng vẫn chấm điểm, tuy nhiên cách làm không tối ưu thì không được tối đa điểm.
- Khi duyệt tay, để tránh phải viết đi viết lại dãy ký tự ví dụ dòng trên viết 5 6 3 / 2 * dòng dưới có thể viết ...2 * - 5
tức là dùng dấu 3 chấm để viết. Điều này không sai, người chấm thi không phải trình độ kém đến mức không hiểu dấu 3 chấm là cái gì, cách viết này để bài thi gọn gàng, không rối mắt. Tuy nhiên lưu ý, trong stack nên dùng khoảng trống rộng, không nên dùng dấu phảy, điều này giúp cho việc theo dõi của người chấm được bao quát cũng như đánh giá chính xác đáp án hơn.

Về câu cây nhị phân Huffman:
Chỉ có 1 lời giải.
Không nên dùng dấu lớn hơn hay nhỏ hơn hoặc bằng, vì khi thi thì người thi hay rối. Nói là sắp xếp giảm dần nhưng lại dùng nhầm dấu ≤ dẫn tới bài thi được luôn 0 điểm. Chỉ cần viết 1 dòng là "Sắp xếp theo tần suất giảm dần" là tốt nhất."
Thứ nữa là khi tạo con lưu ý phải tạo riêng Y sau đó mới sao chép vào, chuyển trỏ vào... chứ làm luôn là sai, 0 đ.

Về câu 5:
Trước khi viết lệnh nên xếp thành một dãy tăng dần từ Xd đến Xm, giảm dần từ X_m+1 đến Xc viết trên cùng một hàng. Viết một vài dòng ý tưởng, để nếu có làm sai sót thì vẫn không bị trừ nhiều điểm.
Sai sót thường thấy là i tăng lên i := i + 1; hoặc i ++; và j giảm đi phải viết là j := j - 1; hay j-- thế nhưng nhiều bài vẫn viết nhầm là j = j + 1 và j ++ nên sẽ bị trừ 0 điểm. Bị đánh giá là không hiểu gì.
Khi một đoạn xong trước, lấy đoạn còn lại hạ xuống, chỉ cần một vòng FOR đối với các phần tử chưa xét. Có thể viết:
Y_k = X_t và k = k + 1 hoặc
Y_k+j-t = X_t
đều được, thấy cái nào dễ nhớ, dễ hiểu hơn thì sử dụng. Tuy nhiên cần chú ý tránh tạo sai mảng đích đối với chỉ số k.

Về câu 7:
Áp dụng danh sách cạnh
+ Thông tin trong lời giải không đầy đủ.
+ Sắp xếp cạnh theo trọng số tăng dần sau đó pải chú ý đánh số thứ tự bên cạnh.
+ Chọn cạnh nào đánh số cạnh thứ mấy để người chấm dễ theo dõi. Khi chọn cạnh xong pải ghi đủ các thông tin sau: Cạnh nào, trọng số là bao nhiêu, tổng trọng số từ điểm xuất phát đến hết cạnh vừa chọn là bao nhiêu. Kết thúc phải nói được là tổng trọng số tìm thấy là con số cụ thể.
+ Trong bài làm chú ý khi sử dụng T[1..n-1] of Cạnh chú ý rằng tìm được cạnh D[j] nào đó , đưa vào chỉ cần T[k] = D[j] , không dùng cách là cho 2 đầu bằng nhau → được đánh giá là trình độ tồi.
+ Nên sắp xếp theo chiều tăng của trọng số trước. Một số bài làm không sắp xếp, như thế là người chấm sẽ khó theo dõi và rất mệt.
+ Viết chú giải giải thích kỹ số hiệu, cấu trúc cây T, G , rồi sự liên thông sẽ được đánh giá cao.

Về câu 8:
+ Nên duyệt theo chiều rộng an toàn hơn. Mỗi khi đánh dấu mới đếm. Đánh dấu xong, đếm luôn để tránh phải duyệt lại, là an toàn nhất. Luôn chọn u là điểm xuất phát, chỉ cần nói "Chọn đỉnh xuất phát là u" thôi.
+ Một số bài nhầm u và v rất nguy hiểm. Nên viết chữ v rõ ràng, không nên viết ngoáy để người chấm không đoán được là u hay v sẽ bị trừ, thậm chí đánh giá sai sẽ không có điểm.

Về câu 6:
Bài này phải giải là sắp xếp hòa nhập, có nhiều cách giải, ở đây chỉ cần hiểu là tại một thời điểm, lấy mỗi hàng một phần tử hiện tại của hàng đó. Chọn phần tử nhỏ nhất trong số đó, đưa vào mảng đích. Hàng nào có phần tử bị lấy sẽ tăng chỉ số phần tử hiện tại lên 1.

code:

Về câu 1:
- Không ghi thủ tục mà chỉ có code không thì không có điểm
- Không khai tham trị
- Hiểu không rõ, không khai báo mà di chuyển lên P mất dữ liệu ngay
- Không dùng tham số

Code:

s : = P;
IF (s !=Nil) THEN
          1)WHILE (s !=Nil) DO { c := s; s := s^.Next}
c^.next = Q;
ELSE P = Q;
OUTPUT P;

Xóa phần tử cuối được xem là bài khó nhất vì nếu có 1 phần tử mà dùng lệnh xóa thông thường sẽ không xóa được. Nên chưa làm 3 trường hợp:
P có 1 phần tử, P rỗng và P có nhiều phần tử.

Code:

1)Input P
2) IF (P != Nil) & (P^.Next = Nil) THEN
          a) s : = P;
          b) WHILE (s^.Next ≠ Nil) DO {c: = s; s = s^.Next}
ELSE P: = Nil;
3) Output P

green.lotus84 đã viết:Câu 1 nếu đổi thành danh sách móc nối đơn và mô tả như sau
List = ^LINK;
LINK = record
K : Data;
Next : List;
End;
Và câu hỏi giống y như câu 1 thì lời giải có gì khác không bạn?

Bạn hỏi như thế chứng tỏ bạn chả hiểu gì về danh sách móc nối cả...????

các bác cho em tý. dòng 8 khi đưa dấu + vào thì thì ut(*)>ut(+) lấy (*) đưa vào n. rồi đưa + vào s. không cần so sánh ut(+) và dấu (-) trong stact nũa.
nhưng dòng số 10. đưa dấu + vào thì lại lấy luôn 2 dấu - đưa sang n?

Trình bày như bạn là rất tốt nhưng theo mình có lẽ là mất nhiều thời gian, hiệu quả lại không cao. Theo mình bạn nên nghiên cứu cách trình bày khác sao cho thỏa mãn hai yêu cầu: 1. Mất ít thời gian; 2. Hiệu quả lại cao.

Em nghĩ câu 2 đáp án thế này mới đúng
≡≡≡≡≡-
Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố.Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4

Đọc theo M	x	Công việc thực hiện	S	N
5	5	Đưa 5 vào N	NULL	5
5-	-	Đưa – vào S	-	5
5-6	6	Đưa 6 vào N	-	5,6
5-6/	/	Kiểm tra UT(Top(S))
5-6/3	3	Đưa 3 vào N	-,/	5,6,3
5-6/3*	*	Kiểm tra UT(Top(S)) ≥ UT(*) lấy / từ dỉnh S đưa vào N, và đưa * vào S	-,*	5,6,3,/
5-6/3*2	2	Đưa 2 vào N	-,*	5,6,3,/,2
5-6/3*2-	-	Kiểm tra UT(UT(Top(S)) ≥ UT(-) lấy *,- từ đỉnh S đưa vào N, và đưa - vào S	-,-	5,6,3,/,2,*,-
5-6/3*2-5	5	Đưa 5 vào N	-	5,6,3,/,2,*,-,5
5-6/3*2-5+	+	Kiểm tra UT(UT(Top(S)) ≥ UT(-) lấy - từ đỉnh S đưa vào N, và đưa + vào S	+	5,6,3,/,2,*,-,5,-
5-6/3*2-5+3	3	Đưa 3 vào N	+	5,6,3,/,2,*,-,5,-,3
5-6/3*2-5+3*	*	Kiểm tra UT(Top(S))
5-6/3*2-5+3*2	2	Đưa 2 vào N	+,*	5,6,3,/,2,*,-,5,-,3,2
5-6/3*2-5+3*2/	/	Kiểm tra UT(UT(Top(S)) ≥ UT(/) lấy * từ đỉnh S đưa vào N và đưa / vào S	+,/	5,6,3,/,2,*,-,5,-,3,2,*
5-6/3*2-5+3*2/3	3	Đưa 3 vào N	+ /	5,6,3,/,2,*,-,5,-,3,2,*,3
5-6/3*2-5+3*2/3-	-	Kiểm tra UT(UT(Top(S)) ≥ UT(-) lấy /,+ từ đỉnh S đưa vào N và đưa - vào S	-	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+
5-6/3*2-5+3*2/3-3	3	Đưa 3 vào N	-	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3
5-6/3*2-5+3*2/3-3*	*	Kiểm tra UT(UT(Top(S))
5-6/3*2-5+3*2/3-3*5	5	Đưa 3 vào N	-,*	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5
5-6/3*2-5+3*2/3-3*5+	+	Kiểm tra UT(UT(Top(S)) ≥ UT(+) lấy *,- từ đỉnh S đưa vào N và đưa + vào S	+	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-
5-6/3*2-5+3*2/3-3*5+4	4	Đưa 4 vào N	+	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-,4
		Lấy toàn bộ S đưa ra N		5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+

Vậy biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố:

PHL102 đã viết:Em nghĩ câu 2 đáp án thế này mới đúng
≡≡≡≡≡-
Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố.Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4

Đọc theo M	x	Công việc thực hiện	S	N
5	5	Đưa 5 vào N	NULL	5
5-	-	Đưa – vào S	-	5
5-6	6	Đưa 6 vào N	-	5,6
5-6/	/	Kiểm tra UT(Top(S))
5-6/3	3	Đưa 3 vào N	-,/	5,6,3
5-6/3*	*	Kiểm tra UT(Top(S)) ≥ UT(*) lấy / từ dỉnh S đưa vào N, và đưa * vào S	-,*	5,6,3,/
5-6/3*2	2	Đưa 2 vào N	-,*	5,6,3,/,2
5-6/3*2-	-	Kiểm tra UT(UT(Top(S)) ≥ UT(-) lấy *,- từ đỉnh S đưa vào N, và đưa - vào S	-,-	5,6,3,/,2,*,-
5-6/3*2-5	5	Đưa 5 vào N	-	5,6,3,/,2,*,-,5
5-6/3*2-5+	+	Kiểm tra UT(UT(Top(S)) ≥ UT(-) lấy - từ đỉnh S đưa vào N, và đưa + vào S	+	5,6,3,/,2,*,-,5,-
5-6/3*2-5+3	3	Đưa 3 vào N	+	5,6,3,/,2,*,-,5,-,3
5-6/3*2-5+3*	*	Kiểm tra UT(Top(S))
5-6/3*2-5+3*2	2	Đưa 2 vào N	+,*	5,6,3,/,2,*,-,5,-,3,2
5-6/3*2-5+3*2/	/	Kiểm tra UT(UT(Top(S)) ≥ UT(/) lấy * từ đỉnh S đưa vào N và đưa / vào S	+,/	5,6,3,/,2,*,-,5,-,3,2,*
5-6/3*2-5+3*2/3	3	Đưa 3 vào N	+ /	5,6,3,/,2,*,-,5,-,3,2,*,3
5-6/3*2-5+3*2/3-	-	Kiểm tra UT(UT(Top(S)) ≥ UT(-) lấy /,+ từ đỉnh S đưa vào N và đưa - vào S	-	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+
5-6/3*2-5+3*2/3-3	3	Đưa 3 vào N	-	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3
5-6/3*2-5+3*2/3-3*	*	Kiểm tra UT(UT(Top(S))
5-6/3*2-5+3*2/3-3*5	5	Đưa 3 vào N	-,*	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5
5-6/3*2-5+3*2/3-3*5+	+	Kiểm tra UT(UT(Top(S)) ≥ UT(+) lấy *,- từ đỉnh S đưa vào N và đưa + vào S	+	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-
5-6/3*2-5+3*2/3-3*5+4	4	Đưa 4 vào N	+	5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-,4
		Lấy toàn bộ S đưa ra N		5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+

Vậy biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố:

5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+

Mình cũng có đáp án giống của bạn!