Teoretyczne Podstawy Informatyki
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
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
Termem jest wyrażenie:
a) ∧(∨a,(¬b∨c))
b) ∧(∨ (a,(¬b∨c)),d)
c) ∨((a,¬b), ∨a)
Wartością termu MAX{3,9,0} + MOD(11,13) jest:
a) 11
b) 9
c) 20
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
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
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
Maszyna ta: S1 b,S1,-1 b,S1,-1 b,S0,+1
a) zatrzyma się na znaku „0”
b) zatrzyma się na najmniej znaczącej cyfrze liczby 1011
c) nigdy nie zatrzyma się
Liczba 1011 z poprzedniego zadania jest :
daną wejściową
daną wyjściową
programem maszyny Turinga
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”
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 ,...
Algorytm sortowania zbioru n liczb naturalnych ma złożoność:
a) n-1
b) n2/2 + n/2
c) n2/2 - n/2
Algorytm jest poprawny jeżeli jest:
a) częściowo poprawny i spełnia warunek stopu
spełnia własność określoności wyników i określoności obliczeń
nie zatrzymując się, w skończonym czasie dochodzi do punktu
końcowego
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
Złożoność problemu wyznaczania „najlepszego” podzbioru zbioru elementowego jest:
a) wielomianowa
b) wykładnicza c) logarytmiczna
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ść
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:
y = x2 x2 - ax2 + b x2
y = x2 (x2 - a + b)
y = x4 - x2 (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:
aკbკc
a∨b ; a∨c ; b∨c
aკb ; aკc ; bკc
21. Wartością termu (a,v1)*(c,w3) w S jest: a) {x1,x2,x3,x5,x6}
b) {x1,x4,x5,x7} c) {x1,x5}
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) y1 = a ∨¬b
y1 = a ∧ b
y1 = 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
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:
stosunek liczby wszystkich podzbiorów opisywanych w systemie S
do liczby wszystkich możliwych podzbiorów zbioru obiektów
stosunek liczby wszystkich termów prostych w systemie S
do liczby termów prostych niepustych
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) 2n
c) n
28. Problem wyboru „najlepszego” podzbioru zbioru n elementowego ma
złożoność:
a) (n-1)!
b) 2n
c) n2/2 - n/2
29. Wartością termu MOD(MOD(11,13), MOD(11,13)) jest:
a) 1 b) 0 c) 11
30. Maszyna Turinga jest:
a) termem
b) algorytmem
c) komputerem
31. Wartością termu NWD(5,17) + MOD(2,2) jest:
a) 11 b) 1 c) 17
32. Algorytm Euklidesa:
a) generuje kolejne liczby pierwsze
b) wyznacza wszystkie liczby pierwsze z danego zbioru
c) generuje wartość największego wspólnego podzielnika
33. 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
33. Dany jest system informacyjny zadany tabelą. Term (a,v1)*(bu2)*(c,w1)
wyznacza zbiór elementarny:
x1 x2 x3 x4 x5 x6 x7 a) {x2}
a v1 v1 v2 v3 v1 v1 v2 b) ∅
b u2 u3 u3 u2 u3 u1 u1 c) {x2,x4}
c w3 w1 w1 w3 w3 w2 w3
34. W systemie informacyjnym z poprzedniego przykładu wartością termu
(b,u1) → (b,u1) jest :
a) 1 b) (x6,x7) c) 0
35. System informacyjny z przykładu # 33 jest:
a) selektywny
b) zupełny (kompletny)
c) nie selektywny systemie niekompletny
36 W systemie informacyjnym z przykładu # 33 zbiorem elementarnym jest:
a) {x3}
b) {x2, x3}
{x2, x3, x5}
37. W systemie informacyjnym z przykładu # 33 termem prostym jest:
a) (a,v1)*(b,u1)
b) (a,v1)*(b,u1)*(c,w1)
c) (a,v1)*(b,u1)*(c,w1) + (a,v1)*(b,u1)*(c,w2)+... +(a,v3)*(b,u3)*(c,w3)
38. 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) y1 = a ∨¬b
y1 = a ∧ b
y1 = a ∧¬b
n=π; i=1
MOD(i,4)<5
Print i
i=i+1
i = n
T
T
Na 99,9% dobrze