Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 13

Структуры данных и модели вычислений - тест 13

Упражнение 1:

Номер 1

Какие из моделей вычислений являются числовыми?

Ответ:

(1) Машина Тюринга

(2) Абак

(3) РАМ-машина

Номер 2

Какие из моделей вычислений являются словарными?

Ответ:

(1) Алгорифмы Маркова

(2) РАМ-машина

(3) Машина Тюринга

Номер 3

Какие из моделей вычислений работают с адресуемой памятью?

Ответ:

(1) Абак

(2) Машина Тюринга

(3) РАМ-машина

Упражнение 2:

Номер 1

Пусть p(n) - максимальная продуктивность Абак-программы, состоящей из  n  команд. Какие соотношения для функции p(n) истинны?

Ответ:

(1) p(100)> 100

(2) p(100)< 166

(3) p(100)≥ 166

Номер 2

В какое слово переработает алгорифм Маркова
11 → 12,
2 → λ,
1 → 1!
последовательность, состоящую из 4 единиц?

Ответ:

(1) в последовательность, состоящую из 3 единиц

(2) в последовательность, состоящую из 2 единиц

(3) в последовательность, состоящую из 1 единицы

(4) в пустую последовательность

Упражнение 3:

Номер 1

Какие соотношения истинны для любых регулярных выражений α, β, γ?

Ответ:

(1) α*(β+γ) = α*β + α*γ,

(2) (β+γ)*α = β*α + γ*α

(3) α*β = β*α

Номер 2

Какие из следующих соотношений истинны для регулярных выражений в алфавите {a, b, c}?

Ответ:

(1) (ab)*c=a*(ab)*c

(2) (abc)*=a*b*c*

(3) (a+b)*c(b+a) =(a+b)*(cb+ca)

Номер 3

Какая из таблиц задает функцию откатов для слова (aabaababaab) в алгоритме Кнута - Морриса - Пратта?

Ответ:

(1)

i	1	2	3	4	5	6	7	8	9	10	11
f(i)	0	1	0	0	1	2	3	0	1	2	3

(2)

i	1	2	3	4	5	6	7	8	9	10	11
f(i)	0	1	2	0	2	3	4	0	1	2	3

(3)

i	1	2	3	4	5	6	7	8	9	10	11
f(i)	0	1	0	1	2	3	4	0	1	2	3

Упражнение 4:

Номер 1

Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X =αX + β, где α = b+с, β = ab*?

Ответ:

(1) (b+c)*+ab*

(2) a+(b+c)*a

(3) (b+c)*ab*

(4) (b+c)*a

Номер 2

Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα + β, где α = b+с, β = ab*?

Ответ:

(1) ab* + (b+c)*

(2) a+(b+c)*a

(3) ab*(b+c)*

(4) a(b+c)*

Номер 3

Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα , где α = ab+aс?

Ответ:

(1) ab* + ac*

(2) a(b+c)*a

(3) (ab+aс)*

(4) (ab)* + (ac)*

Упражнение 5:

Номер 1

Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением a*b*c*?

Ответ:

(1) 1

(2) 6

(3) 10

(4) 27

Номер 2

Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (a+b+c)*?

Ответ:

(1) 1

(2) 3

(3) 10

(4) 27

Номер 3

Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (ab+c)*?

Ответ:

(1) 1

(2) 3

(3) 10

(4) 27

Главная / Алгоритмы и дискретные структуры / Структуры данных и модели вычислений / Тест 13