Вопросы к зачету (САОД) (1016832)
Текст из файла
Вопросы к зачету (1-ый семестр курса) «САОД».
-
Дано на рисунке произвольное несбалансированное дерево. Описать (изобразить) данное дерево с помощью «левого сына – правого брата» и обойти дерево в прямом порядке.
-
Дано на рисунке произвольное несбалансированное дерево. Описать (изобразить) данное дерево с помощью массива и обойти дерево в обратном порядке.
-
Дано на рисунке произвольное несбалансированное дерево. Описать (изобразить) данное дерево с помощью списка сыновей и обойти дерево во внутреннем порядке.
-
Дано простое дерево (корень – узел 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 и все узлы, расположенные слева от него.
-
Дано дерево арифметического выражения в виде массива курсоров следующей структуры (корень узел 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 | 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 |
Изобразить дерево, построить выражение в постфиксной и префиксной формах.
-
По данному арифметическому выражению в префиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью курсоров на сыновей, занося в структуру как имя, так и метку узла.
-
По данному арифметическому выражению в префиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью массива.
-
По данному арифметическому выражению в постфиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью «левого сына – правого брата».
-
По данному арифметическому выражению в инфиксной форме построить помеченное дерево выражения и сохранить (реализовать, изобразить, описать соответствующую структуру) его с помощью списка сыновей.
-
Дано сообщение «Мама мыла раму». Построить код Хаффмана и определить среднюю длину кода.
-
Дана последовательность из 6 символов p, q, r, s, t, z, которые появляются в сообщениях с вероятностью 0.3; 0.15; 0.09; 0.19; 0.11; 0.16. Построить код Хаффмана и закодировать сообщение «pprzstq ».
-
Дана последовательность из 8 символов p, q, r, s, t, x, y, z, которые появляются в сообщениях с вероятностью 0.3; 0.15; 0.08; 0.1; 0.09; 0.11; 0.16. Построить дерево Хаффмана и сохранить (изобразить) в виде любой (по выбору студента) структуре (в виде массива, списка сыновей, левого сына-правого брата, указателей на сыновей), занося как имя узла (включая фиктивные), так и метку.
-
Дано множество чисел: { 123, 345, 234, 831, 547, 555, 768, 764, 763, 460 } и хеш-функция вида h(x) = (x div 100 + x mod 10) mod 5. Реализовать словарь (изобразив соответствующую структуру хранения данных), используя открытое хеширование. Оценить эффективность данной хеш-функции в среднем O(N) и на самом деле Oфакт(N).
-
Дано множество чисел: { 123, 345, 234, 831, 547, 555, 768, 764, 763, 460 } и хеш-функция вида h(x) = (x div 100 * x mod 10) mod 7. Реализовать словарь (изобразив соответствующую структуру хранения данных), используя закрытое хеширование, коллизии разрешать методом линейного хеширования.
-
Дано множество чисел: { 123, 345, 234, 831, 547, 555, 768, 764, 763, 460 } и хеш-функция вида h(x) = ((x div 100)*10 + x mod 10) mod 7. Реализовать словарь (изобразив соответствующую структуру хранения данных), используя закрытое хеширование, коллизии разрешать методом «случайного» хеширования при с = 3.
-
Дано множество чисел: { 12, 20, 10, 11, 15, 22, 50, 25, 16 } и число сегментов 10 (В = 10). Используя в качестве хеш-функции метод среднего разряда квадрата числа, реализовать словарь (изобразив соответствующую структуру хранения данных), используя открытое хеширование. Оценить эффективность данной хеш-функции в среднем O(N) и на самом деле Oфакт(N).
-
Дано дерево в виде массива курсоров следующей структуры (определите корень):
| Имя узла | 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
-
Дано дерево в виде массива курсоров следующей структуры:
| Имя узла | 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
-
Дано дерево двоичного поиска в виде массива курсоров на родителя следующей структуры:
| Имя узла | 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.
-
Отсортировать заданную последовательность чисел указанным методом, объяснить последовательность шагов алгоритма сортировки и оценить время работы алгоритма
(5, 15, 7, 23, 21, 5, 10, 8, 10, 3, 7, 18, 5, 17, 18, 16, 21, 22)
-
простой вставкой
-
методом Шелла
-
быстрая сортировка Хоару
-
пирамидальная сортировка
-
естественное двухпутевое слияние
-
фиксированное двухпутевое слияние
-
сравнение и подсчет
-
распределяющий подсчет
-
бинарная сортировка (метод делением отрезка пополам)
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
