Strona 3
AiSDE Egzamin
Pytanie 17
W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:
napotkamy pozycję wolną
wykonamy rehasz określoną liczbę razy
funkcja rehaszu zwróci tą samą wartość
napotkamy pozycję zajętą przez inny element
Pytanie 18
Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:
liczbie liter najdłuższego słowa
liczbie liter alfabetu
liczbie słów słownika
Żadne z powyższych
Pytanie 19
W algorytmach znajdowania rozłącznych ścieżek przeplot to:
najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek zgodnie z ich skierowaniem
najkrótsza ścieżka nie korzystająca z krawędzi należących do dotychczasowych ścieżek
Pytanie 20
Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie 1/2 w grafie resztkowym odpowiada:
krawędź nieskierowana o przepustowości 1/2
krawędź skierowana przeciwnie do przepływu o przepustowości 1/2
krawędź skierowana zgodnie o przepust. 1/2 i krawędź skierowana przeciwnie o przepustowości 3/2
krawędź nieskierowana o przepustowości 3/2
Pytanie 21
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
najkrótszej, algorytmem Dijkstry
dowolnej, algorytmem poprawiania etykiet
dowolnej, algorytmem Dijkstry
najkrótszej, algorytmem poprawiania etykiet
Pytanie 22
W grafie o m wierzchołkach i n krawędziach stosunek liczby ograniczeń dotyczących przepustowości w sformułowaniach problemu przepływu d towarów i 1 towaru wynosi:
m
d
1
n
Pytanie 23
Dane są 4 krawędzie grafu i ich przepustowości: AB=1, BC=2, CD=1, DA=2 oraz zapotrzebowania AC=3, BD=2. Przepływ wielotowarowy jest:
nierealizowany, bo 6<10
realizowany, bo 6>5
nierealizowany, bo 6>=5
realizowany, bo 6<=10
Pytanie 24
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru rozwiązań dopuszczalnych:
różniący się jedną zmienną bazową i poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
óżniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
zachowujący jedną zmienną bazową i poprawiający wartość funkcji kosztu