lí thuyết.

1:cài dặt bằng mảng.
2:cài đặt bằng con trỏ.
3:cây.
4:danh sach lien ket kép.
6:hàng đợi.

Bắt đầu ôn:
Câu 1( 3 điểm)
1) Th  liu tinh sn ) c lc cao?
2)  liu tinh c l ) bit?
3) Ti sao ch s dng c liu tinh   u v vic t
ch d liu ca mng dng thc t ?. Mt s ng dng
phi cn s du  lii l ? 
mng d th hi

Câu 1
1) C liu tinh c ng l lic 
sn trong  lp i l vic s di (1 đ)
3) M liu ting, bn ghi, tp tin, (1 đ)
 liu ti ly  c nhu cu
 d liu ln ca mi  bn cht cng d li
trong thc t i ta c lii l . (0.5 đ)
 u qu 
  dng c liu mng (c  h 
c hi
  tt c h u s ng h c t l (0.5 đ)
Câu 1( 2 điểm)
 quy phn thu tru
 )  minh ha ?

nut = record
infor: item;
next:list;
end;
var l,f:pqueue;
  qu 
Ưu nhược điểm của từng các cài đặt danh sách: (0.5 đ)
a) i mng
Ưu điểm
i. truy cn t c tip i vi mi phn
t
ii. c hii d 

Nhược điểm
iii. a b nh: Hing gi ch  i
iv. B hn ch b tip trong b nh
v.  li gii hn  nh trong thanh ghi d li
thanh ghi stack
vi. ch chuyn t khi thc hi sung
phn t, hoc loi b phn t         i thut
 phc theo
b) t bi con tr
Ưu điểm:
-  nh (Hing gi ch  
t bi mng)
- C lit bi con tr ng,
 nh c c gii hn b
i vi c li
- n t m  nhng v n dc
nhn m k tit bi

Type list = record
Ele: array[1 n]of integer;
Count: 0 n;
end;
Var L: list;
 tng vu:
1) ng c  (0.5 đ)
function Trungbinh(l:list): integer;
var i, tam: integer;
Begin
for i:=1 to n do tam:= tam+L.Ele[i];
Trungbinh:=tam;
End;
2) Loi b s  (1 đ)
procedure Loaibo(var L: list);
var k,i:integer; found: boolean;
Begin
found:= false;
k:=1;
while (not found)and(k<=L.count) do
if(L.Ele[k]=3) then
begin
for i:=k to L.count-1 do L.Ele[i]:=L.Ele[i+1];
L.count:= L.count -1;
end;
if (not found) then writeln(‘So 3 khong co trong danh sách để loại bỏ’);
End;
3) Hin th  (1 đ)
procedure Hienthi(l:list);
var i: integer;

+ Tc sinh: (1 đ)
procedure taoDS(var l:list);
var M: hocsinh;
begin
write(’nhap so hoc sinh trong danh sách n= ’); readln(n);
for i:=1 to n do
begin
writeln(‘Nhap hoc sinh thu i : ’);
write(‘Nhạp ho ten: ’); readln(M.Hoten);
write(‘Nhạp Lớp: ’); readln(M.lop);
write(‘Nhạp Điem tong kết: ’); readln(M.DiemTK);
insert(M,i,L);
end;
end;
 p:TH2B         t u danh
 (1 đ)
procedure insert (M: hocsinh, k: integer, var L: list);
var i: integer;
begin
i:=L.count;
while i>k do
begin
L.Eles[i]:=L.Eles[i-1];
i:=i-1;
end;
L.Eles[k]:= M;
L.count:=L.count +1;
end;
c khi gi th tp l c a hc sinh c
nh M

