Билет 1.
- Представление
чисел в ЭВМ. Целые числа. Вещественные
числа. Ошибки вычислений. Машинное e.
- Общая структура
С-программы.
- В теле программы,
написанной на языке С, заменить каждый идентификатор
типа name1_name2_name3_... на идентификатор Name1Name2Name3_... . Т.е. во всех идентификаторах,
имеющих в своем составе знак подчеркивания, заменить первую букву и каждую
букву после символа подчеркивания со строчной на прописную, и удалить из
идентификаторов знаки подчеркивания. Имена входного и выходного файлов
ввести из командной строки при запуске программы. Можно считать, что в
программе нет комментариев, символьных и строковых констант.
Билет 2.
- Сортировка
пузырьком. Случай оптимальности алгоритма слияния пузырьком. Сортировка
слиянием с рекурсией и без рекурсии.
- Типы базовых
переменных. Их описание, определение, инициализация.
- В теле программы,
написанной на языке С, заменить каждый идентификатор
типа Name1Name2Name3_... на идентификатор name1_name2_name3_... . Т.е. во всех идентификаторах, имеющих в своем
составе прописные буквы, перед каждой прописной буквой, кроме первой, вставить
знак подчеркивания и заменить прописные буквы на
строчные. Имена входного и выходного файлов ввести из командной строки при
запуске программы. Можно считать, что в программе нет комментариев,
символьных и строковых констант.
Билет 3.
- Сортировка
алгоритмом QuickSort. Теорема о среднем времени работы алгоритма QuickSort.
- Константы (целые,
вещественные, строковые, символьные).
- Вывести в выходной
файл имена всех define-констант,
использующихся в программе (без их определений). Можно считать, что в
программе нет комментариев. Имена входного и выходного файлов ввести из командной
строки при запуске программы.
Билет 4.
- Сортировка
алгоритмом HeapSort или сортировка с помощью пирамиды.
- Структуры и
объединения. Описания и определения.
- Вывести в выходной
файл содержимое всех символьных констант, использующихся в программе.
Можно считать, что в программе нет комментариев. Имена входного и
выходного файлов ввести из командной строки при запуске программы.
Билет 5.
- Алгоритмы сортировки за время O(N). Сортировка подсчетом. Цифровая сортировка.
- Арифметические
операции `+’, `-’, `*’, `/’, `+=’, `-=’, `*=’,
`/=’, `++’, `--’.
- Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе с четным номером строки инвертировать цвет (т.е. вместо 0
записать 1, а вместо 1 записать 0). Ввести имя файла как параметр
командной строки.
Билет 6.
- Алгоритмы сортировки за время O(N). Сортировка подсчетом. Цифровая сортировка.
- Логические операции `&&’, `||’, `!’.
- Во входном текстовом
файле задан массив целых чисел неизвестной длины. Организовать двунаправленный
список, в каждом элементе которого содержится одно вещественное число.
Заполнить список числами из файла. Для заданного x вывести в выходной файл все введенные числа,
отличающиеся от x не
более, чем на 1. Имена входного и
выходного файлов и число x
ввести из командной строки при запуске программы.
Билет 7.
- Структуры
данных. Определения. Различные реализации. Вектор. Стек.
- Указатели. Указатели
на функции.
- Дан файл в формате BMP , 8 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе записать 0, если в двоичном представлении пиксела больше
нулей, чем единиц и записать 1, если в двоичном представлении пиксела
больше единиц, чем нулей. Ввести имя файла как параметр командной строки.
Билет 8.
- Структуры данных.
Определения. Различные реализации. Очередь.
Дек.
- Область видимости
переменных и время жизни переменных.
- Во входном текстовом
файле задан массив рациональных чисел неизвестной длины. Каждое число
представляется парой целых чисел (числителем и знаменателем,
соответственно). Организовать однонаправленный список, в каждом элементе
которого содержится одно рациональное число в виде пары целых чисел
(числителя и знаменателя соответствующей дроби). Заполнить список числами
из файла. Для заданного вещественного x вывести в выходной файл все введенные числа,
отличающиеся от x не
более, чем на 1/N, где N –
число количество введенных чисел. Имена входного и выходного файлов и
число x ввести из командной строки при запуске
программы.
Билет 9.
- Структуры данных.
Определения. Различные реализации. L1 и L2 cписки.
- Описание и
определение функций.
- Во входном текстовом
файле задан массив целых чисел, длина которого задана первым числом в
файле (заранее на длину массива ограничений не наложено). Ввести массив в
программу, отведя необходимую память. Отсортировать массив с помощью
сортировки слиянием с рекурсией. В выходной файл вывести отсортированный
массив. Имена входного и выходного файлов ввести из командной строки при
запуске программы.
Билет 10.
- Структуры данных.
Определения. Реализация. Граф.
- Операторы цикла.
- Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе с четным номером строки инвертировать цвет (т.е. вместо 0
записать 1, а вместо 1 записать 0). Ввести имя файла как параметр
командной строки.
Билет 11.
- Поиск
пути в графе с наименьшим количеством промежуточных вершин. Алгоритм волны.
- Условные операторы.
Оператор перехода.
- Дан файл в формате BMP , 8 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе записать 0, если в бите с номером k двоичного представления данного пиксела записан
0 и 1, если . в бите с номером k двоичного представления данного пиксела записана
1. Ввести имя файла как параметр командной строки.
Билет 12.
- Представление
графа в памяти ЭВМ.
- Строки в языке С.
Функции работы со строками.
- Во входном текстовом
файле задан массив рациональных чисел неизвестной длины. Каждое число
представляется парой целых чисел (числителем и знаменателем,
соответственно). Организовать однонаправленный список, в каждом элементе
которого содержится одно рациональное число в виде пары целых чисел
(числителя и знаменателя соответствующей дроби). Заполнить список числами
из файла. Для среднего арифметического всех введенных чисел m вывести в
выходной файл все введенные числа, отличающиеся от m не более, чем на 1/N, где N –
число количество введенных чисел. Имена входного и выходного файлов ввести
из командной строки при запуске программы.
Билет 13.
- Поиск кратчайшего
пути в графе. Алгоритм Дейкстры.
- Потоковый ввод/вывод
для текстовых файлов. Открытие файла, ввод/вывод с помощью функций fprintf/fscanf/fgets/fputs, закрытие файла.
- Во входном текстовом
файле задан массив целых чисел, длина которого задана первым числом в
файле (заранее на длину массива ограничений не наложено). Ввести массив в
программу, отведя необходимую память. Отсортировать массив с помощью
сортировки слиянием без рекурсии. В выходной файл вывести отсортированный
массив. Имена входного и выходного файлов ввести из командной строки при
запуске программы.
Билет 14.
- Бинарные
деревья поиска. Поиск,
добавление, удаление элемента.
- Потоковый ввод/вывод
для бинарных файлов. Открытие файла, ввод/вывод с помощью функций fread/fwrite, закрытие файла.
- Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе с четным номером строки инвертировать цвет (т.е. вместо 0
записать 1, а вместо 1 записать 0). Ввести имя файла как параметр
командной строки.
Билет 15.
- Бинарные деревья
поиска. Поиск минимального и максимального
элемента в дереве. Поиск следующего/предыдущего
элемента в дереве.
- Отведение/очистка
памяти с помощью функций malloc/realloc/free.
- Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам.
Посчитать, каких пикселов больше в картинке – со значением 0 или 1, и если
пикселов со значением 0 больше, то установить значение всех пикселов
равным 0, а если пикселов со значением 1 больше, то установить значение
всех пикселов равным 1. Ввести имя файла как параметр командной строки.
Билет 16.
- Сбалансированные
и идеально сбалансированные бинарные деревья поиска. Определения. Высота
сбалансированного и идеально сбалансированного бинарного деревьев в
зависимости от количества элементов в дереве.
- Общая структура
С-программы.
- Во входном текстовом
файле задан массив целых чисел, длина которого задана первым числом в
файле (заранее на длину массива ограничений не наложено). Ввести массив в
программу, отведя необходимую память. В выходной файл вывести все те же
самые числа (возможно, в другом порядке), кроме n самых больших чисел. Для отделения максимальных
чисел использовать сортировку, выполняемую с помощью стандартной функции qsort. Имена входного и выходного файлов и число n ввести из командной строки при запуске программы.
Билет 17.
- Сбалансированные бинарные
деревья поиска. Поиск, добавление, удаление элемента.
- Строки в языке С.
Функции работы со строками.
- Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе с четным номером строки инвертировать цвет (т.е. вместо 0
записать 1, а вместо 1 записать 0). Ввести имя файла как параметр
командной строки.
Билет 18.
- Сбалансированные
бинарные деревья поиска. Поиск минимального и максимального элемента в дереве.
Поиск следующего/предыдущего элемента в дереве.
- Типы базовых
переменных. Их описание, определение, инициализация.
- Дан файл в формате BMP , 1 бит на пиксел, размером 32x32 пиксела. Известно, что смещение к данным лежит
в ячейке со смещением 10 от головы файла в виде числа unsigned
long. Данные лежат все подряд по строкам. В
каждом пикселе с четным номером столбца инвертировать цвет (т.е. вместо 0
записать 1, а вместо 1 записать 0). Ввести имя файла как параметр
командной строки.
Билет 19.
- Сбалансированные
бинарные деревья поиска. Слияние двух деревьев. Разбиение дерева по разбивающему
элементу.
- Константы (целые,
вещественные, строковые, символьные).
- Во входном текстовом
файле задан массив вещественных чисел неизвестной длины. Организовать
двунаправленный список, в каждом элементе которого содержится одно
вещественное число. Заполнить список числами из файла. Для заданного x вывести в выходной файл все введенные числа,
отличающиеся от x не
более, чем на 1/N, где N –
число количество введенных чисел. Имена входного и выходного файлов и
число x ввести из командной строки при запуске
программы.