Informatyka UJ forum

chlebek

Pomoc dla naszych to zestaw pytan jakie byly na egzaminie, wspolnymi silami odtworzymy caly egzamin:

( pomijamy pytania, ktore udostepnil dr Slusarek )

1. Zlozonosc Dijkstry
2. W 200-elementowym kopcu wykonujemy operację
insert .Pesymistyczna liczba porównań kluczy wynosi:
3. Jezeli wstawimy do drzewa AVL elementy: 1,2,3,4,5,67, to ile razy
wykonaja sie rotacje( podwoja liczmy jako raz )
4. Majac dane 4 elementy, chcemy je posortowac najszybszym
algorytmem, ile wykona sie porownan
5. Dany jest kopiec, aby odczytac elementy rosnaco nalezy: (odczytac
inorder lub preorder ... itp, jest tez zadne z pozostalych :) )
6. Mam dany pewne liczby np ( 535, 245,421, 611 ) sortujemy je radix
sortem wedlug bitu najmniej znaczacego, liczb 421 bedzie na pozycji:
7. Algorytmy ktory sortuje stabilnie to:
8. Jaki zachodzi stosunek pomiędzy funkcjami f(x)=2^(x+1),
g(x)=3^(x/2)? (Chodziło o funkcje "O duże", "omega", "theta", czyli czy
np. g należy do O(f))
9. Złożoność algorytmu sortowania przez zliczanie: (Wypisane jakieś
własności typu "nie zależy od danych wejściowych", "jest kwadratowa",
"nie zależy od zakresu kluczy", wskaż poprawną)
10. Dana jest funkcja: f(0)=0; f(2x)=2*f(x) + x + 1
Która z własności nie zachodzi:
(Do wyboru 5 przynależności typu f należy do O(n), f należy do
O(n^2), f należy do theta(n log n))
11. Realizujemy kolejkę priorytetową za pomocą drzewa AVL. Jakie są
minimalne złożoności operacji: Insert, FindMin, RemoveMin
12. Losowy wybór elementu dzielącego w QuickSorcie: (Wypisane jakieś
opcje typu "uniezależnia działanie algorytmu od danych wejściowych",
"zmienia złożoność pesymistyczną", wskaż poprawną)
13. Mamy 2048 bajtow pamieci. Ile pozostanie nam wolnych blokow gdy
zaalokujemy takie bloki: 512, 128, 32? Przydzielamy pamiec
algorytmem z wykladu, ktory operuje na blokach rozmiarow potegi
dwojki.

Rogal

Proponuję, żebyś Ty Chlebek zmieniał pierwszego posta i wrzucał wszystkie nowości z całego topicu.

8. Jaki zachodzi stosunek pomiędzy funkcjami f(x)=2^(x+1), g(x)=3^(x/2)? (Chodziło o funkcje "O duże", "omega", "theta", czyli czy np. g należy do O(f))

9. Złożoność algorytmu sortowania przez zliczanie: (Wypisane jakieś własności typu "nie zależy od danych wejściowych", "jest kwadratowa", "nie zależy od zakresu kluczy", wskaż poprawną)

10. Dana jest funkcja: f(0)=0; f(2x)=2*f(x) + x + 1
Która z własności nie zachodzi:
(Do wyboru 5 przynależności typu f należy do O(n), f należy do O(n^2), f należy do theta(n log n))

11. Realizujemy kolejkę priorytetową za pomocą drzewa AVL. Jakie są minimalne złożoności operacji: Insert, FindMin, RemoveMin

12. Losowy wybór elementu dzielącego w QuickSorcie: (Wypisane jakieś opcje typu "uniezależnia działanie algorytmu od danych wejściowych", "zmienia złożoność pesymistyczną", wskaż poprawną)

exeman

12. Mamy 2048 bajtow pamieci. Ile pozostanie nam wolnych blokow gdy zaalokujemy takie bloki: 512, 128, 32? Przydzielamy pamiec algorytmem z wykladu, ktory operuje na blokach rozmiarow potegi dwojki.