Нашли в сети список экзаменационных вопросов по программированию и решили, что возможно кому то пригодится. Вопросы к экзамену по программированию в НГУ.
Вопросы к экзамену по программированию в НГУ (Новосибирский государственный университет)
Вопросы по курсу Программирование на языке высокого уровня (ЯВУ)
- Системы счисления (с.с.)
1.1. Запись чисел цифрами и числовые значения. С.с. как система правил записи чисел.
1.2. Правила записи значений целых и действительных чисел в позиционных с.с. по основанию b (b-с.с.).
1.3. Рекурентные функции перевода «число-запись» и «запись-число». Вычисления по схеме Горнера с минимальным числом операций.
1.4. Алгоритмы перевода целых чисел из одной b-с.с. в другую:
— из произвольной b-c.с. в 10-с.с.;
— из 10-с.с. в произвольную b-с.с.;
— из произвольной b1-с.с в произвольную b2-с.с.;
— между кратными с.с.
1.4.1. Модификации этих алгоритмов для перевода действительных чисел.
1.4.2. Кратные с.с. Приемы использования кратных с.с. для ускорения перевода чисел между произвольными b-с.с.
1.5. Операции сложения и умножения для произвольных b-с.с.
1.6. Достаточное условие бесконечности представления рациональной дроби в произвольной b-с.с.
1.7. Понятие символьных вычислений. Формальное определение вычислений как преобразование цепочек символов по заданным правилам (на примере определения арифметических операций таблицами значений).
-
Модели машинной арифметики с конечной разрядностью
2.1. Модель машинной памяти как однородного линейно-адресуемого массива ячеек фиксированной разрядности.
2.2. Понятие разрядной сетки и характеризующие параметры: разрядность и формат.
2.3. Модель целых чисел конечной разрядности. Понятие переноса и переполнения.
2.4. Беззнаковые целые числа конечной разрядности. Формулы для min и max. Дополнительный код. Знаковый разряд. Формулы для мин и макс целого числа со знаком.
2.5. Правила представления чисел и арифметика в дополнительном коде.
2.6. Единообразие правил знаковой и беззнаковой арифметики. Примеры.
2.6. Модель вещественной арифметики с фиксированной точкой (равномерная точность представления). Формулы для max и точности.
2.7. Модель вещественной арифметики с плавающей точкой.
2.7.1. Экспоненциальное (нормализованное, с плавающей точкой) представление вещественного числа. Мантисса и порядок, их вид. Нормализация. Особенности арифметики с плавающей точкой:
— денормализация аргументов при сложении;
— нормализация результата;
— расширение разрядной сетки при денормализации и округлении.
Разрядность мантиссы и порядка. Формулы для max.
2.7.2. Источники погрешности при арифметике с плавающей точкой. Приведите примеры
-
Вопросы по C
3.1. Базовые типы языка С. Представление значений базовых типов в памяти. Диапазоны значений базовых типов.
3.2. Базовые типы языка С. Операции над значениями базовых типов. Перенос и переполнение. Преобразования между базовыми типами языка С.
3.3. Массивы. Многомерные массивы. Индексация многомерных массивов. Распределение памяти в многомерных массивах. Связь понятия указателя и массива. Инициализаторы
массивов.
3.4. Понятие времени жизни и области видимости переменных. Глобальные и локальные переменные. Модификаторы области видимости и времени жизни.
3.5. Арифметические и логические выражения. Разбор порядка вычисления выражения, приоритеты операций.
3.6. Понятие типа/преобразование типов и структуры. Синтаксис описания структур. Обращение к полям структур для объектов и к полям по указателю на объект типа структура. Инициализатор структур.
3.7. Функции. Описание функций. Возвращаемые значения. Передаваемые параметры. Порядок передачи параметров через стек.
3.8. Функции с переменным числом параметров. Получение переменных передаваемых после фиксированных параметров.
3.9. Функции printf, sprintf, fprintf, scanf, sscanf, fscanf. Форматная строка (целые знаковые и беззнаковые в десятичном и шестнадцатеричном виде, числа с плавающей запятой, буквы, строки). Возвращаемое значение.
3.10. Строки в языке С. Понятие длины строки. Инициализаторы строк. Функции работы со строками: определение длины строки, копирование строк, слияние строк.
3.11. Основные стандартные функции языка Си для работы с файлами. Текстовые и бинарные файлы.
3.12. Понятие указателя в С. Операции над указателями.
3.13. Препроцессор языка С. Включаемые файлы. Макроопределения и условная компиляция.
3.14. Выделение памяти под локальные переменные (класс памяти auto в языке С). Стек вызовов.
-
Управление памятью:
4.1. Классы памяти переменных в языке C. Каков срок жизни переменных для
каждого из классов памяти?
4.2. Динамическая память. Функции работы с ДП. Основные ошибки: утечка памяти, висящие указатели.
4.3. Стратегии выделения памяти. (first fit, best fit, worst fit).
Какие структуры данных используются для реализации first fit (линейный
список) и worst fit (heap).
4.4. Что такое внешняя фрагментация и при каких условиях она возникает?
4.5. Что такое внутренняя фрагментация и при каких условиях она
возникает?
4.6. Выделение памяти алгоритмом парных меток.
4.7. Выделение памяти алгоритмом близнецов. Каковы преимущества этого
алгоритма?
4.8. Слабовые аллокаторы. Где они используются?
4.9. Сборка мусора: область применения, основные методы.
-
Алгоритмы: перестановки, поиск, сортировки
5.1. Размер задачи как характеристика объема входных данных. Временная и емкостная сложность программы как функции размера задачи. Верхняя, нижняя и средняя оценки. Классы эффективности алгоритмов: примеры задач, допускающих решение за константное, логарифмическое, линейное, квадратичное, полиномиальное, экспоненциальное время.
5.2. Основные методы программирования: повторение, ветвление и рекурсия. Рекурсивный переход, правила выхода, ветвящаяся и хвостовая рекурсия. Примеры использования для каждого метода.
5.3. Перестановки набора. Подсчет числа перестановок.
— Инверсии. Число инверсий, как мера сложности упорядочения набора; таблицы инверсий; алгоритм восстановления перестановки по таблице инверсий;
— Таблица инверсий как число в особой с.с.; итерационный алгоритм генерации всех таблиц инверсий.
— Алгоритмы перебора перестановок: рекурсивный, итерационный с лексикографическим упорядочением (Дейкстры).
5.4. Постановка задач поиска (П) и сортировки (С) записей в произвольном наборе данных. Внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора).
— Методы простого поиска в массиве: линейный поиск, бинарный поиск, оценки сложности.
— Методы поиска подстроки в строке: алгоритм прямого перебора, алгоритм Бойера-Мура, Рабина-Карпа, оценки сложности.
— Методы сортировки массива:
метод простых вставок;
метод бинарных вставок;
метод простого выбора;
метод «пузырька»;
шейкер-сортировка;
метод Шелла;
быстрая сортировка Хоара;
пирамидальная сортировка;
сортировка слиянием;
оценки сложности.
5.5. Cортировка файлов простым двухпутевым слиянием
6 Элементы теорий вероятностей, информации и кодирования.
6.1. Модель информационной системы связи Шеннона. Источник; приемник; канал; де/кодер. Алфавит источника как формализация языка сообщений. Кодирование как преобразование сообщения при переходе в среду с другим алфавитом.
6.2. Префиксный код. Однозначная декодируемость префиксного кода. Примеры непрефиксного однозначно декодируемого кода.
6.3. Метод Хаффмана построения кода типа А-{0,1}* с минимальной избыточностью. Реализация проекта по созданию архиватора.
-
Классические модели динамической памяти.
7.1. Список; как универсальная модель линейно упорядоченных структур данных последовательного доступа; разновидности списков: одно/двусвязные; циклические; иерархические
7.2. Операции над списками, алгоритмы поиска и включения для списков, анализ их эффективности, способы реализации списков (статика, динамика), реализация алгоритма топологической сортировки на иерархических списках.
7.3. Стек, преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения.
7.4. Очередь, реализация обхода дерева методом в ширину.
7.5. Основные операции, способы реализации на различных базовых представлениях.
-
Абстрактные структуры данных.
8.1. Графы, граф как наиболее общая модель данных последовательного доступа, пути и маршруты по графу, определения различных типов графов: (не)ориентированного, (а)циклического, много/односвязного.
8.2. Представление графа, как отношения на множестве вершин.
— модели представления в ЭВМ: матрицы смежности и инцидентности, динамическая структура со списками дуг, табличное представление.
8.3. Дерево, как частный вид графа.
— Терминология для деревьев: отец, сын, корень, лист, глубина и др.
8.4. Дерево двоичного поиска, создание орфографического словаря по заданному набору слов. Алгоритмы включения и удаления, сравнение их эффективности с известными алгоритмами на массивах.
8.5. Левое\правое скобочное представление деревьев.
8.6. Б-деревья. Алгоритмы поиска и включения элемента в Б-дерево.
-
Алгоритмы перебора на абстрактных динамических структурах (с обсуждением способов реализации)
9.1. Алгоритмы с возвратом — обход шахматной доски конем, поиск всех гамильтоновых циклов.
9.2. Обход графа методом в ширину. Реализация, примеры задач.
9.3. Обходы деревьев (в ширину, слева направо, в глубину: в ре/пост/инфиксном порядке).
9.4. Обход всех вершин графа — метод поиска в глубину.
9.5. Поиск кратчайших путей в графе, алгоритм Дейкстры, Беллмана-Форда, Флойда-Уоршелла.
9.6. Транзитивное замыкание графа. Алгоритм Флойда.
9.7. Каркас графа минимальной стоимости, алгоритмы Краскала и Прима.
9.8. Эйлеров граф. Способ определения Эйлерова цикла (теорема). Алгоритм Флери. Поиск Эйлерова цикла за время O(n+m).
9.9 Потоки в сетях, алгоритмы поиска максимального потока, теорема о максимальном потоке и минимальном разрезе.
-
Динамическое программирование
— Динамическое программирование как решение задач с помощью табличной техники.
— Примеры задач: об умножении матриц, о делимости, о гангстерах, о расстановке скобок в выражении.
-
Элементы теории языков (очень поверхностно, глубже будет позже).
— Символьные формализмы для описания синтаксиса языков: БНФ, РБНФ.
— Формальные грамматики. Классификация грамматик по Хомскому. Примеры грамматик.
— Синтаксический анализатор. Нисходящий и восходящий разбор. Полный перебор правил подстановки.
ЛИТЕРАТУРА
- В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу «Методы программирования» (часть первая). Новосибирск: 2003г.
- Вирт Н. Алгоритмы и структуры данных.
- Кнут Д. Искусство Программирования для ЭВМ. Т.3. Сортировка и Поиск.
- Кнут Д. Искусство Программирования для ЭВМ. Т.1. Основные алгоритмы.
- Вирт Н. Алгоритмы + Структуры Данных = Программы.
- Дейкстра Э. Дисциплина программирования.
- А.Ахо, Д.Хопкрофт, Д. Ульман. Построение и анализ вычислительных алгоритмов.
- Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.
- Д.В. Иртегов Введение в операционные системы. (//www.bhv.ru/books/get_pdf_data.php?id=182454)
- Б. Керниган, Д. Ричи. Язык Си
- Хэзфилд Р., Кирби Л. Искусство программирования на C: Фундаментальные алгоритмы, структуры данных и примеры приложений
- А. Ахо, Р. Сети, Дж. Хопкрофт. Коипиляторы
- Боровков А.А. Теория вероятностей
- 14. Ватолин Д., Ратушпяк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.
