Вопросы к экзамену (2011) (1114546)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Вопросы к экзамену 2011/2012 учебного года

Экзаменационные вопросы по курсу лекций «Алгоритмы и алгоритмические языки» для студентов 1 потока, 1 курса факультета ВМК МГУ. 2011/2012 уч.год, 1 семестр.

I. Формальные системы описания алгоритмов.

1. Задачи обработки информации и алгоритмы. Неформальное (интуитивное) определение алгоритма.

2. Формализация алгоритма. Машина Тьюринга.

3. Способы представления машин Тьюринга. Нормальные вычисления.

4. Диаграммы Тьюринга. Построение диаграмм Тьюринга. Построение таблиц по диаграммам.

5. Понятие универсальной машины Тьюринга. Построение универсальной машины Тьюринга.

6. Проблема останова и алгоритмическая неразрешимость.

7. Алгоритмическая неразрешимость проблемы самоприменимости.

8. Тезис Тьюринга – Черча.

9. Нормальные алгоритмы Маркова. Эквивалентность формальных систем описания алгоритмов.

II. Язык программирования Си.

1. Язык программирования Си. Описание Си-машины.

2. Структура Си-программы.

3. Типы данных. Переменные, константы. Классы памяти. Области видимости и существования переменных.

4. Арифметические типы данных. Арифметические операции над целочисленными данными.

5. Приведение типов. Правила неявного преобразования типов («обычные арифметические преобразования»).

6. Старшинство операций.

7. Операторы языка Си: условные операторы, операторы цикла, операторы перехода, составной оператор (блок).

8. Символьный тип данных (char).

9. Массивы и строки.

10. Указатели. Адресная арифметика. Преобразование типа указателя.

11. Указатели и массивы. Массивы указателей. Многомерные массивы.

12. Функции. Объявление функции. Формальные параметры. Возвращаемое значение. Побочный эффект функции. Функции типа void.

13. Определение функции. Библиотечные функции. Вызов функции. Фактические параметры и способ их передачи (по значению). Указатели и параметры функции. Передача массива в функцию.Квалификатор restrict.

14. Рекурсивные функции. Квалификатор inline.

15. Операция sizeof.

16. Арифметические операции над данными с плавающей точкой.

17. Отношения и логические операции. Поразрядные операции. Реализация абстрактного типа данных «множество».

18. Структуры, перечисления, объединения. Указатели на структуры. Битовые поля. Ключевое слово typedef.

19. Динамическое распределение памяти.

20. Указатель на функцию.

21. Сборка Си-программы: препроцессирование, компиляция, компоновка. Директивы препроцессора. Директива #include и заголовочные файлы. Условная компиляция.

22. Стандартные библиотеки языка Си.

III. Алгоритмы и структуры данных.

1. Динамические структуры данных. Список (однонаправленный и двунаправленный). Стек и его реализация на массиве и на списке. Очередь.

2. Применение стека для преобразования выражений в польскую запись.

3. Топологическая сортировка узлов ациклического ориентированного графа: постановка задачи, алгоритм Вирта.

4. Сортировка. Основные алгоритмы сортировки. Оценка сложности алгоритмов сортировки.

5. Быстрая сортировка Хоара.

6. Двоичное дерево. Представление двоичного дерева в памяти компьютера.

7. Способы обхода двоичного дерева и их рекурсивная и нерекурсивная реализации.

8. Прошитое двоичное дерево. Прошитое двоичное дерево с заголовком.

9. Двоичные деревья поиска. Реализация словарных операций: search (найти), insert (вставить) и delete (удалить). Реализация операций min (минимум), max(максимум), pred (предыдущий) и succ (следующий).

10. Построение двоичного дерева поиска.

11. Структура данных «пирамида». Пирамидальная сортировка.

12. Сбалансированные двоичные деревья. Деревья Фибоначчи. Число узлов в дереве Фибоначчи высоты h.

13. АВЛ-деревья. Базовые операции над АВЛ-деревьями (удалить дерево, поиск по ключу, минимальный ключ, максимальный ключ) и их реализация.

14. Балансирование АВЛ-деревьев. Реализация операции вставки узла в АВЛ-дерево. Построение АВЛ-дерева.

15. Красно-черные деревья. Вставка узла в красно-черное дерево.

16. Словарные операции и их реализация с помощью хеш-функций. Методы построения хеш-функций.

17. Хеширование с цепочками. Хеширование с открытой адресацией. Двойное хеширование.

18. Оценка среднего времени успешного поиска в хеш-таблице с коэффициентом заполнения α.

19. Цифровой поиск.

20. Поиск подстрок по образцу. Алгоритм Кнута – Морриса – Пратта.

21. Алгоритмы перебора множеств. Рекурсивный алгоритм генерации перестановок. Алгоритм Нарайаны.

https://studizba.com

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов вопросов/заданий