дипломы,диссертации,курсовые,контрольные,рефераты,отчеты на заказ

Основы алгоритмизации и языки программирования
(071900)
Сафьянова Е.Н.
Кафедра АСУ
Томск-2000

№ 1
Определение понятия “алгоритм”:
• Алгоритм - это заданная определенным образом последовательность действий, приводящая за конечное число шагов к решению поставленной задачи.

№ 2
Что такое структурное программирование?
• Это стиль программирования, основные принципы которого состоят в том, чтобы пользоваться при записи алгоритмов (программ) ограниченным набором конструкций.

№ 3
К базовым конструкциям структурного программирования относится:
• Конструкции следования, IF - THEN - ELSE, WHILE - DO.

№ 4
В чем состоит метод пошаговой детализации при составлении алгоритмов?
• В записи алгоритма вначале крупными блоками с последующим расписыванием их на более мелкие, доходя до элементарных действий.

№ 5
Что представляет собой идентификатор в языке Паскаль?
• Последовательность букв латинского алфавита, цифр и знаков подчеркивания, начинающуюся с буквы и не совпадающую с зарезервированными словами.

№ 6
Какова длина идентификатора в Паскале?
• Длина идентификатора произвольна, но значимыми считаются только первые 63 символа.

№ 7
Сколько различных идентификаторов содержится в перечне: MYSELF, MySelf, ELENA, myself, Elena?
• 2.

№ 8
Что является объектами программы на Паскале?
• Константы и переменные.

№ 9
Какие типы данных Паскаля считаются простыми стандартными типами?
• Целый, вещественный, логический, символьный.

№ 10
Чему равно значение выражения 31 div 10 * 2 + 25 mod 16 / 3?
• 9.

№ 11
Чему равно значение выражения NOT (n > 30) OR (n >= 5) AND (n < 12), если n = 35?
• TRUE.

№ 12
Чему равно значение выражения NOT n > 30 OR n >= 5 AND n < 12, если n = 25?
• Не знаю.

№ 13
Какие значения примут переменные a, b, c, d после выполнения следующего участка программы?

var a, b, c, d : integer;
begin
a := 1; b := 2; c := 3; d := 4;
if a > b then
if c < d then
if c > 0 then
c := 0
else
a := b;
if a > b then
if c < d then
if c > b then
d := c
else
else
else
a := b end;
• 2, 2, 3, 4.

№ 14
Укажите номер строки программы, в которой допущена ошибка, поставьте запятую, а затем без пробелов запишите строку правильно.

1) program rt;
2) var
3) list: array[1..10] of integer;
4) indx: integer;
5) a:integer;
6) begin
7) writeln('введите а');
8) read(a);
9) if a=2 then exit;
10) for indx:=1 to 10 do
11) list[indx]:=indx;
12) indx:= 1;
13) while (indx < 11) do
14) begin
15) list[indx]:= -list[indx] end;
16) for indx:=1 to 10 do
17) writeln(list[indx]);
18) end.
• 15*,*list*[*indx*]*:*=*-list*[*indx+]*;*indx*:*=*indx*+*1end

№ 15
Как задать шаг изменения параметра цикла в операторе FOR - TO - DO?
• Никак.

№ 16
Какой тип имеет параметр цикла в операторе FOR - TO - DO?
• Любой порядковый тип.

№ 17
Какой из операторов цикла FOR - TO - DO или WHILE - DO может применяться для более широкого круга задач?
• Оператор WHILE - DO.

№ 18
Сколько раз может выполняться тело цикла WHILE - DO?
• До тех пор, пока справедливо условие, проверяемое в заголовке оператора; может не выполниться ни одного раза.

№ 19
Сколько раз может выполняться тело цикла REPEAT - UNTIL?
• До тех пор, пока не справедливо проверяемое условие, но, по крайней мере, один раз.

№ 20
Что такое рекуррентный алгоритм?
• Это алгоритм, основанный на вычислении рекуррентных последовательностей.

№ 21
Что такое рекуррентная последовательность?
• Это бесконечная числовая последовательность, первые р элементов которой заданы, а каждый последующий вычисляется на основе р предыдущих.

№ 22
Каковы основные задачи, решаемые на заданной рекуррентной последовательности?
• Вычисление элемента с заданным номером, вычисление конечных и бесконечных сумм.

