Питання № 1-20 до тестування за курсом «Теорія алгоритмів і матлогіка» (Основна ідея алгоритмічного методу «Розділяй і пануй». Алгоритм, що покладений в основу алгоритму Дейкстри)

Питання до тестування за курсом «Теорія алгоритмів і матлогика»

“3”

1. У чому складається основна ідея алгоритмічного методу  «розділяй і пануй» ?

·  Задача розбивається на пріоритети по важливості рішення.

·  Задача виконується від верху до низу а потім перевіряється виконання знизу доверху.

·  Задача розбивається на підзадачі. Потім ці підзадачі вирішуються за допомогою рекурсивного виклику або безпосередньо. Рішення комбінуються і виходить рішення вихідної задачі.

·  Задача виконується поетапно з вибором оптимального рішення на кожнім етапі.

2. За умови, що повне бінарне дерево має 128 листів, визначите :

1) висоту цього дерева; 2) кількість вершин.

• 7; – 127.
• 9;  – 127.
• 9;  – 95.
• 8;  – 127.
• 8;  – 95.

3. Дано фрагмент програми рекурсивної функції. Який буде результат при n=3?

Function F( n : integer ) : longint;

 begin

 if n < 2 then F := n

 else F := F( n-1)+ F( n-2)

 end;

Відповіді.

·  неможливо встановити.

·  33.

·  3

·  2

4. Маємо два алгоритми сортування – сортування вставками і злиттям. Який з них за часом виконання більш кращий при значно великій кількості вихідних даних?

·  Обоє мають однаковий час виконання;

·  Кращий сортування вставками;

·  Кращий сортування злиттям.

5. Алгоритми Прима та Крускала – це:    

·  Пошук  Ейлерових шляхів  графа.

·  Пошук  максимальної течії в графі.

·  Пошук мінімального каркасного дерева.

·  Пошук  за зразком.

6. Оцініть трудомісткість двох алгоритмів із заданими асимптотичними оцінками:

O(n²) і O(n*log₂n), якщо кількість даних на вході алгоритму дорівнює n=10.

Який алгоритм кращий за оцінками ?

Відповіді.

• неможливо встановити.
• перший.
• другий.
• однакові.

7. Нехай заданий двомісний предикат P(x,y) : «x любить y». Як за допомогою логіки предикатів представити фразу – « Кожну людини хтось любить» ?

·  "x"yP(x,y).

·  $x$yP(x,y).

·  "y$xP(x,y).

·  $x"y(x,y).

8. До якого класу складності теорії алгоритмів відноситься задача про пошук гамільтонових шляхів у графі?

·  До класу P.

·  До класу NP.

·  До класу NPC.

9. Що означає в теорії алгоритмів поняття «час в найгіршому випадку»?

• Нижня границя цієї величини для будь-яких вхідних даних .
• Верхня границя цієї величини для будь-яких вхідних даних
• Математичне сподівання часу праці.
• Це гіпотетично неможливо.

10. Оберіть яку задачу розв’язує  алгоритм Хаффмена?

·  Задачу мінімальної течії в графі.

·  Задачу максимальної течії в графі.

·  Задачу знаходження остових дерев.

·  Задачу кодування інформації.

11. Знайдіть правильне означення Ейлеревого циклу?

·  Він представляє собою цикл, що проходить по всім ребрам графа тільки один раз, хоча через вершини він може проходити неодноразово.

·  Він представляє собою цикл, що проходить по всім ребрам та вершинам графа тільки один раз.

·  Він представляє собою цикл, що проходить через всі вершини графа тільки один раз, хоча по всім ребрам він може проходити неодноразово.

12. Наведіть оцінку часу пошуку у збалансованому бінарному дереві

· 

· 

· 

13. Граф це

·  множина вершин і ребер які з’єднані між собою

·  сукупність двох множин, вершин і ребер між якими встановлене взаємооднозначна відповідність

·  сукупність двох множин, вершин і ребер між якими встановлена відповідність

14. Які з наведених прикладів не є висловленнями?

·  Дніпро впадає в Балтійське море.

·  Існують натуральні числа x,y,z  x²+y² = z .         

·  5≤2.

·  X+Y>1.

15. Яке з наведених нижче  означень підпадає під поняття  «рекурсивний алгоритм»?

·  Алгоритм розбивається на кроки, на кожному кроці ми обираємо найоптимальніше рішення.

·  Алгоритм розв’язує тільки задачі, що виділені курсивом.

·  Алгоритм під час рішення завдання визиває сам себе.

·  Алгоритм під час рішення використовує метод Монте-Карло.

16. Шлях у графі це

·  кінцева послідовність вершин, у якій кожна вершина (крім останньої) з'єднана з  наступною ребром

·  послідовність вершин у якій перша й остання вершини збігаються

·  послідовність вершин у якій перша й остання вершини з'єднані ребром

17. Як називається бінарне відношення на множині вершин графа, задане як "існує шлях з u в v",

·  відстань між вершинами

·  компонентом  зв’язності

·  відношенням еквівалентності

18. Дводольним називається граф

·  вершини якого можна розбити на дві непересічні підмножини V1 і V2 так, що всяке ребро з'єднує вершину з V1 з вершиною з V2

·  якщо його можна зобразити діаграмою на площині без перетинань ребер

·  якщо будь-які його дві різні вершини з'єднані ребром.

19. Маємо побудувати бінарне дерево пошуку висоти 3 для такого списку слів : фізика, математика, географія, зоологія, метеорологія, біологія, психологія, хімія. Який об’єкт з поданого списку потрібно поставити в корінь дерева ?

·  Географію.

·  Хімію .         

·  Фізику.

·  Математику.

20. Який алгоритм покладений в основу алгоритму Дейкстри

·  пошук у глибину

·  пошук у ширину

·  алгоритм Крускала