Історичні аспекти розвитку біотехнології 1 страница

РОЗДІЛ 1

РОЗДІЛ 1.

Розділ 3

Розділ 2

Рівень А

Розділ 1

1 Граматики, на структуру правил яких, не накладається ніяких обмежень є граматиками

а) з фразовою структурою

б) контекстно-вільними

в) контекстно-залежними

г) регулярними

2 Граматики, в яких один і той же нетермінальний символ може бути змінений на той чи інший ланцюжок символів в залежності від того контексту, в якому він зустрічається є граматиками

а) з фразовою структурою

б) контекстно-вільними

в) контекстно-залежними

г) регулярними

3 Граматики, які мають правила виду А→β, де A VN, β V* є граматиками

а) з фразовою структурою

б) контекстно-вільними

в) контекстно-залежними

г) регулярними

4 Граматики, які мають правила виду А→Вγ, або А→γ, де A,В VN, γ VТ*.

а) з фразовою структурою

б) контекстно-вільними

в) контекстно-залежними

г) регулярними

5 При описі синтаксичних конструкцій мов програмування використовують граматики

а) з фразовою структурою

б) контекстно-вільні

в) контекстно-залежнимі

г) регулярні

6 При описі простіших конструкцій мов програмування (ідентифікаторів, констант, рядків і т. д.) використовують граматики

а) з фразовою структурою

б) контекстно-вільні

в) контекстно-залежні

г) регулярні

7 Мови, які застосовують при аналізі та перекладі текстів на природні мови, відносяться до

а) мов, з фразовою структурою

б) контекстно-вільних мов

в) контекстно-залежних мов

г) регулярних мов

8 Мови, які лежать в основі синтаксичних конструкцій більшості сучасних мов програмування належать до

а) мов, з фразовою структурою

б) контекстно-вільних мов

в) контекстно-залежних мов

г) регулярних мов

9 Мови, для роботи з якими можна використовувати кінцеві автомати належать до

а) мов, з фразовою структурою

б) контекстно-вільних мов

в) контекстно-залежних мов

г) регулярних мов

10 Для мов з фразовою структурою використовують розпізнавач

а) детермінований двосторонній автомат з необмеженою зовнішньою пам’яттю

б) недетермінований двосторонній автомат з необмеженою зовнішньою пам’яттю

в) детермінований двосторонній автомат з обмеженою зовнішньою пам’яттю

г) недетермінований односторонній автомат з необмеженою зовнішньою пам’яттю

д) детермінований односторонній автомат без зовнішньої пам’яті

11 Для контекстно-залежних мов використовують розпізнавач

а) детермінований двосторонній автомат з необмеженою зовнішньою пам’яттю

б) недетермінований двосторонній автомат без зовнішньої пам’яті

в) недетермінований двосторонній автомат з обмеженою зовнішньою пам’яттю

г) недетермінований односторонній автомат з необмеженою зовнішньою пам’яттю

д) детермінований односторонній автомат без зовнішньої пам’яті

12 Для контекстно-вільних мов використовують розпізнавач

а) детермінований двосторонній автомат з необмеженою зовнішньою пам’яттю

б) недетермінований односторонній автомат зі стековою зовнішньою пам’яттю

в) детермінований односторонній автомат зі стековою зовнішньою пам’яттю

г) недетермінований односторонній автомат з обмеженою зовнішньою пам’яттю

д) детермінований двосторонній автомат зі стековою зовнішньої пам’яті

13 Для регулярних мов використовують розпізнавач

а) детермінований односторонній автомат без зовнішньої пам’яті

б) недетермінований двосторонній автомат з бмеженою зовнішньою пам’яттю

в) детермінований односторонній автомат зі стековою зовнішньою пам’яттю

г) детермінований односторонній автомат з обмеженою зовнішньою пам’яттю

д) детермінований двосторонній автомат зі стековою зовнішньої пам’яті

14 На наведене твердження виберіть вірну відповідь.

Розпізнавач складається з наступних основних компонент:

1. Вхідного ланцюга символів

2. Зчитуючої головки

3. Пристрою керування

4. Арифметико-логічного пристрою

5. Робочої пам’яті

6. Алфавітного аналізатора

7. Потактового перетворювача

а) вірно 1, 2, 4, 5, 7

б) вірно 2, 3, 5, 6

в) вірно 1, 2, 3, 5

г) вірно 1, 2, 3, 5, 7

д) вірно 2, 3, 5, 6, 7

