Вопросы к экзамену по программированию в НГУ

0
308

Нашли в сети список экзаменационных вопросов по программированию и решили, что возможно кому то пригодится. Вопросы к экзамену по программированию в НГУ.

Вопросы к экзамену по программированию в НГУ (Новосибирский государственный университет)

 

Вопросы по курсу Программирование на языке высокого уровня (ЯВУ)

  1. Системы счисления (с.с.)

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. Понятие символьных вычислений. Формальное определение вычислений как преобразование цепочек символов по заданным правилам (на примере определения арифметических операций таблицами значений).

  1. Модели машинной арифметики с конечной разрядностью

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. Источники погрешности при арифметике с плавающей точкой. Приведите примеры

 

  1. Вопросы по 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 в языке С). Стек вызовов.

 

  1. Управление памятью:

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. Сборка мусора: область применения, основные методы.

 

  1. Алгоритмы: перестановки, поиск, сортировки

5.1. Размер задачи как характеристика объема входных данных. Временная и емкостная сложность программы как функции размера задачи. Верхняя, нижняя и средняя оценки. Классы эффективности алгоритмов: примеры задач, допускающих решение за константное, логарифмическое, линейное, квадратичное, полиномиальное, экспоненциальное время.

5.2. Основные методы программирования: повторение, ветвление и рекурсия. Рекурсивный переход, правила выхода, ветвящаяся и хвостовая рекурсия. Примеры использования для каждого метода.

5.3. Перестановки набора. Подсчет числа перестановок.

— Инверсии. Число инверсий, как мера сложности упорядочения набора; таблицы инверсий; алгоритм восстановления перестановки по таблице инверсий;

— Таблица инверсий как число в особой с.с.; итерационный алгоритм генерации всех таблиц инверсий.

— Алгоритмы перебора перестановок: рекурсивный, итерационный с лексикографическим упорядочением (Дейкстры).

5.4. Постановка задач поиска (П) и сортировки (С) записей в произвольном наборе данных. Внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора).

— Методы простого поиска в массиве: линейный поиск, бинарный поиск, оценки сложности.

— Методы поиска подстроки в строке: алгоритм прямого перебора, алгоритм Бойера-Мура, Рабина-Карпа, оценки сложности.

— Методы сортировки массива:

метод простых вставок;

метод бинарных вставок;

метод простого выбора;

метод «пузырька»;

шейкер-сортировка;

метод Шелла;

быстрая сортировка Хоара;

пирамидальная сортировка;

сортировка слиянием;

оценки сложности.

5.5. Cортировка файлов простым двухпутевым слиянием

 

6 Элементы теорий вероятностей, информации и кодирования.

 

6.1. Модель информационной системы связи Шеннона. Источник; приемник; канал; де/кодер. Алфавит источника как формализация языка сообщений. Кодирование как преобразование сообщения при переходе в среду с другим алфавитом.

6.2. Префиксный код. Однозначная декодируемость префиксного кода. Примеры непрефиксного однозначно декодируемого кода.

6.3. Метод Хаффмана построения кода типа А-{0,1}* с минимальной избыточностью. Реализация проекта по созданию архиватора.

 

  1. Классические модели динамической памяти.

7.1. Список; как универсальная модель линейно упорядоченных структур данных последовательного доступа; разновидности списков: одно/двусвязные; циклические; иерархические

7.2. Операции над списками, алгоритмы поиска и включения для списков, анализ их эффективности, способы реализации списков (статика, динамика), реализация алгоритма топологической сортировки на иерархических списках.

7.3. Стек, преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения.

7.4. Очередь, реализация обхода дерева методом в ширину.

7.5. Основные операции, способы реализации на различных базовых представлениях.

 

  1. Абстрактные структуры данных.

8.1. Графы, граф как наиболее общая модель данных последовательного доступа, пути и маршруты по графу, определения различных типов графов: (не)ориентированного, (а)циклического, много/односвязного.

8.2. Представление графа, как отношения на множестве вершин.

— модели представления в ЭВМ: матрицы смежности и инцидентности, динамическая структура со списками дуг, табличное представление.

8.3. Дерево, как частный вид графа.

— Терминология для деревьев: отец, сын, корень, лист, глубина и др.

8.4. Дерево двоичного поиска, создание орфографического словаря по заданному набору слов. Алгоритмы включения и удаления, сравнение их эффективности с известными алгоритмами на массивах.

8.5. Левое\правое скобочное представление деревьев.

8.6. Б-деревья. Алгоритмы поиска и включения элемента в Б-дерево.

 

  1. Алгоритмы перебора на абстрактных динамических структурах (с обсуждением способов реализации)

9.1. Алгоритмы с возвратом — обход шахматной доски конем, поиск всех гамильтоновых циклов.

9.2. Обход графа методом в ширину. Реализация, примеры задач.

9.3. Обходы деревьев (в ширину, слева направо, в глубину: в ре/пост/инфиксном порядке).

9.4. Обход всех вершин графа — метод поиска в глубину.

9.5. Поиск кратчайших путей в графе, алгоритм Дейкстры, Беллмана-Форда, Флойда-Уоршелла.

9.6. Транзитивное замыкание графа. Алгоритм Флойда.

9.7. Каркас графа минимальной стоимости, алгоритмы Краскала и Прима.

9.8. Эйлеров граф. Способ определения Эйлерова цикла (теорема). Алгоритм Флери. Поиск Эйлерова цикла за время O(n+m).

9.9 Потоки в сетях, алгоритмы поиска максимального потока, теорема о максимальном потоке и минимальном разрезе.

 

  1. Динамическое программирование

— Динамическое программирование как решение задач с помощью табличной техники.

— Примеры задач: об умножении матриц, о делимости, о гангстерах, о расстановке скобок в выражении.

 

  1. Элементы теории языков (очень поверхностно, глубже будет позже).

— Символьные формализмы для описания синтаксиса языков: БНФ, РБНФ.

— Формальные грамматики. Классификация грамматик по Хомскому. Примеры грамматик.

— Синтаксический анализатор. Нисходящий и восходящий разбор. Полный перебор правил подстановки.

 

ЛИТЕРАТУРА

  1. В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу «Методы программирования» (часть первая). Новосибирск: 2003г.
  2. Вирт Н. Алгоритмы и структуры данных.
  3. Кнут Д. Искусство Программирования для ЭВМ. Т.3. Сортировка и Поиск.
  4. Кнут Д. Искусство Программирования для ЭВМ. Т.1. Основные алгоритмы.
  5. Вирт Н. Алгоритмы + Структуры Данных = Программы.
  6. Дейкстра Э. Дисциплина программирования.
  7. А.Ахо, Д.Хопкрофт, Д. Ульман. Построение и анализ вычислительных алгоритмов.
  8. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.
  9. Д.В. Иртегов Введение в операционные системы. (//www.bhv.ru/books/get_pdf_data.php?id=182454)
  10. Б. Керниган, Д. Ричи. Язык Си
  11. Хэзфилд Р., Кирби Л. Искусство программирования на C: Фундаментальные алгоритмы, структуры данных и примеры приложений
  12. А. Ахо, Р. Сети, Дж. Хопкрофт. Коипиляторы
  13. Боровков А.А. Теория вероятностей
  14. 14. Ватолин Д., Ратушпяк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.