* Tytuł pytania 1. Zaznacz wszystkie poprawne odpowiedzi.
"Dana jest kwota K zł oraz zbiór nominałów. Każdego nominału mamy
nieskończenie wiele monet. Ile minimalnie monet potrzeba do wydania
kwoty K? Przykładowo kwotę 17zł, mając nominały 20zł, 10zł, 5zł i 1zł,
możemy wydać czterema monetami, gdyż 17=10+5+1+1."
Powyższy problem można rozwiązać korzystając z:
a )przeszukiwania z nawrotami (backtracking)
b )programowania dynamicznego
c )algorytmu zachłannego
* Tytuł pytania 2. Zaznacz wszystkie poprawne odpowiedzi.
Uruchomiliśmy algorytm Bellmana-Forda dla grafu skierowanego o 10 wierzchołkach, aby wyznaczyć najkrótsze ścieżki z wierzchołka nr 1. Dziesiąta iteracja w algorytmie spowodowała udaną relaksację. Oznacza to, że:
a )w grafie istnieje cykl o ujemnej wadze przechodzący przez wierzchołek nr 1
b ) popełniliśmy błąd przy implementacji algorytmu Bellmana-Forda
c )w grafie istnieje krawędź o ujemnej wadze
d )w grafie istnieje cykl o ujemnej wadze
* Tytuł pytania 3. Zaznacz poprawną odpowiedź.
Które z podanych słów jest najdłuższym prefikso-sufiksem słowa abaababaabaab ?
a )ab
b )abaabab
c )abaabaab
d )abaab
* Tytuł pytania 4. Zaznacz poprawną odpowiedź.
Chcesz posortować tablicę miliona liczb naturalnych z przedziału [1, 1000]. Która metoda jest najlepsza do tego celu?
a )sortowanie przez scalanie
b )sortowanie przez wybór
c )sortowanie przez zliczanie
d )sortowanie leksykograficzne
* Tytuł pytania 5. Zaznacz poprawną odpowiedź.
Chcemy jednokrotnie sprawdzić, czy w tablicy t jest pewien element x. Które rozwiązanie uważasz za najlepsze?
a )liniowo przejrzeć wszystkie elementy w t, sprawdzając czy są równe x
b )podzielić tablicę na dwie mniejsze, w każdej z nich rekurencyjnie sprawdzić obecność x
c )posortować t przez scalanie, następnie wyszukiwać binarnie x
d )posortować t przez wybór, następnie wyszukiwać binarnie x
* Tytuł pytania 6. Zaznacz wszystkie poprawne odpowiedzi.
Czego należy użyć przy szukaniu najdłuższego wspólnego podciągu dwóch ciągów?
a )metody zachłannej
b )tablicy
c )rekurencji
d )programowania dynamicznego
e )sortowania
* Tytuł pytania 7. Zaznacz poprawną odpowiedź.
Jaka jest ostatnia cyfra NWD(11914, 17710) w zapisie dziesiętnym?
a ) 1
b ) 2
c ) 3
d ) 4
e ) 5
* Tytuł pytania 8. Zaznacz wszystkie poprawne odpowiedzi.
Chcemy wyznaczyć liczbę spójnych składowych w grafie nieskierowanym o
3mln krawędzi i 1mln wierzchołków. W rozsądnym czasie to zadanie
rozwiąże (zakładamy, że nie ma dodatkowego ograniczenia pamięci na
wielkość stosu):
a )algorytm BFS dla grafu w postaci macierzy sąsiedztwa
b )algorytm BFS dla grafu w postaci list sąsiedztwa
c )algorytm DFS dla grafu w postaci list sąsiedztwa
d )algorytm DFS dla grafu w postaci macierzy sąsiedztwa
* Tytuł pytania 9. Zaznacz wszystkie poprawne odpowiedzi.
Sortujemy przez scalanie tablicę złożoną z 16 elementów.
Które z poniższych liczb mogą być długościami scalanych kawałków tablicy?
a )2
b )8
c )12
d )6
* Tytuł pytania 10. Zaznacz wszystkie poprawne odpowiedzi.
Programowanie dynamiczne jest:
a )strategią projektowania algorytmów
b )sposobem pisania kodu programu
c )techniką umożliwiającą rozwiązywanie problemów
d )szukaniem najlepszego wyniku problemów aproksymacyjnych
e )zachłannym sposobem rozwiązywania problemów
* Tytuł pytania 11. Zaznacz wszystkie poprawne odpowiedzi.
W mieście znajduje się skrzyżowania i jednokierunkowe drogi. Każda droga łączy dwa skrzyżowania i znamy czas jej przejazdu. Chcemy wyznaczyć minimalny czas przejazdu pomiędzy dwoma zadanymi skrzyżowaniami. Do rozwiązania tego problemu możemy użyć algorytmu:
a )Fleury'ego
B) Dijkstry
c )Bellmana-Forda
d )Euklidesa
* Tytuł pytania 12. Zaznacz poprawną odpowiedź.
Co pomaga w obliczaniu pól wielokątów na płaszczyźnie?
a ) algorytm Grahama
b ) iloczyn wektorowy
c ) iloczyn skalarny
d ) twierdzenie Pitagorasa
* Tytuł pytania 13. Zaznacz wszystkie poprawne odpowiedzi.
Aby w grafie nieskierowanym istniał cykl Eulera konieczne są poniższe warunki:
a ) graf ma parzyście wiele krawędzi
b ) graf jest spójny
c ) każdy wierzchołek ma parzysty stopień
d ) graf ma parzyście wiele wierzchołków
* Tytuł pytania 14. Zaznacz poprawną odpowiedź.
Który element tablicy [7, 1, 4, 5, 2, 8, 11] zostanie wybrany w trzecim kroku sortownia przez wybór?
a ) 5
b ) 4
c ) 7
d ) 2
* Tytuł pytania 15. Zaznacz poprawną odpowiedź.
Złożoność optymalnego algorytmu szukania wypukłej otoczki zbioru punktów na płaszczyźnie jest:
a ) liniowo-logarytmiczna
b ) liniowa kwadratowa
c ) logarytmiczna sześcienna
* Tytuł pytania 16. Zaznacz wszystkie poprawne odpowiedzi.
Które z poniższych są poprawnymi słowami (w sensie informatycznym)?
a ) słoń
b )abba
c )kursalgorytmiki
d )gytulmnoprt
* Tytuł pytania 17. Zaznacz poprawną odpowiedź.
Ile mniej więcej wykonamy kroków wyszukując binarnie elementu w tablicy o 1000000 elementów?
a )1000000
b )10
c ) 1000
d ) 20
* Tytuł pytania 18. Zaznacz wszystkie poprawne odpowiedzi.
Chcemy wydać jakąś kwotę za pomocą minimalnej liczby monet z pewnego zestawu. Stosujemy algorytm zachłanny: wybieramy zawsze najpierw największą monetę. Które z poniższych zdań są prawdziwe?
a )Czasami wydamy kwotę minimalną liczbą monet.
b )Jeżeli tę kwotę da się wydać, to nam się to uda to zrobić (być może nie w najmniejszej liczbie monet).
c )Czasami nie uda nam się wydać tej kwoty, choć jest to możliwe.
d )Zawsze wydamy kwotę minimalną liczbą monet.
* Tytuł pytania 19. Zaznacz poprawną odpowiedź.
Ile wystąpień słowa abba znajdzie w tekście abbbaabababbbabbabbabbababba algorytm Knutha-Morrisa-Pratta?
a ) 2
b ) 3
c) 4
d ) 5
e ) 6
* Tytuł pytania 20. Zaznacz wszystkie poprawne odpowiedzi.
Aby znaleźć wypukłą otoczkę, trzeba umieć:
a ) sortować punkty po odległości od początku układu współrzędnych
b )obliczać odległości pomiędzy punktami
c )obliczać pola trójkątów
d )używać iloczynu skalarnego
e )używać iloczynu wektorowego lub w inny sposób obliczać, jaki skręt tworzą trzy punkty
"Dana jest kwota K zł oraz zbiór nominałów. Każdego nominału mamy
nieskończenie wiele monet. Ile minimalnie monet potrzeba do wydania
kwoty K? Przykładowo kwotę 17zł, mając nominały 20zł, 10zł, 5zł i 1zł,
możemy wydać czterema monetami, gdyż 17=10+5+1+1."
Powyższy problem można rozwiązać korzystając z:
a )przeszukiwania z nawrotami (backtracking)
b )programowania dynamicznego
c )algorytmu zachłannego
* Tytuł pytania 2. Zaznacz wszystkie poprawne odpowiedzi.
Uruchomiliśmy algorytm Bellmana-Forda dla grafu skierowanego o 10 wierzchołkach, aby wyznaczyć najkrótsze ścieżki z wierzchołka nr 1. Dziesiąta iteracja w algorytmie spowodowała udaną relaksację. Oznacza to, że:
a )w grafie istnieje cykl o ujemnej wadze przechodzący przez wierzchołek nr 1
b ) popełniliśmy błąd przy implementacji algorytmu Bellmana-Forda
c )w grafie istnieje krawędź o ujemnej wadze
d )w grafie istnieje cykl o ujemnej wadze
* Tytuł pytania 3. Zaznacz poprawną odpowiedź.
Które z podanych słów jest najdłuższym prefikso-sufiksem słowa abaababaabaab ?
a )ab
b )abaabab
c )abaabaab
d )abaab
* Tytuł pytania 4. Zaznacz poprawną odpowiedź.
Chcesz posortować tablicę miliona liczb naturalnych z przedziału [1, 1000]. Która metoda jest najlepsza do tego celu?
a )sortowanie przez scalanie
b )sortowanie przez wybór
c )sortowanie przez zliczanie
d )sortowanie leksykograficzne
* Tytuł pytania 5. Zaznacz poprawną odpowiedź.
Chcemy jednokrotnie sprawdzić, czy w tablicy t jest pewien element x. Które rozwiązanie uważasz za najlepsze?
a )liniowo przejrzeć wszystkie elementy w t, sprawdzając czy są równe x
b )podzielić tablicę na dwie mniejsze, w każdej z nich rekurencyjnie sprawdzić obecność x
c )posortować t przez scalanie, następnie wyszukiwać binarnie x
d )posortować t przez wybór, następnie wyszukiwać binarnie x
* Tytuł pytania 6. Zaznacz wszystkie poprawne odpowiedzi.
Czego należy użyć przy szukaniu najdłuższego wspólnego podciągu dwóch ciągów?
a )metody zachłannej
b )tablicy
c )rekurencji
d )programowania dynamicznego
e )sortowania
* Tytuł pytania 7. Zaznacz poprawną odpowiedź.
Jaka jest ostatnia cyfra NWD(11914, 17710) w zapisie dziesiętnym?
a ) 1
b ) 2
c ) 3
d ) 4
e ) 5
* Tytuł pytania 8. Zaznacz wszystkie poprawne odpowiedzi.
Chcemy wyznaczyć liczbę spójnych składowych w grafie nieskierowanym o
3mln krawędzi i 1mln wierzchołków. W rozsądnym czasie to zadanie
rozwiąże (zakładamy, że nie ma dodatkowego ograniczenia pamięci na
wielkość stosu):
a )algorytm BFS dla grafu w postaci macierzy sąsiedztwa
b )algorytm BFS dla grafu w postaci list sąsiedztwa
c )algorytm DFS dla grafu w postaci list sąsiedztwa
d )algorytm DFS dla grafu w postaci macierzy sąsiedztwa
* Tytuł pytania 9. Zaznacz wszystkie poprawne odpowiedzi.
Sortujemy przez scalanie tablicę złożoną z 16 elementów.
Które z poniższych liczb mogą być długościami scalanych kawałków tablicy?
a )2
b )8
c )12
d )6
* Tytuł pytania 10. Zaznacz wszystkie poprawne odpowiedzi.
Programowanie dynamiczne jest:
a )strategią projektowania algorytmów
b )sposobem pisania kodu programu
c )techniką umożliwiającą rozwiązywanie problemów
d )szukaniem najlepszego wyniku problemów aproksymacyjnych
e )zachłannym sposobem rozwiązywania problemów
* Tytuł pytania 11. Zaznacz wszystkie poprawne odpowiedzi.
W mieście znajduje się skrzyżowania i jednokierunkowe drogi. Każda droga łączy dwa skrzyżowania i znamy czas jej przejazdu. Chcemy wyznaczyć minimalny czas przejazdu pomiędzy dwoma zadanymi skrzyżowaniami. Do rozwiązania tego problemu możemy użyć algorytmu:
a )Fleury'ego
B) Dijkstry
c )Bellmana-Forda
d )Euklidesa
* Tytuł pytania 12. Zaznacz poprawną odpowiedź.
Co pomaga w obliczaniu pól wielokątów na płaszczyźnie?
a ) algorytm Grahama
b ) iloczyn wektorowy
c ) iloczyn skalarny
d ) twierdzenie Pitagorasa
* Tytuł pytania 13. Zaznacz wszystkie poprawne odpowiedzi.
Aby w grafie nieskierowanym istniał cykl Eulera konieczne są poniższe warunki:
a ) graf ma parzyście wiele krawędzi
b ) graf jest spójny
c ) każdy wierzchołek ma parzysty stopień
d ) graf ma parzyście wiele wierzchołków
* Tytuł pytania 14. Zaznacz poprawną odpowiedź.
Który element tablicy [7, 1, 4, 5, 2, 8, 11] zostanie wybrany w trzecim kroku sortownia przez wybór?
a ) 5
b ) 4
c ) 7
d ) 2
* Tytuł pytania 15. Zaznacz poprawną odpowiedź.
Złożoność optymalnego algorytmu szukania wypukłej otoczki zbioru punktów na płaszczyźnie jest:
a ) liniowo-logarytmiczna
b ) liniowa kwadratowa
c ) logarytmiczna sześcienna
* Tytuł pytania 16. Zaznacz wszystkie poprawne odpowiedzi.
Które z poniższych są poprawnymi słowami (w sensie informatycznym)?
a ) słoń
b )abba
c )kursalgorytmiki
d )gytulmnoprt
* Tytuł pytania 17. Zaznacz poprawną odpowiedź.
Ile mniej więcej wykonamy kroków wyszukując binarnie elementu w tablicy o 1000000 elementów?
a )1000000
b )10
c ) 1000
d ) 20
* Tytuł pytania 18. Zaznacz wszystkie poprawne odpowiedzi.
Chcemy wydać jakąś kwotę za pomocą minimalnej liczby monet z pewnego zestawu. Stosujemy algorytm zachłanny: wybieramy zawsze najpierw największą monetę. Które z poniższych zdań są prawdziwe?
a )Czasami wydamy kwotę minimalną liczbą monet.
b )Jeżeli tę kwotę da się wydać, to nam się to uda to zrobić (być może nie w najmniejszej liczbie monet).
c )Czasami nie uda nam się wydać tej kwoty, choć jest to możliwe.
d )Zawsze wydamy kwotę minimalną liczbą monet.
* Tytuł pytania 19. Zaznacz poprawną odpowiedź.
Ile wystąpień słowa abba znajdzie w tekście abbbaabababbbabbabbabbababba algorytm Knutha-Morrisa-Pratta?
a ) 2
b ) 3
c) 4
d ) 5
e ) 6
* Tytuł pytania 20. Zaznacz wszystkie poprawne odpowiedzi.
Aby znaleźć wypukłą otoczkę, trzeba umieć:
a ) sortować punkty po odległości od początku układu współrzędnych
b )obliczać odległości pomiędzy punktami
c )obliczać pola trójkątów
d )używać iloczynu skalarnego
e )używać iloczynu wektorowego lub w inny sposób obliczać, jaki skręt tworzą trzy punkty