Pytania i odpowiedzi
AiSDE Egzamin
Zebrane pytania i odpowiedzi do zestawu. Odpowiedzi na podstawie "biblii algorytmów"
Ilość pytań: 73
Rozwiązywany: 3908 razy
Pytanie 21
Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:
dowolnej, 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:
1
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
Pytanie 24
W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru rozwiązań dopuszczalnych:
óżniący się jedną zmienną bazową i najbardziej poprawiający wartość funkcji kosztu
Pytanie 25
W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może prowadzić do stwierdzenia:
że problem jest nieograniczony
Pytanie 26
Jeżeli jeden sektor mieści k rekordów danych albo k' rekordów indeksu, to przy n rekordach danych
indeks gęsty jest k razy większy niż indeks rzadki
Pytanie 27
Jeżeli wielkość rekordu danych to 100B wielkość rekordu indeksu 10B, wielkość sektora 1kB. to wyszukanie jednego spośród 100 000 rekordów przy zastosowaniu indeksu gęstego w porównaniu z zastosowaniem funkcji haszującej o 100 wartościach jest:
10 razy wolniejsze
Pytanie 28
W rekurencyjnym algorytmie sortowania pozycyjnego k ciągów binarnych o długości m znaków grupy bitów są sortowane:
od lewej strony ze złożonością k
Pytanie 29
W trakcie wyszukiwania wzorca w tekście gdy stwierdzamy niezgodność znaków wzorca i tekstu:
przesuwamy wzorzec o i znaków i zaczynamy porównywanie od bieżącego znaku tekstu
Pytanie 30
Kompresja tekstu xyuzyzy z użyciem algorytmu Huffmana zwróci:
0111000101001
Pytanie 31
W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:
publicznego A
Pytanie 32
W modelu klucza publicznego treść wiadomości wysyłanej przez stronę A jest szyfrowana przy użyciu klucza:
tajnego wygenerowanego przez A
Pytanie 33
Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:
ograniczyć przedział poszukiwań minimum funkcji w kierunku
Pytanie 34
Przy maksymalizacji metodą podziałów i ograniczeń podzbioru rozwiązań można nie przeglądać jeśli:
oszacowanie górne funkcji kosztu jest nie wyższe od najlepszego znanego rozwiązania
Pytanie 35
W metodzie programowania liniowego całkowitoliczbowego dzielimy problem zrelaksowany dodając dodatkowe ograniczenia jeśli:
żadne z powyższych
Pytanie 36
Niedeterministyczna maszyna Turinga:
w sposób losowy wybiera przejście
Pytanie 37
Prawdopodobnie obowiązują następujące relacje między klasami problemów:
P <>NP. i PSPACE = NPSPCAE
Pytanie 38
Technika dowodzenia NP. – trudności polega na tym, by:
sprowadzic do niego znany problem NP.- zupełny w czasie wielomianowym
Pytanie 39
W przypadku kompresji tekstu metoda kodowania powtórzeń kodowanie licznika powtórzeń zależy od:
średniej długości ciągu jednakowych znaków
Pytanie 40
Algorytm sortowania przez zliczanie ma złożoność:
mniejszą niż quicksort