zkouska 22.1.2013

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Lysiii

zkouska 22.1.2013

Příspěvek od Lysiii »

Dneska padly tyto otazky (Koubek otazky temer septal, ostatni jsem neslysela):
Perfektni hashovani, A-sort, Fibonnaciho haldy, dvojite hashovani, quicksort (2x), AVL stromy
Tomgr
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 15. 2. 2010 16:06
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: zkouska 22.1.2013

Příspěvek od Tomgr »

Pak ještě RB stromy, vyhledávání v uspořádaným poli, očekávaná délka nejdelšího řetězce u hašování se separovanými řetězci (neměl jsem to já, ale WTF??), c-universální systémy.
Tomgr
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 15. 2. 2010 16:06
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: zkouska 22.1.2013

Příspěvek od Tomgr »

Trochu mě zarazilo hodnocení.
Třeba já měl u RB stromů vše správně i s důkazama, jenom u delete jsem měl slovně popis (předávání černé nahoru, s dvojitě černou barvou, nebo ukončením na červené) a pak 3 konkrétní ukázky stromů, kde se černá propaguje nahoru nebo kde se zastaví, ale neměl jsem úplný algoritmus (správně je rozbor případů podle barvy bratra a synovců, koukám z pohledu uzlu, co má dvojitě černou barvu).

čekal jsem 2 nebo 3, ale vyhodil mě, že tohle je prej základ. To pak nevím, co člověk může mít špatně na trojku.
blabla
Matfyz(ák|ačka) level II
Příspěvky: 70
Registrován: 27. 1. 2010 23:14
Typ studia: Informatika Mgr.

Re: zkouska 22.1.2013

Příspěvek od blabla »

Tomgr píše:čekal jsem 2 nebo 3, ale vyhodil mě, že tohle je prej základ. To pak nevím, co člověk může mít špatně na trojku.
uplne rovnaky scenar ako ja pred rokom - pokazil som delete pritom vsetko ostatne spravne.. v polcase mi povedal nech este urobim delete, ze zatial je to na 1 a ked som delete nevedel dat cely dokopy tak ma vyhodil :D celkovo pre mna najneprijemnejsia skuska aku som zazil, prvykrat sa mi stalo, ze som skusku dal az na 4. pokus.
Tomgr
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 15. 2. 2010 16:06
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: zkouska 22.1.2013

Příspěvek od Tomgr »

To nerad slyším, rád bych ten předmět splnil dokavad si něco pamatuju :mrgreen: .

Jak reaguje, když se ho někdo zeptá, jestli už to nestačí na trojku a jestli už nemůže jít? Nezkoušel to někdo?
QZuzka
Matfyz(ák|ačka) level III
Příspěvky: 209
Registrován: 2. 12. 2007 19:51
Typ studia: Informatika Mgr.
Bydliště: Praha 4

Re: zkouska 22.1.2013

Příspěvek od QZuzka »

předmět je hrozě random, tak trochu se počítá s tím, že máme víc pokusů

měla jsem dvojité hashování, za půl hodiny jsem popsala 4 stránky textem, žádné odhady nebo důkazy, jen algoritmy member a insert jsem měla i skoro formálně, vysvětlení proč delete nejde dobře, zbytek ve větách, třikrát se mi řekl, že tam mám něco špatně, třikrát jsem ukázala, že tu podmínku i<m, kterou chtěl slyšet, tam mám napsanou, pak zeptal se "je jasné, že tohle je za tři?", poděkovala jsem a šla...



Co jsem slyšela zadání, tak padl kromě hezkých (AVL stromy) i Wordsort a "dijsktra v heapu", asi jak nás bylo hodně, tak ty otázky byly hodně nevyrovnané....

A pozorování založené na dvou případech - když holka přijde pozdě, dostane Leftist haldu.
petrf

Re: zkouska 22.1.2013

Příspěvek od petrf »

Tomgr píše: Jak reaguje, když se ho někdo zeptá, jestli už to nestačí na trojku a jestli už nemůže jít? Nezkoušel to někdo?
Dneska jsem to zkusil a uplne v klidu. Ale pak mi rikal, ze by to byla lepsi znamka nebyt chybky v dukazu slozitosti A-Sortu.
Odpovědět

Zpět na „TIN066 Datové struktury I“