15 Спеціальний алгоритм, який дозволяє визначити належність ланцюга символів деякій мові називається

а) генератором

б) розпізнавачем

в) компілятором

г) алфавітним аналізатором

Рівень В

1 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг -532, що виводиться з ланцюга A.

а) 3

б) 5

в) 6

г) 7

д) 9

2 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг 67, що виводиться з ланцюга A.

а) 3

б) 5

в) 6

г) 7

д) 9

3 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг 123, що виводиться з ланцюга В.

а) 3

б) 5

в) 6

г) 7

д) 9

4 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг 1004, що виводиться з ланцюга ВСВ.

а) 2

б) 5

в) 6

г) 7

д) 9

5 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг -5, що виводиться з ланцюга A.

а) 2

б) 3

в) 4

г) 5

д) 6

6 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг -67, що виводиться з ланцюга B.

а) 1

б) 2

в) 3

г) 4

д) ланцюг вивести не можна

7 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг 167, що виводиться з ланцюга A.

а) 3

б) 5

в) 6

г) 7

д) ланцюг вивести не можна

8 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг -134, що виводиться з ланцюга AВ.

а) ланцюг вивести не можна

б) 5

в) 6

г) 7

д) 9

9 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг 67, що виводиться з ланцюга AС.

а) 2

б) 3

в) 4

г) 5

д) ланцюг вивести не можна

10 Задана граматика цілих десяткових чисел зі знаком G({0,1,2,3,4,5,6,7,8,9,-,+},{A,B,C},P,A):

P:

A → B | +B | -B

B → C | BC

C → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Скільки кроків необхідно зробити, щоб отримати ланцюг -67, що виводиться з ланцюга AС.

а) 2

б) 3

в) 4

г) 5

д) ланцюг вивести не можна

Рівень С

1 Задана грамматика G({a,b,c},{B,C,D,S},P,S) з правилами:

P:

S → BD

B → aBbC | ab

Cb → Bc

Cd → Dc

bDc → bcc

abD → abc

Визначити, який з ланцюгів виводу можна вивести, керуючись правилами даної граматики.

а) S=>BD=>aBbCD=>aaBbbCbCD=>aaaBbbCbCbCD=>aaaabbbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCD=>aaaabbbbCD=>aaaabbbbCDc=>aaaabbbcc

б) S=>BD=>aabCD=>aabCbCD=>aabCbCbCD=>aabbCbCbCD=>aabbCCbCD=>

aabbbCbCCD=>aabbbCD=>aaabbbCc=>aaabbbbcc

в) S=>BD=>aBbCD=>aaBbCbCD=>aaaBbCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

г) S=>BD=>abCD=>abCbCD=>aaabCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

д) немає правильного ланцюга виводу

2 Задана грамматика G({a,b,c},{B,C,D,S},P,S) з правилами:

P:

S → BD

B → aBbC | ab

Cb → Bc

Cd → Dc

bDc → bcc

abD → abc

Визначити, який з ланцюгів виводу можна вивести, керуючись правилами даної граматики.

а) SB=>BDB=>abDB=>abcB=>abcab

б) SB=>BBD=>BabD=>Babc=>ababc

в) SB=>BD=>abD =>abc

г) SB =>BDB =>aBbCDB =>aabBcDab =>aababccab

д) немає правильного ланцюга виводу

3 Задана грамматика G({a,b,c},{B,C,D,S},P,S) з правилами:

P:

S → BD | CD

B → aBbC | ab

CD → Bc

C → Dc

bDc → bcc

abD → abc

Визначити, який з ланцюгів виводу можна вивести, керуючись правилами даної граматики.

а) S=>BD=>aaBbCD=>aaaBbCbCD=>aaabCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbBc=>aaaabbbabc

б) S=>BD=>aBbCD=>aaBbCbCD=>aaabbDcbCD=>aaabbDcbCD=>aaabbccbBc=>

=>aaabbccbabc

в) S=>BD=>aBbCD=>aaBbCbCD=>aaaBbCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

г) S=>BD=>abCD=>abCbCD=>aaabCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

д) немає правильного ланцюга виводу

4 Задана грамматика G({a,b,c},{B,C,D,S},P,S) з правилами:

P:

S → BD | CD

B → aBbC | ab

CD → Bc

C → Dc

bDc → bcc

abD → abc

Визначити, який з ланцюгів виводу можна вивести, керуючись правилами даної граматики.

а) S=>BD=>aaBbCD=>aaaBbCbCD=>aaabCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbBc=>aaaabbbabc

