ПРИМЕРНЫЙ ПЕРЕЧЕНЬ
ЭКЗАМЕНАЦИОННЫХ ВОПРОСОВ (1 СЕМЕСТР)
Теоретическая часть:
Структурная схема ЭВМ. Основные функциональные устройства машины.
Согласно принципам фон Неймана компьютер должен иметь следующие устройства:
· процессор, осуществляющий арифметические и логические операции, а также организующий процесс выполнения программ;
· запоминающее устройство, или память для хранения программ и данных;
· внешние (периферийные) устройства для ввода/вывода информации.
Память должна состоять из некоторого количества пронумерованных ячеек, в каждой из которых могут находиться или обрабатываемые данные, или инструкции программ. Все ячейки памяти должны быть одинаково доступны для других устройств компьютера.
В общих чертах работу компьютера можно описать так. Вначале с помощью какого-либо периферийного устройства в память компьютера вводится программа. Процессор считывает содержимое ячейки памяти, где находится первая инструкция (команда) программы, и организует её выполнение. Эта команда может задавать выполнение арифметических или логических операций, чтение из памяти данных для выполнения арифметических или логических операций или запись их результатов в память, ввод данных из внешнего устройства в память или вывод данных из памяти на внешнее устройство.
Как правило, после выполнения одной команды процессор начинает обрабатывать команду из ячейки памяти, которая находится непосредственно за только что выполненной командой. Однако этот порядок может быть изменен с помощью команд управления (перехода). Эти команды указывают процессору, что ему следует продолжить выполнение программы, начиная с команды, содержащейся в некоторой другой ячейке памяти. Такой "скачок", или переход, осуществляется в программе не всегда, а только при соблюдении некоторых условий. Например, если некоторые числа равны, если в результате предыдущей арифметической операции получился нуль. Это позволяет использовать одни и те же последовательности команд в программе много раз (организовывать циклы), выполнять различные последовательности команд в зависимости от соблюдения определенных условий и т.д., одним словом, создавать сложные программы.
Таким образом, процессор выполняет инструкции программы автоматически, без вмешательства человека. Он может обмениваться информацией с памятью и внешними устройствами компьютера. Поскольку внешние устройства, как правило, работают значительно медленнее, чем остальные части компьютера, процессор может приостанавливать выполнение программы до завершения операции ввода-вывода с внешним устройством. Все результаты выполненной программы должны быть ею выведены на внешние устройства компьютера, после чего компьютер переходит к ожиданию каких-либо сигналов внешних устройств.
Определение алгоритма. Свойства алгоритмов.
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
1. Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных.
2. Дискретность - процесс решения задачи по алгоритму разбит на отдельные действия.
3. Однозначность - правила и порядок выполнения действий алгоритма имеют единственное толкование.
4. Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются.
5. Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.
6. Выполнимость - результата алгоритма достигается за конечное число шагов.
Способы записи алгоритмов (словесный, графический, на алгоритмическом языке).
Словесный способ
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задаётся в произвольном изложении на естественном языке.
Графический способ
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма, или блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа.
Алгоритмический способ
На алгоритмической языке каждое действие алгоритма записывается строго по правилам этого языка. Алгоритм, записанный на одном из языков программирования называется программой. В таком виде алгоритм может быть выполнен ЭВМ автоматически без участия человека.
Этапы решения задачи на ЭВМ.
В общем случае решение задачи на ЭВМ можно разбить на следующие этапы:
• постановка задачи;
• разработка алгоритма;
• составление программы;
• трансляция программы;
• отладка и выполнение программы;
• анализ результатов.
5. Структура программы на языке С++. Алфавит языка.
Структура программы на языке C++ представляет собой некоторую совокупность функций, из которых одна является главной и присутствует в каждой программе. Эта функция носит стандартное имя main и с неё начинается выполнение программы. Язык С++ является языком свободного формата, что позволяет размещать в строке как один, так и несколько операторов.
Алфавит
Множество символов языка C++ включает:
· прописные буквы латинского алфавита;
· строчные буквы латинского алфавита;
· арабские цифры;
· разделители:,.;:?! ' " | / \ ~ _ ^ () { } [ ] < > # % & - = + *
Остальные символы могут быть использованы только в символьных строках, символьных константах и комментариях. Язык C++ различает большие и маленькие буквы, таким образом, name и Name – разные идентификаторы
Литералы
Литералы в языке C++ могут быть целые, вещественные, символьные и строковые.
Целые:
· десятичные: 10, 132, -32179;
· восьмеричные (предваряются символом «0»): 010, 0204, -076663;
· шестнадцатеричные (предваряются символами «0х»): 0хА, 0x84, 0x7db3.
Вещественные: 15.75, 1.575e1,.75, -.125
Символьные: 'a', 'e', '.', '?', '2'.
Строковые: "строка".
Комментарии
Комментарий – это последовательность символов, которая игнорируется компилятором языка C++. Комментарий имеет следующий вид: /*<символы>*/. Комментарии могут занимать несколько строк, но не могут быть вложенными. Кроме того, часть строки, следующая за символами //, также рассматривается как комментарий.
Разумное использование комментариев (и согласованное употребление отступов) может сделать чтение и понимание программы более приятным занятием. При неправильном использовании комментариев читабельность программы может, напротив, серьезно пострадать. Компилятор не понимает смысл комментариев, поэтому не существует способа проверить, что комментарий:
· содержателен;
· имеет какое-то отношение к программе;
· не устарел.
Удачно подобранный и написанный набор комментариев является существенной частью хорошей программы. Написание «правильных» комментариев может оказаться не менее сложной задачей, чем написание самой программы.
6. Классификация типов, «дерево» типов в языке программирования С++.
В языке С++ обрабатываются переменные различных типов. Тип любого объекта определяет множество допустимых значений и множество допустимых операций над этими значениями. Любой идентификатор, используемый в исполняемых операторах, должен быть предварительно описан в любом месте программы, но обязательно до начала применения.
В этом строгом требовании языка С++ проявляется тенденция развития языков программирования в сторону повышения надежности создаваемых программ. При описании переменные можно инициализировать.
дерево типов:
Классификация:
Типы данных бывают следующие:
v Простые.
Ø Перечисляемый тип. Может хранить только те значения, которые прямо указаны в его описании.
Ø Числовые. Хранятся числа. Могут применяться обычные арифметические операции.
§ Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.
§ Вещественные: с запятой (то есть хранятся знак и цифры целой и дробной частей) и с плавающей запятой (то есть число приводится к виду m*be, где m — мантисса, b — основание показательной функции, e — показатель степени (порядок) (в англоязычной литературе экспонента), причём в нормальной форме 0<=m<b, а в нормализованной форме 1<=m<b, e — целое число и хранятся знак и числа m и e).
§ Числа произвольной точности, обращение с которыми происходит посредством длинной арифметики. Примером языка с встроенной поддержкой таких типов является UBASIC, часто применяемый среди криптографов.
Ø Символьный тип. Хранит один символ. Могут использоваться различные кодировки.
Ø Логический тип. Имеет два значения: истина и ложь, при троичной логике может иметь и третье значение — «не определено» (или «неизвестно»). Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.
Ø Множество. В основном совпадает с обычным математическим понятием множества. Допустимы стандартные операции с множествами и проверка на принадлежность элемента множеству. В некоторых языках рассматривается как составной тип.
v Составные (сложные).
Ø Массив. Является индексированным набором элементов одного типа. Одномерный массив — вектор, двумерный массив — матрица.
§ Строковый тип. Хранит строку символов. Аналогом сложения в строковой алгебре является конкатенация (прибавление одной строки в конец другой строки). В языках, близких к бинарному представлению данных, чаще рассматривается как массив символов, в языках более высокой абстракции зачастую выделяется в качестве простого.
Ø Запись (структура). Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи. Например, struct в C или record в Pascal.
Ø Файловый тип. Хранит только однотипные значения, доступ к которым осуществляется только последовательно (файл с произвольным доступом, включённый в некоторые системы программирования, фактически является неявным массивом).
Ø Класс.
v Другие типы данных. Если описанные выше типы данных представляли какие-либо объекты реального мира, то рассматриваемые здесь типы данных представляют объекты компьютерного мира, то есть являются исключительно компьютерными терминами.
Ø Указатель. Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило — указатель на переменную.
Ø Ссылка.
7. Вещественные и целые типы в языке программирования С++.
Целые типы:
| Длина, байт | Название типа | Назначение типа | Диапазон значений |
| unsigned char | Небольшие целые числа и коды символов | от 0 до 255 | |
| char | Очень малые целые числа и ASCII-коды | от -128 до 127 | |
| unsigned int | Большие целые и счетчики циклов | от 0 до 65535 | |
| int | Небольшие целые | от -32768 до 32767 | |
| short int | Небольшие целые | от -32768 до 32767 | |
| unsigned long | Астрономические расстояния | от 0 до 4294967295 | |
| long | Большие числа | от -2147483648 до 2147483647 |
Вещественные типы:
| Длина, байт | Название | Диапазон десятичного порядка | Количество значащих цифр |
| float | от -38 до +38 | от 7 до 8 | |
| double | от -308 до +308 | от 15 до 16 | |
| long double | от -4932 до +4932 | от 19 до 20 |
8. Перечисляемый тип в языке программирования С++.
Перечисляемый тип представляет собой ограниченную упорядоченную последовательность скалярных констант, составляющих данный тип. Значение каждой константы задается ее именем. Имена отдельных констант отделяются друг от друга запятыми, а вся совокупность констант, составляющих данный перечисляемый тип, заключается в круглые скобки.
В языках линии Си под тем же термином "перечисляемый тип" понимается нечто другое, поскольку при определении такого типа можно явно сопоставить имени значения некоторое целое (не обязательно положительное) число; при отсутствии явного задания целого первому элементу перечисляемого типа неявно соответствует 0, а каждому следующему — целое значение, на единицу большее целого значения предыдущего элемента. При этом (a) использование имени перечисляемого типа для объявления переменной эквивалентно использованию типа integer, и такая переменная может содержать любое целое значение; (b) имена значений перечисляемого типа на самом деле понимаются как имена целых констант, и к этим значениям применимы все операции над целыми числами, даже если они выводят за пределы множества целых значений элементов перечисляемого типа. Так что перечисляемый тип в смысле языка Си — это не совсем тип в строгом смысле этого слова, а скорее удобное задание группы именованных констант целого типа.
9. Использование указателей в языке программирования С++.
Известно, что данные хранятся в ячейках памяти компьютера. Все ячейки памяти пронумерованы. Номера ячеек памяти называются адресами. Указатели используются для работы с адресами. Указатель – это некоторое символическое представление адреса. Это означает, что будем работать с переменными, хранящими эти адреса. Описываются такие переменные следующим образом:
<тип> *<идентификатор>;
Такое описание синтаксически отличается от описания простой переменной только наличием знака * перед именем переменной. Как видно из описания, указатель всегда связывается с переменной какого-то определенного типа. Это позволяет определить, сколько байт памяти необходимо выделить по указанному адресу. В переменной типа указатель хранится адрес первого байта, выделенного участка памяти:
int *ptr, *ptr1;
float *p, *p1;
Над указателями можно выполнять следующие операции:
– Одному указателю можно присвоить значение другого указателя, если они ссылаются на один и тот же тип:
ptr = ptr1;
p1 = p;
– Значение указателя можно увеличить или уменьшить на константную величину:
ptr++;
ptr1 = ptr1-5;
p1 = p1+2;
– На самом деле ptr увеличивается не на 1, а на столько, сколько байт занимает целое число. Переменная ptr1 уменьшается на 5 умноженное на количество байт, выделяемых под целое число.
– Указателю можно присвоить значение адреса. Для получения адреса используется знакомый значок &:
int a, *ptr;
ptr = &a;
– Можно использовать операцию косвенной адресации. Эта операция обозначается значком * и позволяет получить доступ к значению переменной, на которую ссылается указатель:
int n = 12, *ptr, a;
ptr = &n;
а = *ptr;
После выполнения этого фрагмента переменная а будет иметь значение 12.
– Можно получить разность двух указателей. Это используется чаще всего для указателей, ссылающихся на один и тот же массив.
Здесь следует обратить внимание на то, что символы * и & имеют разное назначение в зависимости от контекста, в котором они используются.
10.Ввод данных (scanf, cin) в языке программирования С++.
(на 10 и 11) Ввод/вывод связан с обменом информацией между оперативной памятью и внешними устройствами. В языке С++ не предусмотрены какие-либо возможности для ввода и вывода. Поэтому, чтобы воспользоваться функциями ввода и вывода, необходимо с помощью директивы препроцессора подключить файл, содержащий заголовки стандартных функций.
Функция ввода scanf служит для чтения информации с клавиатуры и имеет следующий синтаксис:
scanf (управляющая строка, список ввода);
Здесь, управляющая строка-строка символов, содержащая спецификации преобразования. Каждому идентификатору из списка ввода должна соответствовать строго одна спецификация преобразования; cписок ввода - это последовательность из одного или более идентификаторов переменных строкового типа, а также любого целого или вещественного типа. Перед каждым идентификатором должен стоять символ &, который означает, что в функцию передается адрес переменной, а не значение. При вводе числовых переменных функция scanf вначале выделяет подстроку во входном потоке по следующему правилу: все ведущие пробелы, символы табуляции и маркеры конца строки пропускаются, выделяется первый значащий символ, признаком конца подстроки является любой из вышеперечисленных символов или символ конец файла. Выделенная таким образом подстрока рассматривается как символьное представление числовой константы, которое преобразуется в соответствии с типом переменной, и полученное значение присваивается переменной. Если значащих символов в строке нет, а список ввода еще не исчерпан, то автоматически осуществляется переход к новой строке.
Чтобы осмысленно пользоваться потоками ввода-вывода, необходимо иметь представление об объектно-ориентированном программировании. Поэтому будем пользоваться таким вводом-выводом формально:
сin – стандартный ввод, по умолчанию клавиатура;
Далее программа выводит запрос-подсказку пользователю, чтобы он ввел число. Число читается с клавиатуры, используя следующую инструкцию:
cin >> i;
В С++ оператор >> сохраняет свое значение сдвига вправо, но если он используется как показано выше, то служит оператором ввода числа с клавиатуры и записи его в переменную i. Идентификатор cin ссылается на клавиатуру. В общем случае можно использовать cin >> для загрузки переменных любого базового типа или строки.
можно свободно использовать любую функцию С для ввода данных, например, функцию scanf(), вместо cin >>.
11.Вывод данных (printf, cout) в языке программирования С++.
Функция вывода printf служит для чтения информации с клавиатуры и имеет следующий синтаксис:
printf (управляющая строка,список вывода);
Список вывода - это последовательность идентификаторов переменных, констант, выражений, вычисляемых перед выводом на печать. Каждому аргументу из списка вывода должна соответствовать одна спецификация преобразования.
Управляющая строка - это строка символов, содержащая информацию, печатаемую текстуально, спецификации преобразования и специальные символы. Управляющая строка определяет, каким образом будет распечатана информация. В С++ чаще всего используются следующие специальные символы:
\n – перевод курсора на новую строку;
\t – символ табуляции;
\b – шаг назад;
\r – возврат каретки.
Также можно использовать константу \007 (выдается короткий звуковой сигнал).
Спецификацию преобразования можно формально определить следующим образом:
%[флаг] [ширина] [.точность] [l, L] символ_формата
При описании синтаксиса в языках программирования принята нотация, означающая, что все, что стоит в квадратных скобках, является необязательным. В данном случае обязательными являются только символ % и символ_формата.
В качестве флага могут выступать следующие символы:
- выравнять значение по левому краю поля (т.е. добавить пробелы справа);
+ выравнять значение по правому краю поля, вывести обязательно знак значения.
При отсутствии флага выравнивание идет по правому краю и для неотрицательных значений знак не выводится.
Ширина определяет минимальный размер поля вывода. Если в выводимом числе символов больше, то поле автоматически увеличится. Точность используется для определения количества выводимых позиций после запятой в поле вывода вещественного числа. Маркер l или L служит для указания целых длинных типов (long).