3-daraja testi: Oltin

3-darajaOltin — graflar17–24 darslar

Yigirma savol, 17–24 darslar bo’yicha. Bu darajada eng ko’p uchraydigan xato algoritmni bilmaslik emas — qaysi algoritm kerakligini adashtirish va Python chegaralariga urilish.

Usul tanlash

1Vaznsiz grafda eng qisqa yo'l. Qaysi algoritm? A) DFS B) BFS C) Dijkstra D) Topologik saralash

Javobni ko'rish

B. BFS qatlam-qatlam tarqaladi, demak uchga birinchi yetib kelgan qatlam eng qisqa masofa bo’ladi. (19-dars)

2Vaznli grafda eng arzon yo'l, barcha vaznlar musbat. Qaysi algoritm? A) BFS B) DFS C) Dijkstra D) Flood fill

Javobni ko'rish

C. BFS narxni emas, qirralar sonini sanaydi. (24-dars)

3Grafda nechta alohida guruh borligini sanash. Qaysi usul? A) BFS yoki DFS B) Faqat Dijkstra C) Topologik saralash D) Ikkilik qidiruv

Javobni ko'rish

A. Ikkalasi ham bo’ladi — muhimi korilgan butun graf bo’ylab bitta bo’lishi. (18-dars)

4Kurslar bog'liqligi berilgan, o'qish tartibi kerak. Qaysi usul? A) Saralash B) Topologik saralash C) BFS D) Backtracking

Javobni ko'rish

B. Kiruvchi darajasi nol bo’lgan kurslar navbat bilan olinadi. (22-dars)

5Panjarada nechta alohida soha bor. Qaysi usul? A) Prefiks yig'indi B) Flood fill C) Dijkstra D) Ikki ko'rsatkich

Javobni ko'rish

B. Panjara ham graf: qo’shnilar koordinatadan hisoblanadi. (20-dars)

6Barcha mumkin bo'lgan joylashuvlarni sanash, n ≤ 10. Qaysi usul? A) Backtracking B) BFS C) Dijkstra D) Saralash

Javobni ko'rish

A. Qadamma-qadam quriladi va shart buzilgan zahoti orqaga qaytiladi. (21-dars)

7n = 100000 uchli grafni qanday saqlaysiz? A) Qo'shnilik matritsasi B) Qo'shnilar ro'yxati C) Qirralar ro'yxati, har so'rovda qidirish D) Farqi yo'q

Javobni ko'rish

B. Matritsa 10¹⁰ katak talab qiladi va xotiraga sig’maydi. (17-dars)

Murakkablik va chegaralar

8DFS va BFS ning murakkabligi? A) O(n) B) O(m) C) O(n + m) D) O(n · m)

Javobni ko'rish

C. Har uch bir marta ochiladi, har qirra bir marta ko’riladi. (18 va 19-darslar)

9Rekursiv DFS n = 100000 uchli zanjirda nima beradi? A) To'g'ri javob B) RecursionError C) Cheksiz sikl D) Sekin ishlaydi

Javobni ko'rish

B. Chaqiruv steki chegarasi ming atrofida, chuqurlik esa 100 mingga yetadi. (18-dars)

10BFS da list.pop(0) ishlatilsa murakkablik qanday bo'ladi? A) O(n + m) B) O(n²) C) O(n log n) D) O(m log n)

Javobni ko'rish

B. Har chaqiruv butun ro’yxatni suradi. Javob to’g’ri chiqadi, vaqt chegarasidan esa o’tmaydi. (12 va 19-darslar)

11Dijkstra + uyum murakkabligi? A) O(n²) B) O(n + m) C) O(m log n) D) O(n · m)

Javobni ko'rish

C. Har qirra ko’pi bilan bitta uyum yozuvi qo’shadi, uyum amali esa log n. (24-dars)

12Farzinlar masalasida kesish nimani tejaydi? A) Xotirani B) Yaroqsiz boshlanishdan chiqadigan butun shoxni C) Kod hajmini D) Hech narsani

