Ispitna pitanja iz Osnova programiranja


(ispitna pitanja za školsku 2001/2002.)

    PRELIMINARIJE

  1. Istorija razvoja računara (kalkulatori i automati).
  2. Arhitektura i funkcionisanje fon Nojmanove mašine
  3. Struktura računara (engl. hardware). Računarski sistem
  4. Funkcionisanje računara (engl. software)
  5. Bit, bajt, karakter. ASCII-skup karaktera. Standardi o karakterskim skupovima.
  6. Azbuka S , niska (reč), skup S *, jezik nad S , operacije nad jezicima. Faktor i podreč. Poredak nad S *
  7. Sintaksa i semantika programskih jezika
  8. Veštački i prirodni jezici. Formalna gramatika i njen opis. BNF, EBNF i sintaksni dijagrami. Primeri definicije identifikatora i celobrojne konstante
  9. Jezički procesori (kompilatori i interpretatori)
  10. Pojam algoritma. Tjuringova mašina. Čerčova hipoteza. Programski jezici
  11. Poređenje jezika: Paskal i C
  12. Osnovna svojstva jezika C. Struktura programa u jeziku C. Odvojena kompilacija
  13. Iskazi za kontrolu toka u programskom jeziku C (karakteristike njihove upotrebe)
  14. HTML

  15. Jezici za opis strukture teksta (HTML): grafički logički izgled teksta. Pojam hiperteksta i realizacija hiperteksta u HTML-u
  16. Struktura dokumenta u HTML-u. Razlika između word- i html-dokumenta? Etikete u okviru etikete <head> i njihovi atributi
  17. Principi strukturiranja sadržaja dokumenta. Etikete u okviru tela dokumenta <body> i njihovi atributi
  18. SPECIFIKACIJA PROGRAMA

  19. Program - formalna (funkcionalna) specifikacija. Preduslov i pauslov. Završavanje programa. Primeri specifikacije za skip, swap, koren.
  20. Iskaz dodele i kompozicija iskaza dodele, njihova specifikacija. Aksioma dodele. Primer "swap in place". Interpretacija u prostoru stanja
  21. Uslovni iskaz, njegova specifikacija i aksioma uslovnog iskaza. Primer izvođenja programa za maksimum dva broja
  22. Repetitivni iskaz. Njegova specifikacija i aksioma. Invarijanta. Primer - Euklidov algoritam
  23. Princip (teorema) linearnog pretraživanja. Specifikacija. Primer a = [ sqrt(N) ] - odnos Knutovog i Dejsktrinog rešenja. Logaritamska redukcija
  24. Specifikacija celobrojnog nizovskog tipa. Izvođenje programa za određivanje maksimalnog elementa niza iz funkcionalne specifikacije
  25. Algoritmi nad nizovima. Specifikacija, izvođenje i analiza rešenja. Primer programa za rotaciju niza. Primer "trobojke"
  26. TIPOVI PODATAKA

  27. Tipovi podataka. Klasifikacija. Konstrukcija tipova u C-u
  28. Operacije na bitu. Primene
  29. Relacijski operatori. Elementi sintakse logičkog izraza. Izračunavanje logičkog izraza
  30. Celobrojni tip (int). Svojstva i operacije. Interna reprezentacija. Implementacije
  31. Opis sintakse aritmetičkog izraza. Aritmetički operatori, prioritet i asocijativnost u C-u
  32. Algoritmi za unos i ispis celih brojeva (niska karaktera u broj; dekadni u binarni i obratno)
  33. Karakterski tip (char) podataka u jeziku C.
  34. Realni tip (float). Svojstva i operacije. Interna reprezentacija.
  35. Algoritmi za unos i ispis realnih brojeva.
  36. Pokazivački tip. Nizovi i pokazivači. Primeri
  37. Karakterske niske. Funkcije za rad sa karakterima.
  38. Struktura i unija. Konstrukcija i svojstva. Primeri
  39. Nizovski tip, njegova svojstva, operacije nad njim, način implementiranja
  40. Pojam datoteke. Svojstva i operacije. Struktura FILE. Veza sa fizičkom datotekom. Funkcije za rad sa datotekama
  41. Standardni ulaz i izlaz. Redirekcija (preusmeravanje). Povezivanje komandi
  42. Opis i svojstva tekstuelne datoteke.
  43. Kopiranje datoteke u datoteku. Poređenje mogućih rešenja u C-u
  44. FUNKCIJE

  45. Pojam funkcije. Deklaracija i poziv. Argumenti komandne linije
  46. Vrste prenosa parametara i način implementiranja u C-u
  47. Promenljivi broj argumenata funkcije u C-u. Primer funkcije za sabiranje
  48. Globalne i lokalne promenljive. Blok. Vidljivost promenljivih u C-u
  49. Modularizacija programa. Problemi i metode testiranja programa
  50. Čitljivost programa. Uloga komentara. Pismeno programiranje (Knut)
  51. Metodologija strukturnog programiranja. Pristupi u izgradnji programa. Odnos pouzdanosti i efikasnosti programa
  52. Rekurzivne funkcije. Izvršavanje rekurzivne funkcije. Glavni poziv. Primer rekurzivne funkcije za množenje dva cela broja
  53. Analiza rekurzivnih programa za Fibonačijev niz i binomni koeficijent. Problemi i rešenja. Hanojske kule
  54. Konstrukcija rekurzivnih procedura. Svođenje problema. Primer crtanje mustre kvadrata i mustre trouglova
  55. Konstrukcija rekurzivnih procedura. Konstrukcija procedure za brzo sortiranje (quicksort). Analiza složenosti
  56. Konstrukcija rekurzivnih procedura. Rekurzivna procedura za binarno pretraživanje. Složenost
  57. Eliminacija repne rekurzije. Primeri
  58. Bočni (uzgredni) efekat. Primeri u C-u
  59. APSTRAKTNI TIPOVI I ALGORITMI NAD NJIMA

  60. Apstraktni tipovi (skupovi, polinomi). Svosjtva. Način implementacije
  61. Metode sortiranja. Poređenje algoritama. Karakteristike implementacije
  62. Linearno, binarno i interpolirano pretraživanje.
  63. Linearne liste. Svojstva i operacije nad listama. Načini implementacije liste.
  64. Problem alokacije i oslobađanja memorije. Funkcije za alokaciju memorije
  65. Primer sa ispisivanjem elemenata linearne liste u obrnutom redosledu. Analiza mogućih rešenja
  66. Strukture podataka: stek. Svojstva i operacije. Načini implementacije. Primer izračunavanja aritmetičkog izraza
  67. Strukture podataka: red. Svojstva i operacije. Način implementacije. Primeri
  68. Pojam drveta. Vrste drveta. Svojstva i implementacija drveta. Obilazak drveta u dubinu. Binarizacija drveta
  69. Binarno drvo. Svojstva i operacije nad binarnim drvetom. Obilazak drveta u dubinu.
  70. Prefiksni kodovi i kompresija. Hafmanovi kodovi
  71. Pretraživanje binarnog drveta. Pretraživanje binarnog drveta sa umetanjem. Primer rečnika
  72. Pojam grafa. Predstavljanje i implementacija grafa. Vrste grafova. Primeri
  73. Određivanje najkraćeg puta (Dejsktrin algoritam)
  74. Obilazak acikličnog grafa (određivanje čvora maksimalne težine). Markiranje. Primene
  75. Metode direktnog pretraživanja (hashing). Razrešenje kolizije. Otvoreno adresiranje i dvostruko heširanje
  76. Pretraživanje po osnovi (cifarsko pretraživanje, radix)
  77. Problem poređenja niski. Gruba sila. KMP-algoritam. Pojam obrasca (engl. pattern)