CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
I. Phần câu hỏi.
1. Xác định độ phức tạp tính toán của đoạn chương trình con sau:
Function Tong(n:word): longint;
Var i:word; S:longint;
Begin
I:=1;
S:=0;
While i<=n do
Begin
S:=S+sqr(i);
i:=2*i;
end;
Tong:=S;
End;
2. Cho cây nhị phân hoàn chỉnh được lưu trữ kế tiếp bởi mảng A gồm 10 phần
tử, với giá trị A[1], A[2],…,A[10] lần lượt là: 7, 5, 10, 3, 6, 8, 12, 1, 4, 2. Vẽ cây này và cho biết
đây có phải là cây nhị phân tìm kiếm hay không? Tại sao?
II. Phần lập trình
Câu 1.
Tại một công ty, người ta quản lý các thành phố trên toàn quốc có mở đại lý cho công ty bằng cách
sử dụng một danh sách liên kết đơn (mà người ta gọi là danh sách thành phố) với nút đầu được trỏ bởi con
trỏ First. Mọi nút của danh sách thành phố là một bản ghi gồm 3 trường: trường TenThanhPho để lưu tên
thành phố, trường Down lưu địa chỉ nút tiếp theo, và trường DSDaiLy lưu địa chỉ nút đầu của một danh
sách khác chứa thông tin các đại lý trong thành phố đó (gọi là danh sách đại lý). Mỗi nút của danh sách
đại lý là một bản ghi gồm 4 trường: TenDaiLy (tên đại lý), SDT (số điện thoại), DoanhThu (doanh thu)
và con trỏ Tiep trỏ đến đại lý tiếp theo. Lưu ý rằng:
- Danh sách thành phố được sắp theo thứ tự tăng dần của TenThanhPho
- Cho biết khai báo của cấu trúc dữ liệu nói trên như sau:
Type st25 = string[25];
St8 = string[8];

NutTrenCay = Record
GiaTri: integer;
Left, right: TroNutTrenCay;
End;
Var Top: TroNutTrenCay;
a. Viết hàm Function Chieucao(top:TroNutTrenCay): word; trả về giá trị là chiều cao của cây nhị
phân Top.
b. Để biểu diễn một hàng đợi người ta có thể sử dụng một danh sách liên kết kép với nút đầu (lối
trước) và nút cuối (lối sau) lần lượt bởi trỏ First và Last. Ngoài ra mỗi nút trên danh sách này còn
có thể lưu thông tin của một nút trên cây nhị phân Top. Cụ thể ta có khai báo bổ sung như sau:
Type TroNutTrenDS = ^NutTrenDS;
NutTrenDS = record
Info: NutTrenCay;
Before, next: TroNutTrenDS;
End;
Var First, last: TroNutTrenDS;
Viết hai thủ tục:
Procedure ChenQ(var first, last: troNutTrenDS; X: NutTrenCay;); để bổ sung một nút
mà trường info có giá trị bằng X tại vị trí lối sau Last
Procedure DelQ(var first, last: TroNutTrenDS; var X: nutTrenCay); để loại bỏ một
nút tại vị trí lối trước first và gán giá trị trường info của nút này cho tham biến X.
c. Viết thủ tục Procedure LietKe(Top: TroNutTrenCay); nhằm liệt kê giá trị của info.giatri tại mỗi
nút trên cây nhị phân Top với yêu cầu:
- Thứ tự các nút được liệt kê giá trị là theo thứ tự tăng dần của mức các nút trên cây.
- Các nút có cùng mức sẽ được liệt kê theo thứ tự từ trái sang phải.
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT K25 (Đề lẻ).
Phần câu hỏi:
1. Xác định độ phức tạp tính toán của đoạn chương trình sau theo n và p;
I:=1; S:=0;
While i<=sqrt(n) do

được trỏ bởi p^.dssdt, trong đó P là trỏ vào một nút thuộc danh sách List.
c. Viết thủ tục Del_Node(name: str10); để xóa nút thuộc danh sách list có tên được chỉ trong
biến name.
Câu 2.
Xét cây nhị phân tìm kiếm, mỗi nút trong cây có dữ liệu kiểu Banghi có khai báo:
Type contro: banghi;
Banghi= record
Left, right: contro;
Info: real;
End;
a. Viết hàm GTLN(T: contro); cho kết quả là giá trị lớn nhất của trường info của tất cả các nút trong
cây T (nút gốc trỏ bởi T), biết rằng T khác nil.
b. Xét một danh sách nối kép có nút đầu và nút cuối trỏ bởi con trỏ first và last cùng có kiểu
CONTRO (trường Left trỏ đến nút trước và trường Right trỏ đến nút sau).
Viết thủ tục Bosungdau(X: real; var first, last: contro); để bổ sung vào đầu danh sách này một nút
mới sao cho trường Info có giá trị bằng X.
c. Từ cây T ở trên, hãy viết thủ tục
Tao_DS_Noikep(T: contro; Var first, Last: contro); để tạo mới một danh sách nối kép có
nút đầu trỏ bởi con trỏ First, nút cuối trỏ bởi con trỏ Last, và trường Info của các nút trong danh sách
này phải được sắp xếp theo thứ từ giảm dần.
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT K25 (Đề 1).
Câu 1.
Tính độ phức tạp tính toán của giải thuật sau:
Function NguyenTo(n:word): boolean;
Var j,k: word;
Begin
K:=trunc(sqrt(n));
J:=2;
While (j<=k) and(n mod j <>0) do
Inc(j);

- Nếu môn thi Bmon chưa có trong danh sách thì bổ sung môn thi trước rồi mới bổ sung thành tích
của đoàn sau này.
CẤU TRÚC DỮ LIỆU TINK26
Câu 1.
Ban chủ nhiệm khoa CNTT quản lý các lớp sinh viên bằng một danh sách liên kết có nút đầu được
trỏ bởi first. Cấu trúc danh sách khai báo như sau:
Type st4 = string[4];
St6 = string[6];
St20 = string[20];
troSV= ^Sinhvien;
sinhvien = record
hoten: st20;
email: string;
tiep: troSV;
end;
troLop=^Lop;
lop =record
malop: st4;
loptruong: st20;
sdt: byte;
next: troSV;
down: troLop;
end;
Var first: troLop;
Chú ý: các lớp sinh viên trong một lớp được sắp theo thứ tự họ tên (giả thiết trong lớp không có hai sinh
viên cùng tên) và danh sách này luôn khác rỗng.
Viết các thủ tục sau:
a. Procedure Loaibo(bma: st4; bhten:st20); thực hiện việc xóa một sinh viên ở lớp có mã là bma
với họ tên là bhten ra khỏi danh sách lớp.
b. Procedure DSLoptruong; thực hiện in thông tin lớp trưởng của tất cả các lớp trong Khoa (gồm

Left Makhoa First Right