Algoritmy

Kategorie: Pascal

Typ práce: Otázky k Mgr. SZZk

Škola: nezadáno/škola není v seznamu

Charakteristika: Práce se zaměřuje na algoritmy. Práce obsahuje deset základní otázek a několik podotázek týkající se například zásobníku, pointeru, dynamické alokace paměti, objektově orientovaného programování nebo binárních stromů.

Obsah

1.
Otázky - zásobník, fronta a seznam
2.
Otázky - Pointery, dynamická alokace paměti
3.
Otázky - dynamicky alokované datové struktury
4.
Otázky - Objektově orientované programování I
5.
Otázky - Objektově orientované programování II
6.
Otázky - Objektově orientované programování II, polymorfismus
7.
Otázky - Binární stromy
8.
Otázky – Binární vyhledávací stromy
9.
Otázky – Vyvážené a vícecestné stromy
10.
Otázky – Hašování

Úryvek

"1. Vysvětlete co znamená, že zásobník představuje pamět » typu LIFO.
Zásobník (Stack) je jednou ze základních datových struktur, která se využívá především pro
dočasné ukládání dat v průběhu výpočtu. Zásobník data ukládá způsobem, kterému se říká LIFO - last in, first out - čili poslední vložený prvek jde na výstup jako první, předposlední jako druhý a tak dále. Zasobnik lze přirovnat k zásobníku nabojů v pistoli1. Naboje jsou přesouvany do nabojove komory v opačnem pořadi, než byly do zasobniku vloženy. V jednom okamžiku mame k dispozici pouze horni naboj nebo je zasobnik prazdny. Ke spodnim nabojům se lze dostat jen vyjmutim předchozich nabojů.

2. Co je to vrchol zásobníku? Co je to dno zásobníku?
Ukazatel na aktualni prvek v zasobniku (posledně vloženy) se nazyva
vrchol zasobniku (angl. stack pointer). Opakem je dno zásobníku.

3. Jaká je teoreticky kapacita zásobníku?
Zasobnik ma teoreticky neomezenou kapacitu.

Prvky zásobníku jsou uchovávány v poli z, proměnná vrchol ukazuje vždy na vrchol zásobníku (na nejvrchnější položku) a konstanta MAX určuje maximální délku pole. Je tedy zřejmé, že kapacita zásobníku při použití pole je omezená. Pokud bude vrchol = MAX a vykonáme nad zásobníkem operaci push(), dojde k tzv. přetečení zásobníku. Na to je možné reagovat výjimkou. Jinou možností je vytvoření tzv. dynamicky rozšiřovatelného pole, které může měnit svou velikost podle aktuální potřeby.

4. Co je to přetečení zásobníku? Co je to podtečení zásobníku?
Pokud ji omezime např. velikosti přidělene paměti, a nelze již přidat dalši
prvek nastava opět chyba tzv. přetečeni (angl. overflow).

Pokud provedeme operaci Pop na prazdnem zasobniku nastava chyba tzv. podtečeni
(angl. underflow).

5. Jak se typicky nazývá operace vložení prvku do zásobníku? Popište tuto operaci.
Operace vloženi do zasobniku se tradičně nazyva Push. Po provedení příkazu PUSH se prvek X stává novým vrcholem zásobníku a přikrýcá předchozí vrchol(pokud nebyl zásobník prázdný).

6. Jak se typicky nazývá operace vložení prvku do zásobníku? Popište tuto operaci.
Operace vyjmuti se nazyva Pop. Vyjmutí (pop) hodnoty ze zásobníku je jednoduše inverzní operace k vkládání. Prvek na vrcholu je odstraněn a ukazatel je aktualizován v opačném pořadí než jaké bylo použito při vkládání.

7. Závisí složitost operací na počtu prvků v zásobníku? Ano či ne?
IMO ne, operace probíhá pokaždé v podstatě mezi dvěma operandy, takže zvýšeným počtem prvků se zvyšuje počet operací, ale složitost je stejná

8. Uveďte příklady použití zásobníku.
Nejčastější použití zásobníku na úrovni hardwaru (architektury) je jako prostředek k alokování a přidělování paměti. Uchovávání dat a mezivýpočtů, PostScript, PDF.

