Test w formie fiszek Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 4658 razy
Operacja konstruowania stogu zawierającego n elementów ma złożoność
log n
n
1
n log n
n
Najmniejszą złożoność w sensie liczby zmian elementów ma algorytm sortowania:
przez wstawianie
quicksort
bąbelkowy
przez wybieranie
przez wstawianie
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 4<=4
realizowany bo 6<=8
realizowany bo 6>10
niezrealizowany bo 6<8
niezrealizowany bo 6<8
W algorytmie optymalizacji gradientowej metodą największego spadku metoda złotego podziału służy do wyznaczania:
wektora przesunięcia
rzutu kierunku największego spadku na przestrzeń rozwiązań
kierunku przesunięcia
gradientu funkcji kosztu
wektora przesunięcia
Kompresja tekstu abcaca algorytmem Hoffmana zwróci:
010110110
1001110110
1110010110
0111001011
010110110
Wyznaczanie zbioru najkrótszych rozłącznych ścieżek wymaga iteracyjnego wyznaczenia przeplotu:
najkrótszego. algorytmem poprawiania etykiet
o ujemnej długości. algorytmem poprawiania etykiet
o ujemnej długości. algorytmem Dijkstry
najkrótszego. algorytmem Diikstry
najkrótszego. algorytmem poprawiania etykiet
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
1 wierzchołka i 1 krawędzi
d wierzchołków i d krawędzi
d wierzchołków i jednej krawędzi
1 wierzchołka i d krawędzi
W algorytmie Karmarkara dla zadania programowania liniowego Ax=b wektor przesunięcia z ...:
ADy=b
Ay=b
Ay=0
ADy=0
ADy=0
Scalanie ciągów o długościach n (b.duże) i m algorytmem wstawiania, w stosunku do algorytmu sekwencyjnego jest lepsze:
m razy
n / log n razy
n razy
log n razy
n / log n razy
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:
10 razy szybsze
100 razy szybsze
tak samo szybkie
1 razy szybsze
100 razy szybsze
W przypadku znajdowania najdroższego rozwiązania metodą podziałów i ograniczeń, wartość funkcji kosztu ogranicza przeglądanie rozwiązań, gdy jest:
ograniczeniem dolnym. większym od kosztu najlepszego rozwiązania
ograniczeniem dolnym. większym od kosztu najlepszego rozwiązania
ograniczeniem górnym. mniejszym od kosztu najlepszego rozwiązania
ograniczeniem dolnym. mniejszym od kosztu najlepszego rozwiązania
ograniczeniem górnym. mniejszym od kosztu najlepszego rozwiązania
Maszyna Turinga musi mieć własność stopu dla języków:
rozstrzygalnych
akceptowalnych
nieakceptowalnych
nierozstrzygalnych
rozstrzygalnych
W metodzie haszowania zamkniętego funkcja haszująca wyznacza:
