Билеты по информатике.
1 билет. Концепция языка си, его достоинства и недостатки.
Концепция языка си: Си создавался с одной важной целью - сделать более простым написание больших программ с минимум ошибок по правилам процедурного программирования (то есть шаг за шагом), не добавляя на итоговый код лишних накладных расходов для компилятора.
Язык си является процедурным языком программирования, т.е он предоставляет возможность программисту определять каждый в процессе решения задачи. Особенность таких языков заключается в том, что задачи разбиваются на шаги и решаются шаг за шагом. Последовательно выполняемые операторы можно собрать в подпрограммы. Он относится в императивной парадигме программирования.
Парадигма программирования - совокупность идей и понятий, определяющих стиль написания компьютерных программ.
Императивное программирование - описывает процесс вычисления в виде инструкций, изменяющих состояние программы. Императивная программа очень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть последовательность команд, которые должен выполнить компьютер.
Си имеет некоторые особенности:
1) Простая языковая база, из которой вынесены в библиотеки многие существенные возможности, вроде математических функций или функций управления файлами.
2) Возможность типизации данных. Имеется система, предохраняющая от бессмысленных операций.
Неявное приведение - выполняется компилятором, при осуществлении арифметических операций, при выполнении операций сравнения и при присваивании переменные разных типов неявно приводятся к одному типу. Возможна потеря точности - отсекается дробная часть.
Явное приведение - выполняется программистом.
Тип определяется поведением, т.е набором действий, которые можно осуществлять над данными, принадлежащими к этому типу.
3) Использование предпроцессора;
Предпроцессор осуществляет подготовку программы к компиляции, включает содержимое одних файлов в другие, заменяет в тексте исходного кода имена констант на их значения, удаляет символы конца строки, заменяет комментарии на пустые строки. Что-то предпроцессор делает по умолчанию, а какие-то действия программируются с помощью специальных директив в исходном коде. Директивы предпроцессора начинаются со знака # и заканчиваются переходом на новую строку.
Простой пример:
#include <stdio.h>
#define MAX 100
int main()
{
#if MAX>99
printf("bla bla bla");
#endif
return 0;
}
Если находящееся за #if выражение истинно, то компилируется код, который находится между #if и #endif. В противном случае этот промежуточный код пропускается.
Эта программа вывод сообщения на экран потому что МАХ больше 99. Значение выражение, находящего за директивой #if, должно быть вычислено во время компиляции. Поэтому в этом выражении могут находиться только ранее определенные идентификаторы и константы - но не переменные.
4) Непосредственный доступ к памяти компьютера через использование указателей.
5) Передача параметров в функцию по значению, а не по ссылке (при этом передача по ссылке эмулируется с помощью указателей)
6) Области действия имен.
Обозначает область программы, в пределах которой имя некоторой переменной продолжает быть связанным с этой переменной и возвращать ее значение. За пределами области видимости тот же самый идентификатор может быть связан с другой переменной, либо быть свободным.
7) Структуры и объединения - определяемые пользователем собирательные типы данных, которыми можно манипулировать как одним целым;
Структуру можно использовать как тип данных для переменной;
- Переносимость - стандарт языка Си говорит, что программа может быть, как переносимой, так и не переносимой, в случае, если она использует системные функции операционной системы.
Си переносимый, поэтому в нем базовые целочисленные типы (short, int и др) не имеют строгого размера, а зависят от платформы. Однако эти типы не были бы переносимы, если бы их размеры были совершенно произвольные: стандарт устанавливает минимальные диапазоны принимаемых значений для всех базовых целочисленных типов.
- Системное программирование.
Вид программирования, который заключается в работе с системным ПО. Благодаря близости по скорости выполнения программ, написаны на Си, к языку ассемблера, этот язык получил широкое применение при создании системного программного обеспечения и прикладного программного обеспечения
- Универсальность
Заключается в том, что комплияторы существуют почти под все операционные системы
- Язык "высокого уровня"
Характеризуется краткостью выражений, современными управляющими конструкциями и структурами данных, богатым набором операций. Не слишком объемный, но отсутствие в нем каких-либо ограничений делает его более удобным, чем языки, считающиеся более мощными.
Структурное программирование - любая программа строится без использования операторы goto из трех базовых управляющих структур: последовательность, ветвление, цикл; кроме того используются подпрограммы. При это разработка программы ведется пошагово, методом сверху-вниз.
Недостатки языка си:
1) В связи со сравнительно низким уровнем языка многие случаи неправильного использования опасных элементов не обнаруживаются и не могут быть обнаружены ни при компиляции, ни во время исполнения. Иногда в результате неграмотного использования элементов языка появляются уязвимости в системе безопасности.
2) Возможны ошибки из-за слабой типизации
3) Механизм указателей. Указатель может ссылаться на любой объект в памяти, и неправильное использование указателей может порождать непредсказуемые эффекты. К примеру, в результате неверных арифметических операций над указателем, указывать произвольное место в памяти. Работа с таким указателем на незащищенных платформах это может привести к порче произвольных данных в памяти, причем эта порча может проявиться в самые произвольные моменты времени и намного позже момента порчи.
4) Проблемой является так же то, что автоматически и динамически создаваемые объекты не инициализируются и они могут содержать значения, оставшееся в памяти от ранее удаленных объектов. Такое значение полностью непредсказуемо, оно меняется от одной машины к другой, от запуска к запуску, от вызова функции к вызову. Если программа использует такое значение, то результат будет непредсказуемым и не обязательно проявится сразу.
5) Память не может быть использована снова, пока она не будет освобождена программистом с помощью функции free(). В результате прораммист может случайно забыть освобождать эту память, но продолжать ее выделять, занимая все большее и большее пространство. Это обозначается термином утечка памяти. Наоборот, возможно освободить память слишком рано, но продолжать ее использовать. Из-за того что система выделения может использовать освобожденную память по-другому, это ведет к непредсказуемым последствиям.
6) Относ��тельно высокая сложность изучения.
Достоинства языка си:
1) Язык си позволяет получать быстрые и компактные программы. Во многих случаях программы, написанные на Си, сравнимы по скорости с программами, написанными на языке ассемблера. При этом они имеют лучшую наглядность и их более просто сопровождать. Си сочетает эффективность и мощность в относительно малом по размеру языке.
2) Си - современный язык. Он включает в себя те управляющие конструкции, которые рекомендованы теорий и практикой программирования. Си обеспечивает полный набор операторов структурного программирования Предлагает большой набор операций. Многие операции Си соответствуют машинным командам, и поэтому допускают прямую трансляцию в машинный код. Разнообразие операций позволяет выбирать их различные наборы для минимизации результирующего кода.
3) Си - эффективный язык. Его структура позволяет наилучшим образом использовать возможности компьютеров. Программирование на этом языке отличается компактностью и быстротой исполнения.
4) Си - переносимый и мобильный язык. Компиляторы Си разрабатываются сравнительно легко благодаря простате языка и малому размеру стандартной библиотеки. К тому же, язык позволяет создавать переносимые программы и поддерживает в этом программиста. Программы, соответствующие стандарту языка, могут компилироваться на самых различных компьютерах.
5) Си - мощный и гибкий язык, удобный язык. Он достаточно структурирован, чтобы поддерживать хороший стиль программирования и вместе с тем не связан жесткими ограничениями.
2 билет. Двоичная система и что-то такое еще.
Для компьютера удобнее двоичная система. Для представления числа оно переводится в двоичную систему счисления. Это объясняется тем, что технически гораздо проще реализовать устройства с двумя, а не десятью устойчивыми состояниями. Можно считать, что одно из двух состояний означает единицу, другое - ноль. Поэтому обработку данных внутри компьютера можно воспринимать как преобразование слов из нулей и единиц по правилам, зафиксированным в микросхемах процессора.
Элемент последовательности из нулей и единиц (член такой последовательности) называют битом (один разряд в двоичной системе).
Для представления чисел в ЭВМ обычно используют битовые наборы - последовательности нулей и единиц фиксированной длины. Позиция в битовом наборе называется разрядом. Позиционная система - значение числового знака зависит от его позиции - разряда.
Представление целых в ЭВМ
Целые числа хранятся в формате с фиксированной запятой. Каждому разряду ячейки памяти соответствует один и тот же разряд числа, а запятая находится вне разрядной сетки, справа. Современные ячейки памяти имеют размер, равный одной и степеней двойки.
Для целых чисел существуют два представления: беззнаковое и со знаком. Отрицательные числа можно представлять только в знаковом виде. Знак числа обычно кодируется страшим битом машинного слова. Если старший бит 1 - число отрицательное, только если оно не определено как беззнаковое.
Беззнаковое представление: Максимальное значение целого неотрицательного числа достигается в случае, когда во всех ячейках хранятся единицы. Для n разрядного (n-количество бит) представления оно будет равно (2^n)-1. Например, максимальное число для 8-битовой ячейки - 255(все единицы). Если используется 32-разрядное машинное слово, то целое без знака: (2^32)-1 = 4294967295. Диапазон определяется количеством байтов (битов) компьютера, отводимых под одну переменную.
Целые отрицательные числа - самый левый (старший) разряд содержит информацию о знаке числа. Знак "плюс" кодируется нулем, а "минус" - единицей. Представление в компьютере положительных чисел с использованием формата "знак-величина" называется прямым кодом числа. Например, число 2002х10 = 11111010010х2 будет представлено в 16-разрядном представлении следующим образом:
Максимальное положительное число (с учетом выделения одного разряда на знак) для целых чисел со знаком n-разрядном представлении равно:
A=(2^n-1) -1;
В компьютерной технике применяются три формы записи целых чисел со знаком: прямой, обратный, дополнительный код.
Прямой код:
Представление числа в привычной форме "знак" - "величина", при которой старший разряд ячейки отводится под знак, а остальные - под запись числа в двоичной системе, называется прямым кодом двоичного числа.
Обратный код:
Получается инвертированием всех цифр двоичного кода абсолютной величины (модуля) числа, включая разряд знака: нули заменяются единицами, а единицы - нулями
Положительные числа в прямом, обратном и дополнительном коде абсолютно одинаковые.
Дополнительный код:
Получается образованием обратного кода с последующим прибавлением единицы к его младшему разряду.
Основные типы данных и операции над ними:
void - пустой тип, используется для создания указателей на переменную неизвестного типа и указания того, что функция не возвращает значений.
int - целочисленный тип. Количество числе в машинном изображении множества целых чисел зависит от длины машинного слова, обычно выражаемой в битах.
long - машинное слово увеличенной (двойной) размерности
Модификаторы signed и unsigned могут применяться к типу char и любому целочисленному. Для экономии места, если точно известно, что не будут записывать неотрицательные числа.
sizeof(short) <= sizeof(int) <= sizeof(long)
16 битная - 16 16 32
32х битная - 16 32 32
64х битная - 32 64 64
short (int) = (-32768 - 32767), 16 бит
unsigned short = (0 - 65535), 16 бит
long = (-2147483648 - 2147483647), 32 бита
unsigned long (0 - 4294967295), 32 бита
int (-2147483648 - 2147483647), 32 бита
unsigned int (0 - 4294967295), 32 бита
Так числа с плавающей точкой состоят из набора отдельных двоичных разрядов, услово разделенных на так называемые знак, порядок и мантиссу.
float - тип для вещественных чисел с плавающей точкой одинарной точности.
32 бита в памяти - одно машинное слово
double - тип для вещественных чисел двойной точности;
64 бита в памяти - два машинных слова;
char - символьный тип. Также этот тип может использоваться как целочисленный тип, к нему применимы спецификаторы знака. Размера типа равен 1 байту, может вмещать максимум 1 символ. Ее значениями являются различные символы из кодовой таблицы. Если в переменной типа чар хранится символ из набора, то его значение эквивалентно коду из этого набора и неотрицательно.
Обозначается, соответственно, как signed char и unsigned char. Знаковый тип может хранить в диапазоне от -128 до 127. Беззнаковый от - до 255. Под переменную типа char отводится 1 байт памяти (8бит).
Операции:
1) Арифметические операции (плюс минус деление умножение остаток от деления)
2) Операции отношения:
>, >=, <, <=
==, !=
Имеют более низкий приоритет по сравнению с арифметическими
3) Логические операции
&& - логическое и
|| - логическое "или"
&& выше чем ||
! - отрицание
Исключающее "или" - ^(XOR) - истинно, только если всего 1 из аргументов 1.
4) Подразрядные операции
Их можно применять к переменным, имеющим типы int, char, а также их вариантам ( например long int). Их нельзя применять к переменным типов float, double, long double.
Эти операции задаются следующими символами:
- ~ подразрядное отрицание
- << сдвиг влево
- >> сдвиг вправо
- & подразрядное и
- ^ подразрядное исключающее "или"
- | подразрядное "или"
Примеры:
если a = 00001111; b = 10001000;
~a = 11110000;
a<<1 = 00011110 (умножение на два). Сдвиг вправо числа со знаком может привести к заполнению этих битов значением знакового бита;
a>>1 = 00000111;
a&b = 00001000;
a^b = 10000111;
a|b = 10001111;
Условные выражение: выражение1 ? выражение2 : выражение3
Пример: z=(a>b) ? a:b; // максимальное из чисел a и b
Операции инкремента и декремента
Они предназначены для увеличения и уменьшения на единицу значения операнда. Операции ++ и — можно записывать как перед операндом, так и после него. В первом случае значение операнда (n) изменяется перед его использованием в соответствеющем выражении, а во втором - после его использования.
Преобразование типов
Если операнды одной операции имеют разные типы, то они преобразуются. (f+i = f);
Использовать float в качестве индекса массива нельзя. Помещение более длинного в более короткий тип ведет потерю информации. Неявные арифметические операции: "+" или "*" - более узкий тип расширяется до более широкого.
Особенности операций для вещественных чисел.
Вещественные числа в Си могут быть одного из трех типов: с одинарной точностью - float, с двойной точностью - double, и с расширенной точностью - long double.
Для вещественных чисел определены все стандартные арифметические операции. В отличие от целых чисел, операция нахождения остатка от деления для вещественных чисел не определена. Аналогично, все битовые операции и сдвиги к вещественным числам неприменимы; они работают только с целыми числами.
Если арифметическая операция применяется к двум вещественным числам разных типов, то менее точное число преобразуется в более точное.
Представление в ЭВМ вещественных чисел:
Формат чисел с плавающей запятой базируется на экспоненциальной форме записи, в которой может быть представлено любое число. Так число А может быть представлено в виде:
A = m × q^n
где m - мантисса числа;
q - основание системы счисления;
n - порядок числа.
32 бита - первый - знак; мантисса - 24 бита; 7 бит - порядок (экспанента);
Билет 3. Операторы и блоки.
Выражение наподобие x=0; i++; printf(...) становится оператором, если после него поставить точку с запятой;
В языке си точка с запятой - элемент оператора и его завершающая часть. Фигурные скобки служат для группировки объявлений и операторов в составные операторы и блоки.
Оператор if - else
Выражает процесс принятия альтернативных решений
if(выражение) оператор1 else оператор2
Часть с else необязательна. В начале ищем выражение, если оно истинно, то выполняется оператор1, если ложно и есть блок else, то выполняется оператор2.
Конструкция else-if.
If(выражение) Оператор Else if (выражение) Оператор Else if(выражение) Оператор Else if (выражение) Оператор Else Оператор
Такая последовательность представляет собой способ записи принятие многовариантного решения. Выражение меняются по порядку, если какое истинно, то выполняется оператор и проверка условий прерывается. Последний вариант - ничего из перечисленного.
Оператор switch
Используется для выбора одного из нескольких вариантов в зависимости от того, с какой из набора целочисленных констант совпадает значение некоторого выражения (целые или символьные переменные)
Switch (переменная)
{
case констант-выражение: операторы
case констант-выражение: операторы
default: операторы
}
Каждый из блоков имеет метку в виде константы с целочисленным значением или константного выражения. Если одна из меток совпадает со значением выражения, управление передается операторам этой метки. Все выражение после кейс должны быть различны. Блок дефолт в том случае, если не найдено ни одного соответствия. Если его нет, то операции никакие не выполняются.
break рекомендуется ставить даже в конце последнего блока дефолт. То есть после того как нашлось совпадение в одном из кейс, если явно не указан выход из оператора свитч, то программа выполняет последовательно все остальные ветки, записанные ниже той, с которой выполнено совпадение, пока не закончится оператор свитч или пока не будет явно указан выход из оператора.
Циклы while и for
Цикл while (цикл с предусловием). Сначала вычисляется выражение, если оно не равно 0, выполняется оператор, а потом выражение вычисляется снова до тех пор, пока оно не станет равно 0.
while (выражение) Оператор
/////
Цикл for (итерационный цикл, управляемый счетчиком):
for (выраж 1; выраж 2; выраж 3) Оператор
Что эквивалентно
Выраж 1;
While (выраж2)
{
Оператор;
Выраж3;
}
Бесконечный цикл for (;;;) нужен break или return. Или while(1);
Следует выбрать for, когда есть простая инициализация и инкрементирования переменных цикла, поскольку все управляющие элементы удобно сгруппированы в заголовке. Запятая в цикле фор - в заголовок можно вставлять несколько операторов.
Цикл do - while
Цикл с постусловием. Тело цикла выполняется всегда минимум 1 раз, условие проверяется после выполнения.
do Оператор while (выражение)
Операторы break и continue
Выход из цикла отличным от проверки условий в начале или конце. Принудительный выход из циклов фор вайл ду вайл.
Continue передает управление на следующую итерацию ближайшего цикла. В цикле вайл или ду это означает немедленную проверку условия, а в цикле фор - дополнительно выполняется инкрементирование.
for (i=0; i<n; i++)
{
if (a[i]<0) continue; // обработка только положительных
...
}
Оператор goto и метки
Никогда не необходим, но рекомендуется использовать. В основном, когда нужно прекратить работу структуры с большим количеством вложений и выйти сразу из двух и более вложенных циклов.
For(...)
For(...)
{
...
if(disaster)
Goto error;
}
...
Error: решение проблемы
После метки - двоеточие, можно ставить перед любым оператором в той же функции, где есть goto. Код всегда можно переписать или добавить проверку. Оператор goto передает управление на оператор, помеченный меткой. Помеченный оператор должен находиться в той же функции, что и оператор gotо, а используемая метка должна быть уникальной, то есть одно имя метки не может быть использовано для разных операторов программы. Имя метки - это идентификатор. Любой оператор в составном операторе может иметь свою метку. Используя оператор goto, можно передавать управление внутрь составного оператора. Но нужно быть осторожным при входе в составной оператор, содержащий объявления переменных с инициализацией, так как объявления располагаются перед выполняемыми операторами и значения объявленных переменных при таком переходе будут не определены
Оператор return
Оператор ретурн завершает выполнение функции, в которой он задан и возвращает управление в вызывающую функцию, в точку, непосредственно следующую за вызовом. Функция main передает управление операционной системе.
Значение выражения, если оно задано, возвращается в вызывающую функцию в качестве значения вызываемой функции. Если выражение опущено, то возвращаемое значение не определено.
Если в какой-либо функции отсутствует оператор return, то передача управления в вызывающую функцию происходит после выполнения последнего оператора вызываемой функции. При этом возвращаемое значение не определено. Если функция не должна иметь возвращаемого значения, то ее нужно объявлять с типом void. Таким образом, использование оператора return необходимо либо для немедленного выхода из функции, либо для передачи возвращаемого значения.
Инвариант
Инвариант - соотношение между значениями переменных цикла или некоторое утверждение о таких значениях, которые остаются неизменными на каждом шаге прохождения цикла. Следствие, является истинным при входе и выходе из цикла.
Инварианты используются в теории верификации программ для доказательства правильности выполнения цикла. Порядок доказательства работоспособности цикла с помощью инварианта сводится к следующему:
1) Доказывается, что выражение инварианта истинно перед началом цикла
2) Доказывается, что выражение инварианта сохраняет свою истинности после выполнения тела цикла; таким образом, по индукции, доказывается, что по завершении цикла инвариант будет выполняться.
3) Доказывается, что при истинности инварианта после завершения цикла переменные примут именно те значения, которые требуется получить (это элементарно определяется из выражения инварианта и известных конечных значениях переменных, на которых основывается условие завершения цикла).
4) Доказывается что цикл завершится то есть условие рано или поздно будет выполнено
5) Истинность утверждений доказанных на предыдущих этапах однозначно свидетельствует о том что цикл выполнится за конечное время и даст желаемый результат.
4 билет.
Алгоритм - это последовательность действий, приводящая к достижению результата.
“Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающихся детерменированностью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов”.
Программа - последовательность инструкций, предназначенных для исполнения устройством управления вычислительной машины. Программа - один из компонентов программного обеспечения. В зависимости от контекста рассматриваемый термин может относиться также и к исходным текстам программы.
Язык программирования - язык, предназначенный для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, определяющих внешний вид программы и действия, которые выполнит исполнитель(ЭВМ) под ее управлением.
5 билет.
Указатели.
Указатель - это переменная, значением которой является адрес некоторого объекта (обычно другой переменной) в памяти компьютера. Переменная, содержащая адрес другой переменной. Отдельные операции можно сделать только с их помощью, или позволяют более компактно записать код. Стандартное объявление нетипизированного указателя - void*. Используется в тех случаях, когда нужно иметь прямой доступ к памяти.
Объявление: тип*имя;
Тип указателя определяет тип объекта, на который указатель будет ссылаться.
Операция "&" (унарная) дает адрес объекта. Помещение адреса переменной типа чар c в переменную (указатель) p:
p = &c;
Операция применима к объектам оперативной памяти, нельзя использовать для констант и выражений.
Операция "*" - операция ссылки по указателю (разыменовывания). Ip = &x(x=1). Y=*ip=1;
Указатели и аргументы функций - чтобы в вызываемой функции изменить значения, передать указатели на переменную. Swap (&a,&b) - void swap (int*x, int*y)
{int temp; temp = *x; *x=*y;*y=temp;}
Массивы
Массив - это набор переменных одного типа, имеющих одно и то же имя. Доступ к конкретному элементу массива осуществляется с помощью индекса.
Объявление: тип имя_переменной [размер];
Одномерный массив - это список, хранящийся в непрерывной области памяти в порядке индексации.
Ниже - как хранится в памяти массив а, начинающийся по адресу 1000 и объявленный как int a[8];
Элемент [0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
Адрес 1000 1001 1002 1003 1004 1005 1006 1007
Запись a[i] - означает i-тый элемент массива.
Связь между указателями и массивами.
Int a[10]; int *pa;
Pa=&a[0] - указатель указывает на нулевой элемент массива, содержит адрес a0.
x=*pa - копирует содержимое элемента a0 в x;