№ 23
В каких случаях задача вычисления бесконечной суммы рекуррентной последовательности имеет смысл?
• Только если элементы последовательности убывают по абсолютной величине.

№ 24
Основой алгоритма вычисления бесконечной суммы является:
• Цикл, работающий до тех пор, пока очередной элемент последовательности не станет по модулю меньше некоторого заданного малого числа #math ipsilon.

№ 25
Можно ли для вычисления бесконечных сумм использовать цикл типа FOR?
• Нельзя, потому что неизвестно, сколько раз должен проработать цикл.

№ 26
На чем основаны приближенные методы вычисления корней функции?
• На построении определенным образом последовательности шагов, приводящих от начального значения корня к значению, достаточно близкому к истинному.

№ 27
Какой из методов поиска корня функции реализует приведенный алгоритм?

READ (C, D, EPS);
A:=F (C); B:=F(C+D);
WHILE D>=EPS DO
BEGIN
 D:=D/2;
 IF A*B<0 THEN C:=C+D;
 ELSE BEGIN
 C:=C-D;
 B:=A;
 END;
 A:=F(C);
END;
• Метод дихотомии.

№ 28

READ (A,B, EPS); Y:=F(A);
IF Y*F(B)>0 THEN WRITELN ('неверные данные');
ELSE BEGIN
 FA:=Y;
 FB=F(B);
 WHILE ABS(Y)>=EPS DO
 BEGIN
 X:=A-(B-A)*FA/(FB-FA);
 Y:=F(X);
 IF Y*FB<0 THEN BEGIN
 A:=X; FA:=Y;
 END
 ELSE BEGIN
 B:=X; FB:=Y;
 END;
 END;
 WRITELN(X);
END
• Метод хорд.

№ 29
Данная рекуррентная последовательность: С0 - задано, Сi=Ci-1-(f(Ci-1) / f´(Ci-1)), i>0 справедлива для:
• Метода Ньютона.

№ 30
Для отыскания корня функции методом дихотомии достаточно знать:
• Начальное значение отрезка, в котором заведомо находится корень функции.
• Начальное приближение корня функции и начальное значение отрезка, в котором заведомо находится корень функции.

№ 31
Для отыскания корня функции методом Ньютона достаточно знать:
• Начальное приближение корня функции.

№ 32
Для отыскания корня функции методом линейной интерполяции достаточно знать:
• Начальное значение отрезка, в котором заведомо находится корень функции.

№ 33
Для отыскания корня функции методом итераций достаточно знать:
• Начальное приближение корня функции.

№ 34
При отыскании корня функции с помощью метода дихотомии вычисления функции производятся:
• В точке начального или очередного приближения корня и на одной из границ отрезка, в котором заведомо находится корень функции.

№ 35
При отыскании корня функции с помощью метода Ньютона вычисления функции производятся:
• В точке начального или очередного приближения корня.

№ 36
При отыскании корня функции с помощью метода линейной интерполяции вычисления функции производятся:
• На границах отрезка, в котором заведомо находится корень функции.

№ 37
При отыскании корня функции с помощью метода итераций вычисления функции производятся:
• В точке начального или очередного приближения корня.

№ 38
Какие из ошибок в программе обнаруживаются тестированием?
• “Описки” и некоторые алгоритмические ошибки.

№ 39
Какие из ошибок в программе обнаруживаются компилятором?
• “Описки”.

№ 40
Какие из ошибок в программе обнаруживаются методами верификации?
• Алгоритмические ошибки.

№ 41
Какие из ошибок в программе обнаруживаются с помощью программной защиты?
• Ошибки из-за неправильных данных.

№ 42
Для верификации каких алгоритмов используется метод математической индукции?
• Циклических.

№ 43
Для верификации каких алгоритмов используется метод перебора вариантов?
• Последовательных и ветвящихся.

№ 44
В чем суть метода перебора вариантов при доказательстве правильности алгоритма?
• В переборе различных вариантов проверяемых условий и доказательстве переработки алгоритмом предусловия в постусловие.

№ 45
В чем суть метода математической индукции при доказательстве правильности алгоритма?
• В доказательстве по следующей схеме.
Пусть P(n) - некоторое проверяемое условие. 1) непосредственной подстановкой проверяем, что P(n0) выполняется; 2) предполагаем, что P верно для некоторого n=k, k≥n0; 3) доказываем, что из предположения п.2) следует, что P будет верно для n=k+1.

№ 46
В чем состоит принципиальное различие процедуры и функции?
• В том, что процедура может возвращать в вызывающую программу несколько значений, а функция - лишь одно.

№ 47
В чем состоит отличие в описании процедуры и функции?
• В заголовке и в теле описания.

№ 48
В чем может состоять различие между формальными и фактическими параметрами процедуры или функции?
• В именах.

№ 49
Формальными параметрами процедуры и функции могут быть:
• Переменные, имена процедур и функций.

№ 50
Фактическими параметрами процедуры и функции могут быть:
• Константы, переменные, выражения, имена процедур и функций.

№ 51
Чем различаются параметры-значения и параметры-переменные процедуры?
• Способом описания в списке формальных параметров и тем, что параметры-значения могут быть только входными, а параметры переменные - и входными, и выходными.

№ 52
Дана процедура Minimax, определяющая значение и номер строки максимального элемента матрицы, а также значение и номер столбца максимального элемента матрицы:

procedure Minimax(matrix :mt;n,m:integer;var min,max,s:real;var a,b:integer);
 var
 i,j:integer;
 begin
 max:=matrix[1,1]; a:=1;
 min:=matrix[1,1]; b:=1;
 for i:=1 to n do
 for j:=1 to m do
 begin
 if matrix[i,j] > max then begin max:=matrix[i,j];a:=i end ;
 if matrix[i,j] < min then begin min:=matrix[i,j];b:=j end ;
 end;
 end {sedr};
Какой способ описания формальных параметров и внутренних переменных процедуры будет наиболее грамотным?
• Описание формальных параметров: procedure Minimax(matrix :mt;n,m:integer;var min,max,s:real;var a,b:integer); во внешней программе: type mt = array [1..10,1..10] of real. Описание внутренних переменных: var i,j:integer;

№ 53
В чем суть задачи информационного поиска?
• В нахождении в последовательности элемента с заданными свойствами его значения.

№ 54
Чем различаются алгоритмы нахождения минимального элемента и его номера в последовательностях с различными и совпадающими элементами?
• Ничем, кроме условия, оговаривающего, какой именно из совпадающих минимальных элементов ищется: первый или последний.

№ 55
Чем различаются алгоритмы нахождения номера элемента с заданным значением в упорядоченной и неупорядоченной последовательностях из различных элементов.
• В неупорядоченной последовательности алгоритм представляет собой полный перебор, в упорядоченной последовательности можно реализовать более быстрый алгоритм поиска.

№ 56
В чем суть алгоритма дихотомического поиска номера элемента с заданным значением в последовательности из различных элементов?
• В последовательном выборе среднего элемента последовательности и сравнении его с поисковой переменной. По результатам сравнения производится переход к одной из половин последовательности, где процесс повторяется.

№ 57
Под сортировкой понимают:
• Процесс перестановки элементов некоторой последовательности в порядке возрастания или убывания их ключей.

№ 58
Пусть М - число пересылок элементов массива при сортировке, а N - количество элементов массива. Какая оценка трудоемкости справедлива для простых методов сортировки?
• M∼ N2.

№ 59
Пусть М - число пересылок элементов массива при сортировке, а N - количество элементов массива. Какая оценка трудоемкости справедлива для наиболее эффективных методов сортировки?
• M∼ (log2N)*N.

№ 60
Какой из известных методов сортировки реализует следующий алгоритм?

Ввод (последовательность А);
I := 2;
WHILE I<=N DO
BEGIN
 J:=N;
 WHILE J>=I DO
 BEGIN
 IF A[J-1]>A[J]
 THEN
 BEGIN
 X:=A[J-1]; A[J-1]:=A[J];
 A[J]:=X;
 END;
J:=J-1;
END;
I:=I+1;
END;
• Простой обмен.

№ 61

 Ввод (последовательность А);
I:=1;
WHILE I<=N-1 DO
 BEGIN
 K:=I;
 X:=A[I];
 J:=I+1;
 WHILE J<=N DO
 BEGIN
 IF A[J]<X
 THEN
 BEGIN
 X:=A[J];
 K:=J;
 END;
 J:=J+1;
 END;
 A[K]:=A[I];
 A[I]:=X;
 I:=I+1;
