PK_WE Teoretyczne Podstawy Informatyki Test #1

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.12.2004

1. Termem jest wyrażenie:

a) ∨(DIV(a,b), ∨C)

b) ∧ (MOD(a,b), ∧C)

c) ¬(∨(DIV(a,b), C))

2. begin i:=1; while i≠u do i:=i+1 end przykładowy warunek jest poprawny:

a) „u liczba całkowita” Ÿ

b) „u = i” c) „u>0”

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. Wartością termu NWD(5,17) + MOD(2,2) jest:

a) 11 b) 1 c) 17

5. Który z poniższych algorytmów jest szybszy:

1. 
   y = x^2­ x² - ax² + b x² Ÿ

2. 
   y = x^2­ (x² - a + b)

3. 
   y = x⁴ - x² (a - b)

6. Problem wyboru „najlepszego” podzbioru zbioru n elementowego ma

złożoność:

a) (n-1)!

b) 2ⁿ

c) n²/2 - n/2

7. Algorytm Euklidesa:

a) generuje kolejne liczby pierwsze

b) wyznacza wszystkie liczby pierwsze z danego zbioru

c) generuje wartość największego wspólnego podzielnika

8. 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

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

Maszyna ta:

a) zatrzyma się na znaku „0”

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

9. Algorytm opisany schematem blokowym jest:

a) poprawny

b) niepoprawny

c) skończony

10. Wydrukowane zostanie:

a) -1 , -2 , -3

b) same spacje

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

T

T

i = n

DIV(i,n)=3

n=3; i=1

i=i-1

Print i

---