Информатика и технология программирования

       

Экзаменационные билеты ( семестр )


по курсу "Информатика: алгоритмические языки и программирование" (семестр 1).

Билет 1.

1. Двоичная система счисления. Формы представления целых чисел со знаком и без знака, плавающая точка. Представление текста.

2. Оставить в строке не более чем по одному пробелу между словами.

Билет 2.

1. Представление отрицательных чисел. Дополнительный код.

2. Упорядочить массив в порядке возрастания (сортировка выбором). Ищется минимум из 0..n элементов и переставляется на первое место, ищется минимум из 1..n элементов и переставляется на второе и т.д..

Билет 3.

1. Базовые типы данных в Си: char,int,long,float,double. Модификатор типа unsigned. Особенности типа данных char. Связь с формами представления данных в ЭВМ.

2. Заменить в строке маленькие латинские буквы на большие.



Билет 4.

1. Понятие массива. Особенности определения и использования массивов в Си. Понятие индекса.

2. Подсчитать в строке количество фрагментов, симметричных относительно центрального символа (например, "abcba"), и содержащих не менее 5 символов.

Билет 5.

1. Массивы символов, строки. Работа со строками в Си.

2. Упорядочить массив в порядке возрастания методом пузырька. Сравниваются элементы 0-1,1-2,2-3,...,n-2-n-1 и переставляются, если они не в порядке возрастания. Цикл повторяется, пока число перестановок при просмотре не станет равным 0.

Билет 6.

1. Понятие переменной. Глобальные (внешние) и локальные (автоматические) переменные программы. Определение типа переменных. Инициализация простых переменных и массивов.

2. Преобразовать строку символов, содержащую число в десятичной системе в двоичную систему (целое типа int).

Билет 7.

1. Программа на Си как совокупность переменных и функций. Общая схема синтаксиса функции. Заголовок, результат, формальные параметры, тело функции. Фактические параметры.

2. Найти подстроку в строке. Строка и подстрока заданы в массивах символов. Результат - индекс начала подстроки в строке или -1.

Билет 8.

1. Формальные и фактические параметры функции.
Способ передачи параметров функции в Си. Использование стека при вызове функции.

2. Подсчитать количество повторений наиболее часто встречающейся латинской буквы в заданной строке.



Билет 9.

1. Операции. Выражения. Классификация операций: арифметические, сравнения, логические, машинно-ориентированные, выделения составляющего типа данных. Особенности выполнения операций на Си: приоритеты, направление выполнения.

2. Двоичный поиск индекса (позиции) заданного значения в упорядоченном массиве.



Билет 10.

1. Явные и неявные преобразования типов данных в выражениях.

2. Подсчитать количество слов в строке. Слово - любая последовательность символов, кроме пробела.



Билет 11.

1. Операторы. Роль символа ";". Основные операторы в Си: if, while, do-while, for, switch, continue, break, return, goto. Вложенность операторов.

2. Сформировать массив простых множителей для заданного числа. Очередной множитель определяется попыткой деления нацело числа на все уже накопленные простые числа.



Билет 12.

1. Арифметические операции. "Смысл" операций "%" и "/". Работа с цифрами числа. Особенности выполнения операции присваивания. Ошибки преобразования типов данных в арифметических операциях.

2. Сортировка погружением: если имеется уже отсортированная часть массива, то очередной элемент справа от нее погружается (обменом) до тех пор, пока не натолкнется на меньший элемент.



Билет 13.

1. Структуры данных. Использование массива для представления структур данных: последовательность (строка), стек, очередь.

2. Преобразовать значение переменной типа int во внутренней форме представление в строку символов, представляющих это значение в десятичной системе.



Билет 14.

1. Работа со строками в Си как с последовательностями. Примеры: поиск конца строки, просмотр строки, копирование строки, добавление символа к строке. Стандартные функции ввода-вывода символов и строк.

2. Определить в массиве максимальную длину последовательности расположенных подряд возрастающих значений.





Билет 15.

1. Трансляция и ее фазы: препроцессор, лексический, синтаксический и семантический анализ, генерация кода. Понятие компилятора и интерпретатора.

2. Сортировка подсчетом. Для заданного элемента массива его место в выходном массиве определяется количеством элементов, меньших его во входном (учесть наличие одинаковых).



Билет 16.

1. Модульное программирование.
Объектный модуль, библиотека, связывание, компоновщик (LINK).

2. Преобразовать дробную часть переменной типа double в строку символов (путем последовательного умножения дробной части на 10).



Билет 17.

1. Технология структурного программирования: модульное, пошаговое, нисходящее проектирование программ (функций и данных).

2. Преобразовать значение переменной типа int во внутренней форме в строку символов, содержащих его представление в шестнадцатеричной системе.



Билет 18.

1. Понятие стека и очереди как способов организации данных. Представление стека и очереди в массиве.

2. Преобразовать строку символов, содержащих представление шестнадцатеричного числа в переменную типа int во внутренней форме.



Билет 19.

1. Циклические программы. Итерационный цикл. Программы вычисления суммы ряда, корня функции.

2. Найти в строке максимальное количество одинаковых подряд идущих символов (например, "aaaaaaa").



Билет 20.

1. Сортировка и поиск. Линейный и двоичный поиск. Сортировка. Классификация алгоритмов сортировки. Трудоемкость линейного поиска, двоичного поиска и сортировки.

2. Найти наименьшее общее кратное для всех элементов массива - минимальное число, которое делится на все элементы массива без остатка.



Билет 21.

1. Понятие слияния упорядоченных последовательностей. Сортировка слиянием. Сортировка путем однократного слияния.

2. Сортировка однократным слиянием. Массив из N элементов разделяется на M частей, каждая из которых сортируется независимо, затем данные сливаются обратно во входной массив.



Билет 22.

1. Понятие слияния упорядоченных последовательностей. Сортировка слиянием.


Сортировка путем циклического распределения-слияния.

2. Написать функцию проверки, является ли заданное число простым. С ее помощью написать программу поиска простых чисел в диапазоне 1000-2000, две любые части которого - также простые (например, 1997, 1-997,19-97,199-7)



Билет 23.

1. Сортировка разделением. Понятие медианы. Рекурсивный характер сортировки разделением. "Быстрая сортировка".

2. Сформировать массив простых чисел в диапазоне от 2 до заданного. Очередное простое число определяется попыткой деления нацело числа на все уже накопленные простые числа.



Билет 24.

1. Основы анализа программ. "Смысл" переменных в базовых фрагментах -признак, счетчик, накопитель, максимум (примеры). "Смысл" переменных при завершении циклов.

2. Написать программу поиска чисел в диапазоне 100-10000, для которых куб суммы цифр равен значению самого числа (например 512 - 5+1+2=8).



Билет 25.

1. Последовательность как структура данных. Основные операции над последовательностью (добавление, удаление, включение).

Удалить из строки все комментарии вида /*...*/.














Содержание раздела