Экзаменационные вопросы и задачи (семестр 1)
Экзамен сдается в «закрытой» форме, пользоваться какими-либо внешними источниками запрещено (в т.ч. справочными).
Задача пишется в «казенном» компьютере без выхода в интернет.
Теоретические вопросы
Структура программы и языка программирования. Программа = алгоритм + данные. Структура системы исполнения кода. Особенности Си/Си++.
Основы компьютерной архитектуры. Прямо адресуемая память, сегментация, система команд, исполнение программы, поток команд.
Средства сборки программ в ЯП. Модульное программирование: файлы, библиотеки. Трансляция и компоновка программы. Функция, модуль (файл), проект. Объектный модуль (ОМ), точки входа, внешние ссылки. Компоновка программного модуля из ОМ и библиотек. Программные интерфейсы данных и функций. Заголовочные файлы.
Позиционная система счисления. Представление чисел. Прямое и обратное преобразование из 10CC в СС с другим основанием. Арифметика в СС с другим основанием (сложение, умножение). Особенности двоичной СС.
Единицы представления информации в компьютере: бит, байт, машинное слово. Двоичная и шестнадцатеричная системы счисления и их использование в компьютере. Оценка информационной емкости двоичного числа. Представление целого без знака в машинном слове.
Понятие типа данных и переменной. Определение переменных в Си. Базовые типы данных char,int,long как машинные слова. Особенности типа данных char. Знаковая и беззнаковая формы представления в Си. Представление символов. Представление чисел с плавающей запятой.
Массивы: особенности работы, инициализация. Массивы как формальные параметры функций.
Выражения и операции (обзор и классификация): арифметические, сравнения, логические, машинно-ориентированные, присваивания, адресные, выделения составляющего типа данных. Особенности выполнения операций на Си (совместимость, приоритеты, направление выполнения, действие и результат). Особенности выполнения арифметических операций и операций присваивания. Операция "запятая". Операции сравнения, логические операции.
Преобразование базовых типов данных в выражениях: действия, порядок. Явные и неявное преобразования.
Выражения и операторы. Роль ";" как ограничителя. Классификации управляющей логики программы - последовательность, условие, цикл, переход. Основные операторы Си: if, while, do-while, for, switch, break, continue, return, goto: классификация, особенности синтаксиса и выполнения.
Функции. Формальные и фактические параметры. Способы передачи параметров – по значению и по ссылке. Результат функции. Локальные и глобальные (автоматические и внешние) переменные. Функция как основа модульного программирования.
Структура данных как система взаимосвязанных переменных и значений. Стек. Представление стека в массиве. Свойства. Использование стека при вызове функции.
Структура данных как система взаимосвязанных переменных и значений. Последовательность. Стек и очередь. Свойства. Представление очереди в массиве.
Циклические программы. Виды циклов. Итерационный цикл. Рекуррентные последовательности и итерационные циклы. Программа вычисления корня функции. Программа вычисления суммы степенного ряда.
Работа со строками. Представление строки в Си. Строка и массив символов. Поиск в строке. Посимвольная и пословная обработка. Примеры.
Преобразования целого и вещественного числа из внешней формы во внутреннюю и обратно.
Работа с текстовыми файлами в stdio. Функции открытия/закрытия файла, посимвольный, построчный и форматированный ввод/вывод. Стандартные потоки. (Примеры).
Трудоемкость алгоритмов. Время выполнения и трудоемкость. Оценочный характер трудоемкости. Виды функций трудоемкости, чувствительность к данным. Программные конструкции, определяющие различные виды трудоемкости.
Сортировка и поиск. Понятие записи и ключа. Линейный и двоичный поиск. Трудоемкость алгоритмов сортировки и поиска.
Классификация сортировок: выбор, вставка, обмен, подсчет, разделение, слияние. Идеи. Трудоемкость. (по тестам к защите л.р. Сортировки)
Основы анализа программ. “Исторический” и логический анализ программы. “Смысл” выражений и переменных. Стандартные программные контексты. (Показать на примере)
Жизненный цикл разработки программы. Образная модель. Предварительный сбор фактов. Технология программирования как «выстраивание» текста программы. «Историческое», структурное и «грязное» программирование (показать на примерах).
Идеи (заповеди) структурного программирования – нисходящее, пошаговое, структурное проектирование программы и данных. Последовательность, ветвление и цикл. Модульное программирование (показать на примерах).
Время жизни и область действия переменных и функций. Определения и объявления. Глобальные, локальные переменные и их свойства (показать на примерах).
Задачи
Задачи оформляются в виде функций с передачей всех входных и выходных данных через формальные параметры и результат (глобальные переменные использовать запрещается). В main пишется несколько вызовов функции на статических данных, с выводом результатов, демонстрирующих работоспособность программы.
Найти наименьшее общее кратное для всех элементов массива - минимальное число, которое делится на все элементы массива без остатка.
Написать функцию проверки, является ли заданное число простым. С ее помощью написать функцию поиска простых чисел в диапазоне 1000-2000, две любые части которого - также простые (например, 1997, 1-997,19-97,199-7)
Сформировать массив простых чисел в диапазоне от 2 до заданного. Очередное простое число определяется попыткой деления нацело числа на все уже накопленные простые числа.
Любая целочисленная денежная сумма n>7 может быть выдана без сдачи “трешками” и “пятерками”. Программа находит эти числа для заданного n.
На заданном интервале найти все числа, цифры которых находятся в строго возрастающем порядке (например, 532).
Число Армстронга – такое число из k цифр, для которого сумма k-х степеней его цифр равна самому этому числу, например 153=13+53+33. Найти все трехзначные числа Армстронга.
Найти все двухзначные (трехзначные) числа, которые совпадают с последними цифрами своих квадратов, например, 252=625, 762=5676.
Число называется совершенным, если оно равно сумме всех своих делителей, например, 6=1+2+3, 28=1+2+4+7+14. Найти все совершенные числа в заданном интервале.
Найти все числа в заданном диапазоне, которые делятся на любую из своих цифр.
Найти числа в диапазоне 100-10000, для которых куб суммы цифр равен значению самого числа (например, 512 - 5+1+2=8).
Разложить число на простые множители (например 36=332*2). Результат – последовательность множителей в массиве, ограниченная 0.
Определить в массиве максимальную длину последовательности расположенных подряд возрастающих значений и возвратить индекс ее начала и длину.
Найти в строке слово минимальной длины и возвратить индекс его начала.
Оставить в строке по одному пробелу между словами.
Возвратить индекс начала фрагмента, симметричного относительно центрального символа (например, "abcba"), и имеющего максимальную длину. Длину фрагмента возвратить по ссылке.
Возвратить массив индексов начала фрагмента, симметричного относительно центрального символа (например, "abcba"), и имеющих длину >=5.
"Перевернуть" в строке все слова. (Например: "Жили были дед и баба" - "илиЖ илиб дед и абаб").
Преобразовать целое из внутренней формы во внешнюю в шестнадцатеричной СС.
Преобразовать число в шестнадцатеричной СС из внешней формы во внутреннюю.
Найти в строке два одинаковых фрагмента, не содержащих пробелы и имеющих максимальную длину и возвратить индексы их начала
В строке, содержащей абзац текста, найти концы предложений, обозначенный символом "точка". В следующих за ними словах первую строчную букву заменить на прописную. Между словами количество пробелов может быть любым.
Заменить в строке все восьмеричные целые константы на символы с соответствующими кодами, (например, xxx101yyy102zzz на xxx Ayyy102zzz).
Найти слово, начинающееся с самой младшей латинской буквы и возвратить индекс его начала.
Удалить из строки комментарии вида "/ ... /". Игнорировать вложенные комментарии.
Заменить в строке все большие латинские буквы на соответствующие им шестнадцатеричные коды (например, А на 0x41, в константе использовать 2 цифры для представления байта).
Заменить в строке все целые константы из любого количества цифр соответствующим повторением следующего за ними символа (например "abc5xacb15y" - " abcxxxxxacbyyyyyyyyyyyyyyy ").
Найти в строке и удалить из нее последовательность повторяющихся символов максимальной длины (например, "abcxxxxxacbyyyyyyyyyyyyyyyz" - "abcxxxxxacbz").
Найти в строке наиболее часто встречающийся символ и заменить его на пробел.
Найти все вхождения подстроки в строке. Строка и подстрока заданы в массивах символов. Результат – массив, заполненный индексами начала подстроки в строке, последовательность ограниченна -1.
Найти в строке самую внутреннюю пару скобок и удалить содержащийся между ними текст
Сортировки реализовать в полном соответствии с требованиями варианта.
Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы до конца массива сдвигаются на один влево. Сам элемент заносится на освободившуюся последнюю позицию.
Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем удаляется, а все последующие за ним элементы массива сдвигаются на один влево. Сам элемент переносится в новый массив.
Сортировка выбором. Выбирается минимальный элемент в массиве и запоминается. Затем на его место записывается «очень большое число», например, максимальное +1. Сам элемент переносится в новый массив.
Сортировка выбором. Выбирается максимальный элемент из оставшихся и меняется с последним из них (обратить внимание на диапазон неупорядоченной части).
Сортировка выбором. Выбирается минимальный элемент из оставшихся и меняется с первым из них (обратить внимание на диапазон неупорядоченной части).
Сортировка подсчетом. Выходной массив заполняется значениями “-1”. Затем для каждого элемента определяется его место в выходном массиве путем подсчета количества элементов строго меньших данного. Естественно, что все одинаковые элементы попадают на одну позицию, за которой следует ряд значений “-1”. После чего оставшиеся в выходном массиве позиции со значением “-1” заполняются копией предыдущего значения.
Сортировка вставками. Берется очередной элемент и извлекается из массива. Затем от начала массива ищется первый элемент, больший данного. Все элементы, от найденного до очередного сдвигаются на один вправо и на освободившееся место помещается очередной элемент. (Поиск места включения от начала упорядоченной части).
Сортировка вставками («всплытием»). Берется предпоследний элемент и меняется со следующим, пока не закончится массив и пока следующий будет меньше текущего. Затем берется предыдущий и т.д..
Сортировка вставками. Берется очередной элемент массива. Затем от начала выходного массива ищется первый элемент, больший данного. Все элементы, от найденного до последнего сдвигаются на один вправо и на освободившееся место помещается очередной элемент.
Сортировка выбором. Выбирается минимальный элемент в массиве и переносится в новый массив. Затем на его место записывается последний элемент исходного массива.
