4-daraja testi: Platina

4-darajaPlatina — dinamik programmalash25–32 darslar

Yigirma savol, 25–32 darslar bo’yicha. Bu darajaning asosiy ko’nikmasi — holatni to’g’ri ta’riflash. Savollarning yarmi shu haqda.

Holat va o’tish

1DP masalasida birinchi navbatda nima aniqlanadi? A) Formula B) Holat — dp[i] nimani anglatishi C) Murakkablik D) Kod tuzilishi

Javobni ko'rish

B. Holat noaniq bo’lsa o’tishni yozib bo’lmaydi. Formula holatdan keyin keladi. (26-dars)

2Memoizatsiya ishlashi uchun qanday shart kerak? A) Rekursiya B) Takroriy qism masalalar C) Katta xotira D) Saralangan kirish

Javobni ko'rish

B. Bir xil argument bir necha marta uchramasa, saqlashdan foyda yo’q. (25-dars)

3LIS masalasida dp[i] nimani anglatadi? A) Birinchi i ta son uchun javob B) i-son bilan TUGAYDIGAN eng uzun zanjir C) i-sondan boshlanadigan zanjir D) Umumiy javob

Javobni ko'rish

B. Shu ta’rif tufayli o’tishni yozish oson bo’ladi: chapdagi kichikroq sonlarning eng yaxshisiga bir qo’shiladi. (26-dars)

4Knapsackda holat nima? A) Narsalar soni B) Qolgan joy C) «i ta narsa ko'rildi va j joy ishlatildi» D) Umumiy qiymat

Javobni ko'rish

C. Ikki o’lchovli holat. Amalda i o’lchovi tashlanadi, chunki yangi qator faqat oldingisiga bog’liq. (27-dars)

5LCS jadvalida harflar mos kelmasa nima qilinadi? A) Diagonaldan olinadi B) Tepadagi va chapdagining kattarog'i olinadi C) Nol qo'yiladi D) Bir qo'shiladi

Javobni ko'rish

B. Diagonaldan olish ikkala harfni ham tashlash degani — bu ortiqcha yo’qotish. (29-dars)

6Jadval to'ldirish tartibining umumiy qoidasi nima? A) Chapdan o'ngga B) Har holat faqat allaqachon hisoblanganlarga suyanishi C) Tasodifiy D) Kichikdan kattaga

Javobni ko'rish

B. Panjarada bu chapdan o’ngga, daraxtda esa teskari tartibda degani. (28 va 23-darslar)

Murakkablik

7Naif rekursiv f(n) = f(n-1) + f(n-2) + f(n-3) da f(20) nechta chaqiruv qiladi? A) 20 B) 400 C) Taxminan 400 ming D) Milliard

Javobni ko'rish

C. Aniq son — 433 993. Memoizatsiya bilan 23 ta. (25-dars)

8Knapsackda holatlar soni qancha? A) 2ⁿ B) n × W C) n² D) n log n

Javobni ko'rish

B. DP tanlovlarni emas, holatlarni sanaydi — butun tejam shundan. (27-dars)

9LIS ni O(n log n) ga tushirish uchun nima ishlatiladi? A) Memoizatsiya B) Har uzunlik uchun eng kichik oxir + ikkilik qidiruv C) Fenwick D) DSU

Javobni ko'rish

B. oxir ro’yxati har doim o’suvchi bo’ladi, demak unda ikkilik qidiruv ishlaydi. (26-dars)

10DSU da har amal qancha vaqt oladi? A) O(n) B) O(log n) C) Deyarli o'zgarmas D) O(n log n)

Javobni ko'rish

C. Yo’lni siqish va o’lchamga qarab ulash birga ishlatilganda. (30-dars)

11Kruskalning murakkabligi qayerdan keladi? A) DSU dan B) Saralashdan C) Sikldan D) Xotiradan

Javobni ko'rish

B. m log m. DSU amallari deyarli bepul. (31-dars)

