Pytania i odpowiedzi
AiSDE Egzamin
Zebrane pytania i odpowiedzi do zestawu. Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 4649 razy
Pytanie 61
Operacja konstruowania stogu zawierającego n elementów ma złożoność
n
Pytanie 62
Najmniejszą złożoność w sensie liczby zmian elementów ma algorytm sortowania:
przez wstawianie
Pytanie 63
Dane sa 4 krawędzie grafu i ich przepustowości AB=1, BC=2, CD=1, DA=2 oraz 2 zapotrzebowania AC=2, BD=2. Przepływ wielkotowarowy jest:
niezrealizowany bo 6<8
Pytanie 64
W algorytmie optymalizacji gradientowej metodą największego spadku metoda złotego podziału służy do wyznaczania:
wektora przesunięcia
Pytanie 65
Kompresja tekstu abcaca algorytmem Hoffmana zwróci:
010110110
Pytanie 66
Wyznaczanie zbioru najkrótszych rozłącznych ścieżek wymaga iteracyjnego wyznaczenia przeplotu:
najkrótszego. algorytmem poprawiania etykiet
Pytanie 67
Aby zadany przepływ d towarów o wspólnym ujściu sprowadzić do przepływu jednotowarowego konieczne jest dodanie:
1 wierzchołka i d krawędzi
Pytanie 68
W algorytmie Karmarkara dla zadania programowania liniowego Ax=b wektor przesunięcia z ...:
ADy=0
Pytanie 69
Scalanie ciągów o długościach n (b.duże) i m algorytmem wstawiania, w stosunku do algorytmu sekwencyjnego jest lepsze:
n / log n razy
Pytanie 70
Jeżeli wielkość rekordu to 1kB, wielkość rekordu indeksu 10B, wielkość sektora 10KB?, to wyszukanie jednego spośród 100,000 rekordów przy zastosowaniu indeksu rzadkiego w porównaniu z zastosowaniem funkcji haszującej o 10 wartościach jest:
100 razy szybsze
Pytanie 71
W przypadku znajdowania najdroższego rozwiązania metodą podziałów i ograniczeń, wartość funkcji kosztu ogranicza przeglądanie rozwiązań, gdy jest:
ograniczeniem górnym. mniejszym od kosztu najlepszego rozwiązania
Pytanie 72
Maszyna Turinga musi mieć własność stopu dla języków:
rozstrzygalnych
Pytanie 73
W metodzie haszowania zamkniętego funkcja haszująca wyznacza:
indeks w tablicy dla danego klucza