Khoa CNTT  Trường CĐCN Việt Đức
ĐỀ CƯƠNG ÔN THI HỌC KỲ 4
Môn: Chuyên ngành ( CTDL & GT)
Khóa: 4_2009-2012_Ngành: Công nghệ thông tin
Lớp: K4 CĐ Tin Khoa: CNTT
ĐỀ CƯƠNG ÔN TẬP MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Câu số 1
Cho dãy số: 8, 12, 3, 4, 6, 1, 7, 9, 33, 22.
Ứng dụng thuật toán sắp xếp Chọn để sắp xếp dãy số trên.
Giải:
Thuật toán:
type mang = array [1 100] of integer;
var a:mang;
{sx chon}
procedure sapxepchon (var a:mang; n:integer);
var j,k,i:integer; tg:longint;
begin
for i:=1 to n-1 do
begin
k:=i;
for j:=i+1 to n do if a[j]<a[k] then k:=j;
begin
tg:=a[i];
a[i]:=a[k];
a[k]:=tg;
end;
end;
end;
CTDL&GT - 1 -
Khoa CNTT  Trường CĐCN Việt Đức
ví dụ

a[j+1]:=x;
end;
CTDL&GT - 2 -
Khoa CNTT  Trường CĐCN Việt Đức
end;
end;
ví dụ
Bảng sau ghi lại các giá trị khoá tương ứng với từng bước.
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
Ban đầu 8 12 3 4 6 1 7 9 33 22
8 12 3 4 6 6 7 9 33 22
8 12 3 4 4 6 7 9 33 22
8 12 3 3 4 6 7 9 33 22
8 12 12 3 4 6 7 9 33 22
8 8 12 3 4 6 7 9 33 22
Bước 1 1 8 12 3 4 6 7 9 33 22
8 12 12 4 6 7 9 33 22
8 8 12 4 6 7 9 33 22
Bước 2 3 8 12 4 6 7 9 33 22
8 12 12 6 7 9 33 22
8 8 12 6 7 9 33 22
Bước 3 4 8 12 6 7 9 33 22
8 12 12 7 9 33 22
8 8 12 7 9 33 22
Bước 4 6 8 12 7 9 33 22
8 12 12 9 33 22
8 8 12 9 33 22
Bước 5 7 8 12 9 33 22
Bước 6 8 12 9 33 22
12 12 33 22

8 12 3 4 6 1 7 9 22 33
8 12 3 4 1 6 7 9 22 33
8 12 3 1 4 6 7 9 22 33
8 12 1 3 4 6 7 9 22 33
8 1 12 3 4 6 7 9 22 33
Bước 1 1 8 12 3 4 6 7 9 22 33
8 3 12 4 6 7 9 22 33
Bước 2 3 8 12 4 6 7 9 22 33
8 4 12 6 7 9 22 33
Bước 3 4 8 12 6 7 9 22 33
8 6 12 7 9 22 33
Bước 4 6 8 12 7 9 22 33
8 7 12 9 22 33
Bước 5 7 8 12 9 22 33
Bước 6 8 12 9 22 33
Bước 7 9 12 22 33
Bước 8 12 22 33
Bước 9 22 33
Kết quả 1 3 4 6 7 8 9 12 22 33
Câu số 4
Cho dãy số: 8, 12, 3, 4, 6, 1, 7, 9, 33, 22.
CTDL&GT - 4 -
Khoa CNTT  Trường CĐCN Việt Đức
Ứng dụng thuật toán sắp xếp Quicksort (nhanh) để sắp xếp dãy số trên.
Giải:
type mang = array [1 250] of longint;
var a:mang;
{ctc hoan vi}
procedure hoanvi(p,q:longint);
var x:longint;

