Czy problem gniazdowy to inaczej: a



Yüklə 83,07 Kb.
tarix27.10.2017
ölçüsü83,07 Kb.
#16749

  1. Czy problem gniazdowy to inaczej:
    a) job shop
    b) flow shop
    c) flow job
    d) żadna z powyższych


    2. Przez ile wierzchołków musi przechodzić ścieżka, żeby tworzyć cykl hamiltona?
    a) n/2
    b) wszystkie n
    c) n-1
    d) żadna z powyższych


    3. Ile cykli hamiltona może wystąpić w grafie o n wierzchołkach?
    a) zawsze tylko 1
    b) dokładnie log n
    c) zawsze n
    d) żadna z powyższych


    4. Co jest zmienną decyzyjną w problemie rpq?
    a) kolejność maszyn
    b) całkowity koszt
    c) kolejność zadań
    d) żadna z powyższych


    5. Co jest zmienną decyzyjną w problemie liniowego jednorzędowego rozmieszczenia maszyn?
    a) kolejność maszyn
    b) całkowity koszt
    c) kolejność zadań
    d) żadna z powyższych


    6. Który z algorytmów ma najmniejszą złożoność obliczeniową?
    a) NEH z akceleracją
    b) NEH IRRk
    c) a i b mają taką samą złożoność
    d) żadna z powyższych

    7. Ile krawędzi wychodzi z pojedynczego węzła w grafie reprezentującym problem gniazdowy?



a) od 0 do 2

b) dokładnie 1

c) dokładnie 2

d) dokładnie 59


8. Jaką złożoność obliczeniową ma algorytm Bellmana-Forda dla grafu pełnego?
a) O(n log n)
b) O(n^3)
c) O(n^2 log n)
d) żadna z powyższych


9. Dla którego z zadań nie jest znany algorytm dający optymalne rozwiązanie w czasie wielomianowym (zakładając P != NP)
a) problem rpq z możliwością podziału zadań
b) problem komiwojażera
c) problem rozmieszczenia zadań na dwóch maszynach
d) żadna z powyższych


10. Czy dla ogólnego problemu komiwojażera algorytm epsilon-aproksymacyjny


a) zawsze istnieje

b) nie może istnieć

c) nie jest znany ale wiadomo, że istnieje

d)istnieje tylko dla problemów o liczbie węzłów mniejszej od 5


11. Który z wymienionych algorytmów rozwiązujących problem RPQ uzyskuje zawsze optymalną wartość funkcji celu?
a) Carlier
b) Pottsa
c) Schrage
d) żadna z powyższych


12. Który z algorytmów sortowania, poprawnie zaprogramowany, zapewnia złożoność O(n log n) w każdej sytuacji?
a) QuickSORT
b) sortowanie przez kopcowanie
c) Sortowanie bąbelkowe
d) żadna z powyższych


13. Czy problem przepływowy to inaczej:
a) job shop
b) flow shop
c) flow job
d) żadna z powyższych


14. Jaką złożoność obliczeniową ma algorytm Schrage:
a) O(n)
b) O(n log n)
c) O(log n)
d) żadna z powyższych


15. Jaką złożoność obliczeniową ma algorytm Carliera?
a) wielomianową
b) pseudowielomianową
c) wykładniczą
d) żadna z powyższych


16. Który z wymienionych algorytmów, zawsze wygeneruje rozwiązanie optymalne dla ogólnego problemu RPQ:
a) Schrage
b) NEH
c) Tabu Search
d) żadna z powyższych


18. Jakiej metody używa algorytm Carliera do generowania rozwiązania:
a) przeglądu zupełnego
b) podziału i ograniczeń
c) płaszczyzn odcinających
d) żadna z powyższych


19. Kryterium jakości Csum oznacza
a) sumę czasów wykonywania zadań
b) sumę czasów rozpoczęcia zadań
c) moment zakończenia ostatniego z zadań
d) żadna z powyższych


20. System planistyczno-sterujący charakteryzuje się


a) występowaniem jednego centralnego planisty

b) każda z maszyn przesyła komunikaty do pozostałych

c) małą odpornością na zakłócenia

