1. Wymień o opisz struktury sterujące stosowane do budowy algorytmów.
Podstawowe struktury sterujące to:
1.1. bezpośrednie następstwo wykonaj instrukcję A, potem instrukcję B, potem instrukcję C, itd.
1.2. wybór warunkowy jeśli warunek Q jest spełniony wykonaj instrukcję A, jeśli nie to wykonaj
instrukcję B.
1.3. iteracja ograniczona wykonaj instrukcję A dokładnie N razy.
1.4. iteracja warunkowa dopóki dopóki warunek Q jest spełniony wykonuj instrukcję A.
1.5. Iteracja warunkowa aż do wykonuj instrukcję A dopóki warunek Q jest spełniony.
2. Jaka jest konstrukcja algorytmu sortowania bąbelkowego?
Sortowanie bąbelkowe polega na przestawianiu sąsiednich par elementów stojących w niewłaściwej
kolejności. Istotne jest iż ciąg elementów przeglądany jest zawsze w tym samym kierunku, a przeglądanie to
trwa dopóki mogą się w nim pojawić elementy w nieodpowiedniej kolejności.
Zapis słowny algorytmu sortowania bąbelkowego:
1. wykonaj co następuje N-1 razy;
1.1. wskaż na pierwszy element;
1.2. wykonaj co następuje N-1 razy;
1.2.1. porównaj ze sobą wskazany element i element następny;
1.2.2. jeśli elementy stoją w złej kolejności to zamień je miejscami;
1.2.3. wskaż na następny element;
3. Narysuj schemat blokowy: wyboru warunkowego, iteracji warunkowych typu: dopóki i aż do .
Schematy znajdują się na załączonym dodatku.
4. Zapisz słownie i naszkicuj schemat blokowy algorytmu sumowania wektora (jednowymiarowej
tablicy) n elementowego. Wykorzystaj zmienną indeksującą i znajomość długości wektora.
Zapis słowny algorytmu sumowania n -elementowego wektora:
1. zanotuj na boku liczbę zero;
2. wskaż na pierwszy element wektora;
3. wykonaj co następuje n-1 razy;
a. dodaj wartość wskazanego elementu do liczby zanotowanej na boku;
b. wskaż na kolejny element wektora;
4. dodaj wartość wskazanego elementu do liczby na boku;
5. wypisz wartość liczby na boku;
Schemat blokowy algorytmu w załączonym dodatku.
5. Jakie korzyści przynosi stosowanie procedur (podprogramów) w algorytmach?
Zalety stosowania procedur są następujące:
1. oszczędność tekstu
2. znacznie większa przejrzystość i czytelność struktury algorytmu
3. znacznie większa kontrola nad poprawnością algorytmu
4. uproszczenie we wprowadzaniu poprawek i usuwaniu błędów
5. możliwość programowania analitycznego i syntetycznego
6. Na czym polega rekurencja i jak można ją wykorzystać w konstruowaniu algorytmów?
Rekurencja to zdolność podprogramu (procedury) do wywoływania samej siebie. Przykładem
zastosowania procedury rekurencyjnej jest algorytm przenoszenia krążków znany z Wież Hanoi. Tam aby
wykonać pewne przeniesienie należy przy okazji wykonać inne, czyli wywołać tę samą procedurę wewnątrz
procedury wywoływanej na początku.
Inne przykłady wykorzystania procedur rekurencyjnych to:
- przeglądanie lewostronne struktur drzewiastych
- obliczanie wartości n! liczby n.
7. Jakie znasz podstawowe typy danych? Jak są one kodowane binarnie?
Podstawowe typy danych to:
- liczby (całkowite, dziesiętne, dwójkowe, szesnastkowe)
- słowa (układy liter z różnych alfabetów)
- wskazniki (dane tego typu zawierają adresy - wskazania na inne elementy w pamięci
operacyjnej dane tego typu wymagają specjalnego traktowania)
Kodowanie liczb przeliczenie ich wartości na wartości binarne, czyli zero jedynkowe.
Kodowanie słów - odbywa się za pomocą standardu ASCII (American Standard Code for Information
Interchange). Zgodnie z nim każdemu znakowi przypisana jest liczba od 0 do 127 kodowanie na ośmiu bitach.
8. Jakie znasz statyczne struktury danych?
Do statycznych struktur danych należą:
1. zmienne podstawowe obiekty w pamięci, posiadające własną nazwę i zdolność przechowywania
pojedynczego elementu.
2. wektory czyli tablice jednowymiarowe są to obiekty w pamięci mające nadaną własną nazwę i
posiadające zdolność przechowywania określonej mnogości elementów, z których każdy oznaczony jest
odpowiednim, unikalnym indeksem.
3. tablice dwuwymiarowe macierze - są to obiekty w pamięci mające nadaną własną nazwę i posiadające
zdolność przechowywania określonej mnogości elementów, z których każdy oznaczony jest dwoma
indeksami.
4. Tablice wielowymiarowe są to obiekty w pamięci mające nadaną własną nazwę i posiadające
zdolność przechowywania odpowiedniej mnogości elementów, z których każdy oznaczony jest n
indeksami.
9. Jaka struktura sterująca byłaby właściwa do przejrzenia tablicy dwuwymiarowej?
Odpowiednią do tego zadania strukturą sterującą jest iteracja zagnieżdżona. Iteracja zewnętrzna odpowiada
za przeglądanie kolumn a iteracja wewnętrzna za przegląd wierszy.
10. Z jakich obiektów są zbudowane dynamiczne struktury danych?
Dynamiczne struktury danych budowane są z dwóch głównych rodzajów obiektów:
1. zmiennych kluczowych i dodatkowych (przechowujących odpowiednie dane)
2. zmiennych wskaznikowych (wskazujących na kolejne elementy tych struktur, lub przechowujące
wartość NIL)
Rozróżniając dokładniej wyróżniamy:
a) listy jednokierunkowe każdy element tej struktury posiada pola kluczowe, dodatkowe i jedno
pole wskaznikowe, odwołujące się do następnego elementu struktury.
b) listy dwukierunkowe każdy element tej struktury posiada pola kluczowe, dodatkowe i dwa
pola wskaznikowe, odwołujące się do następnego i poprzedniego elementu struktury.
c) drzewa każdy element tej struktury posiada pola kluczowe, dodatkowe, pola wskaznikowe na
potomków (w liczbie n, np.: drzewa binarne 2) i pole wskaznikowe na rodzica.
11. Jak jest zorganizowana struktura danych zwana kolejką?
Kolejka (zwana także strukturą FIFO z ang. first in first out) to specjalna struktura dynamiczna, o
ograniczonych możliwościach modyfikacji. Operacja dodawania elementu do struktury (insert) odbywa się
zawsze na początku, a operacja odłączania (delete) elementu od struktury odbywa się zawsze na końcu tejże
struktury. Zachowana zostaje kolejność dołączania i odcinania elementów od struktury pierwszy
przyłączony będzie pierwszym odłączonym.
12. Jak jest zorganizowana struktura danych zwana stosem?
Stos (zwany także strukturą LIFO z ang. last in first out) to specjalna struktura dynamiczna, o
ograniczonych możliwościach modyfikacji. W strukturze tego typu zarówno operacje dołączania (insert) jak
i odłączania (delete) elementów struktury odbywają się z tej samej strony struktury na początku. Porządek
dołączania i odcinania elementów jest taki, że element położony na strukturze jako ostatni pierwszy będzie z
niej zdjęty.
13. Jak jest zorganizowana struktura danych zwana listą?
Lista to struktura składająca się z wielu odpowiednio ze sobą połączonych ze sobą elementów. Każdy
element jest identyczny jak pozostałe i składa się z odpowiedniej ilości pól kluczowych, dodatkowych i
wskaznikowych (lista jednokierunkowa 1 pole wskaznikowe, dwukierunkowa 2 pola wskaznikowe). Pola
kluczowe i dodatkowe przechowują informacje, natomiast pola wskaznikowe zawierają adresy do
elementów: następnego (jednokierunkowa) i poprzedniego (dwukierunkowa).
14. Narysuj schemat blokowy sumowania pól kluczowych obiektów z listy. Wykorzystaj pola
wskaznikowe i wartość NIL.
Schemat blokowy znajduje się w załączonym dodatku.
15. Jakie znasz typy list?
a) lista jednokierunkowa każdy węzeł zawiera pole kluczowe, pola dodatkowe i jedno pole
wskaznikowe z adresem następnego węzła struktury.
b) lista dwukierunkowa każdy węzeł zawiera pole kluczowe, pola dodatkowe i dwa pola
wskaznikowe z adresami następnego i poprzedniego węzła struktury.
http://notatek.pl/informatyka-62-pytania-i-odp?notatka
c) lista z wartownikiem jest to dwukierunkowa lista, z której wyeliminowano wskazanie NIL.
Pierwszy węzeł jako wskazanie na węzeł poprzedni odnosi się do węzła ostatniego. Węzeł
ostatni jako wskazanie na węzeł następny odnosi się do węzła pierwszego. (Jest to jak gdyby
zapętlenie struktury.)
d) lista jako kolejka
e) lista jako stos
16. Jak jest zorganizowana struktura danych zwana drzewem?
Drzewo składa się z odpowiedniej mnogości identycznych elementów - zwanych węzłami. Każdy węzeł
zawiera:
- pole kluczowe (zawiera dane)
- pola dodatkowe (zawierają dane)
- pola wskaznikowe na potomstwo (zawierają adresy potomstwa elementów następnych)
- pole wskaznikowe na rodzica (zawiera adres rodzica elementu poprzedniego)
Opis biologiczny drzewa:
1. wskazanie na korzeń element wskaznikowy (na grafie często pomijany), zawierającym adres
pierwszego węzła drzewa.
2. korzeń pierwszy węzeł drzewa (zazwyczaj w grafie umieszczony na górze), nie posiadający rodzica.
3. węzły wszystkie elementy struktury leżące pomiędzy korzeniem a liśćmi.
4. liście elementy leżące na najniższym poziomie drzewa i nie posiadające potomstwa (ich pola
wskaznikowe przechowują wartość NIL).
Połączenia pomiędzy poszczególnymi węzłami określa się mianem gałęzi drzewa.
W celu ustanowienia hierarchii w strukturze drzewiastej przyjęto iż elementy leżące na gałęziach danego
węzła określa się mianem potomstwa danego węzła. Wskazany element jest zatem rodzicem elementów
jemu podległych.
W drzewie wyróżnia się także poziomy, przy czym ich odliczanie zaczyna się od góry: korzeń stanowi
poziom pierwszy, a poziom ostatni tworzą liście.
Wszystkie drzewa dzieli się na:
BST drzewo, którego rząd wyjściowy potomków ograniczony jest przez 2.
PEANE drzewo, w którym wszystkie wierzchołki poza liśćmi mają jednakową liczbę potomków i
wszystkie liście są na tym samym poziomie.
17. Co to jest drzewo binarne?
Drzewo binarne to drzewo, którego rząd wyjściowy węzłów jest ograniczony przez 2. Każdy węzeł może
zatem posiadać maksymalnie 2 potomków.
18. Jaki obiekt w drzewie nazywany jest liściem a jaki korzeniem?
Korzeń jest to wierzchołek drzewa (w grafie zazwyczaj umieszczany na górze) - nie posiadający rodzica.
W korzeniu mają początek wszystkie procesy algorytmiczne oparte na strukturze danych tego typu.
Liść wierzchołek końcowy drzewa (w grafie umieszczony zazwyczaj na dole) - nie posiadający
potomstwa. Odpowiada on różnym wynikom zakończenia obliczeń w algorytmie.
Wyszukiwarka
Podobne podstrony:
głowacki,lokalne sieci komputerowe, pytania i odp egzaminMB pytania ODPpytania odp rachunekpytania i odp do wyderkipytania odp PROWEgzamin pytania i odp, gr 1!Pmisw pytania odp czesc teoretycznaściągi jelop spisane pytania i odppytania odp sitmp informatyka styczeń 2009 odpNota Informacyjna TS pytania prejpytania odp23 Studia niestacjonarne I stopnia Informatyka SI pytania na egzamin dyplomowypytania?z odp po weryfikacjiangielski pytania 3 odpangielski pytania 5 odpwięcej podobnych podstron