Билет 1.

 

  1. Представление чисел в ЭВМ. Целые числа. Вещественные числа. Ошибки вычислений. Машинное e.
  2. Общая структура С-программы.
  3. В теле программы, написанной на языке С, заменить каждый идентификатор типа name1_name2_name3_... на идентификатор Name1Name2Name3_... . Т.е. во всех идентификаторах, имеющих в своем составе знак подчеркивания, заменить первую букву и каждую букву после символа подчеркивания со строчной на прописную, и удалить из идентификаторов знаки подчеркивания. Имена входного и выходного файлов ввести из командной строки при запуске программы. Можно считать, что в программе нет комментариев, символьных и строковых констант.

 

 

 

 

Билет 2.

  1. Сортировка пузырьком. Случай оптимальности алгоритма слияния пузырьком. Сортировка слиянием с рекурсией и без рекурсии.
  2. Типы базовых переменных. Их описание, определение, инициализация.
  3. В теле программы, написанной на языке С, заменить каждый идентификатор типа Name1Name2Name3_... на идентификатор name1_name2_name3_... . Т.е. во всех идентификаторах, имеющих в своем составе прописные буквы, перед каждой прописной буквой, кроме первой, вставить знак подчеркивания и заменить прописные буквы на строчные. Имена входного и выходного файлов ввести из командной строки при запуске программы. Можно считать, что в программе нет комментариев, символьных и строковых констант.

 

 

 

 

Билет 3.

  1. Сортировка алгоритмом QuickSort. Теорема о среднем времени работы алгоритма QuickSort.
  2. Константы (целые, вещественные, строковые, символьные).
  3. Вывести в выходной файл имена всех define-констант, использующихся в программе (без их определений). Можно считать, что в программе нет комментариев. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

 

 

Билет 4.

  1. Сортировка алгоритмом HeapSort или сортировка с помощью пирамиды.
  2. Структуры и объединения. Описания и определения.
  3. Вывести в выходной файл содержимое всех символьных констант, использующихся в программе. Можно считать, что в программе нет комментариев. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

Билет 5.

  1. Алгоритмы сортировки за время O(N). Сортировка подсчетом. Цифровая сортировка.
  2. Арифметические операции `+’, `-’, `*’, `/’, `+=’, `-=’, `*=’, `/=’, `++’,   `--’.
  3. Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит в ячейке со смещением 10 от головы файла в виде числа unsigned long. Данные лежат все подряд по строкам. В каждом пикселе с четным номером строки инвертировать цвет (т.е. вместо 0 записать 1, а вместо 1 записать 0). Ввести имя файла как параметр командной строки.

 

 

 

 

