А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиА.А. Белеванцев, С.С. Гайсарян, В.П. Иванников,Л.С. Корухова, В.А. ПадарянЗАДАЧИ ЭКЗАМЕНОВ ПО ВВОДНОМУКУРСУ ПРОГРАММИРОВАНИЯ(учебно-методическое пособие)Москва2012УДК 004.02+004.043(075.8)ББК 32.973-018я73З-15Печатается по решению Редакционно-издательского Советафакультета вычислительной математики и кибернетикиМГУ имени М.В.

ЛомоносоваРецензенты:C.Ю. Соловьев, профессорА.К. Терехин, доцентА.А. Белеванцев,С.С. Гайсарян,В.П. Иванников,Л.С. Корухова, В.А. Падарян. Задачи экзаменов по вводному курсупрограммирования (учебно-методическое пособие). — М. Издательскийотдел факультета вычислительной математики и кибернетики МГУ(лицензия ИД № 05899 от 24.09.2001), 2012. – 68 с.ISBN 978-5-89407-497-9ISBN 978-5-317-04300-1Пособие содержит варианты коллоквиумов и письменныхэкзаменов основных лекционных курсов по программированию,читаемых для студентов 1 потока 1 курса факультета ВМК МГУ.Варианты письменного экзамена включают задачи различногоуровня сложности. В пособии даны ответы, комментарии иуказания к решению, а также продемонстрированы авторскиерешения некоторых задач.Методическоепособиепредназначенодляпреподавателей, ведущих практические занятия в поддержкулекционных курсов по программированию для студентов 1 курса,а также рекомендуется студентам при подготовке к экзамену.ISBN 978-5-89407-497-9ISBN 978-5-317-04300-1© Факультет ВМК МГУ имени М.В.

Ломоносова. 2012© А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников,Л.С. Корухова, В.А. Падарян, 20122ВведениеПособие содержит варианты коллоквиумов и письменныхэкзаменов основных лекционных курсов по программированию(“Алгоритмы и алгоритмические языки” и “Архитектура ЭВМ иязык ассемблера”), читаемых для студентов 1 потока 1 курсафакультета ВМК МГУ. Варианты письменного экзаменавключают задачи различного уровня сложности: наряду спростейшими задачами и вопросами по конкретной теме, имеютсязадачи, предполагающие знание материала нескольких тем иумение владеть этим материалом. Задачи коллоквиумов, какправило, преследуют цель – проверить усвоение студентомконкретных тем лекционного курса.

При проведении письменногоэкзамена авторы составляли задачи и варианты, стараясьвключить в них все основные темы курса.В первом разделе пособия приведены экзаменационныевопросы по курсам и рекомендуемая литература. В третьемразделе для приведенных типовых задач экзаменов иколлоквиумов даны ответы, комментарии и указания к решению,а также продемонстрированы авторские решения некоторыхзадач,31.ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ ПОКУРСУ1.1.

КУРС ЛЕКЦИЙ "АЛГОРИТМЫ И АЛГОРИТМИЧЕСКИЕЯЗЫКИ” (2011/2012 учебный год, осенний семестр)I. Формальные системы описания алгоритмов.1.2.3.4.5.6.7.8.9.Задачи обработки информации и алгоритмы. Неформальное(интуитивное) определение алгоритма.Формализация алгоритма. Машина Тьюринга.Способы представления машин Тьюринга. Нормальныевычисления.Диаграммы Тьюринга. Построение диаграмм Тьюринга.Построение таблиц по диаграммам.Понятие универсальной машины Тьюринга. Построениеуниверсальной машины Тьюринга.Проблема останова и алгоритмическая неразрешимость.Алгоритмическая неразрешимость проблемысамоприменимости.Тезис Тьюринга – Чёрча.Нормальные алгоритмы Маркова.

Эквивалентностьформальных систем описания алгоритмов.II. Язык программирования Си.1. Язык программирования Си. Описание Си-машины.2. Структура Си-программы.3. Типы данных. Переменные, константы. Классы памяти.Области видимости и существования переменных.4. Арифметические типы данных.

Арифметические операциинад целочисленными данными.45. Приведение типов. Правила неявного преобразования типов(«обычные арифметические преобразования»).6. Старшинство операций.7. Операторы языка Си: условные операторы, операторы цикла,операторы перехода, составной оператор (блок).8. Символьный тип данных (char).9. Массивы и строки.10. Указатели. Адресная арифметика. Преобразование типауказателя.11. Указатели и массивы. Массивы указателей.

Многомерныемассивы.12. Функции. Объявление функции. Формальные параметры.Возвращаемое значение. Побочный эффект функции.Функции типа void.13. Определение функции. Библиотечные функции. Вызовфункции. Фактические параметры и способ их передачи (позначению). Указатели и параметры функции. Передачамассива в функцию. Квалификатор restrict.14.

Рекурсивные функции. Квалификатор inline.15. Операция sizeof.16. Арифметические операции над данными с плавающейточкой.17. Отношения и логические операции. Поразрядные операции.Реализация абстрактного типа данных «множество».18. Структуры, перечисления, объединения. Указатели наструктуры. Битовые поля.19. Динамическое распределение памяти.20. Указатель на функцию.21. Сборка Си-программы: препроцессирование, компиляция,компоновка.