d)brakiem potrzeby magazynowania

21. Dla drzewa binarnego:


a) liście są wyżej niż korzeń – drzewo rośnie „do góry”
b) liście są niżej niż korzeń – drzewo rośnie „w dół”
c) żadna z powyższych
d) każdy z wierzchołków ma trzech potomków
22. Graf jest
a) zbiorem krawędzi i wierzchołków
b) funkcją
c) graficzną reprezentacją problemu
d) parą zbiorów
23. Każdy nieskierowany graf acykliczny:
a) jest Drzewem
b) jest Lasem – bo nie koniecznie spójny
c) jest skierowany
d) posiada co najmniej 3 cykle Hamiltona.
24. Graf rzadki najlepiej zaimplementować jako
a) macierz incydencji
b) listę sąsiadów
c) żadna z powyższych
d) a) i b) są równoważne w sensie złożoności obliczeniowej, wymogów pamięciowych.
25. Minimalnokosztowe drzewo rozpinające grafu o n wierzchołkach
a) zawiera 2n-1 krawędzi
b) zawiera n wierzchołków
c) zawiera najmniej wierzchołków ze wszystkich drzew rozpinających
d) zawiera najmniej krawędzie ze wszystkich drzew rozpinających
26. Co najmniej ile cyklów Hamiltona posiada dowolny graf pełny

a) 1
b) 2
c) może się zdarzyć, że 0
d) żadna z powyższych
27. Czy drzewo o n wierzchołkach to graf spójny o liczbie krawędzi
a) n-1
b) n-2
c) drzewo nie jest grafem spójnym
d) żadna z powyższych
28. Jaką zmienną minimalizujemy w problemie rpq? – niejednoznaczne: jeśli chodzi o 1|rpq|Cmax.
a) koszt – (jeśli koszt jest zależny od czasu to jest też)
b) czas wykonania zadań – Cmax – jeśli X|rpq|Cmax
c) liczbę maszyn
d) żadna z powyższych


29. Ile maszyn występuje problemie rpq? – niejednoznaczne: jeśli chodzi o 1|rpq|Cmax.
a) dowolna liczba
b) 1 – jeśli 1|rpq|X
c) problem rpq nie dotyczy maszyn
d) żadna z powyższych
30. Jaka wartość Cmax w problemie rpq świadczy o źle napisanym programie liczącym funkcje
celu?
a) mniejsza od sumy wszystkich p oraz największego r i q
b) mniejsza od: sumy wszystkich p + najmniejsze r + najmniejsze q
c) różna od sumy wszystkich p
d) żadna z powyższych
31. W którym problemie każda z maszyn wykonuje zadania w jednakowej kolejności?
a) przepływowym
b) permutacyjnym

c) przepływowym i permutacyjnym
d) żadna z powyższych
32. W problemie gniazdowym (job shop) z każdą operacją związany jest:
a) czas wykonania operacji na maszynie
b) numer maszyny, na której ma się wykonać operacja
c) obie powyższe
d) żadna z powyższych
34. Aby drzewo było kopcem, musi mieć następującą właściwość:
a) potomek musi mieć większą wartośc od rodzica
b) rodzic musi mieć większą wartośc od potomka
c) dowolna stała relacja
d) żadna z powyższych
36. O kopcu zupełnym mówimy gdy:
a) liście drzewa występują na ostatnim i ewentualnie przedostatnim poziomie
b) liście na ostatnim poziomie są spójnie ułożone od strony lewej do prawej
c) muszą zachodzić a) i b)
d) żadna z powyższych
37. Jakie zalety ma algorytm Shrage?
a) daje rozwiązanie optymalne
b) daje stosunkowo dobre wyniki w krótkim czasie
c) obie wyżej wymienione
d) żadna z powyższych
38. Złożoność obliczeniowa sortowania przez kopcowanie jest:
a) większa niż złożoność obliczeniowa quicksort
b) mniejsza niż złożoność obliczeniowa quicksort
c) nie da się porównać



d) żadna z powyższych
39. Złożoność obliczeniowa sortowania przez kopcowanie jest:
a) mniejsza niż dla sortowania bąbelkowego