2 [1] [7 3 4 6] [8] [9] [12 33 22]
3 [1] [6 3 4] [7] [8] [9] [12] [33 22]
4 [1] [4 3] [6] [7] [8] [9] [12] [22] [33]
5 [1] [3] [4] [6] [7] [8] [9] [12] [22] [33]
Kq 1 3 4 6 7 8 9 12 22 33
Câu số 5
Cho dãy số: 8, 12, 3, 4, 6, 1, 7, 9, 33, 22.
Ứng dụng thuật toán sắp xếp Mergesort (hòa nhập) để sắp xếp dãy số trên.
Giải:
Thuật toán:
{ctc tron 2 mang}
procedure sxtron(var X, Y: mang; a, b, c: Integer);
var j, p: Integer;
begin
p := a; i := a; j := b + 1;
while (i <= b) and (j <= c) do
begin
if X[i] <= X[j] then
begin
Y[p] := X[i]; i:=i+1;
end
else
begin
Y[p] := X[j]; j:=j+1;
end;
p:=p+1;{hoac la:Inc(p):day la ham tu dong tang bien len 1}
end;
if i <= b then
Move(X[i], Y[p], (b - i + 1) * SizeOf(X[1])) {sizeof:tinh kich thuoc cua mang}
else

1 đến n
- Kiểm tra từ 2 đến n giả sử là số i
- loại bỏ tất cả những số là bội của số i lớn hơn i. Số đầu tiên của dãy này là
số nguyên tố
type mang=array[1 10000] of longint;
var a:mang; n:longint;
procedure sang( n:longint);
var i,j:integer;
begin
for i:=2 to n do
CTDL&GT - 7 -
Khoa CNTT  Trường CĐCN Việt Đức
a[i]:=1;
for i:=2 to n do
if a[i]=1 then
for j:=i to n div i do
a[i*j]:=0;
for i:=2 to n do
if a[i]=1 then
write(' ',i,' ');
end;
Ví dụ: sàng các số nhỏ hơn 60
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
lượt 1 khi số đầu tiên của dãy là 2 ta loại bỏ được các số là bội của 2 là: 4,
6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50,

10 1
0
12 1
2
1
2
12 3 3 3 3 3 3 3 3 12
6 2 - 2 / 8 9 * 1
5
12 - / - * Kq
6-2=4 4/2=2 8*9=72
15-12
=3
72/3
=24
2-24
=-22
12*(-22)
=-264
12
9 1
5
15 3
2 2 8 8 7
2
7
2
72 7
2
2

264
Kết quả: -264
Câu số 8
Khái niệm CTC? Nêu ý nghĩa của việc sử dụng CTC? Viết CTC tìm phần
tử lớn nhất trên mảng có sử dụng CTC tính giá trị lớn nhất của 2 số?
CTDL&GT - 9 -
Khoa CNTT  Trường CĐCN Việt Đức
Giải:
1. Khái niệm CTC. Nêu ý nghĩa của việc sử dụng CTC
- Khái niệm CTC
CTC (hay còn gọi là hàm, thủ tục, thủ tục con) là một chuỗi mã để thực thi
một thao tác đặc thù nào đó như một phần của chương trình lớn hơn. Đây là các
câu lệnh được nhóm vào một khối và được đặt tên và tên này tuỳ theo ngôn ngữ có
thể gán với một kiểu dữ liệu. Những khối mã này có thể tập trung lại thành một thư
viện phần mềm. Các CTC có thể được gọi ra để thi hành (thường thông qua tên của
CTC). Điều này có nghĩa là cho phép sử dụng CTC nhiều lần mà không cần viết lại
khối mã, khối mã đó chỉ được viết một lần.
- Ý nghĩa của việc sử dụng CTC
+ Tránh lặp đi lặp lại một đoạn chương trình
+ Giúp chương trình ngắn gọn, dễ sửa đổi bổ sung
+ Có thể sử dụng trong các chương trình khác nếu được tạo vào thư viện.
+ Tránh được việc khai báo nhiều biến trong chương trình chính
2. CTC tìm phần tử lớn nhất trên mảng có sử dụng CTC tính giá trị lớn nhất của 2
số
type mang=array[1 50] of longint;
var a:mang; i:integer;
procedure max_2so( a, b:longint);
begin
if (a>b) then max_2so :=a
else max_2so :=b;

