Data structures theory midterm test Flashcards
Kas yra Algoritmas?
Tai aiškiai suformuluota tikslių veiksmų seka, nurodanti ką ir kaip reikia atlikti norint išspręsti suformuluotą uždavinį
Kokios yra algoritmų savybės?
Diskretumas - Algoritmas turi būti skaidomas į tiksliai aprašytus vykdymo žingsnius.
Apibrežtumas - Algoritmo sprendimo žingsniai, turi būti apibrėžti vienareikšmiškai (negali būti dviprasmybių) ir vykdomi nustatyta tvarka
Baigtumas - Kompiuterinis uždavinio sprendimas turi būti baigtinis – turi būti aiškiai suformuluota pabaiga
Rezultatyvumas - Algoritmas turi turėti pradinių duomenų įvedimą ir rezultatų išvedimą
Efektyvumas - Apdorojimo žingsniai turi būti lengvai suvokiami, lengvai atvaizduojami ir turėti kiek įmanoma mažesnę realizacijos trukmę
Universalumas - tai galimybė panaudoti tą patį algoritmą įvairiems pradiniams duomenims. Universalumas – tokia savybė, kai algoritmas galioja keičiant kiekybinius ar kokybinius parametrus.
Kas yra tiesiniai algoritmai?
Tiesiniai - Tai tokie algoritmai, kuriuose visi veiksmai atliekami nuosekliai vienas po kito be jokių alternatyvų ar veiksmų grupių kartojimo.
Kas yra šakoti algoritmai?
Šakoti - Tai algoritmai, kuriuose yra alternatyvūs sprendimo keliai.
Kas yra cikliniai algoritmai?
Cikliniuose skaičiavimo procesuose kai kurie veiksmai kartojami su vis naujomis kintamųjų reikšmėmis. * Pasikartojančią skaičiavimo proceso dalį vadinsime ciklu. * Kintamasis, kurio reikšmė lemia, kiek kartų atlikti ciklą, vadinamas ciklo parametru.
Kokie yra algoritmo sudarymo etapai?
- Išanalizuoti užduotį, numatant visus galimus kritinius užduoties sprendimo atvejus.
- Išanalizuoti, kokie gali būti pradiniai duomenys ir kokie turi būti rezultatai.
- Išdėstyti užduoties sprendimą kuo smulkesniais žingsniais.
- Pateikti sudarytą algoritmą pasirinktu būdu.
Kas yra statinės duomenų struktūros?
Statinės duomenų struktūros – tai duomenų struktūros, kurių dydis nurodomas iš anksto ir negali keistis vykdant programą.
Kas yra dinaminės duomenų struktūros?
Dinaminės duomenų struktūros – tai tokios struktūros, kurių dydis gali keistis vykdant programą.
Kokios yra tiesinės duomenų struktūros?
Masyvas, stekas, eilė, dekas, tiesinis sąrašas
Kas yra masyvas?
Masyvas – tai fiksuotas kiekis duomenų, kurie atmintyje laikomi nuosekliai, o išrenkami naudojant indeksą ar indeksus. Kiekvieno duomens reikšmės formuojamos unifikuotai
Kas yra stekas ir kokias operacijas turi?
Stekas – tai duomenų aibė, kuriai apibrėžtos tokios operacijos:
– inicializuoti steką; – įterpti elementą į steką (Push);
– pašalinti elementą iš steko (Pop);
– skaityti steko elementą (Top);
– panaikinti steką
Kas yra eilė ir kokias operacijas turi?
Eilė – tai duomenų aibė, kuriai apibrėžtos tokios operacijos:
– Inicializuoti eilę; – įterpti elementą į eilę (put);
– pašalinti elementą iš eilės (get);
– skaityti elementą;
– panaikinti eilę
Kas yra dekas ir kokias operacijas turi?
Dekas - tai duomenų aibė, kuriai apibrėžtos tokios operacijos:
– inicializuoti deką; – įterpti elementą į deko pradžią arba pabaigą;
– pašalinti elementą iš deko pradžios arba pabaigos;
– skaityti deko elementą nuo pradžios arba pabaigos;
– panaikinti deka
Kas yra tiesinis sąrašas ir kokias operacijas turi?
Tiesinis sąrašas – tai duomenų aibė, kuriai taikomos tokios operacijos:
– inicializuoti sąrašą;
– įterpti elementą į tam tikrą sąrašo vietą;
– įterpti elementą tenkinant nurodytas sąlygas;
– pašalinti iš sąrašo elementą, esantį tam tikroje vietoje;
– pašalinti iš sąrašo elementą tenkinant nurodytas sąlygas;
– skaityti nurodytą sąrašo elementą;
– panaikinti sąrašą
Kokios yra tiesinio sąrašo rūšys ir kas juose įpatingo?
Vienkryptis - tai sąrašas, kurio kiekvienas elementas „žino“, koks elementas yra po jo.
Dvikryptis - tai sąrašas, kurio kiekvienas elementas ne tik „žino“, koks elementas yra po jo, bet ir „žino“, koks elementas yra prieš jį
Ciklinis - tai sąrašas, kurio paskutinis elementas rodo į pirmąjį
Ciklinis dvikryptis - tai dvikryptis sąrašas, kurio paskutinio elemento rodyklė rodo į pirmąjį elementą, o pirmojo į paskutinį
Kas yra duomenų medis?
Medis – tai tokia hierarchinė duomenų struktūra, kurioje:
* į kiekvieną elementą, išskyrus vieną, vadinamą medžio šaknimi, yra tik vienintelė nuoroda iš kito elemento;
* iš kiekvieno elemento gali būti viena arba daugiau nuorodų į kitus elementus;
* iš šaknies einant nuorodomis galima pasiekti visus kitus elementus.
Kokie yra medžio elementai?
Viršūnė - visi medžio elementai, šaknis - viršūnė į kurią nėra nuorodų, lapas - viršūnė iš kurios nėra nuorodų į kitas viršūnes.
Kas yra medžio viršūnės lygis, medžio aukštis, pomedis?
Medžio aukštis – tai viršūnių skaičius nuo šaknies iki tolimiausio lapo. Jei medis tuščias, jo aukštis 0. Jei medis nėra tuščias, jo aukštis lygus maksimaliam viršūnių lygiui.
Pomedis - Kiekviena nuoroda su viršūnėmis, į kurias galima patekti, pradėjus eiti ta nuoroda, vadinama medžio šaka arba pomedžiu
Kas yra dvejetainis medis, pilnas dvejetainis medis, užbaigtas dvejetainis medis?
Dvejetainis medis - toks medis kurio kiekviena viršūnė turi ne daugiau kaip du vaikus arba tusčias.
Pilnas dvejetainis medis - vadiname tokį medį, kuriame kiekviena viršūnė turi du vaikus arba yra lapas.
Užbaigtas dvejetainis medis - tai toks medis, kuriame viršūnės pildomos iš kairės į dešinę tol, kol užpildomas visas lygis ir tik tuomet pereinama į sekant į lygį.
Kas yra subalansuotas pagal aukštį ir visiškai subalansuotas medis?
Subalansuotas pagal aukštį medis (height balanced) – tai medis, kurio kiekvienos viršūnės kairiojo ir dešiniojo pomedžio aukščiai skiriasi ne daugiau kaip vienu lygiu.
Visiškai subalansuotas dvejetainis medis (completely balanced) – tai medis, kurio kairieji ir dešinieji kiekvienos viršūnės pomedžiai yra to paties aukščio
Kaip aritmetinė išraiška išdėstoma medyje?
Medžio viršūnėje (šaknyje) įrašoma išraiškos paskutinė atliekama operacija.
Į kairįjį pomedį įrašomas kairysis operacijos operandas, į dešinįjį dešinysis.
Dvejetainio medžio apėjimo taisyklės ir jų atlikimo tvarka VKD, KVD, KDV
- VKD (tiesioginis): aplankyti Viršūnę; apeiti Kairįjį pomedį; apeiti Dešinįjį pomedį.
- KVD (vidinis): apeiti Kairįjį pomedį; aplankyti Viršūnę; apeiti Dešinįjį pomedį.
- KDV (atvirkštinis): apeiti Kairįjį pomedį; apeiti Dešinįjį pomedį; aplankyti Viršūnę.
Kas yra duomenų krūva (piramidė)?
Duomenų krūva (angl. heap) – tai užbaigtas dvejetainis medis, t. y. toks medis, kuriame viršūnės pildomos iš kairės į dešinę tol, kol užpildomas visas lygis ir tik tuomet pereinama į sekantį lygį
Tiesinių duomenų struktūrų išdėstymas atmintyje
Atmintyje tiesinės duomenų struktūros išdėstomos nuosekliai elementas po elemento
Kokie yra rūšiavimo algoritmai?
- vidinis ir išorinis rūšiavimas (apibrėžimai);
Vidinis - Vidinio rūšiavimo algoritmai naudoja tik vidinę kompiuterio atmintį
Išorinis - Išorinio rūšiavimo algoritmai naudoja vidinę ir išorinę atmintį
Kas yra stabilūs ir nestabilūs rūšiavimo algoritmai?
- stabilūs ir nestabilūs algoritmai (apibrėžimai).
Stabilus - Stabilūs algoritmai nekeičia lygių elementų tvarkos
Nestabilus - Nestabilūs algoritmai lygių elementų vietų išsaugojimo negarantuoja
Kaip įvertinti rūšiavimo algoritmų sudėtingumą?
– elementų lyginimo veiksmų skaičius;
– elementų sukeitimų skaičius rūšiavimo metu
Burbulo rūšiavimo algoritmas
algoritmo principas - nuosekliai iš eilės peržiūrėti gretimų elementų poras, prireikus elementus sukeisti vietomis
Išrinkimo rūšiavimo algoritmas
Pagrindinis principas – mažiausią arba didžiausią elementą rašyti į pirmą duomenų sekos vietą, tada taikyti tą patį principą posekiui be pirmojo elemento ir t. t.
Kiek reikia atminties dvejetainio medžio išdėstymui?
S = N (D + 2 P
Čia N- viršūnių skaičius, P– atminties
kiekis, skirtas rodyklei, D- atminties kiekis, reikalingas duomenims.