V praxi se používá především pro ukládání rekurzí. Příkladem by mohl být program, který počítá jako kalkulačka se závorkami. Každá závorka v závorce je rekurzí. Když hledáme jednu závorku za druhou, zároveň narážíme na další, které se nacházejí uvnitř. Tímto se vytváří jakýsi strom. Prohledáním se zapíše do zásobníku obsah závorek a pak se kalkuluje nejprve ta poslední nalezená. Asi nejběžnějším příkladem je historie v prohlížečích. Když kliknete na zpět, otevře se posledně otevřená stránka.

9. Do zásobníku vložím prvky v pořadí A, B, C, D. Potom je budu ze zásobníku vyjímat. Jakou dostanu posloupnost?
D,C,B,A

10. Vysvětlete co znamená, že fronta představuje paměť typu FIFO.
Fronta uplatňuje mechanismus přistupu FIFO – first in, first out – jako prvni je z fronty odebran prvek, ktery byl do fronty prvni vložen. Jde tudiž o obdobu fronty, jak ji zname z každodenního života.

11. Co je to hlava fronty? Co je to ocas fronty?
Pro implementaci fronty jsou již potřeba dva ukazatele. Jeden ukazatel určuje hlavu (začatek) fronty (angl. head) tj. ukazuje na prvek, ktery je na řadě pro odebrani, druhym ukazatelem je ocas (konec) fronty (angl. tail). Tento ukazatel ukazuje na posledni prvek ve frontě.

12. Závisí složitost operací na počtu prvků ve frontě? Ano či ne?
ne

13. Co je to přetečení fronty? Co je to podtečení fronty?
Pokud provedeme operaci Get nad prazdnou frontou, nastane chyba podtečeni. U velikostně omezene fronty může nastat i přetečeni, překročime-li při vkladani přiděleny prostor.

14. Do fronty vložím prvky v pořadí A, B, C, D. Potom je budu z fronty vyjímat. Jakou dostanu posloupnost?
A,B,C,D ( jako lide stojící v řade u přepážky, tak jak stoji za sebou v rade, tak i postupne odcházejí).

15. Jak se typicky nazývá operace vložení prvku do fronty? Popište tuto operaci.
Operace vloženi prvku se tradičně nazyva Put.
16. Jak se typicky nazývá operace vyjmutí prvku z fronty? Popište tuto operaci.
Vyjmutí prvku z hlavy fronty, tato operace se nazývá GET."

Poznámka

výška, Práce obsahuje tabulky o rozsahu cca půl strany.

Vlastnosti

