Teoretyczne Podstawy Informatyki Test #1

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26.11.2006

1. Termin algorytm oznacza:

a) przepis postępowania przy rozwiązywaniu zadania

b) zbiór zasad wykorzystywanych przy rozwiązywaniu zadania Ÿ

c) procedurę opisującą rozwiązanie problemu

2. Dziedzina algorytmiczna to:

a) rodzina zbiorów obiektów, funkcji, relacji

b) rodzina zbiorów funkcji, operatorów i funktorów

c) dziedzina zmiennych decyzyjnych oraz stałych 3.

3. Termem jest wyrażenie:

a) ∧(∨a,(¬b∨c)) Ÿ

b) ∧(∨ (a,(¬b∨c)),d)

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

4. Wartością termu MAX{3,9,0} + MOD(11,13) jest:

a) 11 b) 9 c) 20

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

1. 
   y = 3(x + b) - 3c Ÿ

2. 
   y = 3(x + b - c)

3. 
   y = 3x + 3b - 3c

.

6. Algorytm sortowania zbioru n liczb naturalnych ma złożoność:

a) n-1

b) n²/2 + n/2 Ÿ

c) n²/2 - n/2

7. Algorytm „sito Erastotenesa:

a) generuje kolejne liczby pierwsze

b) wyznacza wszystkie liczby pierwsze z danego zbioru liczb

naturalnych

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

8. Złożoność problemu wyznaczania „najlepszego” podzbioru zbioru n

elementowego jest:

a) wielomianowa

b) wykładnicza c) logarytmiczna

9. Problem wyznaczenia fałszywej monety ze zbioru n monet jest

problemem:

a) optymalizacyjnym

b) decyzyjnym

c) trudnym

10. Zasada „dziel i zwyciężaj”:

a) zmniejsza złożoność problemu

b) pozwala szybciej rozwiązać problem

c) nie ma wpływu ani na złożoność problemu, ani na

jego efektywność