O laboratoriju
Osebje
Objave
Raziskave
Pravila
Predmeti/ vaje
Izpitni roki
Rezultati
Naloge
Informacije
Real-time Systems Laboratory

Vaje - Podatkovne strukture, RI UNI/2

Gradivo za študij

Vsebina predavanj
Definicije podatkovnih struktur
Demonstracija podatkovnih struktur (zip, 855kb)

Predloge razredov

sklad vrsta seznam drevo test

Splošna navodila

Naloge so ovrednotene s točkami. Vsaka točka  pomeni eno oceno, vendar le v primeru, če je naloga popolnoma opravljena. Za pridobitev podpisa, možnost pristopa k izpitu in za pozitivno oceno je potrebno uspešno opraviti naloge za vsaj 6 točk.

Pred izdelavo naloge je potrebno izvesti analizo in predlagati rešitev problema v obliki razrednega diagrama, psevdo-koda, grobe strukture programa ali podatkovnih struktur ipd. Rezultat je potrebno pripraviti v neformalni pisni obliki, ki je sestavni del opravljene naloge. Za osnovo lahko uporabite Obrazec za pripravo vaj. Dokument je potrebno pripraviti pred prihodom na vaje in je del programske dokumentacije.

Pri izdelavi vaj uporabite programski jezik C++. Delovanje struktur preverite v preprostih testnih programih za (MS-DOS/linux) konzolno okno.

Naloge, ki imajo omejen čas zagovora, je mogoče zagovarjati samo do prvega izpitnega roka po zaključku predavanj!

Besedila vaj

  1. Izdelaj podatkovno strukturo dinamični seznam, ki vsebuje elemente poljubnega tipa.
    (1 točka, omejen čas zagovora)
     

  2. Izdelaj podatkovno strukturo graf. Implementiraj metode za izpis matrike sosednosti in izpis tranzitivne ovojnice. 
    (1 točka)
    Implementiraj metodo za iskanje in izpis minimalnega vpetega drevesa.
    (+1 točka)
     

  3. Implementiraj podatkovno strukturo redka matrika in osnovne matrične operacije (vsota, razlika, produkt) ter izpis.
    (1 točka)
    Implementiraj metodo za izračun determinante matrike in metodo za invertiranje matrike.
    (+1 točka)
     

  4. Implementiraj podatkovno strukturo zgoščena tabela. Uporabite katerokoli zgoščevalno funkcijo in implementirajte metode za vstavljanje, brisanje in iskanje podatkov v tabeli.
    (1 točka, omejen čas zagovora)
    Implementacija s seznami.
    (1 točka) 

  5. Izdelaj podatkovno strukturo kopica. Omogoči linearen in drevesni izpis podatkovne strukture.
    (1 točka, omejen čas zagovora)
     

  6. Implementiraj podatkovno strukturo binarno iskalno drevo, ki naj omogoča tudi vstavljanje ključa v vrh.
    (1 točka, omejen čas zagovora)
     

  7. Implementiraj podatkovno strukturo AVL drevo.
    (2 točki) 

  8. Implementiraj podatkovno strukturo lomljeno drevo.
    (2 točki) 

  9. Implementiraj podatkovno strukturo B-drevo 2. reda.
    (2 točki) 

  10. Iz seznama izpelji podatkovni strukturi sklad in vrsta.
    (1 točka, omejen čas zagovora)
     

  11. Implementiraj podatkovno strukturo množica z operatorji za unijo(+), presek(*), razliko(-), podmnozico(<) in izpis(<<) in funkcijo bool jeElement(const T&).
    (1 točka)
     

  12. Implementiraj podatkovno strukturo polinom z operacijami za vsoto, razliko, produkt, kvocient, odvod in integral polinoma.
    (1 točka)

    Implementiraj metodo, ki vrne seznam ničel polinoma.
    (+1 točka) 

  13. Uporabi razreda za dinamični sklad in vrsto ter implementiraj razred kalkulator, ki bo iz vhodne vrstice prečital izraz v infiksni notaciji ter ga izračunal s skladovnim strojem. Kalkulator naj podpira osnovne aritmetične operacije (seštevanje, odštevanje, množenje, deljenje in potenciranje). Javi naj napake v izrazu (napačni znaki, manjkajoči oklepaji, ...)
    (1 točka)
     

  14. Napiši program, ki uporablja podatkovno strukturo trikrat povezan seznam za predstavitev telefonskega imenika. Podatke naj bo mogoče vstavljati, brisati, iskati in izpisati urejeno po (a) imenu, (b) številki in (c) naslovu ali delu le-teh.
    (1 točka, omejen čas zagovora)
     

  15. Implementiraj dvosmerno povezan asociativen seznam, ki bo omogočal urejen izpis podatkov - naraščajoče in padajoče.
    (1 točka, omejen čas zagovora)
     

  16. Implementiraj podatkovno strukturo dolgo število skupaj z osnovnimi matematičnimi operacijami (+,-,*,/,=,==,<) in izpisom. Dolgo število lahko ima poljubno mnogo desetiških števk.
    (2 točki)
     

Povezave

Vsebina predmeta

Rezultati izpitov

Rezultati študija

Rezultati vaj

Na vrh | Prva stran | O laboratoriju | Osebje | Inštitut za informatiko | E-pošta

 

RTS UM Inštitut za informatiko FERI FERI