STÁHNOUT PRÁCI

  1. SMS platba (ČR) 30 Kč

    Platba prostřednictvím brány mobilního operátora. Pro započetí platebního procesu prosím vyplňte kontrolní kód a stiskněte tlačítko "Zaplatit"

    Po proběhnutí platby budete přesměrováni zpět na tuto stránku, kde najdete odkaz ke stažení práce.


    V případě potíží s realizací platby se neváhejte obrátit na infolinku poskytovatele služby, společnost Advanced Telecom Services s.r.o., na čísle +420 776 999 199

    Nápověda pro zákazníky Telefónica O2:

    1. Vyplňte Vaše číslo na mobil, zvolte jako operátora Telefónica O2 a klikněte na POTVRDIT.
    2. Zobrazí se Vám informace, že SMS byla odeslána.
    3. Na mobilní telefon Vám bude doručena SMS zpráva s odkazem.
    4. Klikněte na odkaz v SMS zprávě, budete propojeni na platební bránu společnosti Telefónica O2. Zde potvrďte platbu.
    5. Na internetu se zobrazí výsledek proběhlé platby.
    Pro úspěšnou realizaci platby je nutné mít aktivní službu „O2 platba“. Služba je většinou aktivní automaticky, takže není třeba nejdřív nic aktivovat.

    Nápověda pro zákazníky Vodafone:

    1. Vyplňte Vaše číslo na mobil, zvolte jako operátora Vodafone a klikněte na POTVRDIT.
    2. Dojde k přesměrování na Vodafone portál.
    3. Potvrďte Vaše mobilní číslo kliknutím na DALŠÍ. .
    4. Na Váš mobilní telefon přijde SMS zpráva s kódem.
    5. Zadejte tento kód do formuláře, klikněte na OK.
    6. Objeví se Vám údaje o platbě, kterou potvrďte kliknutím na POKRAČOVAT.
    7. V té chvíli proběhne platba, o jejímž výsledku Vás informuje došlá SMS zpráva.
    Pro úspěšnou realizaci platby je nutné mít aktivní službu „M-peněženka“. Služba je většinou aktivní automaticky, takže není třeba nejdřív nic aktivovat.

    Nápověda pro zákazníky T-mobile:

    1. Vyplňte Vaše číslo na mobil, zvolte jako operátora T-mobile a klikněte na POTVRDIT.
    2. Dojde k přesměrování na T-mobile portál, potvrďte zde svůj souhlas s podmínkami platby.
    3. Pokud máte na T-zones účet, přihlaste se a pokračujte bodem 7.
    4. Pokud účet na T-zones nemáte, vepište do formuláře svoje mobilní číslo a klikněte na ODESLAT ČÍSLO.
    5. Přijde Vám SMS zpráva s kódem.
    6. Vepište kód jako heslo do formuláře a klikněte na PŘIHLÁSIT.
    7. Objeví se Vám údaje o platbě, které potvrďte kliknutím na tlačítko ZAPLATIT.
    8. V té chvíli proběhne platba, o jejímž výsledku Vás informuje došlá SMS zpráva.
    Pro úspěšnou realizaci platby je nutné mít aktivní službu „M-platba“. Služba je většinou aktivní automaticky, takže není třeba nejdřív nic aktivovat.
  2. Platit kartou 30 Kč

    Platba kartou. Pro započetí platebního procesu prosím vyplňte kontrolní kód a stiskněte tlačítko "Zaplatit"

    Po proběhnutí platby budete přesměrováni zpět na tuto stránku, kde najdete odkaz ke stažení práce.


    Po odeslání kontrolního kódu budete přesměrováni do platební brány GP webpay, kde zadáte údaje potřebné pro platbu. Platbu dokončíte stisknutím tlačítka "ZAPLATIT".

    Akceptované karty: VISA, VISA Electron, V PAY, MasterCard, Maestro.

  3. Koupit za kredity - 25 Kč >>> ZVÝHODNĚNÁ CENA!
    Jedním stiskem tlačítka, obratem a za výhodnou cenu!
    JEN PRO REGISTROVANÉ UŽIVATELE
    Cena za stažení je pouze 450 kreditů (=25Kč).
  4. Platit převodem z ČSOB a Poštovní spořitelny, službou PaySec 25 Kč >>> ZVÝHODNĚNÁ CENA!
    Rychle, bezpečně a pohodlně.
    Zaplatit za tuto práci přes PaySec >>> Kliknutí na odkaz Vás přesměruje do platebního rozhraní
    Kliknutím na ikonku Vás přesměrujeme do platebního systému, kde si vyberete převod z ČSOB, Poštovní spořitelny nebo platbu PaySec
  5. SMS platba (Slovensko) - 1,20€
    Stahovací kód k této práci získáte do několika minut se službou mobilního operátora Premium Rate SMS.
    Zašlete SMS zprávu ve tvaru: SEMmezera29394
    - na telefonní číslo: 8877
    Cena jedné SMS je 1,20€ včetně DPH. Pro využití SMS platby je třeba mít aktivovanou službu Premium Rate SMS. Službu technicky zajišťuje Advanced Telecom Services, s. r. o.
    SMS musí být ve formátu TEXT, bez diakritiky a bez formátování (tj. základní velikost a typ písma). Stahovací kód je použitelný pouze pro tuto práci a je platný až do uzavření okna internetového prohlížeče.
    Stahovací kód přijde obratem na mobil, je platný 24 hodin a lze jej zadat celkem dvakrát.
    Pro stažení této práce zadejte stahovací kód (bez uvozovek):


Důležité informace: Provedením mobilní platby, odesláním SMS, platbou kredity, platbou kartou, PaySecem nebo převodem z účtu souhlasíte s Podmínkami stahování.
Veškeré informace o platbách si můžete přečíst zde.
Máte při placení nebo stahování práce problém? Odpovědi na časté problémy najdete zde nebo kontaktujte naší podporu.

Diskuse