END;
• Простой выбор.

№ 62

Ввод (последовательность А);
I:=2;
WHILE I ? N DO
BEGIN
 X:=A[I];
 J:=I-1;
 K:=0;
WHILE J>0 DO
 BEGIN
 IF A[J]<=A[I] THEN
BEGIN
 K:=J;
 J:=0;
END
ELSE J:=J-1;
 END;
J:=I;
WHILE J>K+1 DO
BEGIN
 A[J]:=A[J-1];
 J:=J-1;
END;
A[K+1]:=X;
I:=I+1;
END;
• Простые вставки.

№ 63
Какая идея лежит в основе метода сортировки простым выбором?
• Многократные просмотры последовательности (или ее части), при каждом из которых находится минимальный элемент и меняется местами с первым.

№ 64
- метода сортировки простым обменом?
• Многократные попарные сравнения соседних элементов последовательности и перестановка их в заданном порядке.

№ 65
- метода сортировки простыми вставками?
• Нахождение в отсортированной части последовательности места для очередного элемента не отсортированной части.

№ 66
- метода сортировки Шелла?
• Многократные попарные сравнения элементов отстоящих друг от друга на величину заданного шага, который постепенно уменьшается.

№ 67
- метода сортировки Хоара?
• Разделение массива на две части с помощью опорного элемента; процесс многократно повторяется для каждой из частей.

№ 68
Задана последовательность чисел 72 14 6 98 17 51 25 33. Производится сортировка последовательности по возрастанию простым выбором. Последовательность просматривается от начала к концу. Как будет выглядеть последовательность после четвертого просмотра?
• 6 14 17 25 72 51 98 33

№ 69
Задана последовательность чисел 72 14 6 98 17 51 25 33. Производится сортировка последовательности по возрастанию простым обменом. Последовательность просматривается от конца к началу. Как будет выглядеть последовательность после четвертого просмотра?
• 6 14 17 25 72 33 51 98

№ 70
Задана последовательность чисел 72 14 6 98 17 51 25 33. Производится сортировка последовательности по возрастанию простыми вставками. Последовательность просматривается от начала к концу. Как будет выглядеть последовательность после вставки четвертого элемента?
• 6 14 72 98 17 51 25 33

№ 71
Задана последовательность чисел 72 14 6 98 17 51 25 33. Производится сортировка последовательности по возрастанию методом Шелла. Последовательность просматривается от начала к концу. Как будет выглядеть последовательность после просмотра с шагом, равным четырем? Введите числа через пробелы.
• 17 14 6 33 72 51 25 98

№ 72
Задана последовательность чисел 25 98 6 72 7 88 14 51. Производится сортировка последовательности по возрастанию с помощью алгоритма Хоара. В качестве опорного выбирается первый элемент последовательности. Последовательность просматривается от конца к началу. Как будет выглядеть последовательность после первого разделения опорным элементом? Введите числа через пробелы.
• 14 7 6 25 72 88 98 51

№ 73
Как оценить трудоемкость методов сортировки?
• По количеству сравнений или пересылок элементов.

№ 74
Алгоритм называется рекурсивным, если он:
• В процессе выполнения обращается к самому себе.

№ 75
Рекурсивность - это:
• Свойство алгоритма решения задачи.

№ 76
Известна рекурсивная процедура вывода в обратном порядке цифр некоторого положительного числа N.

PROCEDURE REVERSE (N: INTEGER);
BEGIN
WRITE (N MOD 10);
IF (N DIV 10) 0
THEN REVERSE (N DIV 10)
END;
Чему равна глубина рекурсии при значении N = 2345?
• 3.

№ 77
Известна рекурсивная процедура, реализующая алгоритм известной игры “Ханойские башни”.

PROCEDURE HANOY (N, A, B, C: INTEGER);
BEGIN
IF N=1
THEN WRITELN (A, B);
ELSE
BEGIN
HANOY (N-1, A, C, B);
WRITELN (A, B);
HANOY (N-1, C, B, A)
END
END;
Пусть N = 3, А = 1, В = 2, С = 3. Что будет выведено на экран в результате работы процедуры?

