6. Złożoność średnia mierzona liczbą zamian przy sortowaniu prawie posortowanego ciągu n-elementowego algorytmami przez wstawianie i przez wybieranie pozostaje w stosunku:

7. Poszukując wśród n elementów k najmniejszych należy wstawić do stogu dokładnie:

8. Złożoności średnie znalezienia wśród n elementów k najmniejszych przy użyciu stogu i k-tego najmniejszego przy użyciu algorytmu Hoare'a są w stosunku:

9. Poszukując najlżejszego drzewa rozpinającego, konstruowanie drzewa:

10. Przy poszukiwaniu najlżejszego drzewa rozpinającego w grafie z n wierzchołkami, po k iteracjach stosunek liczby rozważanych drzew w algorytmie Kruskala i Prima wynosi:

11. W algorytmie znajdowania najgrubszej ścieżki od źródła, węzeł t krawędzi e=(o,t) jest cechowany z o, jeżeli (w - waga, l - etykieta):

12. Stosunek złożoności wyszukania w grafie o n wierzchołkach i m krawędziach najkrótszych ścieżek między wszystkimi parami wierzchołków przy użyciu algorytmu Floyda w stosunku do algorytmu Dijkstry wynosi: (Komandos zdaje się nie dostrzegać lepszych implementacji Dijkstry)

13. Przy wyszukiwaniu metodą interpolacyjną jednego spośród miliona elementów trzeba wykonać kroków około:

14. Stosunek pesymistycznej liczby kroków wymaganych do wyszukania elementu w słowniku 1000 elementów metodami przeszukiwania binarnego i drzewa AVL to:

15. Złożoności pesymistyczne wyszukania elementu w słowniku opartym na drzewie BST i drzewie AVL pozostają w stosunku:

16. W haszowaniu otwartym, przy n elementach i m możliwych wartościach kluczy wartości funkcji haszującej powinno być rzędu:

17. W haszowaniu zamkniętym, gdy stosujemy rehasz przy szukaniu elementu, którego nie ma w słowniku, kończymy, gdy:

18. Liczba wierzchołków drzewa pozycyjnego struktury słownika (nie licząc korzenia) jest równa:

19. W algorytmach znajdowania rozłącznych ścieżek przeplot to:

20. Przy znajdowaniu maksymalnego przepływu, krawędzi nieskierowanej o przepustowości 1 i przepływie 1/2 w grafie resztkowym odpowiada:

21. Wyznaczanie maksymalnego przepływu wymaga iteracyjnego znajdowania ścieżki wzbogacającej:

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:

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:

24. W algorytmie minimalizacji metodą sympleksu zawsze generowany jest kolejny wierzchołek zbioru rozwiązań dopuszczalnych:

25. W algorytmie minimalizacji metodą sympleksu faza analizy kolumny tablicy sympleksowej może prowadzić do stwierdzenia:

26. Jeżeli jeden sektor mieści k rekordów danych albo k' rekordów indeksu, to przy n rekordach danych

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:

28. W rekurencyjnym algorytmie sortowania pozycyjnego k ciągów binarnych o długości m znaków grupy bitów są sortowane:

29. W trakcie wyszukiwania wzorca w tekście gdy stwierdzamy niezgodność znaków wzorca i tekstu:

30. Kompresja tekstu xyuzyzy z użyciem algorytmu Huffmana zwróci:

31. W modelu klucza publicznego strona B udowadnia niezaprzeczalność wiadomości otrzymanej od strony A korzystając z klucza:

32. W modelu klucza publicznego treść wiadomości wysyłanej przez stronę A jest szyfrowana przy użyciu klucza:

33. Przy minimalizacji funkcji metodą największego spadku wykonujemy złoty podział aby:

34. Przy maksymalizacji metodą podziałów i ograniczeń podzbioru rozwiązań można nie przeglądać jeśli:

35. W metodzie programowania liniowego całkowitoliczbowego dzielimy problem zrelaksowany dodając dodatkowe ograniczenia jeśli:

36. Niedeterministyczna maszyna Turinga:

37. Prawdopodobnie obowiązują następujące relacje między klasami problemów:

38. Technika dowodzenia NP. – trudności polega na tym, by:

39. W przypadku kompresji tekstu metoda kodowania powtórzeń kodowanie licznika powtórzeń zależy od:

40. Algorytm sortowania przez zliczanie ma złożoność:

AiSDE Egzamin, test z informatyki

Odpowiedzi na podstawie "biblii algorytmów" z informatyki.

Informatyka. Test składa się z 73 pytań.

Pytania zawarte w teście

Materiały powiązane z testem: AiSDE Egzamin

Test: AISDE Egzamin Komandosa

Test: aisde lab 5

Test: AISDE lab3

Test: AISDE LAB5

Test: AISDE - bank pytań od Komandosa