DSC00125 (7)

należy wstawić x w kratce za każdą poprawną, odpowiedzią.

• Jaka może być maksymalna długość listy korzeni zaraz po wykonaniu Eactrac-t-Hin. na kopcu dwumianowym zawierającym n elementów? ©(lg²n) O; ©(n) Q- ©(ti?) Q-, ©(V) O^-,

©(lg*n) □; ©(lg n) □;

• Jaka może być maksymalna długość listy korzeni zaraz po wykonaniu Ertract-Hia na kopcu Fibonacciego zawierającym n elementów? ©(Ig ri) □; ©(lg²n) O; ©(n) D* ©(n*) Q-0(1) O; @(lg*n) □;

• Jaki może być w najgorszym przypadku faktyczny koszt operacji Decrease-Key na kopcu dwumianowym zawierającym n elementów? ©(Ig n) O; ©(lglg ri) Q*, ©(\g²n) O^-, ©(n) O*, 0(y/ń) □; 0(n²) □; ©(1) □; ©(lg*n) □;

• Jaki jest w najgorszym przypadku faktyczny koszt operacji Dec.rease-K.ey na kopcu Yiko-nacciego zawierającym n elementów? 0(\/n) □; 0(n²) Q-, 0(1) D‘, 0(\g*n) Q‘, 0(\gn) Q‘, 0(lglgn) □; 0(lg²n) O; 0(n) □;

¹ Jaka jest maksymalna długość listy korzeni (2ⁿ)-węzłowego kopca Pibonaceiego? 0(2”) □; 0(1) □; 0(lglgn) □; ©(n²) □; ©(n) O*, ©(lgn) D-, ©(nłgn) Q‘,

Jaka jest maksymalna długość listy kor zeru (2ⁿ — l)-węz\owego kopca dwumianowegc 0(n) □; ©(lgn) □; ©(nlgn) □; ©(2ⁿ) □; ©(1) O; ©(lglgn) Q* ©(n²) |g

Jaki czas jest potrzebny aby policzyć alternatywę n bitów przechowywanych, w n kor Jcach pamięci n-procesorowej maszyny Common-CHCW PRAM? ©(V) Q\ ©(\g*n □; 0(lglg ri) □; ©(lg²n) □; ©(n) □; ©(n²) O;