Đề 04
1/2
Đề thì tuyển Nghiên cứu sinh và Cao học
Môn: Phương pháp lập trình, CTDL và giải thuật
Thời gian: 180 phút Câu 1. Cho chương trình sau:
Program Chuyengiaomang(input,outphut);
Var i:integer;
A:arra ..2
Procedure p(var x,y:integre);
y[1 ]of interger;
Begin
{3} X:=x+1;
{4} Y:=y+1;
{5}
End;
Write(x,y);

BEGIN
{1} i:=1; A[1]:=2; A[2]:=0;
{2} P(i,a[a[i]]);
{7} writeln(i,a[1],a[2]);
{8} END.

a. Cho biết kết quả in ra.
b. Giải thích kết quả đó qua hành động của chương trình theo các bước từ {1}
đến {8}.

Bài 2. Giải thuật tìm kiếm nhị phân được thể hiện như sau:

Function copy(T:tro):tro;
Cho phép, với một cây có gốc
trỏ bởi T, lập một bản sao của cây đó (ở bộ nhớ trong) và cho lại địa chỉ của gốc
của cây mới này.

Bài 4. Với cây nhị phân được khai báo như ở bài 3, ta có thể tiến hành duyệt cây
theo một giải thuật không đệ quy theo sở đồ sau, trong đó có đúng một danh sách
tuyến tính để làm (các con trỏ tới) các nút cần ghi nhớ trong cây.

Nạp (con trỏ) gốc cây vào danh sách;
While danh sách không rỗng do
Begin
Lấy một nút từ danh sách, gọi đó là N;
Thăm N (chẳng hạn in giá trị của nó);
Nạp con trái của N vào danh sách (nếu có);
N
End;
ạp con phải của N vào danh sách (nếu có);

Tuy nhiên, tùy theo cách chọn nút N từ danh sách ra như thế nào, mà ta thành
lập được 2 giải thuật duyệt cây khác nhau:
- Giải thuật S (dùng stack): Lấy nút mới nhất (được nạp muộn nhất) trong
danh sách.
- Giải thuật Q (dùng queue): Lấy nút cũ nhất (đươc nạp sớm nhất) trong danh
sách.
a. Hãy cho biết các giải thuật S, Q duyệt cây sau đây theo các thứ tự nào?
1
2
3
4