А.А. Белеванцев, С.С. Гайсарян, В.П. Иванников, Л.С. Корухова, В.А. Падарян - Задачи экзаменов по вводному курсу программирования (1113412)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М.В. ЛомоносоваФакультет вычислительной математики и кибернетикиА.А. Белеванцев, С.С. Гайсарян, В.П. Иванников,Л.С. Корухова, В.А. ПадарянЗАДАЧИ ЭКЗАМЕНОВ ПО ВВОДНОМУКУРСУ ПРОГРАММИРОВАНИЯ(учебно-методическое пособие)Москва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. Восстановление алгоритмов и типов данных по бинарномукоду программ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