б) S=>BD=>aBbCD=>aaBbCbCD=>aaaBbCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

в) S=>CD =>Bc =>aBbCc =>aaBbCbCc =>aaabbBcbCc =>aaabbBcDcc =>aaabbabDcc =>aaabbabccc

г) S=>CD =>Bc =>aBbCDc =>aabbBcc =>aabbabcc

д) немає правильного ланцюга виводу

5 Задана грамматика G({a,b,c},{B,C,D,S},P,S) з правилами:

P:

S → BD | CD

B → aBbC | ab

CD → Bc

C → Dc

bDc → bcc

abD → abc

Визначити, який з ланцюгів виводу можна вивести, керуючись правилами даної граматики.

а) S =>CD =>Bc => aBbCD=>aaBbCbCD =>aaabbDcbBc =>aaabbbccbBc =>aaabbbccbab

б) S=>CD =>Bc =>aBbCDc =>aabbBcc =>aabbabcc

в) S=>BD=>aBbCD=>aaBbCbCD=>aaaBbCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

г) S=>BD=>abCD=>abCbCD=>aaabCbCbCD=>aaaabbCbCbCD=>aaaabbbCCbCD=>

aaaabbbCbCCD=>aaaabbbbCCCD=>aaaabbbbCCDc=>aaaabbbbCDcc=>aaaabbbbDccc=>aaaabbbbcccc

д) немає правильного ланцюга виводу

6 Задана грамматика G({a,b,c},{B,C,D,S},P,S) з правилами:

P:

S → BD | CD

B → aBbC | ab

CD → Bc

C → Dc

bDc → bcc

abD → abc

Визначити, який з ланцюгів виводу можна вивести, керуючись правилами даної граматики.

а) S=>CD =>Bc =>aBbCc =>aBbCbCc =>aabbBcbCc =>aabbBcDcc =>aabbabDcc =>aabbabccc

б) S=>CD =>Bc =>aBbCDc =>aaBbCbCDc =>aaabbCbDc =>aaabbCbbcc =>aaabbBcbbcc =>aaabbabcbbcc

в) S=>BD=>aBbCD=>aaBbCbCD =>aaabbCbCD =>aaabbDcbCD =>aaabbccbCD =>aaabbccbBc =>aaabbccbabc

г) S=>BD=>aBbCD=>aaBbCbCD =>aaabbCbCD =>aaabbDcbCD =>aaabbbccbCD =>aaabbbccbBc =>aaabbbccbabc

д) немає правильного ланцюга виводу

Рівень А

1 На наведене твердження виберіть вірну відповідь

На етапі аналізу в процесі компіляції програми виконуються наступні фази

1. Лексичний аналіз

2. Синтаксичний аналіз

3. Семантичний аналіз

4. Звернення до таблиць ідентифікаторів

5. Внутрішнє представлення програми

6. Підготовка до генерації коду

7. Генерація коду

а) вірно 1, 2, 3, 4

б) вірно 1, 2, 3, 5

в) вірно 1, 2, 3, 4, 5

г) вірно 1, 2, 3

д) вірно все

2 На наведене твердження виберіть вірну відповідь

На етапі синтезу в процесі компіляції програми виконуються наступні фази

1. Лексичний аналіз

2. Синтаксичний аналіз

3. Семантичний аналіз

4. Звернення до таблиць ідентифікаторів

5. Внутрішнє представлення програми

6. Підготовка до генерації коду

7. Генерація коду

а) вірно 4, 5, 6, 7

б) вірно 5, 6, 7

в) вірно 3, 4, 5, 6, 7

г) вірно 6, 7

д) вірно все

3 Фаза оптимізації відсутня в

а) трансляторах

б) інтерпретаторах

в) компіляторах

4 Скільки програм приймають участь в роботі транслятора

а) 1

б) 2

в) 3

г) 4

д) кількість програм залежить від виду транслятора

5 Відмінність між трансляторами та компіляторами в тому, що

а) в трансляторах відсутня фаза оптимізації

б) в трансляторах відсутня результуюча програма

в) вони застосовують різні алгоритми внутрішнього представлення програми

г) в них різна форма представлення результуючої програми

6 Об’ктний код – це результуюча програма

а) інтерпретаторів

б) трансляторів

в) компіляторів

7 Незалежність виконання програми від архітектури цільової обчислювальної системи характерна для

а) інтерпретаторів

б) трансляторів

в) компіляторів

8 Хеш-функція виконує відображеня імен ідентифікаторів на

а) множину цілих чисел

