Algoritmi in programiranje
Ta domena preverja načrtovanje algoritmov, poznavanje krmilnih in podatkovnih struktur ter sledenje izvajanju kode. Naloge zahtevajo natančno branje pogojev in meja zank, ne le prepoznavanje sintakse.
Lastnosti in krmilne strukture
- Algoritem: končnost, določenost, vhod, izhod, splošnost.
- Zaporedje, pogoj (if/elif/else), zanka (for po znanem obsegu, while po pogoju), break in continue.
- Podprogrami imajo parametre, vračajo vrednost in imajo lokalno območje spremenljivk; rekurzija potrebuje robni pogoj.
Podatkovne strukture in iskanje
- Seznam omogoča dostop po indeksu O(1); slovar v povprečju O(1) po ključu; sklad je LIFO, vrsta FIFO.
- Linearno iskanje je O(n); binarno iskanje O(log n) deluje le na urejenem seznamu.
Rešen primer
Iskanje 23 v urejenem seznamu [2, 5, 8, 12, 16, 23, 38, 56, 72], indeksi 0–8. Sredina 4 → 16 < 23, zato iščemo desno (5–8). Sredina 6 → 38 > 23, zato iščemo levo (5–5). Sredina 5 → 23, najdeno. Tri primerjave; linearno iskanje bi jih potrebovalo šest. Sklep: pogoj za binarno iskanje je urejenost, sicer rezultat ni zanesljiv.
Pasti
- range(1, 6) vrne 1–5, ne 1–6;
- zamenjava = in ==;
- spreminjanje seznama med iteracijo;
- napačna meja pri binarnem iskanju (while low <= high);
- rekurzija brez robnega pogoja;
- zanka while, v kateri se pogojna spremenljivka ne spremeni.