1 / 2
Zestawienie tematów objętych zakresem egzaminu z budowy i analizy algorytmów
Nr
zad.
Tematy
Przykładowe zadania egz.
1.
•
Schematy blokowe podstawowych struktur sterujących:
wyboru warunkowego, pętli „dopóki”, pętli „aż do”, pętli
ograniczonej.
•
Przerabianie schematu algorytmu opartego na pętli
„dopóki” na schemat oparty na pętli „aż do” i odwrotnie.
•
Budowanie pętli ograniczonej w oparciu o pętlę
warunkową i zmienną licznikową.
•
Podstawowe struktur danych: tablice jedno- i
wielowymiarowe, rekordy, wskaźnikowe listy rekordów,
ukorzenione drzewa rekordów (rozróżnianie struktur
statycznych i dynamicznych).
•
Budowa prostych algorytmów wykorzystujących
podstawowe struktury sterujące i struktury danych –
organizowanie współpracy pomiędzy strukturą danych a
strukturą sterującą, np. budowa algorytmów wyszuki-
wania wartości ekstremalnych (wielkości lub położenia),
sumowania, mnożenia i normalizacji liczbowych
elementów zbioru danych wejściowych umieszczonych w
różnych strukturach danych.
•
Opisywanie algorytmu za pomocą schematu blokowego i
pseudojęzyka programowania – przechodzenie z jednego
sposobu opisu na drugi.
Utworzono jednokierunkową listę wskaźnikową z
rekordów o trzech polach: A1, A2 i NST.
Pola A1 i A2 są typu liczbowego, a pole NST jest
wskaźnikiem na kolejny rekord. We wszystkich
rekordach listy pola A1 i A2 wypełniono liczbami.
W oparciu o pętlę (iterację) warunkową typu „dopóki”
narysuj schemat blokowy algorytmu do wyznaczenia
najmniejszej spośród takich liczb zapamiętanych w
polach A1, które są większe lub równe liczbie z pola A2
tego samego rekordu.
Odwołanie do zawartości pola A w rekordzie
wskazanym przez wskaźnik np. X oznacz A[X].
Przyjmij, że zmienna wskazująca na pierwszy rekord
nazywa się GA a pole wskaźnikowe NST w ostatnim
rekordzie na liście zawiera wartość NIL.
Wprowadź odpowiednie zmienne pomocnicze i
zapewnij poprawne działanie algorytmu dla pustej listy.
2.
•
Schemat działania stosu i kolejki, które zbudowano w
oparciu o listę wskaźnikową (realizacja operacji
wstawiania i usuwania rekordów z tych struktur).
•
Zasada działania algorytmów rekurencyjnych.
•
Schematy algorytmów przeszukiwania podstawowych
struktur danych (współpraca struktur sterujących ze
strukturami danych): pętle zagnieżdżone dla tablic
wielowymiarowych, iteracyjne algorytmy przeglądu
drzewa w głąb i wszerz, rekurencyjny algorytm przeglądu
drzewa binarnego.
•
Budowa drzewa BST.
•
Podstawowe algorytmy sortowania: bąbelkowego, ze
scalaniem i drzewiastego (szczegóły działania).
•
Algorytm binarnego wyszukiwania (przez połowienie)
elementu z listy uporządkowanej (szczegóły działania).
•
Przybliżony algorytm wyznaczania upakowania plecaka
oparty na metodzie zachłannej (szczegóły działania).
a)
Z jakich obiektów i jak powiązanych może być
zbudowana struktura danych zwana ukorzenionym
drzewem binarnym? Jaka specyficzna struktura
sterująca w algorytmie jest często powiązana z
drzewiastą strukturą danych? Jaka cecha drzewa
narzuca to pokrewieństwo? Zbuduj drzewo BST dla
ciągu liczb: 7, 4, 6, 2, 11, 5, 8, 12, 9. Podaj ile liści
będzie zawierało to drzewo.
b)
Opisz, w jaki sposób w oparciu o wskaźnikową listę
jednokierunkową można by zbudować strukturę
danych zwaną kolejką. Opisz realizację podstawo-
wych operacji, które pozwalałyby modyfikować tę
strukturę zgodnie z przyjętymi w kolejce zasadami.
Jakie są te zasady? Przyjmij w opisie, że lista
jednokierunkowa utworzona jest z rekordów
posiadających tylko dwa pola: kluczowe i
wskaźnikowe.
3.
•
Cztery metody budowania algorytmów: „wędruj i
sprawdzaj”, „dziel i zwyciężaj”, „zachłanna”,
„programowanie dynamiczne” – schemat działania i
przykładowe realizacje wśród algorytmów omówionych
na wykładach (zapis w pseudojęzyku).
•
Demonstracja działania przykładowych algorytmów na
podanych zestawach danych wejściowych (krok po
kroku).
Podaj charakterystyczne cechy algorytmów opartych na
metodzie „programowania dynamicznego”. Opisz krok
po kroku (podając, co jest wyznaczane, zapamiętywane
i z czym powiązane) jak przebiega realizacja algorytmu
wykorzystującego tę metodę w celu znalezienia
„najkrótszej drogi” z punktu A do punktu J w podanej
sieci połączeń:
2
5
2
2
3
3
4
6
3
6
2
1
A
C
B
D
F
E
G
J
H
I
3
1
4
3
Podaj na koniec długość wyznaczonej drogi i jej
przebieg. Wypunktuj te cechy użytego algorytmu, które
wskazują na zastosowanie programowania
dynamicznego.
