Питання до захисту :
Перерахуйте подібності та відмінності динамічних структур типу «лінійний список», «стек», «дерево».
Відповідь:лінійний список- це кінцева упорядкована множина елементів. Обов”язово елементи множини у порядку зростання або спадання.
Стек-це лінійний список, у якому не обов’язвкого щоб елементи були у порядку сростання або спадання.
Дерево- це ієрархічна СД що показує порядок входження елементів.
Написати процедуру, яка визначає глибину дерева.
Відповідь:
int getMaxDepth(Tree* tree, int depth) {
if (tree == null)
return depth;
return max(getMaxDepth(tree->left, depth + 1), getMaxDepth(tree->right, depth + 1));
}
Який тип інформації зручно представляти за допомогою бінарних дерев?
Відповідь: зручно представляти ієрархічні структури подібні каталогів і файлів або зберігання інформації генеалогічного древа.
Чому пошук на бінарних деревах не дає виграшу по складності в порівнянні з лінійними структурами?
Відповідь:пошук на бінарних деревах не дає виграшу, бо мае обмеження функції та мае більш складну реалізацію в порівнянні з з лінійними структурами.
Роботу виконав Роботу перевірив
Богословський В. Манєва Р. І.
Задніпровський В.
Лабораторна робота №7 «Реалізація алгоритмів обмінних сортувань»
Завдання: сортувати строку 2-ма способами
Код программи
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>
using namespace std;
void bubble(char *i, int n);
void choosing(char str[], int strlen);
int main(void)
{
char s[256];
cout « "\tVvedite stroku:";
cin » s;
unsigned int select = 0;
cout « "\tChoose sort algorythm:\n\t\t1) Select-algorythm;\n\t\t2) Bubble-algorythm.\n\n\tEnter: ";
cin » select;
while((!cin » select) && (cin.peek() != '\n' && select < 1 && select > 2))
{
cin.clear();
cin.sync();
while (cin.get() != '\n');
cout « "\n\tEnter: ";
}
switch (select)
{
case 1: choosing(s, strlen(s));
std::cout « "Otsortirovannaya stroka: " « s;
break;
case 2: bubble(s, strlen(s));
std::cout « "Otsortirovannaya stroka: " « s;
break;
default:
break;
}
cout « "\nHave a nice day!";
_getch();
}
void bubble(char *i, int n)
{
int a, b;
char t;
for (a = 0; a < n; a++)
for (b = n - 1; b >= a; b--)
{
if (i[b - 1] > i[b])
{
t = i[b - 1];
i[b - 1] = i[b];
i[b] = t;
}
}
}
void choosing(char str[],int strlen) {
int size = strlen;
for (int i = 0; i < size; i++)
{
int minValueIndex = i;
for (int j = i + 1; j < size; j++)
{
if (str[j] < str[minValueIndex])
{
minValueIndex = j;
}
}
swap(str[i], str[minValueIndex]);
}
}
вивід:
Чим зумовлене використання алгоритмів зовнішніх сортувань?
Відповідь: зумовлене тим що зонышнэ сортування проходить у внутрышный пам’яті , а зовнішнє на зовнішніх носіях.
Яким злиттям, простим або природним, ефективніше поєднувати два впорядкованих за загальним ключу файлу? Відповідь обґрунтуйте.
Відповідь:краже поеднувати простим сортуванням слиттям, так як природные злиття орієнтоване на великі массиви , в той час як у сортування простим злиттям фіксується кількість елеменів массиву.
Як визначити, яким алгоритмом зовнішніх сортувань віддати перевагу при вирішенні задачі?
Відповідь: прочитати умову задачі, і подивитися на невідсортований массив і в залежності від массиву вибрати алгоритм сортування.
Роботу виконав Роботу перевірив
Богословський В. Манєва Р. І.
Задніпровський В.