Директивы препроцессора. Директива #includeи заголовочные файлы. Условная компиляция.22. Стандартные библиотеки языка Си.5III. Алгоритмы и структуры данных.1.2.3.4.5.6.7.8.9.10.11.12.13.14.Динамические структуры данных. Список(однонаправленный и двунаправленный). Стек и егореализация на массиве и на списке. Очередь.Применение стека для преобразования выражений впольскую запись.Топологическая сортировка узлов ациклическогоориентированного графа: постановка задачи, алгоритмВирта.Сортировка. Основные алгоритмы сортировки.

Оценкасложности алгоритмов сортировки.Быстрая сортировка Хоара.Двоичное дерево. Представление двоичного дерева впамяти компьютера.Способы обхода двоичного дерева и их рекурсивная инерекурсивная реализации.Прошитое двоичное дерево. Прошитое двоичное дерево сзаголовком.Двоичные деревья поиска.

Реализация операций поискаэлемента (search); вставки элемента (insert ) и удаленияэлемента (delete). Реализация операций min (минимум), max(максимум), pred (предыдущий) и succ (следующий).Построение двоичного дерева поиска.Структура данных «пирамида». Пирамидальнаясортировка.Сбалансированные двоичные деревья.

Деревья Фибоначчи.Число узлов в дереве Фибоначчи высоты h.АВЛ-деревья. Базовые операции над АВЛ-деревьями и ихреализация.Балансирование АВЛ-деревьев. Реализация операциивставки узла в АВЛ-дерево. Построение АВЛ-дерева.615.16.17.18.19.20.21.Красно-черные деревья. Вставка узла в красно-черноедерево.Словарные операции и их реализация с помощью хешфункций. Методы построения хеш-функций.Хеширование с цепочками. Хеширование с открытойадресацией. Двойное хеширование.Оценка среднего времени успешного поиска в хеш-таблицес заданным коэффициентом заполнения.Цифровой поиск.Поиск подстрок по образцу. Алгоритм Кнута – Морриса –Пратта.Алгоритмы перебора множеств.

Рекурсивный алгоритмгенерации перестановок. Алгоритм Нарайаны.IV. Рекомендованная литература1. Л.С. Корухова, М.Р. Шура-Бура. Введение валгоритмы. (учебное пособие для студентов 1 курса) - М.,Издательский отдел факультета ВМК МГУ, 2009.2. В.П. Иванников, Л.С.

Корухова, В.Н. Пильщиков. Курс “«Алгоритмы и алгоритмические языки» Варианты письменногоэкзамена. М., Издательский отдел факультета ВМК МГУ,2007.3. М. Минский. Вычисления и автоматы. - М., “Мир”, 1971.Г.4. Эббинхауз, К. Якобс, Ф. Манн, Г. Хермес. МашиныТьюринга и рекурсивные функции.

М., “Мир”, 1972.5 Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы:построение и анализ. – 2-е изд. М., “Вильямс”, 2011...6. Б. Керниган, Д. Ритчи. Язык программирования Си. 2-е изд.М., “Вильямс”, 20107. Г. Шилдт. Полный справочник по Си. 4-е изд,М., “Вильямс”, 2010.8. Стандарт языка Си С99 + TC{1,2,3}. Доступен с сайта7http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf8. Н.

Вирт. Алгоритмы + структуры данных = программы. - М.,“Мир”, 1985.9. Д. Кнут. Искусство программирования для ЭВМ.Т.1. Основные алгоритмы.Т.2. Сортировка и поиск.- М., изд-во Вильямс, 2010, 2011, 2012.10. А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных иалгоритмы. - М., изд-во Вильямс, 2000.11. А.А. Белеванцев, С.С. Гайсарян, Л.С. Корухова,Е.А. Кузьменкова, В.С. Махнычев.

Семинары по курсу«Алгоритмы и алгоритмические языки» (учебно-методическоепособие для студентов 1 курса) - М., Издательский отделфакультета ВМК МГУ, 77 с., 2012.1.2. КУРС ЛЕКЦИЙ "АРХИТЕКТУРА ЭВМ И ЯЗЫКАССЕМБЛЕРА” (2011/2012 учебный год, весеннийсеместр)I. Базовые понятия архитектуры ЭВМ1. Архитектура фон Неймана. Основные компонентыкомпьютера. Машинная команда, типы операндов,адресность ЭВМ, такт работы. Упрощенная схемавыполнения инструкции.2.

Упрощенная схема компиляции Си-программы вокружении: компилятор gcc, операционная система Linux,архитектура IA32.3. Архитектура IA32: основные регистры, форматы команд.Представление машинной команды, ассемблернаяинструкция.4. Организация ассемблерной программы, секции кода иданных. Вычисление арифметических выражений:8пересылка данных, арифметические операции, регистрфлагов.5.

Передача управления, условные и безусловные переходы.6. Проблемы организации вызова функций. Аппаратнаяподдержка стека. Отображение вызова функции языка Си вязык ассемблера.7. Восстановление алгоритмов и типов данных по бинарномукоду программ.