b) taka sama jak dla sortowania bąbelkowego

c) większa niż dla sortowania bąbelkowego

d) żadna z powyższych
40. Problem „Czy dla grafu G istnieje cykl Eulera”
a) jest równoważny problemowi „czy dla grafu G istnieje cykl Hamiltona”
b) jest NP-zupełny
c) jest NP-trudny
d) nie ma rozwiązania

41. Układajdc zadania na czterech maszynach w systemie przepływowym permutacyjnym F* jako wynik otrzymujemy:

a) Cmax = max{c1, c2, c3, c4} -> min,

b) Csum = c1+c2+c3+c4 -> min,



c) Sekwencję operacji dla kazdej z maszyn

d) żadna z powyższych


42.Uładając zadania na pięciu maszynach w systemie przepływowym F jako wynik otrzymujemy:

a) Cmax = max{c1, c2, c3, c4, c5} -> min,

b) Csum = c1+c2+c3+c4+c5 -> min,

c) Sekwencję operacji dla każdej z maszyn

d) żadna z powyższych


43.Ilość operacji wykonanych przez każdą z maszyn w systemie gniazdowym:

a) zawsze jest taka sama,

b) musi być różna,

c) może być różna

d) żadna z powyższych


44. Jak za pomocą grafu sprawdzić, czy podany pomysł przydziału na maszyny jest realizowalny?

a) zadanie jest realizowalne, jeśeli w grafie jest cykl,



b) zadanie jest realizowalne, jeśli w grafie nie ma cyklu ,

c) w grafie nie może byc więcej cykli, niż jest maszyn.

d) żadna z powyższych
45. Czy problem przepływowy to inaczej:

a) job shop



b) flow shop

c) flow job

d) żadna z powyższych
46. Spónienie zakończenia zadania j to?

a) rónica pomiędzy momentem zakoęczenia zadania j, a żądanym czasem zakończenia zadania j,



b) dodatnia różnica pomiędzy momentem zakończenia zadania j, a żądanym czasem zakończenia zadania j,

c) dodatnia różnica między momentem rozpoczęcia wykonywania zadania j, a mozliwie najwcześnejszym momentem zakończenia zadania j.

d) żadna z powyższych
47. Przyspieszenie rozpoczęcia zadania j to?

a) różnica pomiędzy najwcześniejszym możliwym momentem rozpoczęcia zadania j, a momentem rozpoczęcia wykonywania zadania j,



b) dodatnia różnica pomiędzy najwcześniejszym możliwym momentem rozpoczęcia zadania j, a momentem rozpoczęcia wykonywania zadania j,

c) dodatnia różnica pomiędzy najwcześniejszym możliwym momentem rozpoczęcia zadania j, a czasem zakończenia zadania j

d) żadna z powyższych
48. Jeśeli algorytm może obliczyć maksymalną nieterminowość (Lmax) w systemie, to potrafi także policzyć:

a) Maksymalny moment zakończenia zadania w systemie (Cmax),

b) sumę spóźnień (STi),

c) ilość spóźnionych zadań (SUi).

d) żadna z powyższych


49. Wartość funkcji celu w problemie Flow-shop z kryterium cmax jest

a) równa najkrótszej ścieżce w grafie reprezentującym ten problem



b) równa najdłuższej ścieżce w grafie reprezentującym ten problem

c) nie do policzenia

d) żadna z powyższych
50. Jeżeli V oznacza ilość wierzchołków w dany grafie to:
a) W algorytmie Bellmana-Forda relaksacja wykonywana jest V-1 razy na każdej krawędzi
b) Cykl Hamiltona zawsze istnieje
c) Obie powyższe
d) żadna z powyższych

51. Czy ciąg <23,17,14,6,13,10,1,5,7,12> jest kopcem?


a) nie
b) tak
c) nie, ale będzie po zamianie miejscami 5 z 6
d) żadna z powyższych


