Data structures theory midterm test Flashcards
(31 cards)
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į
