2-daraja testi: Kumush

2-darajaKumush — usullar9–16 darslar

Yigirma savol, 9–16 darslar bo’yicha. Bu darajada savollar ko’proq «qaysi asbobni olasiz» va «nega bu to’g’ri» degan turdan — aynan olimpiadada beriladigan savollar.

Usul tanlash

1Ro'yxatda takrorlangan element bormi? n ≤ 200000. Qaysi asbob? A) Ro'yxatda in B) To'plam C) Ikkilik qidiruv D) Stek

Javobni ko'rish

B. To’plamda qidirish narxi o’zgarmas. Ro’yxatda in yozilsa yechim jimgina O(n²) bo’lib qoladi. (9-dars)

2Saralangan ro'yxatda yig'indisi X bo'lgan juftlik. Qaysi usul? A) Har juftni ko'rish B) Ikki ko'rsatkich C) Stek D) Deque

Javobni ko'rish

B. Ikki chetdan boshlab o’rtaga yurish — O(n). Saralanganlik aynan shu usul uchun kerak. (10-dars)

3Har element uchun o'ngdagi birinchi katta element. Qaysi tuzilma? A) Navbat B) Stek C) To'plam D) Prefiks yig'indi

Javobni ko'rish

B. Monoton stek. O’ngdan chapga yurilganda stekda faqat «hali kerak bo’lishi mumkin» bo’lganlar qoladi. (11-dars)

4Har k uzunlikdagi oyna uchun maksimum. Qaysi tuzilma? A) Stek B) Deque C) To'plam D) Lug'at

Javobni ko'rish

B. Dequeda indekslar kamayuvchi qiymat tartibida saqlanadi, boshidagi — joriy maksimum. (12-dars)

5«Eng kam vaqt shuncha bo'lsin» turidagi masala. Javobni hisoblash qiyin, tekshirish oson. Qaysi usul? A) Ochko'zlik B) Saralash C) Javob bo'yicha ikkilik qidiruv D) Prefiks

Javobni ko'rish

C. Javobni qurmaymiz — taxmin qilib tekshiramiz. (13-dars)

6Eng ko'p to'qnashmaydigan intervalni tanlash. Nima bo'yicha saralanadi? A) Boshlanish vaqti B) Tugash vaqti C) Uzunlik D) Tasodifiy

Javobni ko'rish

B. Eng erta tugaydigan interval resursni eng erta bo’shatadi va qolganlarga eng ko’p joy qoldiradi. (14-dars)

7Navbat kerak. Nima ishlatasiz? A) list.pop(0) B) deque.popleft() C) list.pop() D) To'plam

Javobni ko'rish

B. list.pop(0) butun ro’yxatni suradi — O(n) har chaqiruvda. BFS aynan shu belgi tufayli yiqiladi. (12-dars)

Murakkablik bahosi

8korilgan = [] va ichida x in korilgan. Yechimning murakkabligi? A) O(n) B) O(n log n) C) O(n²) D) O(1)

Javobni ko'rish

C. Ro’yxatdagi in uzunlikka proporsional. Bitta so’z — set() — uni O(n) ga tushiradi. (9-dars)

9Sirpanuvchi oynada ichki while bor. Yechim O(n²) mi? A) Ha B) Yo'q, chunki chap faqat oldinga yuradi C) Ha, agar oyna katta bo'lsa D) Bog'liq emas

Javobni ko'rish

B. chap butun ishlash davomida ko’pi bilan n qadam yuradi, demak ichki sikl jami n martadan ko’p aylanmaydi. (10-dars)

10Monoton stekda ichki while bor. Nechta pop() bo'lishi mumkin? A) n² B) n log n C) Ko'pi bilan n D) Cheksiz

Javobni ko'rish

C. Har element stekka bir marta kiradi va bir marta chiqadi. (11-dars)

11Javob bo'yicha ikkilik qidiruvda yetadimi() narxi O(n), javob oralig'i 10⁹. Jami? A) O(n) B) O(n log n) C) O(n · 30) D) O(n²)

Javobni ko'rish

C. log₂(10⁹) ≈ 30, ya’ni yetadimi() 30 marta chaqiriladi. Tekshiruv funksiyasi ham tez bo’lishi kerakligi shundan. (13-dars)