Giớitinh: boolean;
Diachi, trinhdo, chucdang: string;
` Next: ^ Canbo;
end;
List = ^Canbo;
Var L: List;
2) m s  trong  ( 1 đ)
- S dng bi ng  trong u dem:= 0 ,
- S dng con tr ph M duyt t n cun  

- In bi
3) Hin th  : ( 1 đ)
S dng con tr ph M duyt t n cun  hin
th  :
4) Loi b  n tui v : ( 1 đ)

 n tui v , gi s v c tr bi p
b2) Loi b   v 
b3) Lp ln khi ht v y
-   thu kin ta duyt t p:=L 
dng
-  loi b hc sinh  v p:
a) Di chuyn con tr ph n v c p:
 M:=L;
 While M^.next <>p do M:=M^.next;
b) Bt, gt, gi
 M^.next:=p^.next;
Dispose(p);
Câu 3( 4 điểm )
Hc sinh khi 12 d thi ht hc k i ng. Mn qu

writeln(‘Nhap hoc sinh thu i : ’);
M^.info.SBD:=SBD;
write(‘Nhạp ho ten: ’); readln(M^.info.Hoten);
write(‘Nhạp Lớp: ’); readln(M^.info.lop);
write(‘Nhạp Điem toan: ’); readln(M^.info.toan);
write(‘Nhạp Điemly: ’); readln(M^.infor.ly);
write(‘Nhạp Điem hoa: ’); readln(M^.infor.hoa);
write(‘Nhạp Điem NgoaiNgu: ’); readln(M^.info.ngoaingu);
M^.next := L;
L:= M;
i:= i+1;
end;
end;
b) Sp xng l tng l  01
(1 đ)
c) Loi b tt c m  <5 ra kh, bit r
+ ly+ hoa+ ngoaingu)/4: (1 đ)
 m trung  <5, gi s v 
b2) Loi b hc sinh  v 
b3) Lp ln khi ht v y
 -  c sinh thu kin ta duyt t y
ng
-  loi b hc sinh  v a di chuyn con tr n v n v c
K, thc hin loi b: q^.next:=p^.next; dispose(p);
  (0.5 đ)
- Nhp s 
- Duyt t n cuy, hoc duyng.
Duy i s u
bt luy, np theo trong danh


3) Procedure remove_first(var m: list; var L:list )(loi b phn t  ti
phn t sau khi b loi b kh (0.5 đ)

Begin
if (L<>nil) then M:=L; L:=L^.next;
End;
4) Procedure remove_last(var M:list; var L:list)(loi b phn t cu ti
u khi loi b kh(0.5 đ)
var p,q:list;
Begin
if L<>nil Then
Begin
p:=L; q:=p^.next;
while (q^.next<>nil) do
begin
p:q; q:=q^.next;
end;
M:=q; p^.next:=nil;
End;
End;
2) tạo một hàng đợi và một ngăn xếp chứa n phần tử (1 đ)
a)Tạo ngăn xếp
procedure taoNgănxep(var Top:list);
var n, i, x:integer;
Begin
writeln(‘Nhap n=’); readln(n);
for i:= 1 to n do
write(‘Nhạp gia trị =’); readln(x); insert_first(x, Top);
End;
b) Tạo hàng đợi

Info: Integer;
parent: 0 n;
End;
Tree = Array [1 n ] of Node;
Var T: Tree;
nh th k: (1 đ)
parent (T, k) := T[k].parent;
 cnh th  (1 đ)
Duy nh gc(i:=1), kim tra xem cha c
nu = k, kt lu, dng gii thut, nu cha cnh ting
p lng (found = true),
hoc duyt h t luy
Câu 3( 3 điểm ) 3
Cho m ca tc con 
Anh(ch
1) Vit dn k ca mnh, s dng con tr
2)  c c  t 
3)  c? \users \BT\
1 KB
Tin\
2 KB
Toan\
1KB
BT1

C:=C^.nextsibling;
While (C<>nil) do
Begin
postOrder(C);
C:= C^.nextsibling;
End;
Tong:=tong+T^.kichco;
end;
End;
Câu 3( 3 điểm )
  u din biu thc sau:
3*4+(12+b)/6
T u thc va dng, anh (ch
1) Vit dng con tr,
2) Vit th tc duy t c, sau
3) Vit biu thi dng tin t, hu t? nhi kt qu duy
theo th t c, sau?
Lg: Câu 3
Dựng cây: (0.5 đ)

1) Dt: (0.5 đ)
Type Tree=^nut;
Nut= record
Info: string;
Left, right: Tree;
End;
Var T: Tree;

Câu 3 (2 điểm)
Cho m : 15
10
21
12
0
31
45
9
1
2
3
4
5
6
7

Anh (ch
a mnh (vit d
 nh)
2) D  nh c
c nh t  

Câu 3(bài làm)
1) a mnh (1 đ)
* Dt
Const n= 50;


45

9
2) D  (1 đ)
Câu 3 (2 điểm):Anh (ch m(binary search tree)? Ti ta
l m thun ln vi
kii mnh ra khi 
 th hi
Lg: Câu 3
 m (0.5 đ) a mu kin:
u kinh c i gc
u kin 2: i gnh ci
15
10

- vic truy cc tip, t truy c
i vi mi phn t
Hn ch: - n ta b nh
t bi con tr
m: - a b nh
Hn ch: - Truy cn t p tun t, bao gi 
gc,  truy cm
-
Câu 2(4 điểm ):Cho m   t dt
ng con tr, gc cc tr bi con tr R. Vi dt th tc
 ng vu cu sau:
1) T u kin d 
2) C 
3) Loi b 
4) m s nh hi
lG: Câu 2
+ D dng con tr: (0.5 đ)
Type TreeBSearch = ^Nut;
Nut = Record
Infor: Integer;
Left, Right: TreeBSearch;
End;
Var R : TreeBSearch;
+ T m: (1 đ)
- Vit th t
* S dng con tr ph M cha ch cn 
* Xin MT c cho M
 d liu c a ch M
* G
Nng (R = nil): R := M