Đề 19
1/2
Đề thì tuyển Nghiên cứu sinh và Cao học 1996 (Đề 3)
Môn: Phương pháp lập trình
Thời gian: 120 phút – Được sử dụng tài liệu Câu 1. Người ta thực hiện thuật toán tìm kiếm nhị phân trên một bảng được sắp
xếp theo thứ tự tăng như sau:
Type ptu=record
Khoa:integer;
Info:string[20];
end;
Mang=array[1..100]of ptu;
Function tim(c:integer;var a:mang):integer;
Var trai, phai, giua:integer;
Begin
trai:=1;phai:=100;
Repeat
Giua:=(trai+phai)div 2;
if a[giua].khoa<c then trai:=giua;
Else phai:=giua;
Until (a[giua].khoa=c)or(trai>=phai);
if a[giua].khoa=c then tim:=giua
else tim:=0;
end;

1. Chương trình là đúng đắn nếu trong mọi trường hợp nó sẽ dừng và gán một
giá trị cho hàm tim như sau:
- 1≤tim≤100 nếu mảng a có phần tử a[tim].khoa=c.
- tim = 0 nếu trong mảng a không chứa phần tử có giá trị khóa bằng c.

…
z
Anglais 10 Anglais 5 Antivirus 100 ×AIDS 30
Brain 3 Block 10 ×
Computer 9 Connect 109
Zemple 9 ×
AIDS 30 ×
1.
Procedure Them(n:str25;tr:integer);

Thực hiện các công việc kiểm tra xem từ n có thuộc mảng từ khóa keyword
đã cho trước hay không. Nếu n không thuộc, không làm gì cả. Nếu n thuộc,
thì thêm từ n cùng với chỉ số trang tr vào cuối dánh sách tương ứng, được
xác định bởi chữ cái đầu tiên của n. Chú ý: không phần biệt chữ thường, chữ
hoa.
2.
Procedure Sapxep;

Nhằm sắp xếp lại các từ khóa trong từng danh sách của chỉ dẫn theo thứ tự
từ vựng của cặp (tên, trang):
- Đầu tiên sắp xếp theo thứ tự alphabet của tên.
- Sau đó, trong nhóm các từ khóa cùng tên (không phân biệt chữ hoa, chữ
thường), sắp xếp theo thứ tự tăng của chỉ số trang.
3.
Procedure Thaythe(u,v:str25);

Nếu từ u xuất hiện trong danh sách từ khóa keyword thì thay mọi xuất hiện
của u bởi v trong chỉ dẫn.
4.
Procedure Inchidan;