end ;
Câu số 10
Trình bày thuật toán chèn một thành phần mới vào sau một thành phần của
danh sách được trỏ bởi Q.
Giải:
Type pointer=^cell
cell= record
infor: Kieu_du_lieu_ds;
next: pointer;
end;
Procedure insertafter( Q: pointer; var head: pointer; x: kieu_du_lieu_ds);
var p: ponter;
begin
new(p); { Cấp phát bộ nhớ cho p}
p^.infor:=x;
if head=nil then
begin
p^.next:=nil;
head:=p;
end
else
begin
p^.next:=Q^.next;
Q^.next:=p;
CTDL&GT - 11 -
Khoa CNTT  Trường CĐCN Việt Đức
end;
end;
Hoặc
Const max=N

else
CTDL&GT - 12 -
Khoa CNTT  Trường CĐCN Việt Đức
begin
s.top:=s.top+1;
s.a[s.top]:=x;
end;
end;
{ Loai bo phan tu khoi danh sanh}
Procedure loaibo(var s:nx; var x:integer );
begin
if(s.top=0)then write(‘stack rong’)
else
begin
x:=s.a[s.top];
s.top:=s.top-1;
end;
end;
Câu số 12
Trình bày khái niệm thuật toán và nêu các đặc trưng của thuật toán. Lấy ví
dụ minh họa.
Giải:
Định nghĩa: Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính
xác các phép toán hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra.
Đặc trưng của thuật toán
1. Bộ dữ liệu vào: Mỗi thuật toán cần có một số (có thể bằng 0) dữ liệu vào
(input). Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu
này cần được lấy từ các tập hợp giá trị cụ thể nào đó.
2. Dữ liệu ra: Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó
là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự

= n
2
> r
2
Dãy
số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số bước nào đó giá
trị của r phải bằng 0, thuật toán dừng.
Câu số 13
Định nghĩa hàng đợi ? Cho ví dụ? Viết CTC đẩy 1 phần tử vào hàng đợi?
Giải:
Định nghĩa hàng đợi
Hàng đợi là một danh sách mà trong đó các thao tác thêm một phần tử vào
trong danh sách được thực hiện ở một đầu này và thao tác lấy ra một phần tử từ
trong danh sách lại được thực hiện ở đầu kia. Như vậy, các phần tử đưa vào trong
hàng đợi trước sẽ được lấy ra trước. Do đó hàng đợi còn gọi là danh sách vào trước
ra trước (FIFO List) và cấu trúc này được gọi là cấu trúc FIFO (First In First Out).
Ví dụ: Xếp hàng mua vé tàu, vé xem phim, vé vào xem bóng đá.
Trình bày thuật toán đẩy một phần tử vào Queue và thuật toán loại bỏ một
phần tử khỏi Queue (hàng đợi ).
Giải:
{Khai báo hàng đợi}
const max=100;
type hd=record
d,c,count:integer;
a:array[1 50] of integer;
end;
procedure khoitao(var q:hd);
CTDL&GT - 14 -
Khoa CNTT  Trường CĐCN Việt Đức
begin

end;
Câu số 14
Định nghĩa ngăn xếp? Cho ví dụ? Viết CTC loại bỏ 1 phần tử khỏi ngăn
xếp?
Giải:
1. Định nghĩa ngăn xếp
Ngăn xếp là một danh sách mà trong dó thao tác thêm một phần tử và thao
tác lấy ra một phần tử từ trong danh sách được thực hiện ở cùng một đầu gọi là
đỉnh ngăn xếp. Như vậy, các phần tử được đưa vào trong ngăn xếp sau sẽ được lấy
ra trước, phần tử đưa vào đầu tiên sẽ được lấy ra cuối cùng. Do đó mà ngăn xếp
CTDL&GT - 15 -
Khoa CNTT  Trường CĐCN Việt Đức
còn gọi là danh sách vào sau ra trước (LIFO List) và cấu trúc này được gọi là cấu
trúc LIFO (Last In First Out).
Ví dụ: Xếp đĩa, mua vé, đổi nhị phân, thập phân.
Trình bày thuật toán đẩy một giá trị vào Stack và thuật toán loại bỏ một phần
tử khỏi Stack.
Giải:
{Khai bao Stack}
const max=100;
type nx=record
top:integer;
a:array[1 max] of integer ;
end;
{ day mot phan tu vao ngan xep}
Procedure them(var S:nx; x:integer);
begin
if (s.top=max) then write(‘Stack da day’)
else
begin

