В.Д. Валединский - Программа экзамена по программированию (1115106)
Текст из файла
Программа экзамена по программированиюЛектор — В. Д. ВалединскийIII семестр, 2004-2007 г.1. Билеты к экзамену (2006–2007)1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.Стек, дек, очередь. Непрерывные реализации.Ссылочные реализации списков (одно- и двунаправленного).Бинарное дерево поиска. Реализация; процедуры добавления, удаления, обхода.Произвольное дерево. Реализация; процедуры добавления, удаления, обхода.Сбалансированное бинарное дерево; процедуры добавления, удаления.
Теорема о глубине сбалансированного дерева.Красно-черное дерево; процедуры добавления, удаления. Терема о глубине красно-черного дерева.В-дерево; процедуры добавления, удаления. Трудоемкость операций с В-деревом.Битовая реализация множества.Хеширование. Примеры хеш-функций. Хеш-множество на базе массива списков.Хеш-множество по методу последовательных проб. Оценка среднего количества проб при поиске и добавлении.Совершенная (perfect) хеш-функция; определение, пример построения.Файловая система типа FAT (DOS, Windows).
Атрибуты fat, dir, data. Структура записи в каталоге.Алгоритм доступа к заданной позиции в файле. Особенности и различия версий FAT16, VFAT, FAT32.Файловая система типа EXT (Unix). Разграничение прав доступа к файлам, типы файлов. Областиblock group, superblock, data, INode list, descriptor table. Структура INode, таблица ссылок на блоки. Структура файлов-каталогов. Понятия жесткой и символической ссылок.
Алгоритм доступа к заданнойпозиции в файле.Файловая система типа NTFS (Windows NT, Windows 2000). Файл как набор атрибутов. Файл MFT, назначение, записи о системных метафайлах, записи для пользовательских файлов. Резидентные и нерезидентныеатрибуты. Организация ссылок на кластеры в нерезидентном атрибуте Data.Оценка снизу для трудоемкости сортировки сравнениями.Быстрая сортировка (quicksort); оценка средней трудоемкости.Турнирная (пирамидальная) сортировка (heapsort); оценка трудоемкости.Сортировка подсчетом с «линейной» оценкой трудоемкости.Сортировка с трудоемкостью O(n log2 p) для массива a[i] целых чисел, i = 0, . .
. , n − 1, 0 < a[i] < p.Алгоритм группового кодирования (RLE), байтовый и битовый варианты.Алгоритм Хаффмена (обычный и адаптивный). Теорема об оптимальности кода Хаффмена.Арифметическое кодирование (обычное и адаптивное). Теорема о сжатии данных при арифметическомкодировании.Алгоритм LZW.Формальные грамматики. Нормальная форма Бэкуса – Наура.
Примеры для арифметических к другихвыражений.LR-разборы. Процедура LR(1)-разбора выражений, соответствующих формальной грамматике.Модельный компилятор модельного алгоритмического языка. Разборка входного языка и архитектурымодельного процессора. Реализация модельного компилятора для случая линейных программ.Модельный компилятор. Компиляция условных и безусловных переходов. Реализация вызовов функций.Форма проведения экзамена1.
Письменный ответ на билет с вопросами, относящимися к темам представленной выше программы.2. Практическая задача на реализацию некоторых алгоритмов (или их частей), из лекционного курса.1Структура письменного билета1. Определение понятия, формулировка утверждения.2. Описание интерфейса представления данных на языке C/C++.3-4. Вопросы о сути алгоритмов, доказательств, представлений данных.5-6. Задачи по выполнению или оценке свойств алгоритмов на модельном наборе данных.Пример билета из экзамена 2006–2007Практическая задачаДаны откомпилированные заголовки для заполнения и печати произвольного дерева, в вершинах которогонаходятся буквы. Нужно ввести слово и определить все поддеревья, вершины которых содержат все буквывведенного слова, организовать указатели на корни этих поддеревьев в список и проходом по этому спискураспечатать такие поддеревья.Теоретическая часть1.
Сформулировать теорему о глубине сбалансированного дерева.2. Написать класс вершины красно-черного дерева и пояснить смысл используемых переменных, массивовили функций.3. Описать структуру корневого каталога и других каталогов в файловой системе FAT.4. Пояснить смысл средней трудоемкости в сортировке quicksort и объяснить, как это используется придоказательстве оценки трудоемкости.5. Изначально пустое бинарное сбалансированное дерево последовательно заполняется числами 3, 2, 7, 4, 9,8, 1, 10, 5. Потом удаляются последовательно числа 7 и 9.
Написать деревья, полученные после добавления всехчисел, после удаления 7 и после удаления 9.6. Написать формальную грамматику для прототипов функций.На выполнение письменной части отводится 1 акад. час, на реализацию программы — 2 акад. часа.Последняя компиляция: 3 сентября 2009 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.22. Программа экзамена 2004 года2.1. Структуры представления и хранения данных2.1.1. Непрерывные реализацииСтек, дек, очередь.2.1.2. Ссылочные реализацииСписки. Двунаправленный список. Однонаправленный список.
Кольцевой список.2.1.3. ДеревьяБинарное дерево поиска. Произвольное дерево. Процедуры обходов, поиска, добавления, удаления. Сбалансированное бинарное дерево; процедуры добавления, удаления. Теорема о глубине сбалансированного дерева.Красно-черное дерево; процедуры добавления, удаления. Теорема о глубине красно-черного дерева. В-дерево;процедуры добавления, удаления. Трудоемкость операций с В-деревом.2.1.4. МножестваБитовая реализация множества. Хеширование. Построение хеш-множества на базе массива списков. Хешмножество на базе последовательных проб. Оценка среднего количества проб при поиске и добавлении. Примерыхеш-функций.
Совершенная (perfect) хеш-функция, определения, пример построения.2.1.5. КонтейнерыКонтейнер для элементов фиксированного размера. Контейнер для произвольных элементов без операцииудаления. Идеи реализации управления памятью в общем случае (функции malloc и free).2.1.6. Файловые контейнеры: хранение данных в файловых системахФайловая система FAT (DOS, Windows). Атрибуты файлов.
Области BOOT, FAT, DIR, DATA. Структура записив каталоге. Алгоритмы для основных файловых операций: захват и освобождение кластера, доступ к требуемойпозиции в файле.Файловая система EXT (Unix). Области BOOT, SUPERBLOCK, INODELIST, DATA. Разграничение прав доступа кфайлам, типы файлов. Структура INode, таблица ссылок на блоки. Структура файлов-каталогов. Алгоритмыдля основных файловых операций: захват и освобождение блока, поиск свободного индекса, поиск требуемойпозиции в файле.Файловая система NTFS (Windows NT, Windows 2000). Файл как набор атрибутов. Файл MFT, назначение,записи о системных метафайлах, записи для пользовательских файлов.
Резидентные и нерезидентные атрибуты.Организация ссылок на кластеры в нерезидентном атрибуте Data; случаи разреженного и сжатого файлов.2.2. Некоторые алгоритмы обработки и преобразования данных2.2.1. Эффективные сортировкиОценка снизу для трудоемкости сортировки. Быстрая сортировка (quicksort); оценка средней трудоемкости.Турнирная (пирамидальная) сортировка (heapsort); оценка трудоемкости. Сортировка подсчётом с линейнойоценкой трудоёмкости.
Сортировка массива ai ∈ [1, . . . , p] из n элементов.2.2.2. Сжатие данныхАлгоритм группового кодирования RLE, байтовый и битовый варианты. Алгоритм Хаффмана (обычный иадаптивный). Теорема об оптимальности кода Хаффмана. Арифметическое кодирование (обычное и адаптивное). Теорема о сжатии данных при арифметическом кодировании.
Алгоритм LZW.2.2.3. КомпиляцияФормальные грамматики. Нормальная форма Бэкуса – Наура. Примеры для арифметических и других выражений. Рекурсивная процедура построения дерева разбора. Понятие о грамматических LR разборах. ПроцедураLR(1) разбора выражения, соответствующего формальной грамматике.Модельный компилятор модельного алгоритмического языка. Разработка входного языка и архитектурымодельного процессора.
Реализация модельного компилятора в случае линейных программ. Модельный компилятор. Компиляция условных и безусловных переходов. Компиляция вызовов функций. Передача параметровфункций через стек.32.2.4. Разделы из программы прошлого года, не вошедшие в программу этого годаЕщё немного о компиляторах Отображение результатов синтаксического разбора на другие архитектуры процессоров. Команды с одним, двумя, тремя операндами.Общая архитектура вычислительной системы Общая шина и ее составные части. Тактовый генератор и таймер.Интерфейсы внешних устройств и памяти.
Адресное пространство. Процесс обмена данными с памятью и дисками.Арбитраж шины.Общая архитектура процессора Основные устройства (управления, очередь команд, регистры, интерфейс шиныи пр.) Использование регистров, режимы адресации, разнообразные архитектуры и системы команд. Процесс обработкии выполнения команды в процессоре.Основные принципы работы операционной системы Система прерываний. Обработка сигнала прерыванияпроцессором. Управление памятью. Страничная организация виртуальной памяти. Структура таблицы страниц. Процесспреобразования виртуального адреса в реальный. Стратегии загрузки и замещения страниц.Кеш-память. Прямое отображение. Ассоциативное отображение.Состав билета для экзамена1. Письменный ответ на вопросы, относящиеся к темам представленной выше программы.2.
Практическая задача на реализацию алгоритмов (или их частей), рассматриваемых в лекционном курсе.3. Практическая задача на использование разных структур представления данных (списки, деревья, множества и пр.) при наличии откомпилированных заготовок.На выполнение письменной части отводится 1 академический час, на подготовку программ —2 академических часа.Структура письменного билета1.2.3.4.Определение понятия, формулировка утверждения.Описание интерфейса представления данных на языке C/C++.Вопросы о сути алгоритмов, доказательств представлений данных.Задача по выполнению или оценке свойств алгоритмов на модельном наборе данных.Пример из прошлогодних билетов1.
Сжатие данных. Арифметическое кодирование (обычное и адаптивное).2. Пусть массив int fat[1024] моделирует таблицу FAT32. Реализуйте функцию, которая возвращает дисковый номер k-го кластера файла по значению k и номеру стартового кластера. Функция должна правильнообрабатывать возможные некорректные ситуации.3. Даны откомпилированные функции для заполнения бинарного дерева поиска целыми числами. Реализовать функцию, вычисляющую значение суммы элементов дерева, лежащих на k-м уровне.Последняя компиляция: 3 сентября 2009 г.Обновления документа — на сайтах http://dmvn.mexmat.net,http://dmvn.mexmat.ru.Об опечатках и неточностях пишите на dmvn@mccme.ru.4.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
