1 trang 21 lượt tải

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

42

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.

Môn: Nhập môn độ phức tạp thuật toán 8 tài liệu

Trường: Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh 779 tài liệu

Tác giả:

Profile

0136_Trần Thảo Vy

2 tháng trước
Danh sách Quiz
/1
Ñeà Thi
NHAÄP MOÂN PHAÂN TÍCH ÑOÄ PHÖÙC TAÏP THUAÄT TOAÙN
(120 phuùt, khoâng duøng taøi lieäu)
Caâu 1.
Xeùt hai haøm f(n)=20000n
3
+ 9000 vaø g(n)=n
4
– 700n
2
Chöùng minh: f=O(g) vaø g≠O(f)
Caâu 2.
Giaû söû n laø moät soá nguyeân döông. Xem thuaät toaùn sau ñaây:
count :=0; i:=n;
while i>0 do
if (i mod 3) = 1 then
count := count+1;
fi;
i := i – 6;
od;
a) Vôùi n=101 thì giaù trò cuûa bieán count laø bao nhieâu khi thuaät toaùn keát thuùc?
b) Goïi ∝ laø soá laàn thöïc hieän voøng laëp while. Xaùc ñònh theo ∝ vaø bieän luaän theo n soá pheùp
so saùnh vaø soá pheùp gaùn ñöôïc thöïc hieän
c) Tính ∝ theo n vaø xaùc ñònh ñoä phöùc taïp cuûa thuaät toaùn tuøy theo n.
Caâu 3.
Xem thuaät toaùn sau ñaây:
S:=0; i:= 1;
while i<=n do
j := 1;
while j <= i*i do
if j>=i then
S:=S+j;
fi;
j := j+1;
od;
i := i+1;
od;
a) Haõy öôùc löôïng soá pheùp gaùn, soá pheùp so saùnh cuûa thuaät toaùn
b) Xaùc ñònh ñoä phöùc taïp cuûa thuaät toaùn

Tài liệu khác của Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Preview text:

Ñeà Thi
NHAÄP MOÂN PHAÂN TÍCH ÑOÄ PHÖÙC TAÏP THUAÄT TOAÙN
(120 phuùt, khoâng duøng taøi lieäu) Caâu 1.
Xeùt hai haøm f(n)=20000n3 + 9000 vaø g(n)=n4 – 700n2
Chöùng minh: f=O(g) vaø g≠O(f) Caâu 2.
Giaû söû n laø moät soá nguyeân döông. Xem thuaät toaùn sau ñaây: count :=0; i:=n; while i>0 do if (i mod 3) = 1 then count := count+1; fi; i := i – 6; od;
a) Vôùi n=101 thì giaù trò cuûa bieán count laø bao nhieâu khi thuaät toaùn keát thuùc?
b) Goïi ∝ laø soá laàn thöïc hieän voøng laëp while. Xaùc ñònh theo ∝ vaø bieän luaän theo n soá pheùp
so saùnh vaø soá pheùp gaùn ñöôïc thöïc hieän
c) Tính ∝ theo n vaø xaùc ñònh ñoä phöùc taïp cuûa thuaät toaùn tuøy theo n. Caâu 3.
Xem thuaät toaùn sau ñaây: S:=0; i:= 1; while i<=n do j := 1; while j <= i*i do if j>=i then S:=S+j; fi; j := j+1; od; i := i+1; od;
a) Haõy öôùc löôïng soá pheùp gaùn, soá pheùp so saùnh cuûa thuaät toaùn
b) Xaùc ñònh ñoä phöùc taïp cuûa thuaät toaùn

Tài liệu liên quan: