МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

(ДГТУ)
Факультет «Информатика и вычислительная техника»

наименование факультета

Кафедра «Вычислительные системы и информационная безопасность»

наименование кафедры

КОНТРОЛЬНАЯ РАБОТА
Дисциплина (модуль) «Алгоритмы и структуры данных»

наименование учебной дисциплины (модуля)

Направление подготовки/специальность 09.03.02 «Информационные системы и технологии»

код наименование направления подготовки/специальности

Направленность (профиль) «Информационные системы и технологии»

Номер зачетной книжки 2057688 Номер варианта 9 Группа ВЗИ21

Обучающийся _______________________ К.Ю. Симавонян

подпись, дата И.О. Фамилия

Контрольную работу проверил _____________________ к.т.н., доцент А.Р. Айдинян

подпись, дата должность, И.О. Фамилия

Ростов-на-Дону

2022

Вариант 9

Задание 1. Сортировка с помощью двоичного дерева

Дана исходная последовательность: 49, 10, 47, 26, 33, 5, 4, 50, 59, 2, 39, 57, 8, 23, 30, 54, 10, 49, 39, 14, 3, 54, 29, 40, 4.

1. 
   Построить дерево сортировки на основе исходной последовательности.
   
2. 
   Определить параметры полученного дерева: глубину дерева и является ли оно сбалансированным.
   
3. 
   Сборка отсортированного массива путем обхода узлов в необходимой последовательности.
   

Решение:

1 этап.

49	10	47	26	33	5	4	50	59	2	39	57	8
1	2	3	4	5	6	7	8	9	10	11	12	13
23	30	54	10	49	39	14	3	54	29	40	4
14	15	16	17	18	19	20	21	22	23	24	25

---

Дерево не является сбалансированным. Глубина равна 7.

2 этап.

1. 
   Левая, корень, правая часть = (левая) 49 (правая)
   
2. 
   (левая) 10 (правая) 49 (левая-нет) 50 (правая)
   
3. 
   раскроем правую ветвь 50 (правая); 50 (левая) 57 (правая-нет); 50, 54, 54, 57. Таким образом получили частично отсортированную последовательность: (левая), 49, 50, 54, 54, 57.
   
4. 
   Осталось раскрыть левую ветвь, от вершины 49, считая ее отдельным деревом с вершиной 10. (левая) 10 (правая)
   
5. 
   Раскроем правую часть от вершины 10, считая ее отдельным деревом с вершиной 47; (левая) 47 (правая=49); (левая) 26 (правая), 47, 49; 14,23,26, (правая), 47, 49;
   
6. 
   Раскроем правую ветвь от вершины 26, считая ее отдельным деревом с вершиной 33: (левая), 33, (правая) 29, 30, 33, (левая=39), 39, (правая=40); 29,30,33, 39,39,40;
   
7. 
   Получили отсортированную правую часть от вершины 10: 14,23,26, 29,30,33, 39,39,40,47,49.
   
8. 
   Отсортируем левую ветвь от вершины 10, считая ее отдельным деревом с вершиной 4: (левая) 4 (правая); (левая) 4 (правая - нет),4,5,8,10; (левая-нет),2, (правая),4,4,5,8,10; 2,3,4,4,4,5,8,10;
   
9. 
   Отсортированная правая ветвь от вершины 49: 4,4,5,8,10; 2,3,4,4,4,5,8,10, 14,23,26, 29,30,33, 39,39,40,47,49.
   
10. 
    Полностью отсортированный массив: 2,3,4,4,4,5,8,10,14,23,26,29,30,33, 39,39,40,47,49, 50, 54, 54, 57.
    

Задание 2. Построение Хеш-таблицы

Построить 6 хеш-таблиц для слов: health, plaster, bruise, bump, cough, cut, diarrhea, fever, headache, medicine, scratch, shot, sick, sneeze, sunburn, thermometer, tooth

Размер первых трех хеш-таблицы принять равным (количество заданных слов + 4).

Размер последних трех хеш-таблицы принять равным (количество заданных слов)

Решение:

Количество слов 17. Первые три хэш-таблицы будут иметь размер 21.

Для вычисления хэш-функций используем MS Excel.



2. Вычислим значения хеш-функций для всех слов.

S1=ОСТАТ(A13;21)+1

