Uvod u računarstvo, 17.6.2002.

Studenti koji su kolegij upisali akademske godine 2001./2002.

rješavaju zadatke 3–7, a ostali rješavaju zadatke 1–5.

1. (a) Izračunajte zbroj (43123)_{5} + (4024)_{5} (b) Izračunajte produkt (1101001)_{2} · (101101)_{2}

(c) Metodom dvojnog komplementa izračunajte razliku (101100010)_{2}−(110110)_{2} Računske operacije izvedite u bazama u kojima su brojevi zadani, bez pretvaranja u dekadsku ili neku drugu bazu.

2. Konstruirajte konačan automat koji prepoznaje jezik

L = { a^{m}b^{n}c | m, n ∈ ℕ_{0}, m − n ≡ 1 (mod 3) }

3. Formula računa sudova f sadrži sudovne varijable x, y, z i poprima vrijednost 1 ako je najviše jedna od varijabli istinita, a 0 inače. Napišite KNF i DNF za f i pojednostavnite izraz koliko god je moguće.

4. Napišite program koji učitava prirodan broj m i ispisuje njegove znamenke u rastućem redoslijedu. Svaka znamenka treba se ispisati onoliko puta koliko se javlja u broju m. Za program složenosti O(n) dobit ćete 10 nagradnih bodova (n je broj znamenaka broja m).

5. Za n×n matricu kažemo da je latinski kvadrat ako sadrži brojeve {1, 2, …, n} i ako se svaki broj javlja točno jednom u svakom retku i u svakom stupcu. Napišite program koji učitava cjelobrojnu matricu i provjerava da li je latinski kvadrat. Za program složenosto O(n^{2}) dobit ćete 10 nagradnih bodova.

6. Definirajte zapis za vezanu listu cijelih brojeva. Napišite funkciju koja kao argument uzima pokazivač (pointer) na početak liste i vraća najmanji broj u listi.

7.

Ispišite redoslijed posjećivanja čvorova zadanog binarnog stabla pri obilasku preorder, inorder i postorder algoritmom. Čvor H nema desno dijete, a čvorovi G i J nemaju lijevo dijete.

Napomena. Dozvoljeno je korištenje Bronštejna, logaritamskih tablica i kalkulatora. Programe umjesto u pseudojeziku možete pisati u programskim jezicima C, Pascal ili FORTRAN, ali će se tada uzeti u obzir eventualne sintaktičke pogreške.

REZULTATI:

Vedran Krčadinac