Przykładowe zadania na kolokwium zaliczeniowe
1. Dany jest ciąg funkcji: logn,n2,8logn, logn!, n3.
a) uporządkuj je ze względu na rosnący rząd wielkości
b) ustal rząd funkcji będącej sumą wszystkich funkcji zawartych w rozważanym ciągu.
2. Na komputerze K wykonanie algorytmu A dla danych p o rozmiarze 6 zajmuje 9 sekund. Złożoność tego algorytmu opisuje funkcja T(n) = 3n.
a) ile czasu zajmuje wykonanie algorytmu A dla danych o rozmiarze 10 na tym komputerze
b) ile czasu będzie potrzebował komputer K1 dokładnie 243 razy szybszy od komputera K do wykonania algorytmu A dla danych o rozmiarze 12.
3. Napisz dowolny algorytm iteracyjny i zapisz go w języku Pascal. Wyjaśnij, jakie zadanie wykonuje ten algorytm.
4. Napisz dowolny algorytm rekurencyjny i zapisz go w języku Pascal. Wyjaśnij, jakie zadanie wykonuje ten algorytm.
5. Napisz dowolny program sortujący w języku Pascal (lub pseudokodzie) i ustal jego rząd wielkości.
6. Podaj przykłady zmiennych dynamicznych oraz nazwij operacje, jakie się na tych zmiennych wykonuje.
7. Podaj definicję listy i utwórz listę cykliczną jednokierunkową.
8. Jakie działania można wykonać na stosie? Do wykonywania, jakich algorytmów jest on przydatny.
9. Jaka jest różnica wyszukiwania sekwencyjnego od binarnego? Jaka jest złożoność obliczeniowa tych algorytmów?
10. Naszkicuj dowolne drzewo stopnia trzeciego o wysokości cztery takie, dla którego tylko dwa węzły będą miały stopień trzy.
11. Podaj przykład drzewa BST o wysokości cztery(wpisując odpowiednie klucze) i zastosuj znane Tobie metody przechodzenia drzewa.
12. Podaj przykład drzewa czerwono czarnego.
13. Czy na podstawie listy składającej się z następujących liczb: 23,11,20,10,7,18,16,8,3,5,2,14 można utworzyć kopiec?
14. Czym różni się kolejka od kolejki priorytetowej?
15. Narysuj drzewo dwumianowe stopnia czwartego.
16. Co to są algorytmy zachłanne? Podaj klika przykładów.
17. Zastosuj algorytm Huffmana w celu kompresji danych przyjmując następującą częstość liter:
a-24, b-7, c-6, d-11, e-14, f-2, g-1, i-13
Na podstawie tak skonstruowanego kodu zakoduj wyraz „babcia”.
18. Utwórz 20 dowolnych liczb dwucyfrowych i zastosuj funkcję laszującą stosując łańcuchowanie jako k mod 10 oraz dla bloków nadmiarowych k mod 4.
19. Zastosuj algorytm RSA w celu utworzenia klucza publicznego i prywatnego dla wybranych par liczb pierwszych: (11,17),(23,11),(11,19),(19,23) itp.
Wyjaśnij metodę szyfrowania i deszyfrowania na podstawie otrzymanych kluczy.
20. Narysuj dowolny graf o co najmniej 8 wierzchołkach i zapamiętaj go przy pomocy macierzy sąsiedztwa.
21. Narysuj graf ważony o co najmniej 10 wierzchołkach i zbuduj minimalne drzewo rozpinające.