S2=ОСТАТ(СУММ(A13:A23);21)+1

S3=ОСТАТ(1*A13+2*A14+3*A15+4*A16+5*A17+6*A18+7*A19+8*A20+9*A21+10*A22+11*A23;21)+1

Формулы приведены для первого слова.

№ пп	Слово	S1	S2	S3
	health	9	13	8
	plaster	17	8	19
	bruise	3	12	11
	bump	3	11	1
	cough	4	13	18
	cut	4	3	1
	diarrhea	5	2	6
	fever	7	15	4
	headache	9	15	10
	medicine	14	21	6
	scratch	20	10	6
	shot	20	21	14
	sick	20	1	7
	sneeze	20	12	12
	sunburn	20	5	3
	thermometer	21	15	19
	tooth	21	16	6

---

S1			S2				S3
1	shot	+2	1	sick				1	bump
2	tooth	+2	2	shot		+2		2	cut		+1
3	bruise		3	cut				3	sunburn
4	cough		4	diarrhea		+2		4	fever
5	diarrhea		5	sunburn				5
6	bump	+3	6					6	diarrhea
7	fever		7					7	sick
8	cut	+4	8	plaster				8	health
9	health		9					9	medicine		+3
10	headache	+1	10	scratch				10	headache
11	sick	+12	11	bump				11	bruise
12	sneeze	+13	12	bruise				12	sneeze
13	sunburn	+14	13	health				13	scratch		+7
14	medicine		14	cough		+1		14	shot
15			15	fever				15	tooth		+9
16			16	tooth				16
17	plaster		17	headache		+2		17
18			18	sneeze		+6		18	cough
19			19	thermometer		+4		19	plaster
20	scratch		20					20	thermometer		+1
21	thermometer		21	medicine				21

---

Таким образом, хеш-таблица, построенная по хеш-функции S1 требует при поиске по одному разу каждого слова 51 лишних операций, хеш-таблица, построенная по хеш-функции S2, требует при поиске по одному разу каждого слова 17 лишних операций, а хеш-таблица, построенная по хеш-функции S3 требует 21 лишнюю операцию. Таким образом, наиболее предпочтительная хеш-функция S2.

Аналогично вычисляем хэш-функции для таблиц размера 17.

S1=ОСТАТ(A13;17)+1

S2=ОСТАТ(СУММ(A13:A17);21)+1

S3=ОСТАТ(1*A13+2*A14+3*A15+4*A16+5*A17+6*A18+7*A19+8*A20+9*A21+10*A22+11*A23;17)+1

№ пп	Слово	S1	S2	S3
	health	9	4	14
	plaster	17	7	2
	bruise	3	7	8
	bump	3	2	12
	cough	4	4	12
	cut	4	11	4
	diarrhea	5	14	7
	fever	7	6	6
	headache	9	2	4
	medicine	14	12	7
	scratch	3	5	3
	shot	3	12	8
	sick	3	9	6
	sneeze	3	7	5
	sunburn	3	8	15
	thermometer	4	5	5
	tooth	4	11	12

---

S1			S2			S3
1	thermometer	+14	1	tooth	7	1	tooth	6
2	tooth	+15	2	bump		2	plaster
3	bruise		3	headache	1	3	scratch
4	cough		4	health		4	cut
5	diarrhea		5	scratch		5	sneeze
6	bump	+3	6	fever		6	fever
7	fever		7	plaster		7	diarrhea
8	cut	+4	8	sunburn		8	bruise
9	health		9	sick		9	headache	5
10	headache	+1	10	bruise	3	10	medicine	3
11	scratch	+8	11	cut		11	shot	3
12	shot	+9	12	medicine		12	bump
13	sick	+10	13	cough	9	13	cough	1
14	medicine		14	diarrhea		14	health
15	sneeze	+12	15	shot	3	15	sunburn
16	sunburn	+13	16	sneeze	9	16	sick	10
17	plaster		17	thermometer	12	17	thermometer	12

---

Смотрите также файлы

• Практическое задание Каковы, на Ваш взгляд, последствия внедрения профстандартов.docx

• Миссионеры и людоеды.pdf

• биология как наука.docx

• Нгммммщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщщ.docx

• Краткое описание выступления Жукова Кирилла Валерьевича, обучающегося 9 Г класса на защите темы индивидуального итогового проекта Тема проекта.doc