top:=0 max;
a: array[1 max] of integer;
end;
{khai bao mang}
type mang=array[1 100] of string;
{CTC day mot phan tu vao ngan xep}
procedure them(var s:nx; x: integer);
{CTC loai bo mot phan tu khoi ngan xep}
procedure loai( var s:nx; x:integer);
{CTC tinh bieu thuc dang hau to}
procedure hauto( a: mang);
var
begin
writeln(‘Nhap bieu thuc dang hau to. Nhan E de ket thuc nhap’);
repeat
write(‘Nhap toan tu hoac toan hang: ‘); readln(a[i]);
val(a[i], x, loi);
if loi<>0 then
them(s,x)
else
begin
loai(s,t);
loai(s,m);
ch=a[i];
case ch of
‘^’ : z:= exp(t*ln(m)); {Z=m^t}
‘*’ : z :=m*t;
‘/’ : z :=m/t;
‘+’ : z :=m+t;
‘-’ : z :=m-t;

n:=n+1;
end;
Câu số 17
Trình bày thuật toán ghép 2 mảng đã được sắp xếp thành một mảng mới
được sắp xếp.
Giải:
- G/sử ghép 2 mảng a có n phần tử và mảng b có m phần tử được sắp
xếp tăng
- Dùng mảng c để lưu mảng sau khi trộn. Mảng c có n+m phần tử
- So sánh 2 phần tử đầu của mảng a và mảng b. phần tử nào nhỏ hơn
được đưa vào mảng c và loại bỏ phần tử đó khỏi mảng gốc. tiếp tục
cho đến khi loại bỏ hết phần tử ở một mảng a hoặc b.
- Chuyển phần tử còn lại vào mảng c
CTC trộn 2 mảng theo ý tưởng trên:
{ctc tron}
type mang=array[1 100] of real;
CTDL&GT - 18 -
Khoa CNTT  Trường CĐCN Việt Đức
procedure tron(a:mang; n:integer; b:mang; m:integer; c: mang);
var i,j,t,k:integer;
begin
i:=0; j:=0; k:=0;
while (i<n and j<m) do
if(a[i]<=b[j])
begin
c[k]:=a[i];
i:=i+1;
k:=k+1;
end
else

{ Tron}
Procedure tron(var a:mang; n: integer; b:mang;m: integer);
Var i:integer;
begin
for i=0 to i<m do
chen(a,n,b[i]);
end;
Câu số 18
Mô tả cách dùng ngăn xếp để chuyển đổi cơ số? Viết CTC chuyển đổi 1 số
từ hệ thập phân sang hệ nhị phân dùng ngăn xếp?
Giải:
1. Mô tả cách dùng ngăn xếp để chuyển đổi cơ số
Ta dùng một stack (ngăn xếp) để lưu trữ số dư qua từng phép chia: Khi thực
hiện phép chia thì nạp số dư vào ngăn xếp. Sau đó lấy chúng lần lượt từ ngăn xếp
ra để hiển thị sẽ được số cần chuyển đổi.
2. CTC chuyển đổi 1 số từ hệ thập phân sang hệ nhị phân dùng ngăn xếp
const max=100;
type nx=record
top:integer;
a:aray[1 max] of integer;
end;
{ them vao nx}
Procedure them(var s:nx; x:integer);
begin
if(s.top=max) then write(‘Stack da day’)
else
begin
s.top:=s.top+1;
s.a[s.top]:=x;
end;