12Fenwick daraxtida so'rov va o'zgartirish qancha turadi? A) O(1) va O(n) B) O(n) va O(1) C) Ikkalasi ham O(log n) D) Ikkalasi ham O(1)

Javobni ko'rish

C. Prefiks jadvali bilan oddiy massiv orasidagi o’rtacha yo’l. (32-dars)

Xato topish

13Memoizatsiyada xotira tekshiruvi hisoblashdan KEYIN qo'yildi. Natija? A) Xato javob B) To'g'ri javob, lekin tezlik naif yechimniki C) RecursionError D) Cheksiz sikl

Javobni ko'rish

B. Kodda memoizatsiya bor ko’rinadi, lekin u hech narsa tejamaydi. Topishning yagona yo’li — chaqiruvlarni sanash. (25-dars)

14Knapsackda ichki sikl oldinga yurdi. Nima bo'ladi? A) Xato xabari B) Narsa bir necha marta olinadi C) Sekinlashadi D) Hech narsa

Javobni ko'rish

B. Kod cheksiz nusxali ryukzak masalasini yechib qo’yadi — u ham to’g’ri masala, faqat boshqasi. (27-dars)

15LIS da javob dp[n-1] deb olindi. Qachon xato? A) Hech qachon B) Eng uzun zanjir oxirgi elementda tugamasa C) n = 1 bo'lsa D) Sonlar teng bo'lsa

Javobni ko'rish

B. Javob max(dp). [1, 2, 3, 0] da dp[n-1] = 1, to’g’ri javob esa 3. (26-dars)

16LCS da mos kelmagan katakka dp[i-1][j-1] yozildi. Oqibat? A) Javob kamayadi B) Javob oshadi C) Xato xabari D) Cheksiz sikl

Javobni ko'rish

A. Ikkala harf ham tashlab yuboriladi, holbuki faqat bittasini tashlash yetardi. (29-dars)

17DSU da ota[b] = a yozildi (vakillar emas). Nima buziladi? A) Hech narsa B) Bor bog'lanishlar buziladi C) Sekinlashadi D) Xato xabari

Javobni ko'rish

B. Vakil emas, elementning o’zi ulanmoqda — uning ostidagi butun guruh ajralib qoladi. To’g’risi: ota[rb] = ra. (30-dars)

18Kruskalda olingan qirralar soni tekshirilmadi. Qachon xato? A) Graf bog'lanmagan bo'lsa B) Vaznlar teng bo'lsa C) n = 1 bo'lsa D) Hech qachon

Javobni ko'rish

A. Chala yig’indi chiqadi va yechim xato bermaydi. n - 1 ga tengligini tekshirish shart. (31-dars)

19Fenwickda qosh(i, x) bilan element x ga o'rnatilmoqchi bo'lindi. Natija? A) To'g'ri ishlaydi B) Eski qiymat qoladi va ustiga x qo'shiladi C) Xato xabari D) Cheksiz sikl

Javobni ko'rish

B. qosh farq qo’shadi, o’rnatmaydi. To’g’risi: qosh(i, x - a[i]). (32-dars)

20Fenwickda indekslar 0 dan boshlandi. Nima bo'ladi? A) Bitta element yo'qoladi B) Nolinchi indeksda sikl abadiy aylanadi C) Javob bittaga kam D) Hech narsa

Javobni ko'rish

B. 0 & (-0) = 0, demak indeks hech qachon siljimaydi. Fenwick majburan 1 dan indekslanadi. (32-dars)

Keyingi qadam

To’rttadan ko’p xato qilgan bo’lsangiz, mos darslarni qayta oching: 25-dars · 26-dars · 27-dars · 28-dars · 29-dars · 30-dars · 31-dars · 32-dars.

25-dars savollarida xato qilgan bo’lsangiz, uni albatta qaytaring: qolgan yetti dars shu bitta g’oyaning turli ko’rinishlari. DP formula emas — u «hisoblanganini saqlab qo’yish» degan bitta gapdan iborat.