Ответы на курс: Основы программирования
Является ли индуктивной функция, которая последовательности
коэффициентов многочлена по убыванию степеней ставит
в соответствие пару чисел:
(степень многочлена, интеграл многочлена по отрезку [0, 1])?
Пусть описан тип R2Vector, представляющий вектор
на плоскости с вещественными координатами:
typedef struct {
double x;
double y;
} R2Vector;
также описаны три переменные u, v и w
типа вектор и вещественная переменная s:
R2Vector u, v, w;
double s;
при этом переменная u содержат конкретный вектор
единичной длины. Указать, чему будет
приблизительно равно значение переменной s в
результате выполнения следующего фрагмента программы:
v.x = (-u.y);
v.y = u.x;
w.x = u.x + v.x;
w.y = u.y + v.y;
s = sqrt(w.x * w.x + w.y * w.y);
(функция sqrt извлекает квадратный корень из вещественного
числа).
Целочисленная переменная x
представляет короткое целое число со знаком
в диапазоне -128…127 и занимает 1 байт.
Чему равно значение x после выполнения приведенного
ниже фрагмента программы?
x := 30; x := x * 5;
Всегда ли равны выражения
(x + y) + y, x + (y * 2.0)
для произвольных вещественных переменных x, y
типа double?
Указать, чему будет равно значение переменной n в результате
выполнения следующего фрагмента программы:
int n = 3, k = 5;
while (n != k) {
n = (n * 2) % 11;
k = (k * 7) % 11;
}
Какой механизм применяется для выполнения программы,
написанной на языке C#?
Что можно сказать об условии, указанном в заголовке цикла «пока»,
после полного завершения цикла?
Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?
x := 1; цикл пока x < 100 | x := -(x * 2); конец цикла
Завершится ли когда-нибудь выполнение цикла в приведенном ниже фрагменте программы (!= — означает «не равно»)?
x := 1; цикл пока x != 56 | x := x * 11; | если x <= 253 | | то x := x - 253; | конец если конец цикла
Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?
x := 1; цикл пока x < 11 | x := -2*x + 11; конец цикла
Какой механизм применяется для выполнения программы,
написанной на языке C++?
Указать, чему может быть равно значение переменной z
в результате выполнения следующего фрагмента программы:
z := 0; цикл пока x < y | . . . | если z > 100 | | то | | z := 10; x := y; | | иначе | | z := 20; x := y - 1; | конец если конец цикла
Сколько раз будет выполнено тело цикла в приведенной
ниже программе? Многоточием обозначен фрагмент,
не содержащий переменной x.
x := 0; цикл пока x < 1000 | . . . | x := x + 1; конец цикла
Пусть A = A(x) —
некоторое условие, зависящее только от
значения переменной x.
Указать, чему может быть равно значение переменной y
в результате выполнения следующего фрагмента программы:
x := 1; y := 1; цикл пока A(x) | . . . | если y < 0 | | то | | x := 2; | | y := 10; | | иначе | | x := 1; | | y := 20; | конец если конец цикла
В каком случае выполняется тело цикла «пока»?
Завершится ли когда-нибудь выполнение цикла
в приведенном ниже фрагменте программы?
x := 1; цикл пока x != 144 | x := x * 13; | если x <= 299 | | то x := x - 299; | конец если конец цикла
(!= — означает «не равно»)
Что представляет собой двоичный код мантиссы
вещественного числа 1.5 типа double?
Какова точность вычислений с вещественными
числами типа double?
Всегда ли равны выражения
(x + y) + z, x + (y + z)
для произвольных вещественных переменных x, y, z
типа double?
Всегда ли равны выражения
(x - y) + (y * 2.0), x + y
для произвольных вещественных переменных x, y
типа double?
Сколько двоичных разрядов отводится для хранения мантиссы
в двоичном коде вещественного числа типа double длиной 8 байтов?
Содержимое одного байта можно интерпретировать либо
как неотрицательное целое число в диапазоне 0…255,
либо как число со знаком в диапазоне -128…127.
Какое число со знаком имеет тот же двоичный код,
что и неотрицательное число 254?
Целочисленная переменная x
представляет короткое целое число со знаком
в диапазоне -32768…32767 и занимает 2 байта.
Чему равно значение x после выполнения приведенного
ниже фрагмента программы?
x := 32760; x := x + 10;
Содержимое двухбайтового слова можно интерпретировать либо
как неотрицательное целое число в диапазоне 0…65535,
либо как число со знаком в диапазоне -32768…32767.
Какое число со знаком имеет тот же двоичный код,
что и неотрицательное число 65533?
Целочисленная переменная x
представляет короткое целое число со знаком
в диапазоне -128…127 и занимает 1 байт.
Чему равно значение x после выполнения приведенного
ниже фрагмента программы?
x := 120; x := x + 40;
Сколько двоичных разрядов отводится под знак, порядок и мантиссу
в двоичном коде вещественного числа типа float длиной 4 байта?
Сколько двоичных разрядов отводится для хранения порядка
в двоичном коде вещественного числа типа double длиной 8 байтов?
Пусть x и y — вещественные
переменные типа double.
Может ли произойти прерывание из-за деления на ноль
при вычислении логического выражения
x / y >= 1.0 и y > 0.1?
Есть ли ограничение на длину текстовой строки в языке Си?
В каком алгоритмическом языке — в Паскале или в Си —
операция конкатенации (соединения) строк реализуется более
эффективно?
Пусть значения целочисленных переменных x и y
равны 100 и 10 соответственно.
Указать значение логического выражения
(x > 1 и y <= 10) или x == 0
В какой кодировке под символ отводится 2 байта?
Указать, что произойдет с элементами массива a
в результате выполнения следующего фрагмента программы:
вещ a[100]; вещ t; цел i; . . . i := 0; цикл пока i < 50 | t := a[i]; | a[i] := a[99 - i]; a[99 - i] := t; | i := i+1; конец цикла
В каком алгоритмическом языке — в Паскале или в Си —
операция нахождения длины строки реализуется более
эффективно?
Какой диапазон кодов символов используется в кодировке ASCII (стандарт ISO-646)?
Пусть значения целочисленных переменных x и y
равны 20 и 10 соответственно.
Указать значение логического выражения
y != 0 и x/y <= 1
Пусть x и y — вещественные
переменные типа double.
Может ли произойти прерывание из-за деления на ноль
при вычислении логического выражения
y > 0.1 и x / y >= 1.0?
Есть ли ограничение на длину текстовой строки в языке Паскаль?
Пусть значения целочисленных переменных x и y
равны 1 и 2 соответственно.
Указать значение логического выражения
(x >= 1 и y < 0) или (x <= 1 и y > 0)
Чему равен минимум пустой последовательности
целых чисел?
Что вычисляет следующий фрагмент программы?
вещ последовательность p; вещ a, s, x, y; . . . s := 0.0; x := 0.0; y := 0.0; встать в начало последовательности p; цикл пока есть непрочитанные элементы в посл-ти p | прочесть очередной элемент посл-ти p в (вых: a); | s := s + a - x; | x := y; y := a; конец цикла ответ := s;
Является ли индуктивной функция, которая последовательности
вещественных чисел ставит в соответствие сумму ее первого
и последнего элементов?
Следующий фрагмент программы вычисляет сумму четырех
последних элементов последовательности p:
вещ последовательность p;
вещ x, y, z, t;
. . .
x := 0.0; y := 0.0; z := 0.0; t := 0.0;
встать в начало последовательности p;
цикл пока есть непрочитанные элементы в посл-ти p
| x := y; y := z; z := t;
| прочесть очередной элемент посл-ти p в (вых: t);
конец цикла
ответ := x + y + z + t;
В нем используются четыре вспомогательные переменные
x, y, z, t. Можно ли упростить
программу, использовав меньшее количество вспомогательных
переменных? (Последовательность разрешается читать только один раз.)
Чему равен максимум пустой последовательности
вещественных чисел?
Рассмотрим функцию F, которая в последовательности
коэффициентов многочлена по возрастанию степеней
ставит в соответствие значение второй производной многочлена
в точке t. Какая из приведенных ниже функций на
последовательностях является индуктивным расширением
функции F?
На вход следующей программе передается
последовательность целых чисел в диапазоне от 0 до 9,
представляющая цифры десятичной записи целого числа n.
Программа определяет, делится ли число n на 75
(символом процента ‘%’ обозначается операция
нахождения остатка от деления первого числа на второе):
цел последовательность p; // Цифры числа n
цел s, r, d;
. . .
s := 0; r := 0;
встать в начало последовательности p;
цикл пока есть непрочитанные элементы в посл-ти p
| прочесть очередной элемент посл-ти p в (вых: d);
| s := s + d; // s -- сумма цифр
| r := (r % 10) * 10 + d; // r -- число из 2-х
конец цикла // последних цифр
ответ := ( // n делится на 75, когда
s % 3 == 0 и // s делится на 3 и
r % 25 == 0 // r делится на 25
);
В ней используются три вспомогательные переменные
s, r, d. Можно ли упростить
программу, использовав меньшее количество вспомогательных
переменных? (Последовательность разрешается читать только один раз.)
Функция F последовательности цифр в десятичной записи числа
n ставит в соответствие единицу, если n делится на 7,
и ноль в противном случае. Какая из приведенных
ниже функций на последовательности десятичных цифр числа n
является индуктивным расширением функции F?
Чему равно произведение пустой последовательности
вещественных чисел?
Что вычисляет следующий фрагмент программы?
вещ последовательность p; вещ a, s; цел n; . . . s := минус бесконечность; n := 0; встать в начало последовательности p; цикл пока есть непрочитанные элементы в посл-ти p | прочесть очередной элемент посл-ти p в (вых: a); | если a > s | | то | | s := a; n := 1; | иначе если a == s | | то | | n := n + 1; | конец если конец цикла ответ := n;
Является ли индуктивной функция, которая последовательности
коэффициентов многочлена по возрастанию степеней ставит
в соответствие пару чисел (степень многочлена, интеграл многочлена по отрезку [0, 1])?
Что вычисляет следующий фрагмент программы?
вещ последовательность p; вещ a, s; цел n; логическое b; . . . s := минус бесконечность; n := 0; b := ложь; встать в начало последовательности p; цикл пока есть непрочитанные элементы в посл-ти p | прочесть очередной элемент посл-ти p в (вых: a); | если a >= s | | то | | если не b или a == s | | | то | | | n := n + 1; | | конец если | | b := истина; | | s := a; | иначе | | b := ложь; | конец если конец цикла ответ := n;
Рассмотрим функцию F, которая последовательности
коэффициентов многочлена по убыванию степеней
ставит в соответствие значение второй производной многочлена
в точке t. Какая из приведенных ниже функций на
последовательностях является индуктивным расширением
функции F?
Функция F последовательности цифр в десятичной записи числа
n ставит в соответствие единицу, если n делится на 15,
и ноль в противном случае. Какая из приведенных
ниже функций на последовательности десятичных цифр числа n
является индуктивным расширением функции F?
Следующая программа вычисляет количество
вхождений фрагмента «xyz» в последовательность
символов:
последовательность символов p;
цел n;
символ c1, c2, c3;
. . .
n := 0;
// Инициализируем переменные c1, c2, c3 пробелами
c1 = ' '; c2 = ' '; c3 = ' ';
встать в начало последовательности p;
цикл пока есть непрочитанные элементы в посл-ти p
| c1 := c2; c2 := c3;
| прочесть очередной элемент посл-ти p в (вых: c3);
| если c1 == 'x' и c2 == 'y' и c3 == 'z'
| | то n := n + 1;
| конец если
конец цикла
ответ := n;
В ней используются четыре вспомогательные переменные
n, c1, c2, c3. Можно ли упростить
программу, использовав меньшее количество вспомогательных
переменных? (Последовательность разрешается читать только один раз.)
Указать, что вычисляет следующий фрагмент программы:
дано: цел n; цел s, k; s := 10; k := 0; цикл пока s <= n | инвариант: s = 10 * (k + 1) | s := s + 10; k := k + 1; конец цикла ответ := k;
Рассмотрим следующий фрагмент программы:
цел m, n;
цел a, b, p;
. . .
a := m; b := n;
p := 0;
цикл пока b != 0
| если b четное
| | то
| | b := b / 2;
| | a := a * 2;
| | иначе
| | b := b - 1;
| | p := p + a;
| конец если
конец цикла
ответ := p;
Какое условие является инвариантом цикла?
Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что n неотрицательно.
вещ r, x; цел n; . . . r := r * x * x; r := r / ((n + 1) * (n + 2)); n := n + 2;
Указать, что вычисляет следующий фрагмент программы:
дано: цел n; цел x, y; x := 1; y := 4; цикл пока y <= n | инвариант: y = (x + 1)2; | x := x + 1; | y := y + 2*x + 1; конец цикла ответ := x;
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма Евклида
вычисления НОД двух целых чисел:
дано: целые числа m, n, хотя бы одно отлично от нуля надо: вычислить наибольший общий делитель пары (m, n) цел a, b, r; a := m; b := n; цикл пока b != 0 | инвариант: НОД(a, b) == НОД(m, n) | r := a % b; // находим остаток от деления a на b | a := b; b := r; // заменяем пару (a, b) на (b, r) конец цикла ответ := a;
Пусть a — вещественный массив размера n
(индекс элементов меняется от 0 до n-1).
Определить, содержит ли следующий фрагмент программы ошибку
(т.е. действительно ли тело цикла сохраняет инвариант):
// Программа Быстрая сортировка
дано: цел n;
вещ a[n]; // вещественный массив размера n
цел m; // индекс медианы
утверждение: n >= 2 и
0 <= m и m < n;
надо: // разделить массив на три части:
// 1) слева элементы, меньшие медианы;
// 2) в центре медиана;
// 3) справа элементы, большие или равные медиане.
цел i, j, k; вещ t;
i := (-1); j := n;
цикл пока i+1 < m или m < j-1
| инвариант: a[0], a[1], ..., a[i] < a[m] и
| a[m] <= a[j], a[j+1], ..., a[n-1] и
| i < m и m < j
|
| если i+1 < m
| | то
| | если a[i+1] < a[m]
| | | то i := i+1; // расширяем левую часть
| | иначе если j-1 > m
| | | иначе
| | | утверждение: a[i+1] >= a[m];
| | | // меняем местами элементы a[i+1] и a[j-1]
| | | t := a[i+1]; a[i+1] := a[j-1]; a[j-1] := t;
| | | если j-1 == m
| | | | то m := i+1; // новое положение медианы
| | | конец если
| | | j := j-1; // расширяем правую часть
| | конец если
| | иначе
| | утверждение: j-1 > m;
| | . . . // этот случай рассматривается аналогично
| | . . . // случаю i+1 < m
| |
| конец если
конец цикла
утверждение: 0 <= m и m < n и
a[0], a[1], ..., a[m-1] < a[m] и
a[m] <= a[m+1], a[m+2], ..., a[n-1]
Выполняется ли инвариант цикла в процессе выполнения
тела цикла?
Пусть a — целочисленный массив размера n
(индекс элементов меняется от 0 до n-1),
элементы которого строго возрастают:
a[0] < a[1] <… < a[n-1].
Определить, содержит ли следующий фрагмент программы ошибку
(т.е. действительно ли тело цикла сохраняет инвариант):
// Программа Поиск
дано: цел n;
цел a[n]; // a[0] < a[1] < ... < a[n-1]
цел x; // искомый элемент
цел b, e, c;
. . . // рассматриваются исключительные случаи
утверждение: a[0] < x и x <= a[n-1]; // общий случай
b := 0; e := n - 1;
цикл пока e - b > 1
| инвариант: a[b] < x и x <= a[e];
| c := (b + e) / 2; // c -- целая часть (b+e)/2
| если x < a[c]
| | то e := c; // выбираем левую половину отрезка
| | иначе b := c; // выбираем правую половину отрезка
| конец если
конец цикла
утверждение: b == e - 1 и
a[b] < x и x <= a[e];
Указать, что вычисляет следующий фрагмент программы:
дано: цел n; цел s, k; s := 2; k := 0; цикл пока s <= n | инвариант: s = 2k+1 | s := s * 2; k := k + 1; конец цикла ответ := k;
Укажите, в какие моменты работы программы выполняется
инвариант цикла.
Пусть f(x) — целочисленная функция от целочисленного
аргумента. Определить,
содержит ли следующий фрагмент программы ошибку
(т.е. действительно ли тело цикла сохраняет инвариант):
// Программа корень функции цел a, b, c; . . . утверждение: a < b и f(a) * f(b) <= 0; // Значения функции на концах отрезка [a,b] разных знаков цикл пока b - a > 1 | инвариант: f(a) * f(b) <= 0 | // Делим отрезок [a, b] пополам | c := (a + b) / 2; // c -- целая часть (a+b)/2 | если f(a) * f(c) < 0 | | то b := c; // выбираем левую половину отрезка | | иначе a := c; // выбираем правую половину отрезка | конец если конец цикла утверждение: a == b - 1 и f(a) * f(b) <= 0;
Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что n > 0.
вещ r, x; цел n; . . . r := -r * x; r := r * n / (n + 1); n := n + 1;
Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что n не меньше k.
Восклицательным знаком обозначается операция вычисления факториала.
цел n, k, c; . . . c := c * (n + 1); c := c/(n + 1 - k); n := n + 1;
Рассмотрим следующий фрагмент программы:
цел m, n;
. . .
дано: m >= 0 и n >= 0
цел a, b, c;
a := m; b := n;
c := 1;
цикл пока a != 0 и b != 0
| если a четное и b четное
| | то a := a / 2;
| | b := b / 2;
| | c := c * 2;
| иначе если a четное
| | то a := a / 2;
| иначе если b четное
| | то b := b / 2;
| иначе
| | если a > b
| | | то a := a - b;
| | | иначе b := b - a;
| | конец если
| конец если
конец цикла
ответ := c * (a + b);
Какое условие является инвариантом цикла?
(Через НОД и НОК обозначены наибольший общий делитель и
наименьшее общее кратное.)
Как подключаются внешние устройства к шине?
Как располагаются разряды двоичного представления
целого числа внутри машинного слова
в архитектуре Little Endian (процессоры Intel, Alpha и т.п.)?
В какой аргумент помещается результат команды с
двумя аргументами (например, сложения) при использовании
Ассемблера «Masm» фирмы Microsoft для процессоров Intel 80×86?
Где располагаются элементы аппаратного стека?
Какой архитектуре соответствует представление целых
чисел в протоколах сети Internet?
Сколько аргументов имеют команды процессоров типа Motorola 68000?
Как передаются аргументы функций в языке Си?
Как располагаются разряды двоичного представления
целого числа внутри машинного слова
в архитектуре Big Endian (процессоры Motorola, Power PC и т.п.)?
Какой регистр процессора содержит текущий адрес
вершины стека?
Что содержат общие регистры процессора?
Для чего используется регистр FP?
Пусть регистры R1 и R2 содержат два целых числа x
и y. Указать, что будет содержать регистр R0 после выполнения
следующего фрагмента кода на RTL (знаком конъюнкции & обозначена
операция побитового логического умножения):
R0 := 0;
L1:
CC0 := R2 - 0; // сравнить R2 с нулем
if (eq) goto L2; // переход, если равно
CC0 := R2 & 1; // проверить младший бит R2
if (eq) goto L3; // переход, если ноль
R2 := R2 - 1;
R0 := R0 + R1;
goto L4;
L3:
R2 := R2 / 2;
R1 := R1 * 2;
L4:
goto L1;
L2:
Пусть регистр EBX содержит адрес массива целых
чисел, регистр ECX — количество элементов массива.
Указать, что будет содержать регистр EAX
в результате выполнения следующего фрагмента кода
на Ассемблере «Masm» для процессора Intel 80×86:
mov EAX, 2147483647 ; EAX := плюс бесконечность L1: ; метка начала цикла cmp ECX, 0 ; сравнить ECX с нулем jle L2 ; переход, если меньше или равно mov EDX, [EBX] ; EDX := число с адресом EBX cmp EDX, EAX ; сравнить EDX с EAX jge L3 ; переход, если больше или равно mov EAX, EDX ; EAX := EDX L3: ; add EBX, 4 ; EBX := EBX+4 dec ECX ; уменьшить ECX jmp L1 ; переход на метку L1 L2: ; метка конца цикла
В функции f языка Си описана одна целочисленная
переменная z:
int f(int x, int y) {
int z;
. . .
}
Локальные переменные и аргументы функции
адресуются относительно регистра FP, т.е. их адреса
равны сумме содержимого FP и константы, задающей смещение.
Чему равен адрес переменной z?
Какое прерывание происходит при попытке выполнить
деление на ноль?
Являются ли локальные переменные функции общими
для разных нитей (threads), работающих параллельно
в рамках одного процесса?
Что является причиной асинхронного прерывания?
Какой механизм используется для реализации виртуальной
памяти в многозадачных операционных системах?
Какие объекты операционной системы
обычно используются для исключения
одновременного доступа к критическим данным
из разных нитей или процессов?
Где размещаются описания прототипов глобальных функций
языка Си?
Рассмотрим следующий фрагмент программы:
double *p;
int i;
. . .
p = (double*) 1000;
p += 10;
i = (int) p;
Чему будет равно значение переменной i в результате
выполнения этого фрагмента?
Помещается ли число 80000 в переменную типа short
в 32-разрядной архитектуре?
Что означает описание «double (*a)[10]«?
Каковы размеры типов float и double в языке Си?
Что означает описание «char *a[10]«?
Чему равна вещественная константа 1000e-4,
записанная в экспоненциальной форме?
Что содержат заголовочные, или h-файлы, в случае
языка Си?
Чему равно значение выражения 1.5e-2*1000.0?
Чему равно значение выражения
((1234 & 255) << 2)?
Где размещаются определения глобальных и статических
переменных языка Си?
Что означает описание «int *f()«?
Указать, чему будет равно значение переменной n в результате
выполнения следующего фрагмента программы:
int n = 1000;
while (n > 100) {
n /= 2;
}
Где располагаются глобальные переменные?
Прототип функции, которая вычисляет сумму элементов массива a
длины n, выглядит следующим образом:
double sum(const double *a, int n);
Можно ли в описании этой функции и ее прототипа опустить слово const?
(Могут ли при этом в корректной программе возникнуть
ошибки или предупреждения на стадии компиляции?)
Пусть описан тип R2Vector, представляющий вектор
на плоскости с вещественными координатами:
typedef struct {
double x;
double y;
} R2Vector;
также описаны три переменные u, v и
w типа вектор и вещественная переменная s:
R2Vector u, v, w;
double s;
при этом известно, что переменные u и v
содержат два конкретных
вектора единичной длины.
Пусть в результате выполнения следующего фрагмента программы
значение переменной s приблизительно равно 0.7071,
т.е. корню из двух, деленному пополам:
w.x = (-u.y); w.y = u.x;
s = v.x * w.x + v.y * w.y;
// s == 0.7071
На какой угол надо повернуть вектор u,
чтобы получить вектор v?
Прототип функции, которая ищет вхождение строки
s2 в строку s1,
выглядит следующим образом:
int find(char *s1, char *s2);
функция возвращает смещение подстроки
s2 относительно начала строки s1
в случае успеха или (-1) в случае неудачи.
Можно ли воспользоваться функцией find в приведенном ниже
фрагменте программы
(будут ли выданы сообщения об ошибках или предупреждения
при компиляции этого фрагмента)?
void f(char s[1024], const char p[64]) {
int pos = find(s, p);
. . .
}
Пусть описана структура
struct Line {
int len;
char *str;
};
и переменые
struct Line s1, *s2;
int n; char c;
Укажите все корректные выражения языка Си среди перечисленных
ниже:
Указать, чему будет равно значение переменной n в результате
выполнения следующего фрагмента программы:
int n = 33;
switch (n % 4) {
case 1:
n += 3;
case 2:
n += 2;
case 3:
++n;
break;
default:
++n;
}
Прототип функции, вычисляющей степень n числа a,
выглядит следующим образом:
double power(const double a, const double n);
Можно ли в описании этой функции и ее прототипа опустить слова const?
(Могут ли при этом в корректной программе возникнуть
ошибки или предупреждения на стадии компиляции?)
Указать, чему будет равно значение переменной n в результате
выполнения следующего фрагмента программы:
int n = 0;
int i = 2;
switch (i) {
case 2:
n += 2;
case 4:
n += 2;
break;
default:
n += 6;
}
Пусть описан тип R2Vector, представляющий вектор
на плоскости с вещественными координатами,
typedef struct {
double x;
double y;
} R2Vector;
также описаны три переменные
u, v и w типа вектор
и вещественная переменная s:
R2Vector u, v, w;
double s;
при этом переменная u содержат конкретный вектор
единичной длины, а вектор v получается из
u вращением на 30 градусов по часовой
стрелке. Указать, чему будет приблизительно равно
значение вещественной переменной s в результате
выполнения следующего фрагмента программы:
w.x = (-u.y); w.y = u.x;
s = v.x * w.x + v.y * w.y;
Указать, чему будет равно значение переменной i в результате
выполнения следующего фрагмента программы:
int i = 10;
while (i <= 1000) {
i *= 2;
}
Где располагаются переменные, описанные внутри
функции, в описании которых отсутствуют модификаторы типа?
Является ли тип данных FILE частью языка Си?
Что делает следующий фрагмент программы на Си?
FILE *f;
. . .
f = fopen("tmp.dat", "rb+");
Рассмотрим два способа представления матрицы размера
4Ч4. В первом случае используется массив из четырех
элементов типа «массив из четырех элементов»:
double a[4][4];
Во втором случае используется массив из четырех
элементов типа «указатель на double»:
double *a[4];
при этом элемент a[i] содержит адрес
начала i-й строки матрицы.
В обоих случаях обращение к элементу матрицы с индексами
i, j осуществляется с помощью выражения
a[i][j].
Есть ли существенная разница в эффективности программы
в первом и втором случаях при использовании оптимизирующего
компилятора?
Обязательно ли при использовании данных типа FILE
подключать какие-либо стандартные заголовочные файлы?
Что делает следующий фрагмент программы на Си?
FILE *f;
. . .
f = fopen("tmp.dat", "wb+");
В операционной системе MS Windows
файл «tmp.dat» создается в результате выполнения следующего
фрагмента программы:
int a[4]; int i;
FILE *f = fopen("tmp.dat", "wb");
a[0] = 1; a[1] = 2; a[2] = 10; a[3] = 20;
for (i = 0; i < 4; ++i) {
fprintf(f, "%d\n", a[i]);
}
fclose(f);
Чему равен размер файла «tmp.dat» в байтах?
Рассмотрим следующий фрагмент программы:
#include <string.h>
#include <сtype.h>
. . .
int n, i;
char a[32];
strcpy(a, "11B");
n = 0; i = 0;
while (a[i] != 0) {
n *= 16;
if (isdigit(a[i])) {
n += a[i] - '0';
} else if ('A' <= a[i] && a[i] <= 'F') {
n += (a[i] - 'A') + 10;
}
++i;
}
Чему будет равно значение переменной n
в результате выполнения этого фрагмента?
Рассмотрим два способа представления матрицы размера
4Ч4. В первом случае используется массив из четырех
элементов типа «массив из четырех элементов»:
double a[4][4];
Во втором случае используется линейный массив из шестнадцати
элементов:
double a[16];
В первом случае обращение к элементу матрицы с индексами
i, j осуществляется с помощью выражения
a[i][j],
во втором — с помощью выражения
a[4*i + j].
Есть ли существенная разница в эффективности программы
в первом и втором случаях при использовании оптимизирующего
компилятора?
Содержит ли язык Си средства ввода-вывода?
Рассмотрим два способа представления матрицы размера
4Ч4. В первом случае используется массив из четырех
элементов типа «указатель на double»:
double *a[4];
при этом элемент a[i] содержит адрес
начала i-й строки матрицы.
Во втором случае используется линейный массив из шестнадцати
элементов:
double a[16];
В первом случае обращение к элементу матрицы с индексами
i, j осуществляется с помощью выражения
a[i][j],
во втором — с помощью выражения
a[4*i + j].
Есть ли существенная разница в эффективности программы
в первом и втором случаях при использовании оптимизирующего
компилятора?
Рассмотрим следующий фрагмент программы:
#include <string.h>
. . .
int n;
char a[32];
strcpy(a, "abcdefgh" + 5);
strcpy(a + 4, "1234");
n = strlen(a);
Чему будет равно значение переменной n
в результате выполнения этого фрагмента?
Пусть в ОС Windows XP требуется открыть файл
c:\Windows\system32\drivers\hosts
как текстовый для чтения и записи. Для этого
используется следующий фрагмент программы:
FILE *f;
. . .
f = fopen(
"c:\Windows\system32\drivers\hosts",
"rt+"
);
Содержит ли он ошибку?
В операционной системе MS Windows
файл «tmp.dat» создается в результате выполнения следующего
фрагмента программы:
int a[3]; int i;
FILE *f = fopen("tmp.dat", "wt");
a[0] = 1; a[1] = 10; a[2] = 100;
for (i = 0; i < 3; ++i) {
fprintf(f, "%d\n", a[i]);
}
fclose(f);
Чему равен размер файла «tmp.dat» в байтах?
Рассмотрим следующий фрагмент программы:
#include <string.h>
. . .
int n;
char a[32];
strcpy(a, "e2e4e7e5");
strcpy(a + 2, "e3");
strcpy(a + 6, "e6d2d4");
n = strlen(a);
Чему будет равно значение переменной n
в результате выполнения этого фрагмента?
Какая структура данных обычно используется
для передачи заданий драйверу операционной системы?
Даны очередь и стек элементов одного и того же типа. Можно ли
написать программу, которая удаляет из очереди предпоследний
элемент и не меняет порядка остальных элементов? При этом
разрешается использовать стек как вспомогательную структуру данных;
другими структурами (за исключением простых переменных)
пользоваться запрещено.
Рассмотрим фрагмент программы на языке PostScript:
10 10 moveto
20 30 lineto
30 10 lineto
15 20 moveto
25 20 lineto
stroke
Что будет нарисовано в результате его выполнения?
Рассмотрим следующую реализацию функции onMul,
которая исполняет команду умножения в проекте
«Стековый калькулятор»:
static void onMul() {
double y, x;
assert(st_size() >= 2); // утв: глубина стека
// не меньше двух
y = st_pop();
x = st_pop();
st_push(x * y);
display();
}
Правильно ли здесь используется конструкция «утверждение»,
которая в Си реализуется функцией assert?
Какая структура данных обычно используется
для сохранения состояния прерванного задания?
Обозначим через push и pop команды добавления
элемента в стек и извлечения элемента из стека.
Рассмотрим фрагмент программы на псевдокоде:
push x;
push y;
pop x;
pop y;
Что происходит с переменными x и y в результате
его выполнения?
Какая структура данных обычно используется
при передаче параметров подпрограммам и функциям?
Выражение содержит числа, переменную x и знаки четырех
арифметических операций (переменная x может
использоваться многократно). Выражение можно преобразовывать,
пользуясь известными свойствами арифметических операций.
Значение переменной x сообщается только после того,
как выражение преобразовано в удобную для вычисления форму.
Какой максимальной глубины стека достаточно, чтобы вычислить
значение любого такого выражения с помощью стекового
калькулятора (записывать промежуточные результаты на бумаге
запрещено)?
Рассмотрим следующую реализацию функции onSqrt,
которая исполняет команду извлечения квадратного корня в проекте
«Стековый калькулятор»:
static void onSqrt() {
double x;
if (st_empty()) {
printf("Stack empty.\n");
return;
}
x = st_pop();
assert(x >= 0.0); // утв: x неотрицательно
st_push(sqrt(x));
display();
}
Правильно ли здесь используется конструкция «утверждение»,
которая в Си реализуется функцией assert?
Выражение записано с использованием обратной польской
записи:
0, 1, *, 2, -, 3, 4, *, 5, +, 6, *, +
Чему равняется его значение?
Рассмотрим фрагмент программы на языке PostScript:
10 10 moveto
20 30 lineto
10 50 lineto
30 50 moveto
20 30 lineto
30 10 lineto
stroke
Что будет нарисовано в результате его выполнения?
Рассмотрим непрерывную реализацию множества с помощью
бинарного поиска. Пусть множество содержит миллион элементов.
Сколько операций сравнения может быть выполнено при поиске
элемента?
Бинарное дерево называется полным, если
длины всех путей к внешним (нулевым) вершинам одинаковы.
(Это означает, что у каждой нетерминальной вершины ровно
два сына, и длины всех путей от корня к терминальным вершинам
одинаковы и равны высоте дерева.) Высотой дерева называется
число вершин в пути максимальной длины от корня к
некоторой терминальной вершине, включая первую и последнюю вершины
пути. Сколько вершин в полном бинарном дереве высоты 10?
Может ли в красно-черном дереве число красных вершин
более чем в два раза превышать число черных вершин?
В хеш-реализации множества хеш-функция принимает 5 различных
значений с равной вероятностью, т.е. множество представляется
в виде объединения пяти непересекающихся подмножеств. Пусть
множество содержит 3 элемента. Какова вероятность того,
что все они попадут в разные подмножества?
Пусть требуется реализовать упорядоченный
набор различных элементов, при этом элементы можно
добавлять и удалять. Какая структура данных
лучше всего подходит для этого?
Текст представляет собой последовательность строк.
При этом строки можно изменять, удалять и добавлять
в любое место текста. Какая структура данных
лучше всего подходит для хранения и редактирования
такого текста?
В хеш-реализации множества хеш-функция принимает 4 различные
значения с равной вероятностью, т.е. множество представляется
в виде объединения четырех непересекающихся подмножеств. Пусть
множество содержит 4 элемента. Какова вероятность того,
что все подмножества будут непустыми?
На базе какой структуры данных удобно реализовать очередь?
Как оценивается сверху высота h сбалансированного (почти
сбалансированного) бинарного дерева в зависимости от числа
вершин n?
На базе какой структуры данных удобно реализовать
стек?
Пусть требуется реализовать упорядоченный набор элементов,
причем элемент может повторяться в наборе несколько раз.
Элементы можно добавлять к набору и удалять из набора. Какая
структура данных лучше всего подходит для этого?
Пусть у каждой нетерминальной вершины бинарного дерева есть
ровно два сына. Пусть в дереве 123 вершины. Какова
максимальная высота такого дерева? (Высотой дерева называется
число вершин в пути максимальной длины от корня к некоторой
терминальной вершине, включая первую и последнюю вершины
пути.)
Может ли в красно-черном дереве
длина одного пути от корня к терминальной вершине
равняться 20, длина другого — 10?
Что представляет собой двоичный код мантиссы
вещественного числа 0.75 типа double? Мантисса больше или равна 0 и меньше 1.
Можно ли сохранить произвольное целое число длиной в четыре
байта в вещественных переменных типа float и типа double без потери
точности?
Указать, что произойдет с элементами массива a
в результате выполнения следующего фрагмента программы:
вещ a[100]; цел i; . . . i := 0; цикл пока i < 99 | a[i+1] := a[i]; | i := i+1; конец цикла a[0] := a[99];
В каком алгоритмическом языке — в Паскале или в Си —
операция поиска конкретного символа в строке реализуется более
эффективно?
Диаметром множества вещественных чисел называется
максимум из абсолютных величин попарных разностей
его элементов. Рассмотрим функцию F, которая последовательности
вещественных чисел ставит в соответствие диаметр
множества ее элементов. Какая из приведенных ниже функций
на последовательностях является индуктивным расширением
функции F?
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма быстрого возведения в степень:
дано: основание a и показатель степени n >= 0 надо: вычислить a в степени n вещ b, p; цел k; b := a; p := 1.0; k := n; цикл пока k > 0 | инвариант: bk p = an | если k четное | | то | | k := k / 2; | | b := b * b; | | иначе | | k := k - 1; | | p := p * b; | конец если конец цикла ответ := p;
Локальные переменные функции языка Си адресуются
относительно регистра FP (Frame Pointer — указатель
кадра). Что содержится в ячейке памяти, адрес которой
записан в регистре FP, в процессе выполнения тела
функции?
Что больше в современных архитектурах:
объем физической памяти или объем виртуальной памяти?
Пусть регистр R1 содержит целое число n > 0.
Указать, что будет содержать регистр R0 после выполнения
следующего фрагмента кода на RTL:
R0 := 1;
R2 := 4;
L1:
CC0 := R2 - R1; // сравнить R2 c R1
if (gt) goto L2; // переход, если больше
R0 := R0 + 1;
R2 := R2 + R0;
R2 := R2 + R0;
R2 := R2 + 1;
goto L1;
L2:
Пусть регистр EBX содержит адрес массива целых
чисел, регистр ECX — количество элементов массива.
Указать, что будет содержать регистр EAX
в результате выполнения следующего фрагмента кода
на Ассемблере «Masm» для процессора Intel 80×86:
mov EAX, 0 ; EAX := 0 L1: ; метка начала цикла cmp EAX, ECX ; сравнить EAX с ECX jge L2 ; переход, если больше или равно mov EDX, [EBX] ; EDX := число с адресом EBX cmp EDX, 0 ; сравнить EDX с нулем je L2 ; переход, если равно add EBX, 4 ; EBX := EBX+4 inc EAX ; увеличить EAX jmp L1 ; переход на метку L1 L2: ; метка конца цикла
Может ли задача использовать объем виртуальной памяти,
который превышает объем физической памяти компьютера?
Пусть регистры R1 и R2 содержат два целых числа x
и y. Указать, что будет содержать регистр R0 после выполнения
следующего фрагмента кода на RTL (знаком конъюнкции & обозначена
операция побитового логического умножения):
R0 := 1;
L1:
CC0 := R2 - 0; // сравнить R2 с нулем
if (eq) goto L2; // переход, если равно
CC0 := R2 & 1; // проверить младший бит R2
if (eq) goto L3; // переход, если ноль
R2 := R2 - 1;
R0 := R0 * R1;
goto L4;
L3:
R2 := R2 / 2;
R1 := R1 * R1;
L4:
goto L1;
L2:
Чему равно значение выражения
((40 & 27) >> 2)?
Указать, чему будет равно значение переменной n в результате
выполнения следующего фрагмента программы:
int n = 1;
int i = 3;
switch (i) {
case 4:
n *= 7;
case 3:
n *= 5;
case 2:
n *= 3;
case 1:
n *= 2;
break;
default:
n = (-1);
}
Рассмотрим следующий фрагмент программы на Си:
static int *p = 0;
. . .
p = (int *) malloc(sizeof(int));
*p = 123;
Где хранится значение выражения «*p» (т.е.
число 123)?
Выражение записано с использованием обратной польской
записи:
1, 2, 3, +, *, 4, *, 5, *
Чему равняется его значение?
Пусть даны очередь и стек.
Рассмотрим фрагмент программы на псевдокоде:
сделать стек пустым;
цикл пока очередь непуста
| x := взять элемент из начала очереди;
| добавить (вход: x) в стек;
конец цикла
цикл пока стек непуст
| x := взять элемент из стека;
| добавить (вход: x) в конец очереди;
конец цикла
Что произойдет с очередью в результате
его выполнения?
Элементы множества хранятся в массиве в возрастающем
порядке. Пусть множество содержит 10 элементов.
Сколько операций сравнения достаточно выполнить,
чтобы найти произвольный элемент в множестве или убедиться в его
отсутствии?
В хеш-реализации множества хеш-функция принимает 10
различных значений с равной вероятностью. Пусть множество содержит
3 элемента. Какова вероятность коллизии? (Коллизией
называется ситуация, когда у двух элементов значения
хеш-функции совпадают.)
Что представляет собой двоичный код мантиссы
вещественного числа 2.5 типа double?
В каком алгоритмическом языке текстовая строка представляется
последовательностью байтов, в которой первый байт содержит
длину строки, а далее следуют коды символов, составляющих строку?
Функция F последовательности цифр в десятичной записи числа
n ставит в соответствие единицу, если n делится на 14,
и ноль в противном случае. Какая из приведенных
ниже функций на последовательности десятичных цифр числа n
является индуктивным расширением функции F?
Каков размер машинного слова в компьютерах
на базе процессора Intel 80386-80686?
Что содержат плавающие регистры процессора?
Какой регистр процессора содержит адрес инструкции,
которая будет выполняться на следующем шаге?
Где хранятся локальные переменные функции в языке Си?
Что содержит регистр флагов?
Сколько аргументов имеют команды процессоров типа Intel 80×86?
Каковы размеры типов short, int и long в 32-разрядной
архитектуре?
Чему равна вещественная константа 0.001e+4,
записанная в экспоненциальной форме?
Пусть описана структура
struct List {
struct List *next;
void *value;
};
и переменые
struct List e, *p;
int m;
Укажите все корректные выражения языка Си среди перечисленных
ниже:
Текстовый файл содержит последовательность
целых чисел в десятичной записи, каждое число записано
в отдельной строке. Какую функцию следует использовать
для последовательного считывания чисел?
Рассмотрим следующий фрагмент программы:
#include <string.h>
#include <сtype.h>
. . .
int n, i;
char a[32];
strcpy(a, "375e10");
n = 0; i = 0;
while (a[i] != 0) {
if (isdigit(a[i]) && a[i] < '8') {
n *= 8;
n += a[i] - '0';
} else {
break;
}
++i;
}
Чему будет равно значение переменной n
в результате выполнения этого фрагмента?
Выражение записано с использованием обратной польской
записи:
1, 2, 3, +, *, 4, 5, *, -
Чему равняется его значение?
Рассмотрим следующую реализацию функции onDiv,
которая исполняет команду деления в проекте
«Стековый калькулятор»:
static void onDiv() {
double y, x;
if (st_size() < 2) {
printf("Stack depth < 2.\n");
return;
}
y = st_pop();
x = st_pop();
assert(y != 0.0); // утв: y отлично от нуля
st_push(x / y);
display();
}
Правильно ли здесь используется конструкция «утверждение»,
которая в Си реализуется функцией assert?
