Đề Thi cao học môn Cấu trúc Dữ liệu

DANH SÁCH MÓC NỐI



Biến động (Nút)
Cấu trúc cây nhị phân:









Đối với cây có ba phép duyệt:
Gốc – Trái – Phải
Trái – Gốc – Phải
Trái – Phải – Gốc
Ví dụ:



A BDE CFGH

2. Cây nhị phân tìm kiếm:
Là cây nhị phân chứa dãy khóa thỏa mãn điều kiện tại mỗi cây con thì khóa ở gốc lớn hơn khóa tại các nút của cây con trái của nó và nhỏ hơn khóa tại các nút của cây con phải của nó.
Ví dụ:








Nhận xét:
Duyệt cây theo phương án: Trái – Gốc – Phải : 5 9 11 15 16 17 19 25 cho dãy khóa theo thứ tự tăng dần. Như vậy việc tìm kiếm nút chứa khóa k. Nếu tìm có thì cho ra địa chỉ nút đó, nếu không thì cho ra địa chỉ NULL.
Function Timnut(T: Tro; K: Integer): Tro;
Var p: Tro;
Begin
P:= T;
While (p<> Nil) and (p^.Giatri <> k) do
If (p^.Giatri < k then p:= p^.Phai
Else
P:= p^.Trai;
Timnut:= p;
End;
Tìm theo đệ quy:
Function Timnut(T: Tro; k: Integer):Tro;
Begin
If (T=NIL) or (T^.Giatri= k) Then
Timnut:= T
Else
If (T^.Giatri > k) Then
Timnut: = Timnut(T^.Phai, k)
Else
Timnut:= Timnut(T^.Trai, k);
End;
2.1 Bổ sung thêm khóa K vào cây T (nếu chưa có nút nào chứa K):
Procedure Bosung(T: Tro; K: Integer);
Var p,r : Tro; OK: Boolean;
Begin
If (T=NIL) Then
Begin
New(T);
T^.Giatri: = k;
T^.Trai:= NIL;
T^.Phai:= NIL;
End
Else
Begin
P:= T; OK:= True;
While (p^.Giatri <> k) and OK do
If (p^.Giatri > k) Then
If (p^.Trai <> NIL) Then p:= p^.Trai else OK:= False
Else
If (p^.Phai <> NIL) Then p:= p^.Phai else OK:= False
If (p^.Giatri = k) Then Write(“Gia tri nay da ton tai”)
Else
Begin
New(r);
R^.Giatri:= k;
R^.Phai:= NIL;
R^.Trai:= NIL;
If (p^.Giatri > k) Then p^.Trai := r Else p^.Phai:= r;
End;
End;
End;

Đề thi năm 2003:
Câu 2: Người ta biểu diễn thông tin các câu lạc bộ bóng đá chuyên nghiệp của một quốc gia dưới dạng một cây nhị phân tìm kiếm có khóa là TenCLB (Tên câu lạc bộ). Mỗi nút của cây là một bản ghi gồm 4 trường: TenCLB và 3 trường con trỏ Left, Right, First. Hai con trỏ Left và Right lần lượt trỏ tới 2 nút con trái và con phải của nút đó. Con trỏ First trỏ bởi phần tử đầu của một danh sách liên kết đơn chứa thông tin các cầu thủ thuộc câu lạc bộ (danh sách này có ít nhất 11 phần tử). Mỗi phần tử con danh sách này là một bản ghi gồm 4 trường: TenCT (Tên cầu thủ), SoAo (số áo), Tuoi (tuổi), và Next (lưu địa chỉ của phần tử tiếp theo trong danh sách). Danh sách này được sắp theo thứ tự tăng dần của SoAo. Người ta cho khai báo cấu trúc dữ liệu nói trên như sau:

Type st25 = string[25];
TroCT = ^Cauthu;
Cauthu = Record
TenCT: St25;
SoAo, Tuoi: Byte;
Next: TroCT;
End;
TroCLB = ^Nut;
Nut = Record
TenCLB: St25;
First: TroCT;
L,R: TroCLB;
End;
Var Top: TroCLB;


Viết thủ tục in danh sách các cầu thủ trong câu lạc bộ có tên club.
Procedure List(Club: st25);
Var P: TroCLB; r: TroCT;
Begin
P:= Top;
While (p<> Nil) and (p^.TenCLB <> Club) do
If (p^.TenCLB > Club) Then p:= p