WSKiZ Teoretyczne Podstawy Informatyki Test #2

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Data……………….

1. MT opisana tabelą znajduje się w stanie S₀. Jej głowica czyta

najbardziej znaczącą cyfrę liczby 1011. 0 1 b

S₀ 0,S₀,+1 1,S₀,+1 b,S₁,-1

Maszyna ta: S₁ b,S₁,-1 b,S₁,-1 b,S₀,+1

a) zatrzyma się na znaku „0”

b) zatrzyma się na najmniej znaczącej cyfrze liczby 1011 c) nigdy nie zatrzyma się

2. 
   Liczba 1011 z poprzedniego zadania jest :

1. daną wejściową

2. daną wyjściową

3. programem maszyny Turinga

3. Dany jest n elementowy zbiór nie 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

4 Problem ustawienia n osobowej drużyny harcerzy ma złożoność:

a) (n-1)!

b) 2ⁿ

c) n²/2 - n/2

5. Wartością termu MOD(MOD(11,13), MOD(11,13)) jest:

a) 1 b) 0 c) 11

6. Maszyna Turinga jest:

a) termem

b) algorytmem

c) komputerem

7. Problem wyznaczania NWD(m,n) jest problemem:

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

8.
. Algorytm opisany schematem blokowym jest:

a) poprawny

b) niepoprawny

c) skończony

9. Wydrukowane zostanie:

a) 1 , 2 , 3, 1 , 2, …

b) same spacje

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

10. Program rozwiązuje problem:

a) łatwy

b) taki sobie

c) trudny

T

T

i = n

n! =π

n=6; i=1

i=i+1

Print i

---