52. Czy aby w algorytmie Schrage uzyskać złożoność obliczeniową n^2, tablice względem "q" należy sortować za pomocą:
a) quick sort
b) heap sort
c) dowolna z powyższych
d) żadna z powyższych
53. Jakich narzędzi używamy, jeżeli spotykamy się z deterministycznymi danymi problemu?
a) teorii szeregowania
b) teorii procesów stochastycznych
c) teorii zbiorów rozmytych
d) żadna z powyższych

54. Przyporządkuj problemowi probabilistycznemu odpowiednie narzędzie teoretyczne:


a) teoria szeregowania
b) teoria kolejek i teoria procesów stochastycznych
c) teoria zbiorów rozmytych
d) żadna z powyższych

55. Przyporządkuj problemowi rozmytemu odpowiednie narzędzie teoretyczne:


a) teoria zbiorów rozmytych
b) teoria kolejek i teoria procesów stochastycznych
c) teoria szeregowania
d) żadna z powyższych

56. Co oznacza symbol c w równaniu c=s+p, gdzie s-moment rozpoczecia zadania, p-czas trwania zadania:


a) nieterminowosc
b) spóźnienie zakonczenia zadania
c) moment zakonczenia zadania
d) żadna z powyższych


57. W kopcu o 23 elementach, element tego kopca o indeksie 6 ma potomka o indeksie?
a) 12
b) 13
c) obie powyższe
d) żadna z powyższych

58. W kopcu o 23 elementach, element tego kopca o indeksie 6 ma rodzica o indeksie?


a) 2
b) 3
c) 4
d) żadna z powyższych

59. W kopcu o 23 elementach, element tego kopca o indeksie 12 ma potomka o indeksie?


a) 23
b) 22
c) 24
d) żadna z powyższych

60. Algorytm sort R dla problemu rpq daje rozwiązanie:
a) zawsze najgorsze możliwe
b) może dać rozwiązanie optymalne
c) zawsze lepsze od shrage
d) żadna z powyższych

61. Zastosowanie dodatkowych testów eliminacyjnych w algorytmie Carliera ma na celu:

a) obliczenie lepszego dolnego ograniczenia

b) uzyskanie bardziej optymalnego rozwiązania

c) przyspieszenie obliczeń

d) znalezienie lepszego górnego ograniczenia


62. Czy poszukiwanie cyklu Hamiltona w grafie jest problemem NP-zupełnym:
a) TAK
b) NIE
c) Jeszcze nie udowodniono
d) żadna z powyższych

63. Rolą algorytmu Schrage z podziałami w algorytmie Carliera jest:

a) obliczanie górnego ograniczenia dla generowanych węzłów

b) wyszukiwanie zadania interferencyjnego

c) umożliwienie wykorzystania kopca w algorytmie



d) znajdywanie dolnego ograniczenia dla generowanych węzłów

64. Która z par algorytmów oparta jest na metodzie wstawień?
a) Schrage, Carlier
b) NEH, Carlier
c) INSA, NEH
d) INSA, Schrage
65. W problemie job shop z każdego wierzchołka grafu reprezentującego ten problem może wychodzić:

a) nieskończenie wiele krawędzi



b) jedna krawędź

c) dwie krawędzie

d) problemu job shop nie da się zamodelować z wykorzystaniem grafu


66. Jaka jest najmniejsza złożoność obliczeniowa potrzeba do stworzenia kopca? :
a) O(n)
b) O(nlogn)
c) O(n^2)
d) żadna z powyższych


67. Jezeli w algorytmie forda-bellmana graf zawiera ujemny cykl to rozwiazanie jest..? :
a) niedopuszczalne
b) optymalne
c) dopuszczalne
d) żadna z powyższych


68. W zagadnieniu sterowania procesami produkcyjnymi wyróżnia się następujące strategie wytwarzania:
a) push, pull, press
b) push, press, skip
c) push, pull, squeeze
d) żadna z powyższych


69. Czy w algorytmie NEH rozważamy:
a) różne permutacje maszyn
b) różne permutacje zadań
c) obie powyższe
d) żadna z powyższych


70. Algorytm Carriera modyfikuje :
a) r dla znalezionego zadania lub q danego zadania
b) q dla znalezionego zadania
c) p dla znalezionego zadania lub q danego zadania
d) żadna z powyższych


