Основы программирования - ответы
Количество вопросов - 211
x := 30;x := x * 5;
(x > 1 и y <= 10) или x == 0
double a[4][4];Во втором случае используется линейный массив из шестнадцатиэлементов:
double a[16];В первом случае обращение к элементу матрицы с индексамиi, j осуществляется с помощью выражения
a[i][j],во втором — с помощью выражения
a[4*i + j].Есть ли существенная разница в эффективности программыв первом и втором случаях при использовании оптимизирующегокомпилятора?
#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в результате выполнения этого фрагмента?
дано: цел n;цел x, y;x := 1; y := 4;цикл пока y <= n| инвариант: y = (x + 1)2;| x := x + 1;| y := y + 2*x + 1;конец циклаответ := x;
// Программа Поискдано: цел 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];
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?
цел 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);Какое условие является инвариантом цикла?(Через НОД и НОК обозначены наибольший общий делитель инаименьшее общее кратное.)
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?
int f(int x, int y);(т.е. имеет два целочисленных аргумента ивозвращает целочисленное значение).Локальные переменные и аргументы функцииадресуются относительно регистра FP, т.е. их адресаравны сумме содержимого FP и константы, задающей смещение.Чему равен адрес аргумента y функции?
1, 2, 3, +, *, 4, *, 5, *Чему равняется его значение?
x := 0;цикл пока x <= 100| . . .| x := x + 2;конец цикла
x := 1;y := 1;цикл пока A(x)| . . .| если y < 0| | то| | x := 2;| | y := 10;| | иначе| | x := 1;| | y := 20;| конец есликонец цикла
x := 1;цикл пока x < 100| x := -(x * 2);конец цикла
x := 1;цикл пока x != 120| x := x * 7;| если x <= 490| | то x := x - 490;| конец есликонец цикла
(x + y) + z, x + (y + z)для произвольных вещественных переменных x, y, zтипа double?
y != 0 и x/y <= 1
y > 0.1 и x / y >= 1.0?
вещ a[100]; цел i;. . .i := 0;цикл пока i < 99| a[i+1] := a[i];| i := i+1;конец циклаa[0] := a[99];
вещ последовательность 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;
цел последовательность 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. Можно ли упроститьпрограмму, использовав меньшее количество вспомогательныхпеременных? (Последовательность разрешается читать только один раз.)
утверждение: A(x)цикл пока B(x)| инвариант: A(x)| x := T(x)конец циклаЗдесь через A(x) и B(x)обозначены условия, зависящие от переменной x.Какое условие выполняется по окончании цикла?
дано: цел n;цел s, k;s := 10; k := 0;цикл пока s <= n| инвариант: s = 10 * (k + 1)| s := s + 10; k := k + 1;конец циклаответ := k;
дано: целые числа a >= 0, b > 0 цел q, r, e, m; q := 0; r := a; e := 1; m := b цикл пока r >= b | если 2*m <= r | | то e := e*2; m := m*2; | иначе если m > r | | то e := e/2; m := m/2; | иначе | | утверждение: m <= r и r < 2*m | | q := q + e; r := r - m; | конец если конец цикла // q и r -- частное и остаток от деления a на bКакое условие является инвариантом цикла?
вещ r, x; цел n;. . .r := r * x * x;r := r / ((n + 1) * (n + 2));n := n + 2;
дано: целые числа 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, 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;
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:
mov ESI, 0 ; ESI := 0 mov EDI, -2147483648 ; EDI := минус бесконечностьL1: ; метка начала цикла cmp ESI, ECX ; сравнить ESI с ECX jge L2 ; переход, если больше или равно mov EDX, [EBX] ; EDX := число с адресом EBX cmp EDX, EDI ; сравнить EDX с EDI jle L3 ; переход, если меньше или равно mov EDI, EDX mov EAX, ESI ; EAX := ESIL3: ; add EBX, 4 ; EBX := EBX+4 inc ESI ; увеличить ESI jmp L1 ; переход на метку L1L2: ; метка конца цикла
int *p, q[100];Укажите все корректные выражения языка Си среди перечисленныхниже:
int i = 10; while (i <= 1000) { i *= 2; }
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); }
double power(const double a, const double n);Можно ли в описании этой функции и ее прототипа опустить слова const?(Могут ли при этом в корректной программе возникнутьошибки или предупреждения на стадии компиляции?)
struct Line { int len; char *str; };и переменые
struct Line s1, *s2; int n; char c;Укажите все корректные выражения языка Си среди перечисленныхниже:
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 извлекает квадратный корень из вещественногочисла).
double a[4][4];Во втором случае используется массив из четырехэлементов типа «указатель на double»:
double *a[4];при этом элемент a[i] содержит адресначала i-й строки матрицы.В обоих случаях обращение к элементу матрицы с индексамиi, j осуществляется с помощью выражения
a[i][j].Есть ли существенная разница в эффективности программыв первом и втором случаях при использовании оптимизирующегокомпилятора?
#include <string.h>. . . int n; char a[32]; strcpy(a, "e2e4"); strcpy(a + 5, "c7c5"); n = strlen(a);Чему будет равно значение переменной nв результате выполнения этого фрагмента?
#include <string.h>#include <сtype.h>. . . int n, i; char a[32]; strcpy(a, "20e"); n = 0; i = 0; while (a[i] != 0) { n *= 16; if ('a' <= a[i] && a[i] <= 'f') { n += (a[i] - 'a') + 10; } else if (isdigit(a[i])) { n += a[i] - '0'; } ++i; }Чему будет равно значение переменной nв результате выполнения этого фрагмента?
0, 1, *, 2, -, 3, 4, *, 5, +, 6, *, +Чему равняется его значение?
10 10 moveto 20 30 lineto 30 10 lineto 15 20 moveto 25 20 lineto strokeЧто будет нарисовано в результате его выполнения?
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?
// Программа Быстрая сортировкадано: цел 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]
double sum(const double *a, int n);Можно ли в описании этой функции и ее прототипа опустить слово const?(Могут ли при этом в корректной программе возникнутьошибки или предупреждения на стадии компиляции?)
push x; push y; pop x; pop y;Что происходит с переменными x и y в результатеего выполнения?
static int *p = 0; . . . p = (int *) malloc(sizeof(int)); *p = 123;Где хранится значение выражения "*p" (т.е.число 123)?
int f(int x, int y) { int z; . . . }Локальные переменные и аргументы функцииадресуются относительно регистра FP, т.е. их адресаравны сумме содержимого FP и константы, задающей смещение.Чему равен адрес переменной z?
(x + y) + y, x + (y * 2.0)для произвольных вещественных переменных x, yтипа double?
вещ последовательность 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. Можно ли упроститьпрограмму, использовав меньшее количество вспомогательныхпеременных? (Последовательность разрешается читать только один раз.)
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" в байтах?
c:\Windows\system32\drivers\hostsкак текстовый для чтения и записи. Для этогоиспользуется следующий фрагмент программы:
FILE *f; . . . f = fopen( "c:\Windows\system32\drivers\hosts", "rt+" );Содержит ли он ошибку?
int find(char *s1, char *s2);функция возвращает смещение подстрокиs2 относительно начала строки s1в случае успеха или (-1) в случае неудачи.Можно ли воспользоваться функцией find в приведенном нижефрагменте программы(будут ли выданы сообщения об ошибках или предупрежденияпри компиляции этого фрагмента)?
void f(char s[1024], const char p[64]) { int pos = find(s, p); . . . }
цел 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;Какое условие является инвариантом цикла?
int n = 33; switch (n % 4) { case 1: n += 3; case 2: n += 2; case 3: ++n; break; default: ++n; }
вещ a[100]; вещ t; цел i;. . .i := 0;цикл пока i < 50| t := a[i];| a[i] := a[99 - i]; a[99 - i] := t;| i := i+1;конец цикла
z := 0;цикл пока x < y| . . .| если z > 100| | то| | z := 10; x := y;| | иначе| | z := 20; x := y - 1;| конец есликонец цикла
x := 1;цикл пока x < 11| x := -2*x + 11;конец цикла
x := 32760;x := x + 10;
1.0 <= x и x <= 1.0e+30 и x*x < 1000.0?
вещ a[100]; вещ t; цел i;a[0] = 0;. . .a[99] = 99;i := 0;t := a[0];цикл пока i < 99| a[i] := a[i+1];| i := i+1;конец циклаa[99] := t;
вещ последовательность p;вещ a, s; цел n;. . .s := минус бесконечность;n := 0;встать в начало последовательности p;цикл пока есть непрочитанные элементы в посл-ти p| прочесть очередной элемент посл-ти p в (вых: a);| если a > s| | то| | s := a; n := 1;| иначе если a == s| | то| | n := n + 1;| конец есликонец циклаответ := n;
вещ r, x; цел n;. . .r := -r * x;r := r * n / (n + 1);n := n + 1;
дано: основание 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;
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:
mov EAX, 0 ; EAX := 0L1: ; метка начала цикла 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 ; переход на метку L1L2: ; метка конца цикла
double *p; int i; . . . p = (double*) 1000; p += 10; i = (int) p;Чему будет равно значение переменной i в результатевыполнения этого фрагмента?
int n = 1000; while (n > 100) { n /= 2; }
struct Tree { struct Tree *left; struct Tree *right; void *value; };и переменые
struct Tree *t1, *t2; int m;Укажите все корректные выражения языка Си среди перечисленныхниже:
double *a[4];при этом элемент a[i] содержит адресначала i-й строки матрицы.Во втором случае используется линейный массив из шестнадцатиэлементов:
double a[16];В первом случае обращение к элементу матрицы с индексамиi, j осуществляется с помощью выражения
a[i][j],во втором — с помощью выражения
a[4*i + j].Есть ли существенная разница в эффективности программыв первом и втором случаях при использовании оптимизирующегокомпилятора?
#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в результате выполнения этого фрагмента?
1, 2, 3, +, *, 4, 5, *, -Чему равняется его значение?
10 10 moveto 20 30 lineto 10 50 lineto 30 50 moveto 20 30 lineto 30 10 lineto strokeЧто будет нарисовано в результате его выполнения?
10 10 moveto 10 40 lineto 10 20 moveto 30 40 lineto 15 25 moveto 30 10 lineto strokeЧто будет нарисовано в результате его выполнения?
(x - y) + (y * 2.0), x + yдля произвольных вещественных переменных x, yтипа double?
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:
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;
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" в байтах?
последовательность символов 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. Можно ли упроститьпрограмму, использовав меньшее количество вспомогательныхпеременных? (Последовательность разрешается читать только один раз.)
сделать стек пустым; цикл пока очередь непуста | x := взять элемент из начала очереди; | добавить (вход: x) в стек; конец цикла цикл пока стек непуст | x := взять элемент из стека; | добавить (вход: x) в конец очереди; конец циклаЧто произойдет с очередью в результатеего выполнения?
x := 64;цикл пока x*x > 100| x := -(x / 2);конец цикла
int n = 3, k = 5; while (n != k) { n = (n * 2) % 11; k = (k * 7) % 11; }
struct List { struct List *next; void *value; };и переменые
struct List e, *p; int m;Укажите все корректные выражения языка Си среди перечисленныхниже:
x := 0;цикл пока x < 1000| . . .| x := x + 1;конец цикла
x / y >= 1.0 и y > 0.1?
дано: цел n;цел s, k;s := 2; k := 0;цикл пока s <= n| инвариант: s = 2k+1| s := s * 2; k := k + 1;конец циклаответ := k;
дано: x > 0, a > 1, ε > 0надо: вычислить loga x с точностью εвещ y, z, t;y := 0.0; z := x; t := 1.0;цикл пока |t| >= ε или z <= 1.0/a или z >= a| инвариант: ay * zt = x| если z >= a| | то| | z := z/a; y := y + t;| иначе если z <= 1.0/a| | то| | z := z*a; y := y - t;| иначе| | z := z*z; t := t/2.0;| конец есликонец циклаответ := y;
#include <string.h>. . . int n; char a[32]; strcpy(a, "abcdefgh" + 5); strcpy(a + 4, "1234"); n = strlen(a);Чему будет равно значение переменной nв результате выполнения этого фрагмента?
int n = 0; int i = 2; switch (i) { case 2: n += 2; case 4: n += 2; break; default: n += 6; }
x := 1;цикл пока x != 144| x := x * 13;| если x <= 299| | то x := x - 299;| конец есликонец цикла(!= - означает "не равно")
x := 120;x := x + 40;
x := 1;цикл пока x != 56| x := x * 11;| если x <= 253| | то x := x - 253;| конец есликонец цикла
#include <string.h>. . . int n; char a[32]; strcpy(a, "e2e4e7e5"); strcpy(a + 2, "e3"); strcpy(a + 6, "e6d2d4"); n = strlen(a);Чему будет равно значение переменной nв результате выполнения этого фрагмента?
цел n, k, c;. . .c := c * (n + 1);c := c/(n + 1 - k);n := n + 1;
x := 100;цикл пока x >= 0| . . .| x := x - 1;конец цикла
static void onMul() { double y, x; assert(st_size() >= 2); // утв: глубина стека // не меньше двух y = st_pop(); x = st_pop(); st_push(x * y); display();}Правильно ли здесь используется конструкция «утверждение»,которая в Си реализуется функцией assert?
int *p, *q;Укажите все корректные выражения языка Си среди перечисленныхниже:
(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;
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 := EDXL3: ; add EBX, 4 ; EBX := EBX+4 dec ECX ; уменьшить ECX jmp L1 ; переход на метку L1L2: ; метка конца цикла