end ;
Câu số 19
Trình bày thuật toán chèn thêm một nút mới vào cây tìm kiếm nhị phân. Lấy
ví dụ minh họa.
Giải:
Việc thêm một một nút có trường khoá bằng x vào cây phải đảm bảo điều
kiện ràng buộc của Cây TKNP. Ta có thể thêm vào nhiều chỗ khác nhau trên cây,
nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiện quá trình
tương tự như thao tác tìm kiếm. Khi kết thúc việc tìm kiếm cũng chính là lúc tìm
được chỗ cần chèn.
Giải thuật đệ quy
Type keytype =array[1 max] of real; {kiểu dữ liệu của mỗi nút}
Tree = ^ node;
Node = record
Info : keytype;
Left, Right : Tree;
end;
Procedure Insert (var Root :Tree; x: kkeytype);
Var p : tree;
CTDL&GT - 21 -
Khoa CNTT  Trường CĐCN Việt Đức
Begin
New(p);{Tạo ra nút mới}
P^.info := x;
if root=nil then
begin
Root :=p;
P^.left:= nil;s
P^.right:= nil;
End

CTDL&GT - 22 -
Khoa CNTT  Trường CĐCN Việt Đức
else begin
q^.left :=p;
p := nil;
end
else if x > q^.info then
if q^.right <> nil then q:=q^.right
else begin
q^.right :=p;
q =nil;
end;
end;
end;
Ví dụ: Để dựng được cây TKNP ứng với một dãy khoá đưa vào bằng cách
liên tục bổ các nút ứng với từng khoá, bắt đầu từ cây rỗng. Ban đầu phải dựng lên
cây với nút gốc là khoá đầu tiên sau đó đối với các khoá tiếp theo, tìm trên cây
không có thì bổ sung vào.
Ví dụ với dãy khoá: 42 23 74 11 65 58 94 36 99 87
thì cây nhị phân tìm kiếm dựng được sẽ có dạng ở hình dưới đây
Trình bày thuật loại bỏ một nút khỏi cây tìm kiếm nhị phân. Lấy vi dụ minh
họa.
Giải:
Đối lập với phép toán chèn vào là phép toán loại bỏ. Chúng ta cần phải loại
bỏ khỏi Cây TKNP một đỉnh có khoá x (ta gọi tắt là nút x) cho trước, sao cho việc
huỷ một nút ra khỏi cây cũng phải bảo đảm điều kiện ràng buộc của Cây TKNP.
Có ba trường hợp khi huỷ một nút x có thể xảy ra:
• X là nút lá
• X là nút nửa lá ( chỉ có một con trái hoặc con phải)
• X có đủ hai con (trường hợp tổng quát)

Info : keytype;
Left, Right : Tree;
end;
procedure Del (var Q: Tree); {xoá nút trỏ bởi Q}
var T, S : Tree;
begin
P := Q; {Xử lý trường hợp nút lá và nút nửa lá}
if P
^
.left = nil then
Begin
Q:=P
^
.right ;{R
^
.left := P
^
.right}
Dispose(P);{Đây là thủ tục thu hồi bộ nhớ của biến động}
end
else
if P
^
.right = nil then
begin
Q :=P
^
.left;
Dispore (P);
end

S := T
^
.right;
end;
S
^
.right := P
^
.right;
T
^
.right := S
^
.left;
S
^
.left := P
^
.left;
Q:=S;
Dispose(p);{Tìm nút thay thế, là nút cực phải của cây }
end;
end;
end;
Thủ tục xoá nút dữ liệu bằng X
Tìm đến nút có trường dữ liệu bằng X
Áp dụng thủ tục Del để xoá
Sau đây chúng ta sẽ viết thủ tục loại khỏi cây gốc Root đỉnh có khoá x cho
trước. Đó là thủ tục đệ qui, nó tìm ra đỉnh có khoá x, sau đó áp dụng thủ tục Del để
loại đỉnh đó ra khỏi cây.

1
R
Q
T
S
a) Cây trước khi xoá nút trỏ bởi Q
T
5
A
E
B
T
4
C
T
2
T
1
R
Q
T
S
T
3
b) Cây sau khi xoá nút trỏ bởi Q