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:
y = x2 x2 - ax2 + b x2
y = x2 (x2 - a + b)
y = x4 - x2 (a - b)
6. Problem wyboru „najlepszego” podzbioru zbioru n elementowego ma
złożoność:
a) (n-1)!
b) 2n
c) n2/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 S0. Jej głowica czyta najbardziej znaczącą cyfrę liczby 1011. 0 1 b
S0 0,S0,+1 1,S0,+1 b,S1,-1
S1 b,S1,-1 b,S1,-1 b,S0,+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