Teoretyczne Podstawy Informatyki

1. Termin algorytm oznacza:

a)spis danych wejściowych i oczekiwanych wyników

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

c) procedurę opisującą sposób rozwiązania 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. 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:

a) y = 3(x + b) - 3c

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

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

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

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

8. 
   Liczba 1011 z poprzedniego zadania jest :

1. daną wejściową

2. daną wyjściową

3. programem maszyny Turinga

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

10. 
    Algorytm opisany schematem blokowym jest:

a) poprawny

b) niepoprawny

c) skończony

11. Wydrukowane zostanie:

a) 1 , 2 , 3

b) same spacje

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

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

a) n-1

b) n²/2 + n/2 Ÿ

c) n²/2 - n/2 Ÿ

13. Algorytm jest poprawny jeżeli jest:

a) częściowo poprawny i spełnia warunek stopu Ÿ

2. spełnia własność określoności wyników i określoności obliczeń

3. 
   nie zatrzymując się, w skończonym czasie dochodzi do punktu Ÿ

końcowego

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

15. Złożoność problemu wyznaczania „najlepszego” podzbioru zbioru elementowego jest:

a) wielomianowa

b) wykładnicza c) logarytmiczna

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

a) optymalizacyjnym

b) decyzyjnym

c) trudnym

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

18. Termem jest wyrażenie:

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

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

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

19. 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)

20. Dane są trzy zbiorniki wyposażone w trzy sygnalizatory dwupołożeniowe podające informacje o poziomach cieczy. Należy zasygnalizować przypadki: gdy co najmniej dwa zbiorniki osiągną określony poziom. Notując odpowiednie informacje przez a, b, c warunki te można zapisać: jako:

1. 
   aკbკc

2. a∨b ; a∨c ; b∨c

3. aკb ; aკc ; bკc

21. Wartością termu (a,v₁)*(c,w₃) w S jest: a) {x₁,x­₂,x₃,x₅,x₆}

b) {x₁,x­₄,x₅,x₇} c) {x₁,x­₅}

22. Dane są informacje z dwóch punktów a i b. Sygnalizowana ma być sytuacja

gdy na wejściach a i nie b pojawi się 1. Funkcja przełączająca ma postać:

a) y₁ = a ∨¬b

2. y₁ = a ∧ b

3. y₁ = a ∧¬b

23. System informacyjny kompletny to taki, w którym:

a) każda informacja jest nie pusta

b) każdej informacji odpowiada co najwyżej jeden obiekt

c) każdemu obiektowi odpowiada co najwyżej klika informacji

24. Problem wyznaczania NWW(m,n) jest problemem:

a) decyzyjnym trudnym

b) optymalizacyjnym łatwym

c) decyzyjnym łatwym

25. System informacyjny zupełny to taki, w którym:

a) każda informacja jest nie pusta

b) każdej informacji odpowiada co najwyżej jeden obiekt

3. 
   każdemu obiektowi odpowiada co najwyżej klika informacji

26. Pytanie dotyczące zbioru obiektów należy do klasy pytań:

a) relacyjnych

b) liczbowych

c) mnogościowych

27. Dokładność systemu informacyjnego to:

1. 
   stosunek liczby wszystkich podzbiorów opisywanych w systemie S

do liczby wszystkich możliwych podzbiorów zbioru obiektów

19. stosunek liczby wszystkich termów prostych w systemie S

do liczby termów prostych niepustych

20. 
    stosunek liczby wszystkich termów prostych w systemie S

do liczby wszystkich możliwych podzbiorów zbioru obiektów

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

a) (n-1)!

b) 2ⁿ

c) n

29. Dany jest automat M zadany przez stan S₀ = 0 zbiór stanów końcowych:

	a b
0 1 2	0 1 0 2 2 2

F = {2} i funkcję przejścia zadaną tabelą. Automat ten rozpoznaje słowo:

a) aⁿ

b) aⁿ b aⁿ

c) aⁿ bⁿ

31. Funkcja przełączająca y₁ = (¬x₂ ∨ ¬x₁) ∧ (¬x₂ ∨ x₁ ) ∧ (x₂ ∨ ¬x₁) ∧ (x₂ ∨ x₁) jest postaci:

a) normalnej zupełnej sumy

b) normalnej prostej regularnej

c) normalnej zupełnej iloczynu

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

złożoność:

a) (n-1)!

b) 2ⁿ

c) n²/2 - n/2

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

a) 1 b) 0 c) 11

34. Maszyna Turinga jest:

a) termem

b) algorytmem

c) komputerem

35. Wartością termu NWD(5,17) + MOD(2,2) jest:

a) 11 b) 1 c) 17

36. Algorytm Euklidesa:

a) generuje kolejne liczby pierwsze

b) wyznacza wszystkie liczby pierwsze z danego zbioru

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

37. System informacyjny selektywny to taki, w którym:

a) każda informacja jest nie pusta

b) każdej informacji odpowiada co najwyżej jeden obiekt

c) każdemu obiektowi odpowiada co najwyżej klika informacji

38. Dany jest system informacyjny zadany tabelą. Term (a,v₁)*(bu₂)*(c,w₁)

wyznacza zbiór elementarny:

x₁ x₂ x₃ x₄ x₅ x₆ x₇ a) {x₂}

a v₁ v₁ v₂ v₃ v₁ v₁ v₂ b) ∅

b u₂ u₃ u₃ u₂ u₃ u₁ u₁ c) {x₂,x₄}

c w₃ w₁ w₁ w₃ w₃ w₂ w₃

39. W systemie informacyjnym z poprzedniego przykładu wartością termu

(b,u₁) → (b,u₁) jest :

a) 1 b) (x₆,x₇) c) 0

40. System informacyjny z przykładu # 38 jest:

a) selektywny

b) zupełny (kompletny)

c) nie selektywny systemie niekompletny

41 W systemie informacyjnym z przykładu # 38 zbiorem elementarnym jest:

a) {x₃}

b) {x₂, x₃}

3. 
   {x₂, x₃, x₅}

42. W systemie informacyjnym z przykładu # 38 termem prostym jest:

a) (a,v₁)*(b,u₁)

b) (a,v₁)*(b,u₁)*(c,w₁)

c) (a,v₁)*(b,u₁)*(c,w₁) + (a,v₁)*(b,u₁)*(c,w₂)+... +(a,v₃)*(b,u₃)*(c,w₃)

43. Dane są informacje z dwóch punktów a I b. Sygnalizowana ma być sytuacja gdy na wejściach a i b pojawi się 1. Funkcja przełączająca ma postać:

a) y₁ = a ∨¬b

4. y₁ = a ∧ b

5. y₁ = a ∧¬b

n=π; i=1

MOD(i,4)<5

Print i

i=i+1

i = n

T

T

Na 100% dobrze

Na 60% dobrze

---