б) множину дійсних чисел

в) множину натуральних чисел

г) множину натуральних додатніх чисел

д) множину цілих невід’ємних чисел

9 Метод побудови таблиць ідентифікаторів, який вимагає організації роботи з динамічними масивами даних називається

а) метод бінарного пошуку

б) метод бінарного дерева

в) метод ланцюжків

г) метод простого рехешування

д) метод на основі хеш-функцій

10 Метод побудови таблиць ідентифікаторів, при якому пошук здійснюється в упорядкованому списку називається

а) метод бінарного пошуку

б) метод бінарного дерева

в) метод ланцюжків

г) метод простого рехешування

д) метод на основі хеш-функцій

11 Метод побудови таблиць ідентифікаторів, при якому таблиця має вигляд бінарного дерева називається

а) метод бінарного пошуку

б) метод бінарного дерева

в) метод ланцюжків

г) метод простого рехешування

д) метод на основі хеш-функцій

Рівень А

1 Лексемами мов програмування є:

1. Ідентифікатори

2. Константи

3. Службові слова

4. Знаки операцій

5. Розділювачі

а) вірно 1, 2, 3

б) вірно 1, 2, 4

в) вірно 1, 3, 4

г) вірно 1, 2, 3, 4

д) вірно все

2 Метод організації взаємозв’язку лексичного та синтаксичного аналізаторів, при якому таблиця лексем будується зразу є

а) послідовним

б) паралельним

в) незалежним

г) поетапним

д) лінійним

3 Метод організації взаємозв’язку лексичного та синтаксичного аналізаторів, при якому лексичний аналіз виконується поетапно є

а) послідовним

б) паралельним

в) незалежним

г) поетапним

д) лінійним

4 Виходом лексичного аналізатора є

а) ланцюг вхідної мови

б) таблиця лексем

в) таблиця ідентифікаторів

г) машинні коди

д) ланцюг вхідної мови без зайвих розділювачів

5 Основною частиною на етапі аналізу є

а) лексичний аналізатор

б) синтаксичний аналізатор

в) семантичний аналіз

г) внутрішнє представлення програми

д) генерація коду

6 Пошук границі рядка символів, що розпізнається здійснюється на етапі

а) лексичного аналізу

б) синтаксичного аналізу

в) семантичного аналізу

д) генерації коду

7 Розпізнавачами для лексичних аналізаторів є

а) кінцеві автомати

б) автомати з магазинною пам’яттю

в) імовірнісні автомати

8 Розпізнавачами для синтаксичних аналізаторів є

а) кінцеві автомати

б) автомати з магазинною пам’яттю

в) імовірнісні автомати

9 При побудові синтаксичного аналізатора за алгоритмом «зсув-зготка» моделюють

а) висхідний розпізнавач

б) нисхідний розпізнавач

в) рекурсивний розпізнавач

г) розширений розпізнавач

д) стековий ропізнавач

10 Розпізнавач для граматик передування будується на основі алгоритму

а) підбору альтернатив

б) зсуву-згортки

в) рекурсивного спуску

г) умовного перебору

11 Якщо, в процесі виконання синтаксичного розбору за алгоритмом «зсув-згорка», в граматиці передування зустрічається символ відношення <∙,

а) необхідно виконати зсув

б) необхідно виконати згортку

в) залишити все без змін і перейти до аналізу наступного відношення

12 Якщо, в процесі виконання синтаксичного розбору за алгоритмом «зсув-згорка», в граматиці передування зустрічається символ відношення ∙>,

а) необхідно виконати зсув

б) необхідно виконати згортку

в) залишити все без змін і перейти до аналізу наступного відношення

13 Якщо, в процесі виконання синтаксичного розбору за алгоритмом «зсув-згорка», в граматиці передування зустрічається символ відношення =∙,

а) необхідно виконати зсув

б) необхідно виконати згортку

в) залишити все без змін і перейти до аналізу наступного відношення

Рівень В

1 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А1 при умові, що h(A1)=h(A2)= h(A5)=n1, h(A3)=n2, h(A4)=)=n4.

а) 1

б) 2

в) 3

г) 4

д) 5

2 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А2 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д)5

3 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А3 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

4 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А4 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

5 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А5 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

6 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А1 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

7 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А2 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

8 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А3 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

9 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А4 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

