Câu 1.
a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))
Câu 2.
a. Danh sách D lưu trữ các ký tự và tần suất xuất hiện của chúng trong văn bản T có n ký tự:
List = ^Node;
          Node = Record;
          Ch: Ký tự;
          Prob: Tần suất;
          Left, Right: List
          End;
K: Array[1..n] of List;
Viết giải thuật xây dựng cây nhị phân Huffman mã hoá văn bản T.
b. Văn bản T chỉ gồm các ký tự u, r, d, e, e, g, h, p, k với số lần xuất hiện như sau:

Ký tự	u	r	d	e	g	h	p	k
Tần suất xuất hiện	0,21	0,08	0,13	0,09	0,15	0,12	0,1	0,12

Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng. Cho biết số bit trung bình để mã hoá một ký tự và hiệu suất mã hoá.
Câu 3:
Đồ thị có hướng G(V, E) có trọng số dương có n đỉnh đánh số từ 1 đến n, cho bởi ma trận trọng số D.
[You must be registered and logged in to see this image.]
Với i, j = 1..n
Viết thủ tục tìm đường đi ngắn nhất u đến v. Danh sách các đỉnh trên đường đi được lưu trong danh sách c[1..n] of Integer
Câu 4:
a) Trình bày thuật toán sắp xếp nổi bọt.
b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}
Câu 5:
Trình bày thuật toán sắp xếp chèn ở dạng sơ đồ khối

Câu 4:
a) Trình bày thuật toán sắp xếp nổi bọt.
b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}
a.
void bubble (int a[i], int N)
{
int i, j, tg;
for (i = 0; i

Đề tuyển sinh CTDL> 2010 đã viết:Câu 3:
Đồ thị có hướng G(V, E) có trọng số dương có n đỉnh đánh số từ 1 đến n, cho bởi ma trận trọng số D.
[You must be registered and logged in to see this image.]
Với i, j = 1..n
Viết thủ tục tìm đường đi ngắn nhất u đến v. Danh sách các đỉnh trên đường đi được lưu trong danh sách c[1..n] of Integer

Giải:
A)

Trường hợp đã biết đồ thị đã liên thông rồi:

B)

Trường hợp chưa biết được liên thông hay không:

Đề CTDL và GT 2010 đã viết:Câu 1.
a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))

a)

Giải thuật:

b)

Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2))):

Đề tuyển sinh 2010 đã viết:Câu 4:
a) Trình bày thuật toán sắp xếp nổi bọt.
b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}

a)

Thuật toán sắp xếp nổi bọt:

b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}

i	j	1	2	3	4	5	6	7	←chỉ số phần tử
1		24	15	44	42	22	16	25	←dãy ban đầu
							↑	↑	đổi chỗ 16,25
1	7	24	15	44	42	22	25	16
						↑	↑		đổi chỗ 22,25
1	6	24	15	44	42	25	22	16
					↑	↑			không đổi
1	5	24	15	44	42	25	22	16
				↑	↑				không đổi
1	4	24	15	44	42	25	22	16
			↑	↑					đổi chỗ 15, 44
1	3	24	44	15	42	25	22	16
		↑	↑						đổi chỗ 24,44
1	2	44	24	15	42	25	22	16	hết vòng i = 1
2	7						↑	↑	không đổi
2	6	44	24	15	42	25	22	16
						↑	↑		không đổi
2	5	44	24	15	42	25	22	16
					↑	↑			không đổi
2	4	44	24	15	42	25	22	16
				↑	↑				đổi chỗ 15, 42
2	3	44	24	42	15	25	22	16
			↑	↑					đổi chỗ 24, 42
		44	42	24	15	25	22	16	hết vòng i = 2
3	7						↑	↑	không đổi
	6	44	42	24	15	25	22	16
						↑	↑		không đổi
	5	44	42	24	15	25	22	16
					↑	↑			đổi chỗ 15, 25
	4	44	42	24	25	15	22	16
				↑	↑				đổi chỗ 24, 25
		44	42	25	24	15	22	16	hết vòng i = 3
4	7						↑	↑	không đổi
	6	44	42	25	24	15	22	16
						↑	↑		đổi chỗ 15, 22
	5	44	42	25	24	22	15	16
					↑	↑
		44	42	25	24	22	15	16	hết vòng i = 4
5	7						↑	↑	đổi chỗ 15, 16
	6	44	42	25	24	22	16	15	hết vòng i = 5
6							↑	↑	không đổi
	7	44	42	25	24	22	16	15	hết vòng i = 6