12Intervallar masalasida ochko'z yechimning murakkabligi nimadan kelib chiqadi? A) Sikldan B) Saralashdan C) Taqqoslashdan D) Xotiradan

Javobni ko'rish

B. Sikl O(n), saralash esa O(n log n) — umumiy baho eng qimmat qismga qarab beriladi. (14-dars)

Xato topish

13Dequeda indekslar emas, qiymatlar saqlandi. Qachon xato chiqadi? A) Hech qachon B) Oyna kichik bo'lsa C) Takrorlangan qiymatlar bo'lsa D) Sonlar manfiy bo'lsa

Javobni ko'rish

C. Elementning oynadan chiqib ketganini faqat o’rni orqali bilish mumkin; bir xil qiymat ikki joyda uchrasa ajratib bo’lmaydi. (12-dars)

14Ikki ko'rsatkichda yig'indi kichik bo'lganda ikkala ko'rsatkich ham surildi. Oqibat? A) Cheksiz sikl B) Ba'zi juftliklar ko'rilmay qoladi C) Xato xabari D) Sekinlashadi

Javobni ko'rish

B. Yechim yiqilmaydi, shunchaki ba’zi javoblarni o’tkazib yuboradi. Shuning uchun xato uzoq yashirin qoladi. (10-dars)

15Qavslar tekshiruvida satr oxirida stek bo'sh ekani tekshirilmadi. Qaysi kirishda xato chiqadi? A) () B) (( C) (] D) )(

Javobni ko'rish

B. Ikkita qavs ochiq qoladi, lekin hech qanday nomuvofiqlik yo’q — yechim «to’g’ri» deb javob beradi. (11-dars)

16Kadane usulida joriy nolga tashlandi. Qaysi testda xato chiqadi? A) Barcha sonlar musbat B) Barcha sonlar manfiy C) n = 1 va son musbat D) Sonlar aralash

Javobni ko'rish

B. Javob 0 chiqadi, ya’ni «hech narsa tanlamadim» — shart esa bo’sh bo’lmagan oraliqni talab qiladi. (15-dars)

17Javob bo'yicha ikkilik qidiruvda yetadimi(orta) rost bo'lganda chap = orta + 1 yozildi. Natija? A) Cheksiz sikl B) Xato xabari C) Eng kam emas, eng ko'p qiymat chiqadi D) Javob to'g'ri

Javobni ko'rish

C. Yo’nalish teskari qilingan: yetarli qiymatlar tashlanadi va qidiruv yuqori chegaraga suriladi. (13-dars)

18Intervallar uzunlik bo'yicha saralandi. Nega yiqiladi? A) Sekin B) Qisqa interval ikki uzunning o'rtasiga tushib ikkalasini buzadi C) Saralash noto'g'ri D) Yiqilmaydi

Javobni ko'rish

B. Bitta qisqa olinadi, ikkitasi yo’qoladi. (0,4), (3,5), (4,8) — eng oddiy misol. (14-dars)

Isbot

19Stress-test 500 testda farq topmadi. To'g'ri xulosa qaysi? A) Yechim to'g'ri B) Yechimda xato yo'q C) Ishonch ortdi, isbot yo'q D) Generator yaxshi

Javobni ko'rish

C. Testlar xatoning borligini ko’rsatadi, yo’qligini emas. Generator yasay olmagan holatdagi xato ham chiqmaydi. (15-dars)

20Ochko'z yechim uchun almashish argumenti nimani ko'rsatadi? A) Yechim tez ishlashini B) Optimal yechimni ochko'z yechimga aylantirganda u yomonlashmasligini C) Testlarda o'tishini D) Kod qisqaligini

Javobni ko'rish

B. Shu sababli ochko’z yechim ham optimal bo’ladi. Isbot hech qanday testga tayanmaydi. (16-dars)

Keyingi qadam

To’rttadan ko’p xato qilgan bo’lsangiz, mos darslarni qayta oching: 9-dars · 10-dars · 11-dars · 12-dars · 13-dars · 14-dars · 15-dars · 16-dars.

13-dars savollarida xato qilgan bo’lsangiz, uchinchi darajaga o’tishdan oldin uni albatta qaytaring: javob bo’yicha ikkilik qidiruv keyingi darajalarda qayta-qayta uchraydi va u eng ko’p ball keltiradigan bitta g’oya.