10 Таблиця ідентифікаторів заповнюється методом простого рехешування. В послідовних комірках таблиці n1, n2, n3, n4, n5 поміщено ідентифікатори А1, А2, А3, А4, А5. Визначити, скільки порівнянь необхідно зробити при пошуку ідентифікатора А5 при умові, що h(A1)=h(A2)=n1, h(A3)=n4, h(A4)=h(A5)=n2.

а) 1

б) 2

в) 3

г) 4

д) 5

11 Дано граматику для арифметичних дій над символами G({+, -, /, *, a, b}, {S, T, E}, P, S) з правилами:

P:

S → S+T | S-T | T

T→T*E | T/E | E

E→ (S) | a | b

Визначити, яка з множин є крайньою лівою множиною L(S) відносно нетермінального символу S.

а) L(S)={+, -,(}

б) L(S)={+, - *, /}

в) L(S)={+, -, *, /, (, a,b}

г) L(S)={*, /, (, a,b}

д) L(S)={(, a, b}

12 Дано граматику для арифметичних дій над символами G({+, -, /, *, a, b}, {S, T, E}, P, S) з правилами:

P:

S → S+T | S-T | T

T→T*E | T/E | E

E→ (S) | a | b

Визначити, яка з множин є крайньою лівою множиною L(T) відносно нетермінального символу T.

а) L(T)={+, -,(}

б) L(T)={+, - *, /}

в) L(T)={+, -, *, /, (, a,b}

г) L(T)={*, /, (, a,b}

д) L(T)={(,), a, b}

13 Дано граматику для арифметичних дій над символами G({+, -, /, *, a, b}, {S, T, E}, P, S) з правилами:

P:

S → S+T | S-T | T

T→T*E | T/E | E

E→ (S) | a | b

Визначити, яка з множин є крайньою лівою множиною L(E) відносно нетермінального символу E.

а) L(E)={+, -,(}

б) L(E)={+, - *, /}

в) L(E)={+, -, *, /, (, a,b}

г) L(E)={*, /, (, a,b}

д) L(E)={(, a, b}

14 Дано граматику для арифметичних дій над символами G({+, -, /, *, a, b}, {S, T, E}, P, S) з правилами:

P:

S → S+T | S-T | T

T→T*E | T/E | E

E→ (S) | a | b

Визначити, яка з множин є крайньою правою множиною R(S) відносно нетермінального символу S.

а) R(S)={+, -,)}

б) R(S)={+, - *, /}

в) R(S)={+, -, *, /,), a,b}

г) R(S)={*, /,), a,b}

д) R(S)={), a, b}

15 Дано граматику для арифметичних дій над символами G({+, -, /, *, a, b}, {S, T, E}, P, S) з правилами:

P:

S → S+T | S-T | T

T→T*E | T/E | E

E→ (S) | a | b

Визначити, яка з множин є крайньою правою множиною R(T) відносно нетермінального символу T.

а) R(T)={+, -,)}

б) R(T)={+, - *, /}

в) R(T)={+, -, *, /,), a,b}

г) R(T)={*, /,), a,b}

д) R(T)={*, /, (,), a, b}

16 Дано граматику для арифметичних дій над символами G({+, -, /, *, a, b}, {S, T, E}, P, S) з правилами:

P:

S → S+T | S-T | T

T→T*E | T/E | E

E→ (S) | a | b

Визначити, яка з множин є крайньою правою множиною R(E) відносно нетермінального символу E.

а) R(E)={+, -, (,)}

б) R(E)={+, - *, /}

в) R(E)={ *, /,), a,b}

г) R(E)={(,), a,b}

д) R(E)={), a, b}

Рівень С

1 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів LL2, K12, DD, T3,K2, D1, KI2.

2 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів T34, KI2,T3,D1,TT,K2,J56,A1,DD.

3 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів Y5, F1, DD, Y, AA, T4, T3, D1, FA.

4 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів Y1, Y5, F1,DD, T3, FA, TT1, K1, D1, Y.

5 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів A2, FA, TT, L1, A, T3, D6, D1, FF, LL.

6 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів FAT, T3, A2, D1, TT, L1A, Y2, K, TT3, FA, DA.

7 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів J5, F1, DD, T3, KI2, T2, D1, K2.

8 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів Y1, T3, D1, Y2, FA, TT, Y5, F1, DD, M.

9 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів A5, F1, FF, LL, T3, D1, A2, FA, TT, L1.

10 Яке, з побудованих бінарних дерев, відповідає послідовності ідентифікаторів T3, D1, A2, FT, TT, L1, Y2, K, FA, TR, DIA.

Розділ 4

Рівень А

Дата добавления: 2017-02-01