Đề thi cuối kỳ học phần Nhập môn phân tích độ phức tạp thuật toán năm 2024 - 2025 | Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

NHAÄP MOÂN PHAÂN TÍCH THUAÄT TOAÙN
(120 phuùt, khoâng duøng taøi lieäu) Caâu 1
Thuaät toaùn tìm kieám sau ñaây xaùc ñònh xem coù maåu tin naøo trong maûng a (goàm n maåu tin a[1],
a[2], ..., a[n]) coù khoùa laø K hay khoâng. Giaû söû caùc maåu tin ñöôïc choïn ngaãu nhieân coù khoaù ñoâi moät phaân bieät. I := 1; success := 0;
while (i<=n) and (success=0) do if K=a[i].Key then success := i; endif; i := i+1; endw;
Haõy öôùc löôïng soá pheùp toaùn (pheùp gaùn vaø pheùp so saùnh soá hoïc, pheùp so saùnh khoùa) trung bình
cuûa thuaät toaùn trong caùc tröôøng hôïp sau:
a) Giaû söû a[i].Key=i2+i vaø K ñöôïc choïn ngaåu nhieân trong caùc soá nguyeân töø -n3 ñeán n3+n.
Tröôøng hôïp naøy khaû naêng “tìm coù” (töùc success ≠ 0) coù cao hôn khaû naêng “tìm khoâng coù” hay khoâng?
b) Giaû söû a[i].Key=i3 vaø K laø giaù trò ghi treân moät laù phieáu naøo ñoù ñöôïc choïn ngaåu nhieân töø caùc
laù phieáu ñöôïc ghi caùc soá nhö sau:
- n+1 phieáu coù giaù trò -2n, -2n-1 , -2n-2, ..., -2, -1
- goàm coù 4n phieáu coù giaù trò laø 1
- goàm coù 4n-1 phieáu coù giaù trò laø 2
- goàm coù 4n-2 phieáu coù giaù trò laø 3 - ...
- goàm coù 41 phieáu coù giaù trò laø n
(Taát caû nhöõng phieáu naøy ñöôïc xaùo troän ñeå vieäc boác phieáu mang tính ngaåu nhieân) Caâu 2
Giaû söû n laø moät soá nguyeân döông. Xem thuaät toaùn trong ñoaïn chöông trình C sau ñaây:
float Alpha(float x, long n) { long i=1; float z=0; while(i<=n){ long j=1; float t=1; while(j<=i){ t = t*x; j = 2*j; } z = z + i*t; i = i + 1; } return z; }
Haõy xaùc ñònh theo n soá pheùp gaùn vaø soá pheùp so saùnh ñöôïc thöïc hieän trong thuaät toaùn. Öôùc löôïng
ñoä phöùc taïp cuûa thuaät toaùn.
Document Outline

• Caâu 1
• Caâu 2