9988996109

Egzamin Poprawkowy ze Wstępu do Informatyki. 8 września 2011.

Zadanie 1

Dane są dwie listy: pierwsza zawiera liczby ujemne i jest posortowana rosnąco, druga zawiera liczby dodatnie i jest posortowana malejąco. Napisać procedurę, która połączy te listy w jedną posortowaną rosnąco.

Zadanie 2

Drzewo BST o kluczach całkowitych jest fc-rzadkie, jeśli moduł różnicy kluczy z każdych dwóch różnych wierzchołków jest większy od k. Napisz procedurę, która dla danego drzewa BST o kluczach całkowitych i liczby k sprawdzi czy to drzewo jest fc-rzadkie.

Zadanie 3

Dla danego grafu skierowanego G = (V, E) i zbioru wierzchołków X C V sprawdzić czy z każdego wierzchołka grafu można dojść do pewnego wierzchołka w zbiorze X.

UWAGA. To zadanie można rozwiązać opisując algorytm słownie (tzn. nie jako procedurę w Języku Pascal) używając do opisu algorytmów poznanych na wykładzie.

Zadanie 4

Zdefiniuj co to jest minimalne drzewo rozpinające grafu z wagami G. Jaka jest złożoność algorytmu znajdowania minimalnego drzewa rozpinającego? Jak by się zmieniła złożoność tego algorytmu, gdyby graf reprezentować przy pomocy macierzy incydencji?

Naszkicuj minimalne drzewo rozpinające dla grafu G z funkcją wag w reprezentowanych przez następujące listy incydencji:

1	(2,2)	(4,6))
2	(1,2)	(3,4)	(6,3)	(5	2)
3	(2,4)	(6,2)
4	(1,6)	(5,4)	(8,6)
5	(2,2)	P,l)	(4,4)	(9	3)
6	(3,2)	(2,3)	(7,6)
7	(6,6)	(5,1)	(9,7)
8	(4,6)	(8,4)
9	(5,3)	P,7)	(8,4)

Para na liście oznacza koniec krawędzi i jej wagę. Na przykład druga para na pierwszej liście (4,6) oznacza, że krawędź z 1 do 4 ma wagę 6.

Egzamin ze Wstępu do Informatyki. 6 czerwca 2011.