Билет 6.

  1. Алгоритмы сортировки за время O(N). Сортировка подсчетом. Цифровая сортировка.
  2. Логические операции `&&’, `||’, `!’.
  3. Во входном текстовом файле задан массив целых чисел неизвестной длины. Организовать двунаправленный список, в каждом элементе которого содержится одно вещественное число. Заполнить список числами из файла. Для заданного x вывести в выходной файл все введенные числа, отличающиеся от x не более, чем на 1. Имена входного и выходного файлов и число x ввести из командной строки при запуске программы.

 

 

 

Билет 7.

  1. Порядковые статистики. Определения медианы и k-той порядковой статистики. Поиск порядковой статистики за время Q(N) в среднем.
  2. Бинарные поля в структурах.
  3. Во входном текстовом файле задан массив целых чисел, длина которого задана первым числом в файле (заранее на длину массива ограничений не наложено). Ввести массив в программу, отведя необходимую память. В выходной файл вывести все различные числа из введенного массива. Для выделения различных чисел использовать сортировку, выполняемую с помощью стандартной функции qsort. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

 


 

Билет 9.

  1. Структуры данных. Определения. Различные реализации. Вектор. Стек.
  2. Указатели. Указатели на функции.
  3. Дан файл в формате BMP , 8 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит в ячейке со смещением 10 от головы файла в виде числа unsigned long. Данные лежат все подряд по строкам. В каждом пикселе записать 0, если в двоичном представлении пиксела больше нулей, чем единиц и записать 1, если в двоичном представлении пиксела больше единиц, чем нулей. Ввести имя файла как параметр командной строки.

 

 

 

 

Билет 10.

  1. Структуры данных. Определения. Различные реализации. Очередь. Дек.
  2. Область видимости переменных и время жизни переменных.
  3. Во входном текстовом файле задан массив рациональных чисел неизвестной длины. Каждое число представляется парой целых чисел (числителем и знаменателем, соответственно). Организовать однонаправленный список, в каждом элементе которого содержится одно рациональное число в виде пары целых чисел (числителя и знаменателя соответствующей дроби). Заполнить список числами из файла. Для заданного вещественного x вывести в выходной файл все введенные числа, отличающиеся от x не более, чем на 1/N, где N – число количество введенных чисел. Имена входного и выходного файлов и число x ввести из командной строки при запуске программы.

 

 

 

Билет 11.

  1. Структуры данных. Определения. Различные реализации. L1 и L2 cписки.
  2. Описание и определение функций.
  3. Во входном текстовом файле задан массив целых чисел, длина которого задана первым числом в файле (заранее на длину массива ограничений не наложено). Ввести массив в программу, отведя необходимую память. Отсортировать массив с помощью сортировки слиянием с рекурсией. В выходной файл вывести отсортированный массив. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

 

 

Билет 12.

  1. Структуры данных. Определения. Реализация. Граф.
  2. Операторы цикла.
  3. Во входном текстовом файле задан двумерный массив целых чисел. Число строк массива задается первым числом в файле. Далее для каждой строки массива задается ее длина (длины разных строк могут различаться), после которой следуют числа данной строки (заранее на размеры массива ограничений не наложено). Организовать двумерный массив (в виде указателя на указатель), в каждой строке которого расположена соответствующая строка массива из файла. Ввести массив из входного файла в организованный массив последовательно по строкам, отводя память под каждую строку при ее введении. В выходной файл вывести самую длинную строку введенного массива. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 


 

Билет 13.

  1. Поиск пути в графе с наименьшим количеством промежуточных вершин. Алгоритм волны.
  2. Условные операторы. Оператор перехода.
  3. Дан файл в формате BMP , 8 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит в ячейке со смещением 10 от головы файла в виде числа unsigned long. Данные лежат все подряд по строкам. В каждом пикселе записать 0, если в бите с номером k двоичного представления данного пиксела записан 0 и 1, если . в бите с номером k двоичного представления данного пиксела записана 1. Ввести имя файла как параметр командной строки.

 

 

Билет 14.

  1. Представление графа в памяти ЭВМ.
  2. Строки в языке С. Функции работы со строками.
  3. Во входном текстовом файле задан массив рациональных чисел неизвестной длины. Каждое число представляется парой целых чисел (числителем и знаменателем, соответственно). Организовать однонаправленный список, в каждом элементе которого содержится одно рациональное число в виде пары целых чисел (числителя и знаменателя соответствующей дроби). Заполнить список числами из файла. Для среднего арифметического всех введенных чисел m  вывести в выходной файл все введенные числа, отличающиеся от m не более, чем на 1/N, где N – число количество введенных чисел. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

 

Билет 15.

  1. Поиск кратчайшего пути в графе. Алгоритм Дейкстры.
  2. Потоковый ввод/вывод для текстовых файлов. Открытие файла, ввод/вывод с помощью функций fprintf/fscanf/fgets/fputs, закрытие файла.
  3. Во входном текстовом файле задан массив целых чисел, длина которого задана первым числом в файле (заранее на длину массива ограничений не наложено). Ввести массив в программу, отведя необходимую память. Отсортировать массив с помощью сортировки слиянием без рекурсии. В выходной файл вывести отсортированный массив. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

 

 

Билет 16.

  1. Бинарные деревья поиска. Поиск, добавление, удаление элемента.
  2. Потоковый ввод/вывод для бинарных файлов. Открытие файла, ввод/вывод с помощью функций fread/fwrite, закрытие файла.
  3. Во входном текстовом файле задан двумерный массив целых чисел. Число строк массива задается первым числом в файле. Далее для каждой строки массива задаются их длины (длины разных строк могут различаться), после задания всех длин следуют числа массива, расположенный по строкам (заранее на размеры массива ограничений не наложено). Организовать двумерный массив (в виде указателя на указатель), в каждой строке которого расположена соответствующая строка массива из файла. Разрешается вызывать функцию malloc всего два раза: для отведения памяти под массив указателей и для отведения памяти под данные. Ввести массив из входного файла в организованный массив. В выходной файл вывести самую длинную строку введенного массива. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

Билет 17.

  1. Бинарные деревья поиска. Поиск минимального и максимального элемента в дереве. Поиск следующего/предыдущего элемента в дереве.
  2. Отведение/очистка памяти с помощью функций malloc/realloc/free.
  3. Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит в ячейке со смещением 10 от головы файла в виде числа unsigned long. Данные лежат все подряд по строкам. Посчитать, каких пикселов больше в картинке – со значением 0 или 1, и если пикселов со значением 0 больше, то установить значение всех пикселов равным 0, а если пикселов со значением 1 больше, то установить значение всех пикселов равным 1. Ввести имя файла как параметр командной строки.

 

 

 

 

Билет 18.

  1. Сбалансированные и идеально сбалансированные бинарные деревья поиска. Определения. Высота сбалансированного и идеально сбалансированного бинарного деревьев в зависимости от количества элементов в дереве.
  2. Общая структура С-программы.
  3. Во входном текстовом файле задан массив целых чисел, длина которого задана первым числом в файле (заранее на длину массива ограничений не наложено). Ввести массив в программу, отведя необходимую память. В выходной файл вывести все те же самые числа (возможно, в другом порядке), кроме n самых больших чисел. Для отделения максимальных чисел использовать сортировку, выполняемую с помощью стандартной функции qsort. Имена входного и выходного файлов и число n ввести из командной строки при запуске программы.

 

 

Билет 19.

  1. Сбалансированные бинарные деревья поиска. Поиск, добавление, удаление элемента.
  2. Строки в языке С. Функции работы со строками.
  3. Во входном текстовом файле задан массив целых чисел, длина которого N задана первым числом в файле (заранее на длину массива ограничений не наложено). Организовать двумерный массив (в виде указателя на указатель), в k-той строке которого расположено k+1 чисел. Размер массива должен быть достаточен для хранения N элементов. При организации массива разрешается вызывать функцию  malloc  всего один раз. Ввести массив из входного файла в организованный массив последовательно по строкам. В выходной файл вывести организованный массив последовательно по столбцам. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

Билет 20.

  1. Сбалансированные бинарные деревья поиска. Поиск минимального и максимального элемента в дереве. Поиск следующего/предыдущего элемента в дереве.
  2. Типы базовых переменных. Их описание, определение, инициализация.
  3. Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит в ячейке со смещением 10 от головы файла в виде числа unsigned long. Данные лежат все подряд по строкам. В каждом пикселе с четным номером столбца инвертировать цвет (т.е. вместо 0 записать 1, а вместо 1 записать 0). Ввести имя файла как параметр командной строки.

 


Билет 21.

  1. Сбалансированные бинарные деревья поиска. Слияние двух деревьев. Разбиение дерева по разбивающему элементу.
  2. Константы (целые, вещественные, строковые, символьные).
  3. Во входном текстовом файле задан массив вещественных чисел неизвестной длины. Организовать двунаправленный список, в каждом элементе которого содержится одно вещественное число. Заполнить список числами из файла. Для заданного x вывести в выходной файл все введенные числа, отличающиеся от x не более, чем на 1/N, где N – число количество введенных чисел. Имена входного и выходного файлов и число x ввести из командной строки при запуске программы.

 

 

 

Билет 22.

  1. Красно-черные деревья. Высота красно-черного дерева.
  2. Структуры и объединения. Описания и определения.
  3. Во входном текстовом файле задан массив целых чисел, длина которого задана первым числом в файле (заранее на длину массива ограничений не наложено). Ввести массив в программу, отведя необходимую память. В выходной файл вывести все различные числа из введенного массива. Для выделения различных чисел использовать сортировку, выполняемую с помощью стандартной функции qsort. Имена входного и выходного файлов ввести из командной строки при запуске программы.

 

 

 

Билет 23.

  1. Красно-черные деревья. Классическое добавление элемента в красно-черное дерево.
  2. Арифметические операции `+’, `-’, `*’, `/’, `+=’, `-=’, `*=’, `/=’, `++’,   `--’.
  3. Во входном текстовом файле задан массив целых чисел, длина которого N задана первым числом в файле (заранее на длину массива ограничений не наложено). Организовать двумерный массив (в виде указателя на указатель), в k-той строке которого расположено k%m+1 чисел. Размер массива должен быть достаточен для хранения N элементов. При организации массива разрешается вызывать функцию  malloc  всего один раз. Ввести массив из входного файла в организованный массив последовательно по строкам. В выходной файл вывести первый столбец организованного массива. Имена входного и выходного файлов и число m  ввести из командной строки при запуске программы.

 

Билет 24.

  1. Красно-черные деревья. Классическое удаление элемента из красно-черного дерева.
  2. Логические операции `&&’, `||’, `!’.
  3. Дан файл в формате BMP , 8 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит в ячейке со смещением 10 от головы файла в виде числа unsigned long. Данные лежат все подряд по строкам. В каждом пикселе записать 0, если в двоичном представлении пиксела больше нулей, чем единиц и записать 1, если в двоичном представлении пиксела больше единиц, чем нулей. Ввести имя файла как параметр командной строки.