71. Rozkład topologiczny grafu wykorzystywany jest w algorytmie:
a) Carliera
b) INSA
c) Schrage
d) żadna z powyższych


72. Prawdziwe jest stwierdzenie:
a) oczekiwany czas zakończenia procesu jest równy sumie oczekiwanych czasów zakończenia podprocesów
b) oczekiwany czas zakończenia procesu nie jest równy sumie oczekiwanych czasów zakończenia podprocesów
c) oczekiwany czas zakończenia procesu jest zawsze nieokreślony
d) oczekiwany czas zakończenia procesu jest zawsze równy czasowi zakończenia najdłużeszgo podprocesu


73. Czy kopiec umożliwia bezpośredni dostep do wierzchołka o największej lub najmniejszej wartości danego zbioru zapisanego w kopcu :
a) tak
b) nie
c) tylko największej
d) żadna z powyższych


74. Twierdzenie blokowe:
a) Jest wykorzystane w algorytmie Carliera
b) pozwala stwierdzić, że rozwiaznie problemu RPQ jest optymalne
c) nie dotyczy problemu RPQ
d) żadna z powyższych


75. Najwieksze (z wymienionych) oszacowanie wartości takie, że jest zawsze mniejszej bądz równej wartości funkcji celu rozwiazania optymalnego w problemie RPQ to:
a) suma Pi + najmniejsze R + największe Q
b) suma Pi + największe R + największe Q
c) suma Pi + największe R + najmniesze Q
d) żadna z powyższych


76. Do oszacowania wartości, poniżej której nie może zejść wartość funkcji celu w problemie flow-shop wykorzystuje się:
a) algorytmy o złożoności obliczeniowej większej niż wielomianowa
b) algorytmy do rozwiazywania problemu RPQ
c) popawne są odpowiedzi a i b
d) żadna z powyższych


77. Wartośc funkcji celu w problemie Flow-shop jest :
a) równa najkrótszej scieżce w grafie reprezentującym ten problem
b) równa najdłuższej scieżce w grafie reprezentującym ten problem
c) nie do policzenia
d) żadna z powyższych


78. Algorytm NEH polega na:
a) przeglądzie zupełnym zbioru rozwiązań
b) konstruowanie rozwiazania przez wyrzucenie zadania (bez ktorego wartość funkcji celu bedzie najmniejsze) i wstawienie go w inne miejsce
c) dokładani nowych zadan do aktalego rozwiazanie w optymalne miejsce
d) żadna z powyższych
79. Zasada podziału w algorytmie Carliera mówi, że:

a) rozwiązanie uzyskiwane jest dzięki generowaniu podproblemów poprzez modyfikacje problemu bazowego

b) szukanie dolnego ograniczenia musi być oparte na algorytmie wykorzystującym kopiec

c) problemy można wkładać i zdejmować z maszyny w dowolnej chwili, to znaczy nie trzeba czekać na zakończenie ich wykonywania

d) zadanie interferencyjne znajduje się na ścieżce krytycznej.



80. Do wad strategii push w sterowaniu globalnym należy:

a) duża wrażliwość na opóźnienia przy wykonywaniu poszczególnych etapów zadania

b) duży poziom skomplikowania systemu zarządzania produkcją

c) problemy z magazynowaniem produktów.

d) żadne z powyższych.
81. Co przechowuje rejestr TIME STAMP COUNTER w procesorze?


  1. nazwę kodową procesora

  2. nazwę producenta procesora

  3. licznik taktów zegara procesora

  4. jest to rejestr instrukcji (przechowuje kod aktualnie wykonywanej instrukcji)



82. Zakładając, że procesor posiada rejestry MSR oraz rejestr TSC, w jakich odstępach czasu zwiększana będzie wartość rejestru TSC, przy zegarze 2000MHz?

  1. co 1ns

  2. co 0,01ns

  3. co 10ms

  4. co 0,5ns


83.Kiedy algorytm Carliera kończy swoje działanie?

  1. po n krokach, gdzie n = liczba zadań w problemie jobshop

  2. dopiero po przejrzeniu całego drzewa z rozwiązaniami