1 2
1 3
2 3
1 2
3 1
3 2
1,2

№ 78
В каких случаях целесообразно использовать рекурсию?
• В случаях, когда не рекурсивное решение слишком громоздко.

№ 79
Каковы достоинства и недостатки рекурсивного подхода?
• Достоинство: краткость программы. Недостатки: неэкономное использование памяти, увеличение времени работы.

№ 80
Пусть переменная st описана как var st : string [10]; В каком интервале может изменяться номер элемента строки?
• От 0 до 10.

№ 81
Можно ли определить текущую длину строки, не используя стандартной функции?
• Можно. Она хранится в нулевом байте строки.

№ 82
Какие значения примут переменные i и j в результате выполнения следующей программы?

program stroka;
uses crt;
VAR str: array[1..10] of string;
 i:Integer;
 j:integer;
begin
 clrscr;
 str[1]:='asdfghjgjkwlofkvmneu';
 i:=length(str[1]);
 j:=ord(str[1,0]);
 end.
• 20 20

№ 83
Как происходит сравнение строк в Турбо Паскале?
• Посимвольно слева направо до первого несовпадения. Меньшей считается строка, код очередного из сравнивемых символов которой меньше. Строки разной длины сравнивать можно.

№ 84
Какие процедуры можно использовать при работе со строками в Турбо Паскале?
• DELETE, INSERT, STR, VAL.

№ 85
Какие функции можно использовать при работе со строками в Турбо Паскале?
• COPY, LENGTH.

№ 86
Какие операции можно производить над переменными X, Y комбинированного типа (запись)?
• Присваивание X := Y, остальные операции производятся только над компонентами записи в соответствии с их типом.

№ 87
Какие операции определены над данными перечисляемого типа?
• Присваивание значений из списка, заданного при определении типа, операции сравнения.

№ 88
Пусть даны следующие описания:
type colors = (red, white, black, blue);
var ton : color;
и выполнено присваивание ton := black;
Чему равны значения выражений: PRED (ton), SUCC (ton), ORD (ton)?
• white blue 2

№ 89
Что такое множество в языке Паскаль?
• Любой неупорядоченный набор данных одного типа.

№ 90
Каким может быть базовый тип элементов множества?
• Любым порядковым типом, содержащим не более 256 значений.

№ 91
Какие операции определены для данных типа множество?
• Операции +, - , *, =, <>, <=, >=, in.

№ 92
Чему равны значения выражений: [1, 2, 6, 7] + [2..6] * [3, 9], [3, 4, 5] * [1, 3, 6, 7] + [5..7] - [6]?
• [1,2,3,6,7]; [3,5,7]

№ 93
Пусть переменная М описана как SET OF 1..10 и выполнен оператор M := [2, 3, 5, 7]. Чему равны значения выражений: 5 in М, [2, 3, 4, 5] <= M, [] <= M, (6 in M) AND ([7] <= M)?
• TRUE FALSE TRUE FALSE

№ 94
Что представляет собой файл как тип данных в Паскале?
• Совокупность компонент одного типа (любого типа данных Паскаля, кроме файла), количество которых заранее не оговаривается.

№ 95
Какие разновидности файлов существуют в Паскале?
• Типизированные, не типизированные, текстовые и стандартные текстовые файлы.

№ 96
Какие процедуры реализуют установочные и завершающие операции над файлами в Паскале?
• ASSIGN, CLOSE, RESET, REWRITE.

№ 97
Какие процедуры и функции реализуют перемещения по файлу в Паскале?
• SEEK, FILEPOS, EOF, FILESIZE, TRUNCATE.

№ 98
Какие действия выполняет процедура TRUNCATE (f)?
• Удаляет “хвост” файла, начиная с текущей позиции (текущего значения указателя).

№ 99
Какие действия выполняет функция FILEPOS (f)?
• Возвращает номер элемента, на который установлен текущий указатель.

№ 100
Какие дополнительные процедуры и функции для работы с текстовыми файлами существуют в Паскале?
• EOLN, READLN, WRITELN, APPEND, SEEKEOF, SEEKEOLN.

на главную база по специальностям база по дисциплинам статьи

Другие статьи по теме

 
дипломы,курсовые,рефераты,контрольные,диссертации,отчеты на заказ