Тема 10 Масиви. Множини I кортежі. Зберігання множин і масивів. Зберігання розріджених матриць. Операції з масивами, множинами та кортежами

Рівень І

Масив це...

Набір однотипних елементів даних, з кожним з яких пов’язана впорядкована послідовність цілих чисел, які називають індексами.

Операції над массивами.

1) Пошук елемента за заданим індексом

2) Локалізація елемента в масиві

3) Запис елемента в масив

4) Злиття масивів і розбиття масиву на частини

5) Сортування елементів масиву за деякими правилами

6) Копіювання масивів

Множина – це...

Найпростіша структура, в якій між окремими ізольованими елементами немає ніякого внутрішнього зв’язку. Набір являє собою множину, яка не має ніякої структури.

Основні операції над множинами.

1) Обєднання

2) Перетин

3) Різниця

Кортеж це...

Елемент n-кратного добутку множини X: X*X*..*X= Xn (Елементи кортежу можуть повторюватись)

Рівень ІІ

Що запезпечує прямий доступ до елементів масивів?

Індекси.

Що визначає розмірність масиву?

Кількість індексів визначає розмірність масиву

Як зберігати розріджену матрицю?

Одним з основних способів їх зберігання є табличний. Він полягає у запам’ятовуванні ненульових елементів матриці в одномірному масиві та ідентифікації кожного елемента масиву індексами рядка і стовпця.

Способи зображення множини в пам‘яті комп‘ютера.

2 способи:

1) Для кожного елемента множини зберігати в памяті його описання аналогічного до математичного способу задання множини переліком її елементів

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

Рівень ІІІ

За якою формулою обчислюється адреса елемента двовимірного масиву при зберіганні його "по стовпцях"?

(j - 1)*n + (i - 1)

За якою формулою обчислюється адреса елемента двовимірного масиву при зберіганні його "по рядках" ?

(i -1)*m + (j - 1)

Тема 11 Нелінійні структури даних. Класифікація нелінійних структур даних. Таблиці. Зображення таблиць. Основні операції з таблицями.

Рівень І

Таблиця це…

Набір поіменованих обєків або записів довільної природи, з кожним з яких однозначно пов’язане його імя.

Основні операції з таблицями.

1) Включення: дана пара (ключ і запис); включити запис в таблицю так, щоб його потім можна було знайти за ключем.

2) Заміна: дана пара (ключ і запис) знайти запис із заданим ключем і замінити його на задане значення

3) Виключення елемента за заданим ключем

4) Пошук: за заданим ключем знайти відповідний запис

5) Друк елементів таблиці

Основні властивості ключа запису в таблиці

1) Однозначна ідентифікація елемента

2) Відсутність надмірності

Первинний ключ це…

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

Рівень ІІ

В залежності від методу доступу до елементів таблиці поділяються на…

1) Послідовні (для зберігання запису потр. Щонайменше одну ділянку пам. з двома полями: Ключ і занчення)

2) Деревоподібні (Організовані як дерева порівнянь)

3) З обчислювальними адресами

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

Однозначно визначається ключем. (кожному ключу(ідентифікатору) належить певне значення(адреса))

Як визначається адреса запису в хеш-таблиці?

Використовується функція хешування h(k), де к – ключ.

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

1) Однорідна сіткова структура (містить однотипні елементи)

2) Неоднорідна сіткова структура (зображення відношення батько – син є складним (в одного батька може бути декілька синів, а зображення відношення син – батько простим (у сина може бути тільки один батько)))