od Dano » 23. 6. 2005 00:18
zadanie bolo nejake taketo:
1. Dokazte nebo vyvratte ze BVS s n uzly se da pomoci O(n) rotaci (definovanych u CC stromu) zdegenerovat na linearni seznam(t.j kazdy uzel ma maximalne jednoho syna).
2. Mame hashovaci funkci z U do (0,1,...,m-1),kde m je moznina 2, ktera resi kolize otevrenou adresaci, vyhledavani probiha nasledovne:
a) i:=h(k); j:=0
b) over pozici i jestli tam je hledany klic nebo jestli je prazdna(ak ano tak konci)
c) j:=(j+1)mod m; i:=(i+j) mod m; goto b
overte ze adresace je spravna teda ze nebudu kontrolovat nakou pozici druhykrat driv nez byx skontroloval vsexny ostatni pozice
urcete o jaky typ adresace se jedna. dokazte dopocitanim koeficientu
3. Mame dan orientovany graf a vahovou funkci ktera kazde hrane prirazuje maximalni vysku vozidla ktere po dane ceste projde bez toho aby narazila na nake prekazky. Popiste co nejefektivnejsi algoritmus, ktery pro dany vrxol s urci pro vsexny ostatni vrxoly ake maximalne vysoke vozidlo sa do daneho vrxolu moze dostat.
zadanie bolo nejake taketo:
1. Dokazte nebo vyvratte ze BVS s n uzly se da pomoci O(n) rotaci (definovanych u CC stromu) zdegenerovat na linearni seznam(t.j kazdy uzel ma maximalne jednoho syna).
2. Mame hashovaci funkci z U do (0,1,...,m-1),kde m je moznina 2, ktera resi kolize otevrenou adresaci, vyhledavani probiha nasledovne:
a) i:=h(k); j:=0
b) over pozici i jestli tam je hledany klic nebo jestli je prazdna(ak ano tak konci)
c) j:=(j+1)mod m; i:=(i+j) mod m; goto b
overte ze adresace je spravna teda ze nebudu kontrolovat nakou pozici druhykrat driv nez byx skontroloval vsexny ostatni pozice
urcete o jaky typ adresace se jedna. dokazte dopocitanim koeficientu
3. Mame dan orientovany graf a vahovou funkci ktera kazde hrane prirazuje maximalni vysku vozidla ktere po dane ceste projde bez toho aby narazila na nake prekazky. Popiste co nejefektivnejsi algoritmus, ktery pro dany vrxol s urci pro vsexny ostatni vrxoly ake maximalne vysoke vozidlo sa do daneho vrxolu moze dostat.