Algorytmy i struktury danych
Przykładowe zadania egzaminacyjne
1. Dla poniższych funkcji podaj asymptotyczne ograniczenia górne:
" f śąnźą=2log nƒÄ…4nƒÄ…n2
,
1
" f śąn źą=nƒÄ…n2ƒÄ…2n
.
2
V ={x1, x2, x3, x4, x5}
G=śąV , Eźą
2. Niech będzie grafem skierowanym, gdzie oraz
E={śą x1, x2źą , śą x2, x3źą ,śą x3, x5źą ,śą x5, x1źą ,śą x3, x2źą , śą x4, x1źą ,śą x5, x1źą}
.
" Podaj macierz sÄ…siedztwa dla grafu G.
" Narysuj graf G.
" Czy graf G jest grafem prostym?
" Czy istnieje co najmniej jeden cykl w grafie G?
3. Narysuj dowolne drzewo z korzeniem zawierające siedem węzłów.
4. Zdefiniuj funkcje w języku C/C++ dla poniższych relacji rekurencyjnych:
1 if n=0
an=
{ }
2an-1 if nÄ…0
1 if n=0
bn=
2 if n=1
{ }
2bn-1-bn-2 if nÄ…1
5. Przedstaw kolejne kroki działania zachłannego algorytmu wydawania reszty dla następujących danych:
Ë% reszta do wydania: 134,
Ë% dostÄ™pne nominaÅ‚y: 50, 20, 10, 5, 2, 1.
6. Przedstaw kolejne kroki działania algorytmu wyszukiwania liniowego dla następujących danych:
Ë% szukany element: 8,
Ë% przeszukiwana tablica: 23 12 3 5 8 -10 10.
7. Przedstaw kolejne kroki działania algorytmu wyszukiwania binarnego dla następujących danych:
Ë% szukany element: 8,
Ë% przeszukiwana tablica: 23 12 3 5 8 -10 10.
8. Przedstaw kolejne kroki działania algorytmu sortowania przez wstawianie dla następujące tablicy:
23 12 8 -10 10.
9. Przedstaw kolejne kroki działania algorytmu sortowania bąbelkowego dla następujące tablicy:
23 12 8 -10 10.
10. Przedstaw kolejne kroki działania algorytmu sortowania przez selekcję dla następujące tablicy:
23 12 8 -10 10.
11. Przedstaw kolejne kroki działania algorytmu prostego przeszukiwania tekstu dla następujących danych:
Ë% wyszukiwany wzorzec: AAB,
Ë% przeszukiwany tekst: ABAAAB.
12. Przedstaw kolejne kroki działania algorytmu Prima znajdowania minimalnego drzewa rozpinającego dla
następującego grafu:
13. Przedstaw kolejne kroki działania algorytmu Kruskala znajdowania minimalnego drzewa rozpinającego
dla następującego grafu: