WSKiZ Teoretyczne Podstawy Informatyki #2

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . data. . . . . . . . . . . .

1. Dany jest n elementowy zbiór ocechowanych odważników. Czy uda się je rozmieścić na tarkach wagi szalkowej, tak aby ta znalazła się w stanie równowagi? Problem ten jest :

a) decyzyjny trudny

b) optymalizacyjny łatwy

c) decyzyjny łatwy

2. Problem wyboru „najlepszego” podzbioru zbioru n elementowego ma złożoność:

a) (n-1)!

b) 2ⁿ

c) n²/2 - n/2

3. Problem sprawdzania czy dana liczba naturalna jest liczba parzystą jest problemem:

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

4. Problem sortowania ma złożoność:

a) 2ⁿ

b) n!

c) n²/2 - n/2

5. Dana jest całkowita liczba dodatnia. Sprawdzenie czy jest ona liczba pierwszą jest problemem:

a) decyzyjnym trudnym

b) decyzyjnym łatwym

c) optymalizacyjnym trudnym

6. Algorytm dla różnych wartości danej wymaga wykonania n², 2ⁿ, 2n ma złożonośc obliczeniową:

a) wielomianową

b) wykładniczą

c) liniową

7. Problem wyboru najwyższego n osobowej druzyny harcerskiej ma złożoność:

a) (n-1)!

b) 2ⁿ

c) (n-1)

8. Problem wyznaczania NWW(m,n) jest problemem:

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

9. Zgodnie z algorytmem opisanym schematem wydrukowane zostanie:

a) 1 , 2 , 3,…

b) same spacje

c) 1 , 2 , 3 , 4 , 5 ,6

10. Algorytm z zadania #9 jest:

a) poprawny

b) niepoprawny

c) skonczony

T

T

i = n

n! =π

n=6; i=1

i=i+1

Print i

---