Przegląd podstawowych algorytmów

Przegląd podstawowych algorytmów

Warszawska Wyższa Szxola

1 N FORMATY JC I

Wynik: 100%

składowe kursu:

sortownia

Test

1. Który element tablicy [7, 1. 4, 5, 2, 8, przez wybór?

® 4

O 5 □ 2 □ 7

2.    "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 20zl, 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:

® programowania dynamicznego

□    algorytmu zachłannego przeszukiwania z nawrotami (backtracking)

3.    Aby znaleźć wypukłą otoczkę, trzeba umieć:

□    sortować punkty po odległości od początku układu współrzędnych

□    używać iloczynu skalarnego

□    obliczać odległości pomiędzy punktami

□    obliczać pola trójkątów

v używać iloczynu wektorowego lub w inny sposób obliczać, jaki skręt tworzą trzy punkty

4. Chcemy jednokrotnie sprawdzić, czy w tablicy t jest pewien element x. Które rozwiązanie uważasz za najlepsze?

v| liniowo przejrzeć wszystkie elementy w t, sprawdzając czy są równe x

□    posortować t przez wybór, następnie wyszukiwać binarnie x

□    posortować t przez scalanie, następnie wyszukiwać binarnie x

□    podzielić tablicę na dwie mniejsze, w każdej z nich rekurencyjnie sprawdzić obecność x

5. 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?

v| Czasami wydamy kwotę minimalną liczbą monet.

Jeżeli tę kwotę da się wydać, to nam się to uda to zrobić (być może nie w najmniejszej liczbie ~ monet).

□    Zawsze wydamy kwotę minimalną liczbą monet.

□    Czasami nie uda nam się wydać tej kwoty, choć jest to możliwe.

6. 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?

□ 6

IV] 2

□ 12

□ 8

7.    Co pomaga w obliczaniu pól wielokątów na płaszczyźnie?

□    iloczyn skalarny

□    twierdzenie Pitagorasa v iloczyn wektorowy

□    algorytm Grahama

8.    Czego należy użyć przy szukaniu najdłuższego wspólnego podciągu dwóch ciągów?

C J metody zachłannej

programowania dynamicznego

□    rekurencji

□    sortowania (V) tablicy

9.    Chcesz posortować tablicę miliona liczb naturalnych z przedziału [1, 1000]. Która metoda jest najlepsza do tego celu?

v sortowanie przez zliczanie

□    sortowanie przez scalanie

□    sortowanie leksykograficzne

□    sortowanie przez wybór

10.    Programowanie dynamiczne jest:

L i zachłannym sposobem rozwiązywania problemów v strategią projektowania algorytmów

□    techniką umożliwiającą rozwiązywanie problemów

□    sposobem pisania kodu programu

□    szukaniem najlepszego wyniku problemów aproksymacyjnych

Zakończ test

Uwaga:

1.    Test może być wykonywany wielokrotnie, aż do uzyskania wyniku uprawniającego do wystawienia auto certyfikatu.

2.    Uczestników kursu będący uczniami i nauczycielami szkól ponadgimnazjalnych, którzy chcą aby punkty uzyskane przez nich z tytułu realizacji kursu, zostały zaliczone na konto ich szkoły w rankingu IT Szkota - informujemy, że na konto szkoły są zaliczane punkty uzyskane bezpośrednio po PIERWSZYM wykonaniu testu oraz naciśnięciu przycisku - zakończ test