Yekun test bütün kursu bir yerə toplayır: mürəkkəbliyin qiymətləndirilməsi, struktur və alqoritm seçimi, əllə izləmələr və səhv axtarışı. O, hər birində üç cavab variantı olan 23 sualdan və 4 məşqçidən ibarətdir (interaktiv dərsdə: 15 sual və 4 məşqçi). Kodu işə salmadan cavab verin: müsahibədə də işə salmaq olmaz. Özünüzü sonra «Cavablar» bölməsində yoxlayın.
Testi necə keçmək
- 40-50 dəqiqə ayırın və konspektlərə baxmayın.
- Kodlu suala əvvəl dəyişənlərin qiymətlərini addım-addım yazın, sonra variant seçin.
- Mürəkkəblik suallarında
n-i və ən bahalı əməliyyatı adlandırın. - Cavabları sonda tutuşdurun. Hər yanlış cavab təkrar üçün mövzuya işarədir.
Suallar
Hissə 1. Mürəkkəblik
1. Mürəkkəblik?
for i in range(n):
for j in range(i):
pass- A)
O(n) - B)
O(n^2) - C)
O(n log n)
2. Mürəkkəblik?
while n > 1:
n //= 2- A)
O(log n) - B)
O(n) - C)
O(sqrt n)
3. Mürəkkəblik? (b siyahıdır)
for x in a: # a and b are lists of length n
if x in b:
count += 1- A)
O(n) - B)
O(n log n) - C)
O(n^2)
4. T(n) = 2T(n/2) + n rekurensiyasının həlli?
- A)
O(n) - B)
O(n log n) - C)
O(n^2)
5. n dəfə list.append çağırmaq: bir əlavənin amortizasiya qiyməti?
- A)
O(1): tutum həndəsi artır, nadir kopyalamalar bölüşdürülür - B)
O(n) - C)
O(log n)
6. Aşağıdakı kod neçə dəfə f gövdəsini icra edəcək?
from functools import lru_cache
calls = 0
@lru_cache(maxsize=None)
def f(n):
global calls
calls += 1
return 1 if n < 2 else f(n - 1) + f(n - 2)
f(10)
f(10)
print(calls)- A)
177 - B)
21 - C)
11
Hissə 2. Struktur və alqoritm seçimi
7. Növbənin əvvəlindən tez-tez element çıxarmaq lazımdır. Ən yaxşı seçim?
- A)
collections.deque - B)
listvəpop(0) - C)
heapq
8. Milyon ədəd axınından k ən kiçiyini O(k) yaddaşla tapmaq lazımdır.
- A) Hamısını saxlayıb çeşidləmək
- B) Ölçüsü
kolan maksimum heap - C)
setilə təkrarları atmaq
9. Mənfi olmayan çəkili qrafda ən qısa yol?
- A) BFS
- B) DFS
- C) Deykstra
10. Dəyişməyən verilənlərdə milyonlarla üzvlük yoxlaması üçün orta hesabla ən sürətli struktur?
- A)
set - B) çeşidlənmiş siyahı və
bisect - C) siyahı və
in
11. O(1) get və put ilə LRU keş üçün hansı struktur?
