Czy problem gniazdowy to inaczej: a
Yüklə 83,07 Kb.
|
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,
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,
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
a) job shop b) flow shop c) flow job d) żadna z powyższych
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
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
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
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
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ą
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?
83.Kiedy algorytm Carliera kończy swoje działanie?
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?
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ş:
|