PK_WE Teoretyczne Podstawy Informatyki Test #1a)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ……16.11.2006

1. Algorytmem jest:

a) dziedzina algorytmiczna

b) a ∨ b + c

c) term

2. Dziedziną algorytmiczną jest:

a) ({1,0}, ∧, ∨, ⇒ , ⇔ , ¬ )

b) ({1,2,…,3}, ∧, ∨, ⇒ , ⇔ , + )

c) (R, ∧, ∨, ⇒ , ⇔ , ¬ )

3. Problem wyboru najwyższego harcerza n+1 osobowej drużyny ma złożoność:

a) (n-1)!

b) n-1

c) n

4. Algorytm „sito Erastotenesa:

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

b) wyznacza wszystkie liczby pierwsze z danego zbioru liczb

naturalnych

c) generuje kolejne liczby pierwsze

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

n elementowego jest:

a) wielomianowa

b) wykładnicza c) logarytmiczna

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

problemem:

a) optymalizacyjnym

b) decyzyjnym

c) nie jest problemem

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

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

a) zmniejsza złożoność problemu

b) zwiększa złożoność problemu

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

9. Algorytm opisany schematem blokowym jest:

a) poprawny

b) niepoprawny Ÿ

c) nieskończony

10. Wydrukowane zostanie:

a) 1, 2 , 3, 4, 5,…

b) 1,2

c) 2

PK_WE Teoretyczne Podstawy Informatyki Test #1b)

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ……16.11.2006

1. Algorytmem jest:

a) dziedzina algorytmiczna

b) problem optymalizacyjny

c) diagram blokowy z zadania 9-ego

4. Algorytm Euklidesa:

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

b) wyznacza wszystkie liczby pierwsze z danego zbioru liczb

naturalnych

c) generuje kolejne liczby pierwsze

2. Dziedziną algorytmiczną jest:

a) (R, ∧, ∨, ⇒ , ⇔ , ¬ )

b) ({1,2,…,3}, ∧, ∨, ⇒ , ⇔ , + )

c) ({1,0}, ∧, ∨, ⇒ , ⇔ , ¬ )

3. Problem wyboru najwyższego harcerza n+1 osobowej drużyny ma złożoność:

a) (n-1)!

b) n-1

c) n

5. Problem wyznaczenia fałszywej monety ze zbioru n monet jest problemem:

a) decyzyjnym

b) optymalizacyjnym

c) nie jest problemem

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

n elementowego jest:

a) wielomianowa

b) wykładnicza c) typu silnia

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

a) „u>0”

b) „u = i” c) „u liczba całkowita”

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

a) zmniejsza złożoność problemu

b) zwiększa złożoność problemu

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

9. Algorytm opisany schematem blokowym jest:

a) niepoprawny

b) poprawny

c) nieskończony

10. Wydrukowane zostanie:

a) 1, 2 , 3, 4, 5,…

b) 1,2

c) 2

a∧¬b∨c - term ten należy do dziedziny algorytmicznej:

a) ({1,0}, ∧, +, ⇒ , ⇔ , ¬ )

2. 
   ({1,0}, ∧, ⇒ , ⇔ , ¬ )

3. 
   ({1,0}, ∧, ∨, ⇒ , ⇔ , ¬ )

8. Dany jest n elementowy zbiór nieocechowanych odważników. Dana jest waga szalkowa. Problem ten jest problemem::

a) decyzyjnym

b) optymalizacyjnym c) nie jest problemem

4. Problem wyboru najwyższego harcerza n osobowej drużyny ma złożoność:

a) (n-1)!

b) 2ⁿ

c) n

5. Termin algorytm oznacza:

a) przepis postępowania przy rozwiązywaniu zadania Ÿ

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

4. 
   procedurę opisującą rozwiązanie problemu

6. 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. Termem jest wyrażenie:

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

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

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

4. Wartością termu MIN{3, 2, MOD(11,DIV(3,2))} jest:

a) 3 b) 1 c) 2

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

.

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ść

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

a) n-1

b) n²/2 + n/2 Ÿ

c) n²/2 - n/2

T

T

i = n

MOD(i,4)<5

n=3; i=2

i=i+1

Print i

Print i

i=i+1

n=3; i=1

MOD(i,4)<5

i = n

T

T

---