Вопросы к зачету (САОД)

Вопросы к зачету (1-ый семестр курса) «САОД».

1. Дано на рисунке произвольное несбалансированное дерево. Описать (изобразить) данное дерево с помощью «левого сына – правого брата» и обойти дерево в прямом порядке.

2. Дано на рисунке произвольное несбалансированное дерево. Описать (изобразить) данное дерево с помощью массива и обойти дерево в обратном порядке.

3. Дано на рисунке произвольное несбалансированное дерево. Описать (изобразить) данное дерево с помощью списка сыновей и обойти дерево во внутреннем порядке.

4. Дано простое дерево (корень – узел g) в виде массива курсоров следующей структуры:

Имя узла	a	b	c	d	e	f	g	h	i	j	k	m	n	p
Метка	18	10	6	10	3	20	18	10	13	21	30	30	13	44
Левый сын	k	d	--	i	--	--	a	b	j	--	p	--	f	--
Правый брат	m	n	e	--	--	--	--	--	--	--	c	h	--	--

Изобразить дерево. Определить высоту дерева; глубину узла b и все узлы, расположенные слева от него.

1. Дано дерево арифметического выражения в виде массива курсоров следующей структуры (корень узел 2):

Имя узла	1	2	3	4	5	6	7	8	9	10	11	12	13
Метка	a	*	b	*	+	c	c	b	*	+	a	–	a
Левый сын	0	5	0	3	7	0	0	0	1	6	0	11	0
Правый сын	0	12	0	10	9	0	0	0	8	13	0	4	0

Изобразить дерево, построить выражение в постфиксной и префиксной формах.

1. Дано дерево арифметического выражения в виде массива курсоров на родителя следующей структуры:

Имя узла	1	2	3	4	5	6	7	8	9	10	11	12	13
Метка	a	*	b	*	+	c	c	b	*	+	a	–	a
Родитель	9	0	4	12	2	10	5	9	5	4	12	2	10

Изобразить дерево, построить выражение в постфиксной и префиксной формах.

1. По данному арифметическому выражению в префиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью курсоров на сыновей, занося в структуру как имя, так и метку узла.

2. По данному арифметическому выражению в префиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью массива.

3. По данному арифметическому выражению в постфиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью «левого сына – правого брата».

4. По данному арифметическому выражению в инфиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью списка сыновей.

5. Дано сообщение «Мама мыла раму». Построить код Хаффмана и определить среднюю длину кода.

6. Дана последовательность из 6 символов p, q, r, s, t, z, которые появляются в сообщениях с вероятностью 0.3; 0.15; 0.09; 0.19; 0.11; 0.16. Построить код Хаффмана и закодировать сообщение «pprzstq ».

7. Дана последовательность из 8 символов p, q, r, s, t, x, y, z, которые появляются в сообщениях с вероятностью 0.3; 0.15; 0.08; 0.1; 0.09; 0.11; 0.16. Построить дерево Хаффмана и сохранить (изобразить) в виде любой (по выбору студента) структуре (в виде массива, списка сыновей, левого сына-правого брата, указателей на сыновей), занося как имя узла (включая фиктивные), так и метку.

8. Дано множество чисел: { 123, 345, 234, 831, 547, 555, 768, 764, 763, 460 } и хеш-функция вида h(x) = (x div 100 + x mod 10) mod 5. Реализовать словарь (изобразив соответствующую структуру хранения данных), используя открытое хеширование. Оценить эффективность данной хеш-функции в среднем O(N) и на самом деле Oфакт(N).

9. Дано множество чисел: { 123, 345, 234, 831, 547, 555, 768, 764, 763, 460 } и хеш-функция вида h(x) = (x div 100 * x mod 10) mod 7. Реализовать словарь (изобразив соответствующую структуру хранения данных), используя закрытое хеширование, коллизии разрешать методом линейного хеширования.

10. Дано множество чисел: { 123, 345, 234, 831, 547, 555, 768, 764, 763, 460 } и хеш-функция вида h(x) = ((x div 100)*10 + x mod 10) mod 7. Реализовать словарь (изобразив соответствующую структуру хранения данных), используя закрытое хеширование, коллизии разрешать методом «случайного» хеширования при с = 3.

11. Дано множество чисел: { 12, 20, 10, 11, 15, 22, 50, 25, 16 } и число сегментов 10 (В = 10). Используя в качестве хеш-функции метод среднего разряда квадрата числа, реализовать словарь (изобразив соответствующую структуру хранения данных), используя открытое хеширование. Оценить эффективность данной хеш-функции в среднем O(N) и на самом деле Oфакт(N).

12. Дано дерево в виде массива курсоров следующей структуры (определите корень):

Имя узла	a	b	c	d	e	f	g	h	i	j	k	m	n	p
Метка	18	10	6	10	3	20	18	10	13	21	30	30	13	44
Левый сын	g	a	h	--	b	k	--	d	--	--	--	--	p	--
Правый брат	f	c	--	i	--	--	m	n	--	--	j	--	--	--

Изобразить дерево, удалить один допустимый узел и добавить узел с меткой 15

1. Дано дерево в виде массива курсоров следующей структуры:

Имя узла	a	b	c	d	e	f	g	h	i	j	k	m	n	p
Метка	18	10	6	10	3	20	18	10	13	21	30	30	13	44
Левый сын	g	a	h	--	b	k	--	d	--	--	--	--	p	--
Правый сын	m	f	n	--	c	j	--	i	--	--	--	--	--	--

Изобразить дерево, удалить узел с именем «f» и добавить узел с меткой 15

1. Дано дерево двоичного поиска в виде массива курсоров на родителя следующей структуры:

Имя узла

a

b

c

d

e

F

g

h

i

j

k

m

n

p

Метка

4

13

10

7

38

5

3

8

15

22

20

23

6

21

Родитель

g

--

n

c

m

N

f

d

b

p

m

i

b

k

Добавить узел с меткой 16. Удалить узел с меткой 10, с меткой 15, с меткой 20.

1. Отсортировать заданную последовательность чисел указанным методом, объяснить последовательность шагов алгоритма сортировки и оценить время работы алгоритма

(5, 15, 7, 23, 21, 5, 10, 8, 10, 3, 7, 18, 5, 17, 18, 16, 21, 22)

1. простой вставкой

2. методом Шелла

3. быстрая сортировка Хоару

4. пирамидальная сортировка

5. естественное двухпутевое слияние

6. фиксированное двухпутевое слияние

7. сравнение и подсчет

8. распределяющий подсчет

9. бинарная сортировка (метод делением отрезка пополам)