Egzamin ze struktur danych i algorytmów
Imię: Nazwisko:
EFEKTYWNOŚĆ ALGORYTMU TO
Zapewnienie, że dla każdego egzemplarza zadania algorytm zatrzymuje się i daje dobry wynik.
Ilość zasobów potrzebnych do jego wykonania, zwykle czasu działania algorytmu (inaczej - liczbą wykonywanych w algorytmie prostych operacji definiowanych odrębnie dla każdego zadania obliczeniowego - przyjmuje się, że wykonanie operacji elementarnej jest sprzętowo niezależne - wymaga stałego czasu)
PĘTLA Z WARTOWNIKIEM:
czyta i przetwarza dane ż do napotkania szczególnego, niedozwolonego elementu
stosuje się w sytuacjach, gdy zawczasu wiadomo, ile razy pętla będzie wykonywana
DEFINICJA ZADANIA TO
Opis danych wejściowych i danych wyjściowych uzupełniony o treść zadania i przykład rozwiązania zadania.
Opis zbioru wartości, które może przyjmować typ zmiennej
OPIS ALGORYTMU TO
Opisu obiektów, na których działa oraz opisu czynności, które są wykonywane na tych obiektach.
Opis typów danych
OBJAWY PĘTLI NIESKOŃCZONYCH TO:
Oscylacje: powtarzanie w kółko pewnych instrukcji na tych samych wartościach
Działania rozbieżne: pojawianie się coraz większych lub coraz większych wartości (zazwyczaj powoduje to oczywiście przerwanie programu)
KAŻDY WIERZCHOŁEK W DRZEWIE MUSI BYĆ OSIĄGALNY Z KORZENIA PRZEZ WYZNACZONY JEDNOZNACZNIE CIĄG KRAWĘDZI, ZWANY ŚCIEŻKĄ
tak
nie
ALGORYTM TO
Ciąg czynności przekształcający dane wejściowe w dane wyjściowe powstały w wyniku rozwiązania jakiegoś zadania.
Opis danych wejściowych i danych wyjściowych.
PROCEDURA TO
Opis zbioru wartości, które może przyjmować typ zmiennej
Część algorytmu z przypisanym mu identyfikatorem, za pośrednictwem którego można się do niej odwołać i spowodować jej wykonanie dla pewnych argumentów.
ODWOŁANIE SIĘ DO INDEKSU WEKTORA SPOZA DOPUSZCZALNEGO PRZEDZIAŁU TO TYPOWY BŁĄD:
logiczny
językowy
algorytmiczny
WYSTĘPUJĄ NASTĘPUJĄCE RODZAJE PĘTLI:
pętle z wartownikiem
pętle z licznikiem
pętle ogólne
DO OPISU DANYCH W JĘZYKU PROGRAMOWANIA WYKORZYSTUJE SIĘ
Definicje stałych, definicje typów i deklaracje zmiennych.
Definicje procedur
STOS TO LINIOWA STRUKTURA DANYCH, DOSTĘPNA DO ZAPISYWANIA I ODCZYTYWANIA TYLKO Z JEDNEGO KOŃCA. STOS MOŻNA ZDEFINIOWAĆ ZA POMOCĄ OPERACJI, KTÓRE ZMIENIAJĄ LUB SPRAWDZAJĄ JEGO STAN. PROSZĘ ZDEFINIOWAĆ TE OPERACJE W POSTACI PROCEDUR.
ZAKRESEM OBIEKTU WPROWADZONEGO W PROCEDURZE JEST
Procedura
Program
CZY TYPY STANDARDOWE SĄ DEFINIOWANE W PROGRAMIE PRZEZ PROGRAMISTĘ?
Tak
Nie
PROSZĘ ZDEFINIOWAĆ DWIE WERSJE PROCEDURY SILNIA: JEDNĄ REKURENCYJNĄ, DRUGĄ WYKORZYSTUJĄCĄ ZAMIAST REKURENCJI PĘTLĘ.
ZMIENNE STATYCZNE
Istnieją przez cały czas realizacji tej części programu, w której są lokalne
Mogą być wygenerowane w wyniku realizacji jednej z instrukcji i nie mają jawnych identyfikatorów
DO NADAWANIA ZMIENNEJ NOWEJ WARTOŚCI, OTRZYMANEJ W WYNIKU WARTOŚCIOWANIA WYRAŻENIA SŁUŻY
Instrukcja przypisania
Instrukcja pętli
DO WYBRANIA JEDNEJ Z KILKU INSTRUKCJI I NASTĘPNIE WYKONANIA JEJ SŁUŻY
Instrukcja skoku
Instrukcja wyboru
DEFINIOWANIE OBIEKTÓW W ALGORYTMIE POWINNO SPEŁNIAĆ ZASADĘ, KTÓRA MÓWI, ŻE DEFINICJA POWINNA ZAWIERAĆ WYŁĄCZNIE TERMINY WCZEŚNIEJ ZDEFINIOWANE. PROSZĘ PODAĆ PRZYKŁAD DEFINICJI TYPU NARUSZAJĄCY TĄ ZASADĘ.
WYRAŻENIA SKŁADAJĄ SIĘ
ze stałych, zmiennych, operatorów i nazewników funkcji
ze stałych, zmiennych i operatorów
INSTRUKCJE ELEMENTARNE
wykonują akcje podstawowe algorytmu
sterują kolejnością ich wykonania
NASTĘPSTWO, WYBÓR I ITERACJA TO INSTRUKCJE
Proste
Sterujące
WYKONAJ A DOKŁADNIE N RAZY TO
Iteracja ograniczona
Iteracja warunkowa
CZY MOGĄ WYSTĘPOWAĆ PĘTLE ZAGNIEŻDŻONE
Nie
Tak
DYNAMICZNE PRZYDZIELANIE PAMIĘCI W DYNAMICZNYCH WIĄZANYCH STRUKTURACH DANYCH
wykonywane jest oddzielnie dla każdej ze składowych struktury w chwili powołania jej do życia podczas wykonywania programu
wykonywane jest dla każdej całej struktury jednocześnie w chwili powołania jej do życia podczas wykonywania programu