c) kiedy w analizowanym węźle UB=LB

d) żadna z powyższyc


84. Na jakiej na jakiej podstawie można stwierdzić ze blok jest ułożony optymalnie (w problemie RPQ)
a) zadania są posortowanie w bloku po R malejaco
b) zadania są posortowanie w bloku po Q roznaco
c) zadania są posortowanie w bloku po R malejaco i po Q roznąco
d) żadna z powyższych

85. W jakim czasie możliwe jest pobranie, bez naprawiania kopca, wartości największej (zakładamy, że wartość ta znajduje się w korzeniu, tzn. kopiec przechowuje wartości posortowane malejąco)?
a) O(n)

b) O(n log n)



c) O(1)

d) O(n^2)


86. Mamy model kolejkowy. Prawdopodobieństwo nadejścia zgłoszenia w zależności od czasu:
a) rośnie wykładniczo
b) rośnie logarytmicznie
c) jest stałe
d) żadna z powyższych

87. Z ilu węzłów składa się pełny (wypełniony na każdym poziomie) kopiec binarny z 3 poziomami?

  1. z 7

  2. z 9

  3. z 27

  4. z 11

88. Problem przepływowy modeluje problem wykonania n zadań na m maszynach. Prawdą jest, że:
a) każde zadanie przepływa przez wszystkie maszyny w tej samej kolejności
b) dla każdego elementu marszruta przepływu nie musi być jednakowa
c) zadania nie muszą przepływać przez maszyny w tej samej kolejności
d) żadna z powyższych

89. Mamy problem przepływowy. Czy kolejność zadań na maszynach może ulec zmianie?
a) tak
b) nie
c) tak, jeżeli dodamy bufory z możliwością magazynowania
d) żadna z powyższych

90. Kopce budowane są na:
a) drzewach binarnych
b) B-drzewach
c) C-krzakach
d) żadna z powyższych
91. Kiedy w grafie zachodzi cykl Hamiltona?
a) wszystkie wierzchołki są dokładnie raz odwiedzane
b) wszystkie wierzchołki są odwiedzane, niekoniecznie raz
c) kiedy odwiedzimy te wierzchołki, które spełniają założenia określone przed rozpoczęciem cyklu
d) żadna z powyższych
92. Jaką złożoność obliczeniową posiada program obliczający Cmax dla problemu gniazdowego?
a) n
b) n^2
c) n^3
d) żadna z powyższych


93. Jaki jest adres ostatniego elementu kopca zupełnego o głębokości 3?
a) 6
b) 7
c) nie wiadomo
d) żadna z powyższych
94. Dany jest zbiór N={1,...,n}. Ile jest wszystich podzbiorów zbioru ?
a) n
b) 2^n
c) n!
d) żadna z powyższych
95. Dany jest graf skierowany z obciążeniami.

Dlugość najdłuższej ściezki wynosi:

a) 0
b) 4
c) 1
d) żadna z powyższych
96. Można powiedzieć, że sortowanie przez kopcowanie...
a) Ma złożoność O(2nlogn).
b) Jest minimalnie szybsze od Qsort.
c) Ma wykładniczy czas wstawiania jak i wyciągania z kopca.
d) żadna z powyższych
97. Ile elementów znajduje sie na ostatnim - najniższym poziomie kopca n-elementowego?
a) od n do 2^n
b) 2^n
c) od 1 do 2^n
d) żadna z powyższych


98. Do czego w oryginalnej postaci służy algorytm Bellmana-Forda?
a) wyznaczenia najkrótszej ścieżki w grafie
b) znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie
c) wyznaczania minimalnego drzewa rozpinającego
d) żadna z powyższych

99. Czy poniższe drzewo jest kopcem?

a) Nie, nie spełnia wymagań.
b) Tak
c) Nie, ale będzie gdy pod rodzica "17" dołożymy potomka o wartości „4”
d) żadna z powyższych
100. Gdy chcemy sortować elementy od najmniejszych za pomocą kopca to:
a) Elementy potomne muszą być mniejsze od rodziców
b) Elementy potomne muszą być większe od rodziców.
c) To nie ma znaczenia w kopcu
d) żadna z powyższych

