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

Vaje - Podatkovne strukture in algoritmi, TE UNI/2

Gradivo za študij

Vsebina predavanj (html), download verzija (exe, 7.12MB)
Demonstracija podatkovnih struktur (zip, 866kb)
Uvodno pradavanje k vajam

Splošna navodila

Vaje so sestavljene iz več skupin nalog. Prva skupina zajema obvezne naloge, ki jih mora študent opraviti, da dobi oceno 6. Za višjo oceno mora po vrsti opraviti po eno od vaj iz naslednjih skupin.

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.

Besedila vaj

Ocena Naloga
6
  1. Implementacija algoritmov urejanja podatkov. Primerjajte sortiranje z navadnim izbiranjem (straightselection), premenami (bubblesort) in s porazdelitvami (quicksort). Opazujte potrebno število primerjav in zamenjav parov podatkov v polju, ki ga urejate. Strategije primerjajte na vzorcu velikosti 100 naključno generiranih števil.
  2. Izdelaj podatkovno strukturo dinamični sklad po predlogi.
  3. Izdelaj podatkovno strukturo dinamični seznam po predlogi.
  4. Iz seznama iz prejšnje naloge izpelji razreda sklad in vrsta (predloga za vrsto).
  5. Izdelaj podatkovno strukturo binarno iskalno drevo po predlogi.
7
  1. Iz podatkovne strukture drevo izpeljite podatkovno strukturo množica z operacijami unija, presek, razlika ter vsebovanost.

    - ali -

  2. Izdelaj podatkovno strukturo kopica po predlogi.

    - ali -

  3. Implementacija strukture graf s seznami sosedov in inverznih sosedov. Ustvari metode za izpis matrike sosednosti in izpis tranzitivne ovojnice.
8
  1. Napiši razred, ki predstavlja dvosmerno krožno povezan asociativni seznam. Kot osnovo vzrami predlogo navadnega seznama.

    - ali -

  2. Implementirajte podatkovno strukturo razpršena tabela s statičnim poljem velikosti 10 mest. Uporabite katerokoli zgoščevalno funkcijo in oblikujte metode za vstavljanje, brisanje in iskanje podatkov v tabeli. V okviru testnega programa izpisujte število potrebnih korakov pri vstavljanju in iskanju podatka.

    - ali -

  3. Napiši razred, ki predstavlja kompleksno število in definiraj vse matematične operacije (+,-,*,/,abs).
9
  1. Ustvari podatkovno strukturo polinom ter implementirajte vsoto, razliko, produkt, kvocient, odvod in integral polinoma. Naredi metodo, ki vrne seznam ničel polinoma.

    - ali -

  2. Implementirajte podatkovno strukturo redka matrika in osnovne matrične operacije (vsota, razlika, produkt) ter izpis. Izdelaj metodo za izračun determinante matrike in metodo za invertiranje matrike.

    - ali -

  3. S pomočjo std knjižnice v C++ ali v ps.h implementiraj kalkulator, ki bo iz vhodne vrstice precital izraz v infiksni notaciji, ga s pomocjo skladov pretvoril v postfiksno notacijo ter ga izracunal s skladovnim strojem. Kalkulator naj podpira osnovne aritmeticne operacije (seštevanje, odštevanje, množenje, deljenje, oklepaje in potenciranje).
10
  1. Implementirajte podatkovno strukturo AVL drevo ter izdelajte testni program za izvedbo osnovnih funkcij nad drevesom. Zgleduj se po predlogi za navadno iskalno drevo.

    - ali -

  2. Implementirajte podatkovno strukturo B-drevo 2. reda ter izdelajte testni program za izvedbo osnovnih funkcij nad drevesom. Zgleduj se po predlogi za navadno iskalno drevo.

Povezave

Vsebina predmeta
Rezultati izpitov

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

 

RTS UM Inštitut za informatiko FERI FERI