ĐỀ SỐ 1

Câu I :

Cho hàm số f(m,n) với m,n là các đối số kiểu nguyên như sau :

a)Tính F(5), giải thích cách tính

b) Viết thủ tục đệ qui để tính hàm F.

Hướng dẫn:

A, Tớnh 5,giải thớch cỏch tớnh.

F(5)=5*5 + F(4)

F(5)=5*5 + 4*4+F(3)

F(5)=5*5 + 4*4 + 3*3 + F(2)

F(5)=5*5 + 4*4 + 3*3 + 2*2 + F(1)

F(5)=5*5 + 4*4 + 3*3 + 2*2 + 1*1 +F(0)

F(5)=5*5 + 4*4 + 3*3 + 2*2 + 1*1 + 0*0 + F(-1)(đây la trường hợp suy biến )

F(5)=25 + 16 + 9 + 4 + 1 + 0 + 1=56

B, Hàm đệ quy tớnh hàm F.

Function F(t:byte):logint;

begin

if (t<0)then H:=abs(t)

else H:=t*t + F(t-1) ;

end;

Câu II :

a) Cho dãy số: 7 9 5 -2 1 4 -5. Hãy minh hoạ việc sắp xếp dãy số trên theo chiều tăng dần bằng phương pháp chèn trực tiếp (còn gọi là phương pháp thêm dần).

b) Viết chương trình nhập một dãy X có n số thực, sắp xếp dãy X theo chiều giảm dần bằng phương pháp nói trên rồi in kết quả ra màn hình.

Hướng dẫn

A, Minh hoạ việc sắp xếp dóy bằng phương pháp thêm dần trực tiếp.

Lần sắp X1 X2 X3 X4 X5 X6 X7

7 9 5 -2 1 4 -5

Lần 1 7 9 5 -2 1 4 -5

7 9| 5 -2 1 4 -5

Lần 2 7 9 9 -2 1 4 -5

5 7 9| -2 1 4 -5

Lần 3 5 7 9 9 1 4 -5

-2 5 7 9| 1 4 -5

Lần 4 -2 5 7 9 9 4 -5

-2 1 5 7 9| 4 -5

Lần 5 -2 1 5 7 9 9 -5

-2 1 4 5 7 9| -5

Lần 6 -2 1 4 5 7 9 9

-5 -2 1 4 5 7 9

B,Viết chương trinh nhập một day số X co : n số thực, sắp day theo chiều giam dần bằng phương phap chốn trực tiếp rồi in kết quả ra màn hỡnh.

program insertion_sort;

uses crt;

type day_so=array [1..50] of longint;

procedure insertion_sort(var x:day_so; n:byte);

var i,j:byte; t:longint;

begin

for i:=1 to n-1 do

begin

j:=i ; t:=x[i+1];

while (j>0) and (x[j]>t) do

begin

x[j+1]:=x[j]; j:=j-1;

end;

x[j+1]:=t;

end;

end;

var n,i,l,r:byte ; a:day_so;

begin

clrscr;

write('nhap so luong phan tu can sap n='); readln(n);

writeln('nhap cac phan tu:');

for i:=1 to n do

begin

write('a[',i,']='); readln(a[i]);

end;

insertion_sort(a,n);

write('day so sau khi sap xep:');

for i:=1 to n do

write (' ',a[i]);readln;

end.

Câu 3:

Cho danh sách thí sinh dự thi, mỗi thí sinh có các thông tin: Số báo danh, họ và tên, năm sinh, điểm toán, điểm lý, điểm hoá, tổng điểm (TĐ = ĐT + ĐL + ĐH).

a) Hãy biểu diễn CTDL của danh sách nói trên dưới dạng một danh sách liên kết đơn.

b) Dựa vào CTDL đã biểu diễn ở trên hãy viết các thủ tục thực hiện các yêu cầu sau:

+ Nhập danh sách n thí sinh (cho n là số nguyên dương).

+ Tìm và in ra những thí sinh có tổng điểm >= 20.

+ Loại bỏ những thí sinh có tổng điểm bằng 0.

Hướng dẫn :

program de_4;

uses crt;

const max=1000;

type ts=record

ten:string[25];

ns:byte;

dt,dl,dh,td:real;

end;

list=record

A:array[1..1000] of ts;

end;

var l:list;n:byte;

procedure nhap_ds(var l:list;n:byte);

var i:byte;x:ts;

begin

for i:=1 to n do

begin

writeln('nhap thi sinh thu',i);

write('nhap ten: ');readln(x.ten);

write('nhap diem toan: ');readln(x.dt);

write('nhap diem ly: ');readln(x.dl);

write('nhap diem hoa: ');readln(x.dh);

x.td:=(x.dt*2 + x.dl + x.dh

l.a[i]:=x;

end;

end;

Function tim_kiem(var l:list):boolean;

var i:byte;

begin

if (n=0) then tim_kiem:= false

else

begin

for i:=1 to n do

if(l.A[i].td >= 20)then

writeln('thi sinh thu',i,l.A[i].ten,l.A[i].td:3:1);

tim_kiem:=true;

end;

end;

Function insert(var l:list; x:ts; k:byte ):boolean;

var i:byte;

begin

if (k<1) or (k>n) then insert:=false

else

begin

n:=n+1;

for i:=n downto k do

begin

l.A[i]:=l.A[i-1];

end;

writeln('nhap thong tin cua thi sinh can chen ');

write('nhap ten: ');readln(x.ten);

write('nhap diem toan: ');readln(x.dt);

write('nhap diem ly: ');readln(x.dl);

write('nhap diem hoa: ');readln(x.dh);

x.td:=(x.dt*2 + x.dl + x.dh

l.a[k]:=x;

insert:=true;

end;

end;

var k,i:byte;x:ts;

begin

clrscr;

write('nhap so luong thi sinh n=');readln(n);

nhap_ds(l,n);

writeln('thi sinh co tong diem >=20 la :');

tim_kiem(l);

write('nhap vi tri thi sinh can chen k: ');readln(k);

insert(l,x,k);

writeln('danh sach sau khi bo sung 1 thi sinh vao vi tri thu ',k );

for i:=1 to n do

writeln ('thi sinh thu',i,l.A[i].ten);

readln;

end.