1-INF-220 Algoritmy a dátové štruktúry

Kto si?
V tomto semestri mám zapísané Algoritmy a dátové štruktúry (ADŠ).
V tomto semestri nerobím ADŠ, kvíz si chcem spraviť len tak.

1. Dá sa z usporiadaného poľa v čase lineárnom od jeho veľkosti vyrobiť halda?
   Áno Nie Ani srnka netuší
2. Dá sa z usporiadaného poľa v čase lineárnom od jeho veľkosti vyrobiť hocijaký binárny vyhľadávací strom?
   Áno Nie Ani srnka netuší
3. Dá sa z usporiadaného poľa v čase lineárnom od jeho veľkosti vyrobiť vyvážený binárny vyhľadávací strom?
   Áno Nie Ani srnka netuší
4. Víla Amálka má pole veľkosti N a kúzelnú paličku. Mávnutím paličky vie vymeniť ľubovoľné dva prvky poľa. Existuje pole, na ktorého usporiadanie nestačí víle Amálke N mávnutí paličkou, nech by sa snažila ako len chce?
   Áno Nie Ani srnka netuší
5. Máme haldu s maximom v koreni. Je v nej uložených 47 prvkov a každé dva sú navzájom rôzne. Sú nutne druhý a tretí najväčší prvok uložené vo vrcholoch, ktoré sú synmi koreňa?
   Áno Nie Ani srnka netuší
6. Vzdialenosťou dvoch vrcholov v strome voláme počet hrán, po ktorých musíme prejsť, aby sme sa z jedného vrcholu dostali do druhého. Majme binárny strom, ktorý je vyvážený. Musí potom platiť, že každé dva jeho vrcholy majú vzdialenosť nanajvýš 42.log₂ N + 47?
   Áno Nie Ani srnka netuší
7. Dané sú dva rôzne binárne vyhľadávacie stromy ktoré obsahujú tú istú množinu prvkov. Dá sa vždy jeden z nich postupným robením vhodných rotácii prerobiť na druhý?
   Áno Nie Ani srnka netuší
8. Hugo má pole obsahujúce N² prvkov. Potrebuje nájsť N najväčších z nich. Povedal si, že jednoducho N-krát prejde celé pole a zakaždým nájde a odstráni najväčší prvok. Má tento algoritmus asymptoticky optimálnu časovú zložitosť?
   Áno Nie Ani srnka netuší
9. Paulína potrebuje dátovú štruktúru, ktorá jej umožní v čase logaritmickom od počtu prvkov v nej robiť všetky nasledujúce operácie: vložiť prvok, vybrať prvok, nájsť najmenší prvok, nájsť najväčší prvok. Existuje takáto dátová štruktúra?
   Áno Nie Ani srnka netuší
10. Máme dátovú štruktúru vector (t. j. pole, ktoré sa samo dynamicky zväčší, keď sa zaplní). V tom našom už je N prvkov. Postupne po jednom do neho pridáme (vždy na koniec) ďalších 3N prvkov. Bude mať táto postupnosť krokov časovú zložitosť O(N)?
    Áno Nie Ani srnka netuší
11. Existuje algoritmus, ktorý každé pole obsahujúce 6 navzájom rôznych prvkov usporiada pomocou nanajvýš 8 porovnaní dvojíc prvkov?
    Áno Nie Ani srnka netuší
12. Patrí funkcia f(n)=42 n².log n + 47/n do triedy O(n³)?
    Áno Nie Ani srnka netuší
13. Klasický algoritmus na násobenie dvoch matíc rozmerov N × N má časovú zložitosť kubickú od N. Esmeralda naprogramovala tento algoritmus na svojom počítači. Keď ním vynásobila dve matice rozmerov 100 × 100, trvalo to presne štyri stotiny sekundy. Esmeralda práve spustila svoj program pre matice rozmerov 3000 × 3000. Dočká sa odpovede do minúty?
    Áno Nie Ani srnka netuší
14. Existuje pre každý možný vstup úlohy o hľadaní stabilných manželstiev práve jedno riešenie?
    Áno Nie Ani srnka netuší
15. Monička je bosorka. Pomocou čiernej mágie napísala funkciu magia, ktorá v ľubovoľnom poli obsahujúcom N ≥ 3 navzájom rôznych prvkov nájde v konštantnom čase prvok, ktorý nepatrí ani medzi tretinu najmenších, ani medzi tretinu najväčších prvkov. Pomocou tohto algoritmu Monička implementovala triedenie QuickSort nasledovne:

    QuickSort(A):
        if dĺžka(A) < 3:
            ak má A dva prvky v nesprávnom poradí, vymeň ich
            return A
        else:
            pivot = magia(A)
            male = prvky z A, ktoré sú menšie ako pivot
            velke = prvky z A, ktoré sú väčšie ako pivot
            return QuickSort(male) + pivot + QuickSort(velke)
    

    Bude mať toto jeho triedenie aj v najhoršom možnom prípade časovú zložitosť O(N.log N)?
    Áno Nie Ani srnka netuší