Teoretyczne Podstawy Informatyki Test #2

Imię i nazwisko . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.05.2005

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

a) n!

b) n²/2 - n/2 

1. 
   n²/2 + n/2

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

a) relacyjnych

b) liczbowych

c) mnogościowych

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

a) relacyjnych

b) liczbowych

3. 
   numerycznych

4. 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₄}

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

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

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

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

6. W systemie informacyjnym z przykładu # 3 termem jest:

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

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

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

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

S₁ 0,S_s,-1 1,S₁,-1 b,S₀,+1

Maszyna ta:

a) zatrzyma się na znaku „0”

b) zatrzyma się na najmniej znaczącej cyfrze liczby 1110 c) nigdy nie zatrzyma się

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

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

1. 
   y₁ = a b

2. 
   y₁ = a b

3. 
   y₁ = a b

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

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

a) aⁿ

b) aⁿ b aⁿ

c) aⁿ bⁿ

10 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

	a b
0 1 2	0 1 0 2 2 2

---