Javobni ko'rish

B. Bir kesish o’sha shoxdagi barcha to’liq joylashuvlarni bir zarbada tashlaydi. (21-dars)

13n uchli daraxtda nechta qirra bor? A) n B) n − 1 C) n + 1 D) 2n

Javobni ko'rish

B. Kamroq bo’lsa bog’lanmaydi, ko’proq bo’lsa halqa paydo bo’ladi. (23-dars)

Xato topish

14DFS da uch stekdan OLINGANDA korilgan ga qo'shildi. Oqibat? A) Noto'g'ri javob B) Bir uch stekka bir necha marta tushadi C) Cheksiz sikl D) Hech narsa

Javobni ko'rish

B. Stek shishib ketadi va yechim O(n + m) bo’lmay qoladi. Uchni stekka qo’yayotganda belgilash kerak. (18-dars)

15Bog'langan guruhlarni sanashda korilgan ichki siklda e'lon qilindi. Natija? A) To'g'ri javob, lekin O(n²) B) Noto'g'ri javob C) Xato xabari D) Cheksiz sikl

Javobni ko'rish

A. Har uchdan qayta kezish boshlanadi. Javob to’g’ri, vaqt esa yo’q. (18-dars)

16Panjarada avval xarita[ny][nx], keyin chegara tekshirildi. Nima bo'ladi? A) Hech narsa B) IndexError yoki manfiy indeks tufayli jimgina noto'g'ri javob C) Sekinlashadi D) Cheksiz sikl

Javobni ko'rish

B. Python manfiy indeksni oxiridan sanaydi, shuning uchun xato ham chiqmasligi mumkin. (20-dars)

17Backtrackingda rekursiv chaqiruvdan keyin holat tiklanmadi. Oqibat? A) RecursionError B) Taxta borgan sari «band» bo'lib boradi va yechimlar kam chiqadi C) Cheksiz sikl D) Yechimlar ko'p chiqadi

Javobni ko'rish

B. Keyingi variant oldingisining izlari bilan tekshiriladi. (21-dars)

18Topologik saralashda uyum bo'shagach tartib darhol chiqarildi. Qaysi holatda xato? A) Graf bog'lanmagan bo'lsa B) Grafda sikl bo'lsa C) n = 1 bo'lsa D) Qirra bo'lmasa

Javobni ko'rish

B. Halqa ichidagi uchlar hech qachon nolga tushmaydi, tartib chala qoladi. Uzunlikni n bilan solishtirish shart. (22-dars)

19Daraxtda shox o'lchami ko'rilgan tartibda (teskari emas) yig'ildi. Natija? A) To'g'ri javob B) Har uch faqat bevosita bolalarini sanaydi C) RecursionError D) Cheksiz sikl

Javobni ko'rish

B. Ota bolalardan oldin ishlanadi, demak bolaning o’lchami hali yig’ilmagan bo’ladi. (23-dars)

20Dijkstra manfiy vaznli grafda ishlatildi. Nima bo'ladi? A) Cheksiz sikl B) Xato xabari C) Uch erta yakunlanadi va u orqali hisoblangan javoblar noto'g'ri qoladi D) Sekin ishlaydi

Javobni ko'rish

C. Kafolat «narxlar musbat» shartiga tayanadi. Manfiy vaznda tartib tanlamaydigan usul kerak. (24-dars)

Keyingi qadam

To’rttadan ko’p xato qilgan bo’lsangiz, mos darslarni qayta oching: 17-dars · 18-dars · 19-dars · 20-dars · 21-dars · 22-dars · 23-dars · 24-dars.

Bu darajada eng ko’p ball rekursiya chuqurligi va pop(0) tufayli yo’qoladi. Ikkalasi ham algoritmga tegishli emas, lekin ikkalasi ham to’g’ri yechimni noldan boshlab qayta yozishga majbur qiladi. Har graf masalasida ikkisini oldindan tekshiring.