Đề 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

Tài liệu đề 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 được sưu tầm và biên soạn dưới dạng PDF gồm 01 trang. Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đón xem.

Thông tin:
1 trang 1 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Đề 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

Tài liệu đề 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 được sưu tầm và biên soạn dưới dạng PDF gồm 01 trang. Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đón xem.

26 13 lượt tải Tải xuống
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=i
2
+i vaø K ñöôïc choïn ngaåu nhieân trong caùc soá nguyeân töø -n
3
ñeán n
3
+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=i
3
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ò -2
n
, -2
n-1
, -2
n-2
, ..., -2, -1
- goàm coù 4
n
phieáu coù giaù trò laø 1
- goàm coù 4
n-1
phieáu coù giaù trò laø 2
- goàm coù 4
n-2
phieáu coù giaù trò laø 3
- ...
- goàm coù 4
1
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.
| 1/1

Preview text:

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