Що таке структура даних. За якими критеріями можна класифікувати структури даних. Приклади.

Структура даних - це згрупований певним способом набір даних, для якого визначені правила обробки елементів.

Структури даних діляться на:

- Лінійні. Структури в яких елементи ніяк між собою не зв’язані. такі структури зберігаються у

ü Масив (векторне представлення)

ü Список, черга, стек (зв’язане представлення)

ü Асоціативній масив, масив в якому елементи мають не індекс, а строкове значення (ключ, ім’я…)

- Не лінійні. Структури в яких елементи мають звязок один з одним. Такі структури сберігаються у кучі (heap)

ü Дерево (бінарне, N-арне)

ü Хеш-таблиця

 

Якими способами розміщуються елементи структур даних у пам’яті? Приклади.

Що таке рекурсивна функція? Які особливості її реалізації? Приклад.

Рекурсивна функція - це функція, що викликає саму себе.

Особливості реалізації:

1. Рекурсивна функція не може викликати себе до безкінечності.

2. Рекурсивна функція завжди повинна мати умову завершення.

3. Кожен наступний виклик виконується зі зменшенням значення параметрам функції.

Приклад:

Вираховування факторіала, рекурсивний алгоритм

int fucktorial(int n)

{

if (n == 0) //Условие выхода из рекурсии

return 1;

return n*fucktorial(n - 1);

}

Теж саме, тільки без рекурсії

int fact(int n)

{

if(n == 0)

return 1;

int temp = 1;

for(int i = 1; i <= n; i++)

temp = temp * i;

return temp;

}

 

 

4. Як визначається структура даних «множина». Що таке хеш-таблиця? За якими критеріями можна класифікувати хеш-таблиці?

Множиною - називається скінченний набір однотипних даних.

Хеш-таблиця — структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем.

Їх можна класифікувати за методами хешування:

ü Метод ділення

ü Метод множення

ü Метод універсального хешування

 

Для чого призначено хешування? Які є методи хешування?

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

Є 3 алгоритми отримання хеш ключа.

1. Ділення.

int GetHash(int key)

{

return (int)Key % size;

}

2. Множення.

int GetHash(int key)

{

double temp = key * 0.6130; //золота середина

temp = temp – (int) temp;

return (int);

}

3. Подвійний хеш. Полягає в тому щоб використовувати суму двох хеш ключів одночасно.

 

За яких умов у хеш-таблиці виникають колізії? Якими способами вони вирішуються?

У хеш таблиці виникають колізії у тому випадку, коли значення елементів (їх ключі) співпадають. Для вирішення колізій використовують зондування:

ü Лінійне зондування

ü Квадратичне зондування

ü Подвійне зондування

 

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

Дерево - одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:

1. існує один відокремлений вузол — корінь (root) дерева

2. інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин в свою чергу є деревом. Дерева T1…Tm мають назву піддерев (subtrees) даного кореня.

Види дерев (їх набагато більше, але тут основні):

1. Бінарне дерево. Дерево, кожен вузол якого має лише 2 посилання на 2 вузла,

лівій і правий. Правило за яким елементи додаються до такого дерева: якщо ключ

нового елемента більше ніж вузол, то перехід до правої гілки, якщо менше то до

лівої, якщо рівні то додавання не здійсниться. Якщо права чи ліва гілка відсутня

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

переходу новій елемент додається то структури.

2. AVL дерево. Схоже на бінарне, але, елементи мають по 3 посилання на 3 вузли. Правила майже теж саме, але у випадку коли ключ нового елемента збігається з ключем вузда, то буде перехід то центральної гілки.

3. N-арне дерево. Дерево, кожен вузол якого має безліч посилань на наступні елементи.

4. Окто дерево. Дуже схоже на бінарне, але на відміну від бінарного, окто дерево має рівно 8 посилань

Э 3 алгоритми базові обходу дерев

1. Послідовний (Лівий, Правий, Вузол) (ЛПВ), всі елементи будуть виведені як відсортований масив, за збільшенням ключа.

2. Паралельний (Лівий, Вузол, Правий) (ЛВП)

3. В ширину (Вузол, Лівий, Правий) (ВЛП) пояснення:

Лівий – перехід до лівого вузла та повтор формули для нього

Правий – перехід до правого вузла та повтор формули для нього

Вузол - вивід значення даного вузла

 

Яким чином видаляються вузли дерева залежно від їх розташування?

Процедура видалення даного вузла z з бінарного дерева пошуку отримує в якості аргументу покажчик на z. Процедура розглядає три можливі ситуації:

1. Якщо у вузла z немає дочірніх вузлів, то ми просто змінюємо його батьківський вузол р[z], замінюючи в ньому покажчик на z значенням NULL.

2. Якщо у вузла z лише один дочірній вузол, то ми видаляємо вузол z, створюючи новий зв'язок між батьківським і дочірнім вузлом вузла z.

3. Якщо у вузла z два дочірніх вузла, то ми переходимо до правого вузла и переходимо вліво, знаходимо наступний за ним вузол у, у якого немає лівого дочірнього вузла, прибираємо його з позиції, де він перебував раніше, шляхом створення нового зв'язку між його батьком і нащадком, і замінюємо ним вузол Z.

 

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

Принцип "розділяй і пануй": задача розвивається на під задачі і рішення під задачі призводить до отримання вирішення всієї задачі.

Реалізація задачі “ханойська вежа”

void nahoi (int N, int d)

{

if(N == 0)

return;

hanoi(N-1, -d);

move(N, d);

hanoi(N-1, -d);

}

 

Який принцип покладено в основу динамічного програмування? Які є види динамічного програмування? Які задачі вирішуються за допомогою динамічного програмування?

Динамічне програмування - це підхід до розробки алгоритмів, що користуються принципом "розділяй і владарюй" для задач, що перекриваються під задачами.

Види динамічного програмування:

1. Ввисхідне динамічне програмування

2. Низсхідне динамічне програмування

Динамічне програмування використовується для розв'язання багатокрокових задач оптимального управління.

 

Як визначається поняття «алгоритм»? Які його властивості?

 

Алгоритм — послідовність, система, набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій. При написанні комп'ютерних програм алгоритм описує логічну послідовність операцій. Для візуального зображення алгоритмів часто використовують блок-схеми.

Властивості алгоритмів

- Скінченність. Алгоритм має завжди завершуватись після виконання скінченної кількості кроків. Процедуру, яка має решту характеристик алгоритму, без, можливо, скінченності, називають методом обчислень.

- Дискретність. Процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму.

- Визначеність. Кожен крок алгоритму має бути точно визначений. Дії, які необхідно здійснити, повинні бути чітко та недвозначно визначені для кожного можливого випадку.

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

- Вихідні дані. Алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений зв'язок із вхідними даними.

- Ефективність. Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу паперу.

- Масовість. Властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв'язання будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до області застосування алгоритму.