101. Sortowanie przez kopcowanie ma złożoność pamięciową równą:
a) O(1)
b) O(logn)
c) O(n^2)
d) żadna z powyższych


102. W pierwszym kroku algorytmu Schrage spośród wszystkich zadań wybieramy:
a) zadania o minimalnym R
b) zadania o minimalnym Q
c) zadania o maksymalnym R
d) żadna z powyższych

103. W drugim kroku algorytmu Schrage spośród dostępnych zadań wybieramy:


a) zadania o minimalnym Q
b) zadania o maksymalnym Q
c) zadania o minimalnym R
d) żadna z powyższych

104. Zaletą sortowania przez kopcowanie jest:


a) Pesymistyczna złożoność obliczeniowa na poziomie 0(logn)
b) Pesymistyczna złożoność obliczeniowa lepsza niż w Q-sort
c) Pesymistyczna złożoność obliczeniowa porównywalna z sortowaniem Q-sort
d) żadna z powyższych

105. Złożoność obliczeniowa sortowania przez kopcowanie to:


a) O(log n)
b) O(n log n)
c) O(n)
d) żadna z powyższych
106. W problemie gniazda krytycznego czas poprzedzający wykonanie zadania na elemencie oznaczamy:
a) r
b) p
c) q
d) żadna z powyższych


107. W problemie gniazda krytycznego czas wykonania zadania na elemencie oznaczamy:
a) r
b) p
c) q
d) żadna z powyższych


108. W problemie gniazda krytycznego czas następujący po wykonaniu zadania na elemencie oznaczamy:
a) r
b) p
c) q
d) żadna z powyższych

109. Dodania nowego elementu do n-elementowego kopca rozpoczynamy od:
a) pozycji n+1 wypadającej w najniższy poziomie kopca
b) od szczytu kopca
c) której kolwiek gałęzi, bo przecież to kopiec
d) żadna z powyższych

110. W problemie gniazdowym obliczenie wartości funkcji celu cmax wymaga ułożenia węzłów w grafie:

a) od największego do najmniejszego

b) od najmniejszego do największego

c) w kolejności topologicznej

d) żadna z powyższych
111. Czy po wstawieniu nowego elementu na najniższy poziom kopca sortowanie można uznać za zakończone?
a) Definitywnie, tak.
b) Nie, gdy spełniony jest warunek kopca.
c) Tak, gdy spełniony jest warunek kopca
d) żadna z powyższych


112. Jaki jest czas wstawiania i wyciągania elementu z kopca zupełnego?
a) logarytmiczy
b) wykładniczy
c) zależny od przypadeku, dla pesymistycznego jest wykładniczy
d) żadna z powyższych


113. Czy Qsort jest szybsze od sortowania przez kopcowanie?
a) Nie
b) Tak
c) Na ogół tak.
d) żadna z powyższych
114. Jak nazywa się algorytm służący do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie?
a) Floyda-Warshalla
b) Andyego Warhola
c) Dijkstry
d) żadna z powyższych


115. W jakim algorytmie wykorzystujemy procedurę relaksacyjną?
a) Floyda-Warshalla
b) Bellmana-Forda
c) Taboo Search
d) żadna z powyższych


118. Procedura RELAX jest wywoływna jednokrotnie w algorytmie:
a) Bellmana-Forda
b) Floyda-Warshalla
c) Dijkstry
d) żadna z powyższych



119. Algorytm NEH w problemie przepływowym polega na:
a) wkładamy kolejne zadania (kolumny) w różne miejsca pomiedzy już istniejące i sprawdzamy f. celu się zmniejszyła
b) wyliczamy odległości pomiędzy wszystkimi wierzchołkami w grafie
c) wyliczamy odległości pomiądzy pierwszym a wszyskimi wierzchołkami w grafie
d) żadna z powyższych

120. W algorytmie Carliera zadania kolidującego nie warto wstawiać:

a) przed blok

b) za blok

c) do środka bloku

d) żadna z powyższych
Yüklə 83,07 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin