Ответы: В.Д. Валединский - Программа экзамена по курсу Работа на ЭВМ и программирование

Распознанный текст из изображения:

Программа экзамена

"Работа на ЭВМ и программирование"

2 курс, лектор В.Д.Валединский 2005 — 2006 учебный год.

1. Стек, дек, очередь. Непрерывные реализации.

2. Ссылочные реализации списков (одно- и двунаправленного).

3. Бинарное дерево поиска. Реализация; процедуры добавления, удаления, обхода.

4. Произвольное дерево. Реализация; процедуры добавления, удаления, обхода.

дерева.

5. Сбалансированное бинарное дерево; процедуры добавления, удаления. Теорема о глубине сбалансированного

6. Красно-черное дерево; процедуры добавления, удаления. Теорема о глубине красно-черного дерева.

7. В-дерево; процедуры добавления, удаления. Трудоемкость операций с В-деревом.

8. Битовая реализация множества.

9. Хеширование. Примеры хеш-фупкций. Хеш-множество на базе массива списков.

10. Хеш-множество по методу последовательных проб. Оценка среднего количества проб при поиске и добавлении.

11. Совершенная (рег(ес!) хеш-функция; определения, пример построения.

12. Файловая система типа РАТ (ПОИ, Ъг!пс(оиз). Атрибуты файлов, Области 1ац йг, Оа!а. Структура записи в каталоге. Алгоритмы для основных файловых операций: захват и освобождение кластера, доступ к требуемой позиции в файле. Особенности и различия версий РАТ16, ЧРАТ, РАТ32.

13. Файловая система типа ЕХТ (Пп!х). Разграничение прав доступа к файлам, типы файлов. Области зпрегЫос1с, !пос(е !!зц ба1а. Структура 1поде, таблица ссылок па блоки. Структура файлов-каталогов. Понятия жесткой и символической ссылок. Алгоритмы для основных файловых операций: захват и освобожценне блока, поиск свободного индекса, поиск требуемой позиции в файле.

14. Файловая система типа ИТРВ (ЪУ!пс1оиз НТ, %!пбоиз 2000). Файл как набор атрибутов. Файл МРТ, назначение, записи о системных метафайлах, записи для пользовательских файлов. Резидентные и нерезидентные лов.

атрибуты. Организация ссылок на кластеры в нерезидентном атрибуте Ва1а случаи разреженного и сжатого фай15. Оценка снизу для трудоемкости сортировки сравнениями.

16. Быстрая сортировка (с!и!с!свог!); оценка средней трудоемкости..

17. Турнирная (пирамидальная) сортировка (Ьеаряог!); оценка трудоемкости.

18. Сортировка подсчетом с "линейной" оценкой трудоемкости.

19. Сортировка с трудоемкостью 0(п !ойт р) для массива а;, 1 = О,...,и — 1, 0 < а.; < р.

20. Алгоритм группового кодирования (В1 Е), байтовый и битовый варианты.

21. Алгоритм Хаффмена (обычный и адаптивный). Теорема об оптимальности кода Хаффмена,

22. Арифметическое кодирование (обычное и адаптивное). Теорема о сжатии данных при арифметическом кодировании.

23. Алгоритм ЬХ ът'.

24. Формальные грамматики. Нормальная форма Бэкуса — Наура. Примеры для арифметических и других выра-

жений.

25. Понятие о ЬН разборах. Процедура ЬВ(1) разбора выралгений, соответствующих формальной грамматике.

26. Модельный компилятор модельного алгоритмического языка. Разработка входного языка и архитектуры модельного процессора. Реализация модельного компилятора для случая линейных программ.

27. Модельный компилятор. Компиляция условных и безусловных переходов. Реализация вызовов функций.

Форма проведения экзамена:

1. Письменный ответ на вопросы, относящиеся к темам представленной выше программы.

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

3. Практическая задача на использование разных структур представления данных (списки, деревья, множества

и пр.) при наличии откомпилированных заготовок.

Структура письменного билета:

1. Определение понятия, формулировка утвержцения.

2. Описание интерфейса представления данных на языке С/С++.

3-4. Вопросы о сути алгоритмов, доказательств, представлений данных.

5-6. Задачи по выполнению или оценке свойств алгоримов на модельном наборе данных.

На выполнение письменной части отводится 1 акад, час, на реализацию программ — 2 акад. часа.

Файл скачан с сайта StudIzba.com

При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник