Программа экзамена по курсу
"Работа на ЭВМ и программирование"

Лектор В. В. Борисенко

2015-16 учебный год

  1. Язык C++. Типы, операции. Классы, члены классов, методы. Конструктор по умолчанию и copy-конструктор. Переопределение операторов для классов на примере классов "вектор на плоскости", "точка", "прямоугольник". Правильное использование модификатора const и задание типов возвращаемых значений для разных типов операторов и методов.
  2. Обработка исключений в языке C++. Стек, реализация стека на базе массива. Обратная польская запись формул и стековый калькулятор. Аппаратная реализация стека. Размещение локальных переменных в аппаратном стеке, механизм вызова функций и передачи параметров.
  3. Статические члены и методы классов. Наследование классов, виртуальные методы, абстрактные классы. Программирование в оконных средах: общие принципы. Преимущества объектно ориентированного в случае программирования в оконной среде. Проект "Графическое окно" как пример простейшей библиотеки классов для поддержки программирования в среде X-Windows.
  4. Структуры данных: последовательного доступа — стек, очередь, дек, двусвязный и односвязный списки; прямого доступа — массив (вектор), динамический массив, матрица, множество, нагруженное множество. Реализация стека и дека (очереди) на базе массива. Способы реализация циклов "для каждого элемента", итераторы.
  5. Схема построения цикла с помощью инварианта. Применения этой схемы: алгоритм Евклида, алгоритм быстрого возведения в степень, бинарные алгоритмы умножения и деления, расширенный алгоритм Евклида, вычисление логарифма без разложения в ряд.
  6. Непрерывные реализации множества и нагруженного множества: наивная реализация, реализация с помощью бинарного поиска. Применение сxемы построения цикла с помощью инварианта в алгоритме бинарного поиска.
  7. Задача сортировки массива. Теоретическая оценка снизу минимального числа операций в произвольном алгоритме сортировки. Алгоритм быстрой сортировки, идея, реализация функции partition с применением схемы инварианта цикла; недостаток чисто рекурсивной схемы реализации функции quickSort, комбинированная схема ее реализации — с применением как итерации, так и рекурсии.
  8. Алгоритм сортировки кучей (или пирамидой) HeapSort. Бинарная куча, ее построение и модификация при удалении максимального элемента. Реализация алгоритма сортировки с помощью кучи, применение схемы инварианта цикла для написания программы. Реализация функции sieve просеивания элемента в куче (при которой элемент опускается на свое место).
  9. Стабильные алгоритмы сортировки (сохраняющие взаимный порядок равных элементов). Алгоритм двунаправленной сортировки слиянием с использованием дополнительной памяти: реализация функции merge, рекурсивная (нисходящая) и итеративная (восходящая) схемы реализации сортировки слиянием. Модификация классического алгоритма: использование вспомогательной памяти вдвое меньшего размера, алгоритм слияния двух соседних упорядоченных блоков, в котором результат получается в исходном массиве, а не во вспомогательном.
  10. Алгоритм стабильной сортировки слиянием, не использующий дополнительной памяти (т.е. основанный только на сравнениях и перестановках элементов сортируемого массива): идея алгоритма и оценка времени его работы. Рекурсивная реализация функции inPlaceMergeBlocks, сливающей два соседних упорядоченных блока в один упорядоченный без использования вспомогательной памяти.
    RADIX-сортировка: идея алгоритма, оценка скорости его работы и объема вспомогательной памяти.
  11. Бинарная куча (очередь с приоритетами): определение, реализация на базе массива. Алгоритм Дийкстры нахождения кратчайшего пути в графе (транспортной сети). Применение бинарной кучи в алгоритме сортировки кучей heapSort и алгоритме Дийкстры.
  12. Непрерывные и ссылочные реализации структур данных. Идея ссылочной реализации, достоинства и недостатки непрерывных и ссылочных реализаций. Реализация Л2-списка на С++: классы L2ListHeader и L2List. Особенность реализации с использованием динамической памяти: наследование и виртуальные деструкторы.
  13. Проект "Текстовый редактор": классы TextLine и Text, особенности их реализации. Реализация класса TextEdit, представляющего собой текстовый редактор в оконной системе X-Windows: основные переменные-члены класса, таблица команд редактора, добавление новых команд.
  14. Бинарные деревья и деревья поиска. Идея реализации множества и нагруженного множества с помощью бинарного дерева поиска. Алгоритмы поиска и добавления элемента для деревьев поиска. Алгоритмы нахождения минимальной и максимальной вершины поддерева. Алгоритм нахождения следующей (предыдущей) вершины дерева и обхода вершин дерева в порядке их возрастания (убывания).
  15. Сбалансированные (полные) и почти сбалансированные деревья. Логарифмическая оценка сверху высоты почти сбалансированного дерева с баланс-фактором C≥1 в зависимости от числа вершин. AVL-деревья (определения и свойства без доказательств).
  16. Красно-черные деревья: определение и свойства. Логарифмическая оценка сверху высоты красно-черного дерева в зависимости от числа вершин. Восстановление структуры красно-черного дерева при добавлении элемента: операции вращения вершины вправо и влево, рассмотрение различных случаев при добавлении элемента с нарушением свойств красно-черного дерева. Реализация нагруженного множества на основе красно-черного дерева: проект "TreeSet".
  17. Не было прочитано из-за недостатка времени...

    Реализация множества и нагруженного множества, основанная на использовании хеш-функции. Идея реализации, требования к хеш-функции. Коллизии и cпособы разрешения коллизий (ссылочная реализации массива подмножеств, использование массивов "мощность слоя и остаток").

Примерные задачи (могут изменяться от экзамена к экзамену)

  1. Реализовать класс "Polynomial", представляющий многочлен произвольной степени над полем вещественных чисел с операциями сложения, умножения, умножения на число и получения степени. Должны быть также конструктор по умолчанию, copy-конструктор, конструктор по степени и массиву коэффициентов, а также operator[], выдающий коэффициент многочлена при i-ой степени.
  2. Реализовать класс "Polynomial", представляющий многочлен произвольной степени с вещественными коэффициентами. Для него реализовать операторы деления "/" и получения остатка от деления "%". Должны быть также реализованы конструктор по умолчанию, copy-конструктор, конструктор по степени и массиву коэффициентов и метод, выдающий степень многочлена.
  3. Реализовать класс "Substitution", представляющий подстановку порядка n из элементов {0,1,2,..., n-1}, т.е. биективное отображение этого множества в себя. Должны быть реализованы композиция подстановок, действие подстановки на элемент x, 0<=x<=n-1, четность подстановки и три конструктора — по умолчанию, copy-конструктор, конструктор по n и массиву из n элементов. На порядок подстановки не накладывается никаких ограничений. Четность подстановки должна вычисляться за время, линейно зависящее от n.
  4. Реализовать класс "Matrix", представляющий прямоугольную матрицу порядка m на n, где числа m, n задаются в конструкторе. Должны быть реализованы также copy-конструктор, деструктор, получение элемента матрицы с заданными индексами (в виде ссылки на элемент типа double), сумма и произведение матриц. Элемент матрицы "a" должен быть доступен на чтение и запись с помощью выражения "a[i][j]", для этого надо правильно реализовать operator[]. На числа m и n не накладывается никаких ограничений. Индексы меняются в пределах от нуля до m-1 и n-1.
  5. Реализовать класс "Matrix", представляющий квадратную матрицу порядка n, где число n задается в конструкторе. Кроме конструктора с целым аргументом, должны быть реализованы copy-конструктор и деструктор, а также следующие методы:
    • получение элемента матрицы с заданными индексами (в виде ссылки на элемент типа double);
    • элементарные преобразования: 1) перестановка строк; 2) прибавление к одной строке другой, умноженной на число;
    • метод, выдающий определитель матрицы (алгоритм должен использовать приведение к ступенчатому виду с помощью элементарных преобразований, с выбором максимального по модулю элемента в столбце в качестве разрешающего).
    На порядок матрицы n не накладывается никаких ограничений. Индексы меняются в пределах от нуля до n-1.
  6. Та же задача, что и в предыдущем случае, только вместо определителя матрицы надо вычислить ее ранг. При вычислениях считать нулевыми элементы матрицы, по модулю не превосходящие значения EPS=0.0000001.
  7. Реализовать класс "Matrix", представляющий квадратную матрицу порядка n, где число n задается в конструкторе. Кроме конструктора с целым аргументом, должны быть реализованы copy-конструктор и деструктор, а также следующие методы:
    • получение элемента матрицы с заданными индексами (в виде ссылки на элемент типа double);
    • элементарные преобразования: 1) перестановка строк; 2) прибавление к одной строке другой, умноженной на число; 3) умножение строки на число.
    • получение обратной матрицы (алгоритм должен использовать приведение к ступенчатому, а затем к диагональному виду с помощью элементарных преобразований, с параллельным выполнением тех же преобразований над изначально единичной матрицей).
  8. Реализовать класс "Rotation", представляющий вращение трехмерного пространства, т.е. линейное ортогональное преобразование векторного пространства R3, сохраняющее ориентацию. (Как известно, любое такое преобразование это поворот вокруг некоторой оси.) Должны быть реализованы
    • конструктор по умолчанию (тождественное преобразование);
    • copy-конструктор;
    • конструктор, на вход которому подаются 3 координаты направляющего вектора оси вращения и угол поворота в радианах. Поворот происходит против часовой стрелки, если смотреть из конца вектора (т.е. по правилу правого винта);
    • композиция преобразований (operator*);
    • действие преобразования на вектор R3, вектор представляется массивом из трех элементов типа double.
  9. Проект "Стековый калькулятор": добавить 1) возведение в целую степень по модулю m с помощью алгоритма быстрого возведения в степень; 2) обращение числа n в кольце вычетов по модулю m с помощью расширенного алгоритма Евклида.
  10. Проект "Стековый калькулятор": добавить 1) вычисление квадратного корня (методом деления пополам или итераций Ньютона); 2) вычисление логарифма числа по основанию 2 через применение схемы построения цикла с помощью инварианта (библиотечными функциями пользоваться нельзя).
  11. Проект "Графическое окно": функция от одного аргумента задается непосредственно в тексте программы. Нарисовать график функции черным цветом, график первообразной синим цветом, график производной зеленым цветом в одном и том же окне
  12. Проект "Графическое окно": функция f(x,y) от двух аргументов задается непосредственно в тексте программы. Пользователь отмечает нажатием клавиши мыши некоторую точку (x0,y0) в окне. В ответ на это программа должна нарисовать линию уровня функции f(x,y) = const = f(x0,y0) (Указание: разбить прямоугольник окна на сетку маленьких прямоугольников, каждый элементарный прямоугольник — диагональю на два треугольника. Для каждого элементарного треугольника вычисляются значения функции в вершинах, затем с помощью линейной интерполяции вычисляются точки на сторонах, в которых функция должна принимать заданное значение. Таких точек либо нет, либо их две. В последнем случае рисуется отрезок.)
  13. Проект "Графическое окно": пользователь нажатиями левой клавиши мыши отмечает последовательность точек. Программа дожна рисовать крестики в отмеченных точках. По нажатию на правую клавишу мыши программа должна нарисовать ломаную без самопересечений, проходящую через отмеченные ранее точки.
  14. Проект "Графическое окно": пользователь отмечает нажатиями клавиши мыши 3 точки, не лежащие на одной прямой. Программа рисует крестики в отмеченных точках. После третьей точки программа должна нарисовать треугольник и окружность, описанную вокруг него.
  15. Проект "Графическое окно": пользователь отмечает нажатиями клавиши мыши 3 точки, не лежащие на одной прямой. Программа рисует крестики в отмеченных точках. После третьей точки программа должна нарисовать треугольник и окружность, вписанную в него.
  16. Проект "Графическое окно": пользователь отмечает нажатиями клавиши мыши 3 точки, не лежащие на одной прямой. Программа рисует крестики в отмеченных точках. После третьей точки программа должна нарисовать треугольник и высоты, проведенные к сторонам из всех его вершин. Треугольник рисуется черным цветом, высоты красным (высота проводится до пересечения с прямой через вершины треугольника).
  17. Проект "Графическое окно": пользователь нажатиями левой клавиши мыши отмечает последовательность вершин замкнутой несамопересекающейся ломаной (т.е. многоугольника, не обязательно выпуклого). После каждого очередного нажатия программа должна нарисовать введенную часть ломаной от первой точки до последней нажатой. По нажатию правой клавиши мыши программа должна замкнуть ломаную и напечатать площадь многоугольника.
  18. Проект "Графическое окно": пользователь отмечает нажатиями клавиши мыши 3 точки, не лежащие на одной прямой. Программа рисует крестики в отмеченных точках. После третьей точки программа должна нарисовать треугольник ABC, а также медиану, биссектрису и высоту, проведенные из вершины A. Треугольник рисуется черным цветом, медиана красным, биссектриса синим, высота зеленым (медиана, биссектриса и высота проводятся до пересечения с прямой BC).
  19. Проект "Графическое окно": пользователь нажатиями левой клавиши мыши отмечает 4 точки A(x0, y0), B(x1, y1), C(x2, y2), D(x3, y3), такие, что x0 < x1 < x2 < x3. Программа дожна рисовать крестики в отмеченных точках. После 4-й точки программа рисует прямые AB и CD и график кубического многочлена на отрезке [x0, x3], проходящий через точки A и D и в этих точках касающийся прямых AB и CD.
    Указание: искомый многочлен удобно искать в форме
     f(x) = a0 + a1(x-x0) + a2(x-x0)2 + a3(x-x0)2 (x-x3)
    Тогда коэффициенты ai последовательно вычисляются через предыдущие, используя последовательно условия о значении функции в точках x0, x3 и значении ее производной в точках x0, x3.
  20. Проект "Графическое окно": программа вводит с консоли точку, через которую проходит плоскость, и вектор нормали к плоскости. После этого программа должна создать графическое окно, нарисовать в кабинетной проекции черным цветом куб с координатами вершин плюс-минус 1 (без удаления невидимых линй), а также красным цветом сечение куба заданной плоскостью.
  21. Проект "Графическое окно": пользователь отмечает нажатиями клавиши мыши 4 точки с различными координатами X. Программа рисует крестики в отмеченных точках. После четвертой точки программа должна нарисовать график кубического многочлена, проходящий через заданные точки.
  22. Проект "Графическое окно": изначально в трехмерном пространстве расположен правильный тетраэдр с координатами вершин t0=(1, 1, 1), t1=(-1, -1, 1), t2=(1, -1, -1), t3=(-1, 1, -1). Программа в любой момент должна рисовать проекцию тетраэдра (всех его ребер) на плоскость XZ (невидимые линии удалять не нужно). По нажатию клавиши "a" программа поворачивает тетраэдр (в его текущем положении) вокруг оси Z против часовой стрелки на 10 градусов, по "s" - вокруг оси X против часовой стрелки на 10 градусов.
  23. Проект "Графическое окно": нарисовать эллипс по двум его фокусам и произвольной точке на эллипсе. Три точки отмечаются левой клавишей мыши. Программа должна нарисовать крестики в отмеченных точках и после третьей точки — требуемый эллипс.
  24. Проект "Графическое окно": нарисовать эллиптическую кривую
         y2 = a x3 + b x + c
    Программа должна ввести с консоли коэффициенты a, b, c. После этого она должна создать графическое окно и нарисовать в нем эллиптическую кривую.
  25. Проект "Текстовый редактор": добавить команду откатки на одно действие назад для следующих двух действий:
    • удаление строки (по Shft+Delete или Ctrl+K);
    • разрезание строки по нажатию Enter;
    команда выполняется нажатием Ctrl+Z. Откатку можно сделать до тех пор, пока не выполнена какая-либо команда, меняющая текст. (Например, если после удаления строки выполнялись только команды перемещения курсора, то восстановить строку можно.)
  26. Проект "Текстовый редактор": добавить команды
    • удаления начала текущей строки до курсора, не включая символ в позиции курсора. Команда должна выполняться по Ctrl+U;
    • удаления конца текущей строки, начиная с символа в позиции курсора. Команда должна выполняться по Ctrl+D;
    • склеивания двух строк: к текущей строке надо приклеить следующую строку, при этом следующая строка удаляется (т.е. из двух строк делается одна). Команда должна выполняться по Ctrl+Delete.
  27. Проект "Текстовый редактор": добавить команду "отформатировать абзац". Курсор стоит на первой строке абзаца и не должен менять положения после выполнения команды. Форматированные строки должны быть по возможности не длиннее 63 символов, отступов слева и красных строк нет, все группы пробелов заменены на один пробел, выравнивать по правому краю не надо. Строки могут разрезаться только по пробелам между словами. Абзац заканчивается пустой строкой.
  28. Проект "Текстовый редактор": добавить команду "заменить символ латинского регистра символом русского регистра, нарисованным на той же клавише", выполняется нажатием Ctrl+R, и обратную команду, выполняется по Ctrl+E. В обоих случаях курсор передвигается на одну позицию вправо. Соответствие между буквами определяется переключением латинского и русского регистров при одной и той же нажимаемой клавише. Прописные и строчные символы различаются.
  29. Проект "Текстовый редактор": добавить команду "табуляция к следующей целой константе", которая должна выполняться по нажатию "Ctrl+A". Редактор должен попытаться найти первую целую константу правее курсора или ниже по тексту и переместиться на ее начало, если константа найдена. Если курсор стоит на константе, то он должен переместиться на следующую.
  30. Проект "Текстовый редактор": добавить команду "инвертировать абзац". Абзац текста ограничен с обеих сторон пустыми строками либо началом или концом текста. По нажатию "Ctrl+A" редактор должен изменить порядок строк текущего абзаца на противоположный.
  31. Проект "Текстовый редактор": добавить команды перемещения курсора в начало следующего / в конец предыдущего абзаца. Абзацы разделяются пустыми или красными строками. Начало абзаца — это его первый символ, конец — пробел, следующий за последним символом последней строки абзаца. Команды выполняются нажатием Ctrl+A и Ctrl+B.
  32. Проект "Текстовый редактор": добавить команду "найти следующее вхождение слова в текст", которая должна выполняться по нажатию "Ctrl+A". Слово ограничено с обеих сторон пробелами либо началом или концом строки. По нажатию "Ctrl+A" редактор должен выделить из текста слово, на котором стоит курсор, и найти следующее вхождение этого слова в текст. Если оно существует, то курсор перемещается на его начало.
  33. Проект "Текстовый редактор": добавить команду "найти предыдущее вхождение слова в текст", которая должна выполняться по нажатию "Ctrl+A". Слово ограничено с обеих сторон пробелами либо началом или концом строки. По нажатию "Ctrl+A" редактор должен выделить из текста слово, на котором стоит курсор, и найти предыдущее вхождение этого слова в текст. Если оно существует, то курсор перемещается на его начало.
  34. Проект "Текстовый редактор": добавить команду "выжать воду из абзаца". Абзац текста ограничен с обеих сторон пустыми строками либо началом или концом текста. По нажатию "Ctrl+A" редактор должен заменить любую связную группу пробелов внутри текущего абзаца на один пробел.
  35. Проект "Текстовый редактор": добавить команду "упорядочить строки текущего абзаца по возрастанию". Абзац текста ограничен с обеих сторон пустыми строками либо началом или концом текста. По нажатию "Ctrl+A" редактор должен переставить строки текущего абзаца так, чтобы они возрастали сверху вниз. Для сравнения строк следует использовать стандартую функцию strcmp языка C (которая сравнивает строки лексикографически по кодам символов).

    36. Во всех перечисленных ниже задачах по проекту "TreeSet" следует модифицировать тестовую программу для исполнителя "Красно-черное дерево", содержащуюся в файле "treeTst.cpp". Программа должна работать с деревом, сгенерированным или прочитанным из файла ранее и содержащимся в переменной "tree". Нужно добавить одну из команд вида 

        exam
    exam n
    exam m n
    в зависимости от необходимости ввода одного или двух числовых аргументов. Например, в задаче
         "напечатать все поддеревья, содержащие ровно n вершин"
    программа должна напечатать поддеревья с пятью собственными вершинами после ввода текстовой строки 
        exam 5
    Под словом "поддерево" понимается максимальное поддерево с корнем в некоторой вершине исходного дерева (т.е. внешние вершины, добавляемые к поддереву, должны совпадать с внешними вершинами, добавляемыми к дереву).

  36. Проект "TreeSet": напечатать высоту и черную высоту RB-дерева.
  37. Проект "TreeSet": найти путь минимальной длины от корня дерева к некоторой внешней вершине и напечатать его.
  38. Проект "TreeSet": найти путь максимальной длины от корня дерева к некоторой внешней вершине и напечатать его.
  39. Проект "TreeSet": напечатать все поддеревья, содержащие ровно n вершин.
  40. Проект "TreeSet": найти и напечатать путь от корня дерева к некоторой внешней вершине, содержащий максимальное количество красных вершин.
  41. Проект "TreeSet": найти и напечатать путь от корня дерева к некоторой внешней вершине, содержащий минимальное количество красных вершин.
  42. Проект "TreeSet": ввести значения в 2-х вершинах дерева, найти и напечатать простой путь из вершины, содержащей первое значение, в вершину, содержащую второе значение.
  43. Проект "TreeSet": среди всех поддеревьев, содержащих ровно n вершин, найти и напечатать поддерево с максимальной суммой значений вершин.
  44. Проект "TreeSet": среди вершин, отстоящих на расстояние n от корня дерева, найти вершину с максимальным значением.
  45. Проект "TreeSet": найти сумму значений вершин дерева, отстоящих на расстояние n от корня.
  46. Проект "TreeSet": найти сумму значений вершин дерева, отстоящих от корня на расстояние, не большее n.
  47. Проект "TreeSet": проверить, является ли дерево почти сбалансированным (т.е. длины путей к внешним вершинам дерева отличаются не больше чем на единицу).
  48. Проект "TreeSet": проверить, является ли дерево AVL-деревом (т.е. для любой его вершины разность высот ее левого и правого поддеревьев по абсолютной величине не превосходит 1).
  49. Проект "TreeSet": вершины бинарного дерева окрашены в красный и черный цвета (при этом дерево может не быть красно-черным). По заданной вершине проверить, является ли она корнем красно-черного поддерева.
  50. Проект "TreeSet": найти и напечатать все максимальные сбалансированные (полные) поддеревья.
  51. Проект "TreeSet": найти и напечатать максимум из длин путей между вершинами дерева.

Общие требования, предъявляемые к студентам на экзамене

  1. Знание элементарных команд операционной системы Unix, таких как копирование файлов cp, удаление файлов rm, создание и удаление директорий mkdir/rmdir, изменение текущей директории cd, печать названия текущей директории pwd, выдача списка файлов в текущей директории ls, просмотр содержимого файла less, печать содержимого файла cat, печать строки echo и т.п. Перенаправление вывода команды из стандартного выходного потока в файл: 
        command > file
    Перенаправление ввода из файла вместо стандартного входного потока: 
        command < file
    Подача вывода первой команды на вход второй команде: 
        command1 | command2
  2. Знание элементарных ключей команды компиляции "g++" (или "gcc" в случае языка C): только компиляция "-c", задание имени выходного исполняемого файла "-o name", выключение оптимизации "-O0", включение информации для отладчика "-g", подключение статической библиотеки "-l library", дополнительная директория поиска стадартных include-файлов "-I dir", дополнительная директория поиска библиотек "-L dir".
  3. Умение пользоваться отладчиком "gdb" или его графической оболочкой "ddd".
  4. Умение написать элементарный Makefile. Например, проект собирается из файлов "a.cpp", "b.cpp", "c.cpp", файл "a.cpp" включает файл "b.h", файл "b.cpp" включает файлы "b.h" и "c.h", файл "c.cpp" включает файл "c.h". Имя выходной программы "abc". Makefile может выглядеть так: 
    CFLAGS = -g -O0
CC = g++ $(CFLAGS)
abc: a.o b.o c.o
        $(CC) -o abc a.o b.o c.o
a.o: a.cpp b.h
        $(CC) -c a.cpp
b.o: b.cpp b.h c.h
        $(CC) -c b.cpp
c.o: c.cpp c.h
        $(CC) -c c.cpp
clean:
        rm -f *.o abc
    Пояснение. В первой строке указываются ключи компилятора: подключить информацию для отладчика "-g", выключить оптимизацию "-O0". Во второй строке задается команда компиляции: "g++", после чего подставляются ключи компилятора (символ "$" означает макроподстановку). Дальше идут пары строк: первая строка в каждой паре — это цель и от чего она зависит; вторая строка — это команда, которая создает цель. Фиктивная цель "clean" нужна для удаления всех объектных файлов и выполняемого файла "abc", т.е. для чистки текущей директории от "мусора" (команда "make clean" удаляет все те файлы, которые создаются командой "make" без аргументов).