pondelok 12. januára 2009

ADS skuska 2008 - zadania

Zohnal som skusku z ADS z minuleho roka. - 08.01.2008

Okej, prepísal som to, čo už s vami.

Písomka ku skúške z Údajových štruktúr – 08.01.08

1.Čo je asymptotický stredný odhad? Vysvetlite a zapíšte aj formálne.

2.Predpokladajme, že chceme reprezentovať všeobecný strom S s operáciami PARENT, LEFTMOSTCHILD a RIGHTSIBLING. Čo musí platiť o vrcholoch stromu S, aby sme mohli použiť reprezentáciu poľom P, kde P[i] je index na otca vrchola i ?

3.Napíšte v Delphi deklarácie potrebné k implementácií prešitého stromu a metódu VlozVlavo(var v1:TVrchol; v2:TVrchol), ktorá vrcholu v1 vloží vrchol v2 ako ľavého syna a pôvodného ľavého syna vrchola v1 spraví ľavým synom vrchola v2.

4.a) Aká je asymptotická zložitosť operácie vymazávania z AA-stromu? Vysvetlite.
b) Aký je vzťah medzi AA-stromom a červeno-čiernym stromom?

5.Aký predpoklad zavádzame pri zatvorenom hašovaní, aby sme mohli robiť odhady na zložitosť jednotlivých operácií? Vysvetlite, čo tento predpoklad znamená a ako ho spĺňajú jednotlivé stratégie riešenia kolízií?

6.Predpokladajme, že máme v 2-3 strome uložených n prvkov. Aká je výška tohto stromu v najhoršom prípade a aká v najlepšom prípade? Odvoďte.

7.Koľko vnútorných vrcholov obsahuje červeno-čierny strom s výškou h ? Dokážte. (Predpokladáme, že pôvodné nily boli nahradené „nilovými listami“ a že všetky pôvodné vrcholy sú teraz vnútornými vrcholmi).

8.Vysvetlite, ako robíme dolný odhad na zložitosť optimálneho algoritmu triediaceho porovnávaním.

9.Vysvetlite, ako triedi algoritmus Sample sort.

10.Nakreslite postupnosť AVL stromov, ktoré vzniknú postupným vkladaním prvkov 100, 200, 500, 300, 400, 370, 330, 350, 390, 380 do pôvodne prázdneho AVL-stromu a následným vymazaním prvkov 370, 380, 390. Pri vymazávaní vrchola s dvoma synmi nahrádzajte minimom sprava.

1 komentár:

Unknown povedal(a)...
Tento komentár bol odstránený autorom.