Понятия «дерева» и «ордерева». Деревья и списки. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Понятия «дерева» и «ордерева». Деревья и списки.



I. Необходимые определения и формулировки теорем.

1. Что называется деревом?

2. Что называется ордеревом?

3. Как связаны между собой дерево и ордерево?

4. Что называется эксцентриситетом вершины?

5. Что такое «центр» дерева?

6. Что такое «радиус» дерева?

7. Что такое бинарное ордерево?

8. Что такое дерево поиска?

9. Что такое идеально сбалансированное ордерево?

10. Что такое сбалансированное ордерево?

11. Что называется атомом?

12. Что называется списком?

13. Что такое глубина списка?

14. Как связаны деревья со списками?

II. Задачи для усвоения материала.

1. Нарисовать все деревья и ордеревья с 5-ю вершинами.

 

 

2.

 

 

Деревья и списки

3. Нарисовать дерево, соответствующее списку

а) ((a,b),(c,(d,e)),f,((g,h),i));

б) (a,(b,(c,d)),(e,(f,(g,h)),(i,j))).

4. Написать список висячих вершин данного ордерева.

 
 

 


c

a b d e f

5. Найти глубину списка (a,(b,(c,(d,k))),(e,(f,((g,m),h)),(i,(j,n)))).

Раздел 12.

«Префиксный код. Код Прюфера

Обход бинарного ордерева.»

I. Необходимые определения и формулировки теорем.

1. Как строится префиксный код бинарного ордерева?

2. Как строится код Прюфера?

3. Какие три способа обхода бинарного ордерева Вы знаете?

II. Задачи для усвоения материала.

1. Восстановить ордерево по префиксному коду а) {00,010,011,101,11}; б) {001, 101, 1101, 111}.

2. Написать код Прюфера для данного дерева.

а) 1 2 6 9   3 4 5 7 8 10 б) 3 4 5 7 8   6 2 9 10 1

3. Восстановить дерево по коду Прюфера

а) {2,2,6,6,3}; б) {3,6,1,4,1,5,1}.

4. Обойти тремя способами данное бинарное ордерево:

а)a
 
 


b f

c d g i


E h j k

 

б)a b c d e f g h i j k m  

Итоговое повторение темы 3. Контрольная работа № 3.

I. Основные вопросы.

1. Что такое матрица смежности орграфа и каким свойством обладает матрица смежности неориентированного графа?

2. Что называется деревом, ордеревом и как они связаны между собой?

3. Что такое бинарное ордерево?

4. Как строится префиксный код бинарного ордерева?

5. Как строится код Харари?

6. Как строится код Прюфера?

7. Какие три способа обхода бинарного ордерева Вы знаете

(с примером)?

8. Что называется атомом, списком и как связаны деревья со списками?

II. Контрольная работа.

Вариант 0

1. Пронумеровав произвольным образом вершины и дуги, найти матрицы смежности и инцидентности графа.

Я бы пронумеровал САМ вершины и дуги, не так уж это долго (даже для нескольких вариантов).

 
 

 


2. Определить, является ли число 357 кодом Харари.

3. Построить префиксный код бинарного ордерева

4. Построить код Прюфера для дерева

5. Восстановить дерево по коду Прюфера {3,1,2,4,1,3}

6. Обойти бинарное ордерево тремя способами.

7. Вопрос по теории 3-го раздела.

8. Вопрос по теории 3-го раздела.

 


ЛИТЕРАТУРА

Основная литература

1. Кузнецов, О.П. Дискретная математика для инженера./ О.П. Кузнецов. - Изд. 3-е, перераб. и доп. - СПб. Лань, 2004. - 394 с.

2. Спирина, М.С. Дискретная математика: учебник./ М.С. Спирина, П.А. Спирин. - М.: ACADEMIA, 2004. - 367 с.

3. Пугач, Л.И. Высшая математика. Задачи по дискретной математике, математической логике и теории алгоритмов: метод. указания к практическим занятиям для студентов 1 курса специальностей 220400 "Программное обеспечение", "22300 " Системы автоматизированного проектирования" и 075300 "Организация и технология защиты информации"./ Л.И. Пугач; БГТУ. - Брянск: Изд-во БГТУ, 2005. - 16 с.

4. Асеев, Г.Г. Дискретная математика: учеб. пособие./ Г.Г. Асеев, О.М. Абрамов, Д.Э. Ситников. - Ростов н/Д; Харьков: Феникс: Торсинг, 2003. - 141 с.

Дополнительная литература

1. Яблонский, С.В. Введение в дискретную математику: Учеб. пособие для вузов./ С.В. Яблонский. - 3-е изд., стер. - М.: Высш. шк., 2001. - 384с.

2. Белоусов, А.И. Дискретная математика: Учеб. Вып. 19./ А.И. Белоусов, С.Б. Ткачев; под ред. В.С. Зарубина, А.П. Крищенко. - М.: МГТУ им Н.Э. Баумана, 2001. - 743с.

3. Горбатов, В.А Дискретная математика: Учебник для студентов втузов./ В.А. Горбатов, А.В. Горбатов, М.В. Горбатова - М.: ООО «Издательство АСТ», ООО «Издательство Астрель», 2003. - 447 с.

4. Элементы дискретной математики: учебное пособие для вузов.–/К.Г. Гараев [и др].– Казань: КазГУ, 2000.

5. Гаврилов, Г.П. Задачи и упражнения по курсу дискретной математики. / Г.П. Гаврилов, А.А.Сапоженко А.А. М., Наука, 1992.

6. Дискретная математика для программиста. – С-Пб., 2000.

7. Берж, К. Основы теории графов /К.Берж – М.:Мир, 1980.

8. Ершов, А.П. Дискретная математика и ее применение в программировании. / А.П. Ершов и др. – Новосибирск, 1992.



Поделиться:


Читайте также:




Последнее изменение этой страницы: 2017-01-19; просмотров: 423; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.193.80.126 (0.027 с.)