Data structures theory midterm test

Question 1

Kas yra Algoritmas?

Answer 1

Tai aiškiai suformuluota tikslių veiksmų seka, nurodanti ką ir kaip reikia atlikti norint išspręsti suformuluotą uždavinį

Question 2

Kokios yra algoritmų savybės?

Answer 2

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.

Question 3

Kas yra tiesiniai algoritmai?

Answer 3

Tiesiniai - Tai tokie algoritmai, kuriuose visi veiksmai atliekami nuosekliai vienas po kito be jokių alternatyvų ar veiksmų grupių kartojimo.

Question 4

Kas yra šakoti algoritmai?

Answer 4

Šakoti - Tai algoritmai, kuriuose yra alternatyvūs sprendimo keliai.

Question 5

Kas yra cikliniai algoritmai?

Answer 5

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.

Question 6

Kokie yra algoritmo sudarymo etapai?

Answer 6

1. Išanalizuoti užduotį, numatant visus galimus kritinius užduoties sprendimo atvejus.
2. Išanalizuoti, kokie gali būti pradiniai duomenys ir kokie turi būti rezultatai.
3. Išdėstyti užduoties sprendimą kuo smulkesniais žingsniais.
4. Pateikti sudarytą algoritmą pasirinktu būdu.

Question 7

Kas yra statinės duomenų struktūros?

Answer 7

Statinės duomenų struktūros – tai duomenų struktūros, kurių dydis nurodomas iš anksto ir negali keistis vykdant programą.

Question 8

Kas yra dinaminės duomenų struktūros?

Answer 8

Dinaminės duomenų struktūros – tai tokios struktūros, kurių dydis gali keistis vykdant programą.

Question 9

Kokios yra tiesinės duomenų struktūros?

Answer 9

Masyvas, stekas, eilė, dekas, tiesinis sąrašas

Question 10

Kas yra masyvas?

Answer 10

Masyvas – tai fiksuotas kiekis duomenų, kurie atmintyje laikomi nuosekliai, o išrenkami naudojant indeksą ar indeksus. Kiekvieno duomens reikšmės formuojamos unifikuotai

Question 11

Kas yra stekas ir kokias operacijas turi?

Answer 11

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ą

Question 12

Kas yra eilė ir kokias operacijas turi?

Answer 12

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ę

Question 13

Kas yra dekas ir kokias operacijas turi?

Answer 13

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

Question 14

Kas yra tiesinis sąrašas ir kokias operacijas turi?

Answer 14

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šą

Question 15

Kokios yra tiesinio sąrašo rūšys ir kas juose įpatingo?

Answer 15

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į

Question 16

Kas yra duomenų medis?

Answer 16

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.

Question 18

Kokie yra medžio elementai?

Answer 18

Viršūnė - visi medžio elementai, šaknis - viršūnė į kurią nėra nuorodų, lapas - viršūnė iš kurios nėra nuorodų į kitas viršūnes.

Question 19

Kas yra medžio viršūnės lygis, medžio aukštis, pomedis?

Answer 19

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

Question 20

Kas yra dvejetainis medis, pilnas dvejetainis medis, užbaigtas dvejetainis medis?

Answer 20

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į.

Question 21

Kas yra subalansuotas pagal aukštį ir visiškai subalansuotas medis?

Answer 21

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

Question 22

Kaip aritmetinė išraiška išdėstoma medyje?

Answer 22

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.

Question 23

Dvejetainio medžio apėjimo taisyklės ir jų atlikimo tvarka VKD, KVD, KDV

Answer 23

• 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ę.

Question 24

Kas yra duomenų krūva (piramidė)?

Answer 24

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į

Question 25

Tiesinių duomenų struktūrų išdėstymas atmintyje

Answer 25

Atmintyje tiesinės duomenų struktūros išdėstomos nuosekliai elementas po elemento

Question 26

Kokie yra rūšiavimo algoritmai?

Answer 26

• 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į

Question 27

Kas yra stabilūs ir nestabilūs rūšiavimo algoritmai?

Answer 27

• 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

Question 28

Kaip įvertinti rūšiavimo algoritmų sudėtingumą?

Answer 28

– elementų lyginimo veiksmų skaičius;
– elementų sukeitimų skaičius rūšiavimo metu

Question 29

Burbulo rūšiavimo algoritmas

Answer 29

algoritmo principas - nuosekliai iš eilės peržiūrėti gretimų elementų poras, prireikus elementus sukeisti vietomis

Question 30

Išrinkimo rūšiavimo algoritmas

Answer 30

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.

Question 31

Kiek reikia atminties dvejetainio medžio išdėstymui?

Answer 31

S = N (D + 2 P
Čia N- viršūnių skaičius, P– atminties
kiekis, skirtas rodyklei, D- atminties kiekis, reikalingas duomenims.