Ответы к контрольной работе: Основы программирования

Чему равно значение выражения((1234 & 255) << 2)?

Является ли индуктивной функция, которая последовательностикоэффициентов многочлена по возрастанию степеней ставитв соответствие пару чисел (степень многочлена, интеграл многочлена по отрезку [0, 1])?

Пусть регистр EBX содержит адрес массива целыхчисел, регистр ECX — количество элементов массива.Указать, что будет содержать регистр EAXв результате выполнения следующего фрагмента кодана Ассемблере "Masm" для процессора Intel 80x86: 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: ; метка конца цикла

Что вычисляет следующий фрагмент программы?вещ последовательность 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;

Бинарное дерево называется полным, еслидлины всех путей к внешним (нулевым) вершинам одинаковы.(Это означает, что у каждой нетерминальной вершины ровнодва сына, и длины всех путей от корня к терминальным вершинамодинаковы и равны высоте дерева.) Высотой дерева называетсячисло вершин в пути максимальной длины от корня кнекоторой терминальной вершине, включая первую и последнюю вершиныпути. Сколько вершин в полном бинарном дереве высоты 10?

Какая структура данных обычно используетсядля сохранения состояния прерванного задания?

Рассмотрим функцию F, которая в последовательностикоэффициентов многочлена по возрастанию степенейставит в соответствие значение второй производной многочленав точке t. Какая из приведенных ниже функций напоследовательностях является индуктивным расширениемфункции F?

Пусть значения целочисленных переменных x и yравны 1 и 2 соответственно.Указать значение логического выражения (x >= 1 и y < 0) или (x <= 1 и y > 0)

В какой аргумент помещается результат команды сдвумя аргументами (например, сложения) при использованииАссемблера "Masm" фирмы Microsoft для процессоров Intel 80x86?

Пусть p и q — два указателя на целочисленное значение: int *p, *q;Укажите все корректные выражения языка Си среди перечисленныхниже:

Рассмотрим следующую реализацию функции onMul,которая исполняет команду умножения в проекте«Стековый калькулятор»:static void onMul() { double y, x; assert(st_size() >= 2); // утв: глубина стека // не меньше двух y = st_pop(); x = st_pop(); st_push(x * y); display();}Правильно ли здесь используется конструкция «утверждение»,которая в Си реализуется функцией assert?

Содержит ли язык Си средства ввода-вывода?

Выполняется ли инвариант цикла в процессе выполнениятела цикла?

Рассмотрим функцию F, которая последовательностикоэффициентов многочлена по убыванию степенейставит в соответствие значение второй производной многочленав точке t. Какая из приведенных ниже функций напоследовательностях является индуктивным расширениемфункции F?

Где размещаются определения глобальных и статическихпеременных языка Си?

Сколько двоичных разрядов отводится для хранения порядкав двоичном коде вещественного числа типа double длиной 8 байтов?

Каков размер машинного слова в компьютерахна базе процессора Intel 80386-80686?

Как передаются аргументы функций в языке Си?

Сколько раз будет выполнено тело цикла в приведеннойниже программе? Многоточием обозначен фрагмент,не содержащий переменной x.x := 100;цикл пока x >= 0| . . .| x := x - 1;конец цикла

Какое утверждение является инвариантом для следующегофрагмента программы (т.е. из справедливости утверждениядо выполнения фрагмента программы вытекает справедливость утвержденияпосле выполнения)? Предполагается, что n не меньше k.Восклицательным знаком обозначается операция вычисления факториала.цел n, k, c;. . .c := c * (n + 1);c := c/(n + 1 - k);n := n + 1;

Рассмотрим следующий фрагмент программы:#include . . . int n; char a[32]; strcpy(a, "e2e4e7e5"); strcpy(a + 2, "e3"); strcpy(a + 6, "e6d2d4"); n = strlen(a);Чему будет равно значение переменной nв результате выполнения этого фрагмента?

Завершится ли когда-нибудь выполнение цикла в приведенном ниже фрагменте программы (!= - означает "не равно")?x := 1;цикл пока x != 56| x := x * 11;| если x <= 253| | то x := x - 253;| конец есликонец цикла

Функция F последовательности цифр в десятичной записи числаn ставит в соответствие единицу, если n делится на 14,и ноль в противном случае. Какая из приведенныхниже функций на последовательности десятичных цифр числа nявляется индуктивным расширением функции F?

Где располагаются глобальные переменные?

Чему равно значение выражения 1.5e-2*1000.0?

Что больше в современных архитектурах:объем физической памяти или объем виртуальной памяти?

Целочисленная переменная xпредставляет короткое целое число со знакомв диапазоне -128...127 и занимает 1 байт.Чему равно значение x после выполнения приведенногониже фрагмента программы?x := 120;x := x + 40;

Завершится ли когда-нибудь выполнение циклав приведенном ниже фрагменте программы?x := 1;цикл пока x != 144| x := x * 13;| если x <= 299| | то x := x - 299;| конец есликонец цикла(!= - означает "не равно")

В каком случае выполняется тело цикла "пока"?

Содержимое одного байта можно интерпретироватьлибо как число со знаком в диапазоне -128...127,либо как неотрицательное целое число в диапазоне 0...255.Какое неотрицательное число имеет тот же двоичный код,что и число со знаком -5?

Указать, чему будет равно значение переменной n в результатевыполнения следующего фрагмента программы: int n = 0; int i = 2; switch (i) { case 2: n += 2; case 4: n += 2; break; default: n += 6; }

Чему равна вещественная константа 0.001e+4,записанная в экспоненциальной форме?

В хеш-реализации множества хеш-функция принимает 4 различныезначения с равной вероятностью, т.е. множество представляетсяв виде объединения четырех непересекающихся подмножеств. Пустьмножество содержит 4 элемента. Какова вероятность того,что все подмножества будут непустыми?

Выражение содержит числа, переменную x и знаки четырехарифметических операций (переменная x можетиспользоваться многократно). Выражение можно преобразовывать,пользуясь известными свойствами арифметических операций.Значение переменной x сообщается только после того,как выражение преобразовано в удобную для вычисления форму.Какой максимальной глубины стека достаточно, чтобы вычислитьзначение любого такого выражения с помощью стековогокалькулятора (записывать промежуточные результаты на бумагезапрещено)?

Рассмотрим следующий фрагмент программы:#include . . . int n; char a[32]; strcpy(a, "abcdefgh" + 5); strcpy(a + 4, "1234"); n = strlen(a);Чему будет равно значение переменной nв результате выполнения этого фрагмента?

Обязательно ли при использовании данных типа FILEподключать какие-либо стандартные заголовочные файлы?

Что означает описание "double (*a)[10]"?

Помещается ли число 80000 в переменную типа shortв 32-разрядной архитектуре?

Что происходит при попытке захвата мьютекса нитью,если он уже захвачен другой нитью?

Что содержит регистр флагов?

Как располагаются разряды двоичного представленияцелого числа внутри машинного словав архитектуре Big Endian (процессоры Motorola, Power PC и т.п.)?

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма:дано: 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;

Указать, что вычисляет следующий фрагмент программы:дано: цел n;цел s, k;s := 2; k := 0;цикл пока s <= n| инвариант: s = 2k+1| s := s * 2; k := k + 1;конец циклаответ := k;

В каком алгоритмическом языке — в Паскале или в Си —операция поиска конкретного символа в строке реализуется болееэффективно?

Пусть x и y — вещественныепеременные типа double.Может ли произойти прерывание из-за деления на нольпри вычислении логического выраженияx / y >= 1.0 и y > 0.1?

Что представляет собой двоичный код мантиссывещественного числа 0.75 типа double? Мантисса больше или равна 0 и меньше 1.

Сколько раз будет выполнено тело цикла в приведеннойниже программе? Многоточием обозначен фрагмент,не содержащий переменной x.x := 0;цикл пока x < 1000| . . .| x := x + 1;конец цикла

Пусть описана структура struct List { struct List *next; void *value; };и переменые struct List e, *p; int m;Укажите все корректные выражения языка Си среди перечисленныхниже:

Указать, чему будет равно значение переменной n в результатевыполнения следующего фрагмента программы: int n = 3, k = 5; while (n != k) { n = (n * 2) % 11; k = (k * 7) % 11; }

Чему равно значение целочисленной переменной xв результате выполнения приведенного ниже фрагмента программы?x := 64;цикл пока x*x > 100| x := -(x / 2);конец цикла

Есть ли ограничение на длину текстовой строки в языке Паскаль?

Пусть даны очередь и стек.Рассмотрим фрагмент программы на псевдокоде: сделать стек пустым; цикл пока очередь непуста | x := взять элемент из начала очереди; | добавить (вход: x) в стек; конец цикла цикл пока стек непуст | x := взять элемент из стека; | добавить (вход: x) в конец очереди; конец циклаЧто произойдет с очередью в результатеего выполнения?

Является ли индуктивной функция, которая последовательностивещественных чисел ставит в соответствие сумму ее первогои последнего элементов?

Укажите, в какие моменты работы программы выполняетсяинвариант цикла.

Следующая программа вычисляет количествовхождений фрагмента "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. Можно ли упроститьпрограмму, использовав меньшее количество вспомогательныхпеременных? (Последовательность разрешается читать только один раз.)

В операционной системе 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, "%dn", a[i]); } fclose(f);Чему равен размер файла "tmp.dat" в байтах?

Пусть описан тип 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;

Пусть регистр 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:

Всегда ли равны выражения (x - y) + (y * 2.0), x + yдля произвольных вещественных переменных x, yтипа double?

Рассмотрим фрагмент программы на языке PostScript: 10 10 moveto 10 40 lineto 10 20 moveto 30 40 lineto 15 25 moveto 30 10 lineto strokeЧто будет нарисовано в результате его выполнения?

Пусть в красно-черном дереве число черных вершин(не включая внешние, или нулевые, вершины) равно 21.Какое максимальное количество красных вершин можетбыть в дереве?

Пусть у каждой нетерминальной вершины бинарного дерева естьровно два сына. Пусть в дереве 123 вершины. Каковамаксимальная высота такого дерева? (Высотой дерева называетсячисло вершин в пути максимальной длины от корня к некоторойтерминальной вершине, включая первую и последнюю вершиныпути.)

Элементы множества хранятся в массиве в возрастающемпорядке. Пусть множество содержит 12 элементов.Сколько операций сравнения достаточно выполнить,чтобы найти произвольный элемент в множестве или убедиться в егоотсутствии?

На базе какой структуры данных удобно реализовать очередь?

Рассмотрим фрагмент программы на языке PostScript: 10 10 moveto 20 30 lineto 10 50 lineto 30 50 moveto 20 30 lineto 30 10 lineto strokeЧто будет нарисовано в результате его выполнения?

Выражение записано с использованием обратной польскойзаписи: 1, 2, 3, +, *, 4, 5, *, -Чему равняется его значение?

Какая структура данных обычно используетсядля передачи заданий драйверу операционной системы?

Рассмотрим следующий фрагмент программы:#include #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в результате выполнения этого фрагмента?

Что делает следующий фрагмент программы на Си? FILE *f; . . . f = fopen("tmp.dat", "wb+");

Рассмотрим два способа представления матрицы размера4×4. В первом случае используется массив из четырехэлементов типа «указатель на double»: double *a[4];при этом элемент a[i] содержит адресначала i-й строки матрицы.Во втором случае используется линейный массив из шестнадцатиэлементов: double a[16];В первом случае обращение к элементу матрицы с индексамиi, j осуществляется с помощью выражения a[i][j],во втором — с помощью выражения a[4*i + j].Есть ли существенная разница в эффективности программыв первом и втором случаях при использовании оптимизирующегокомпилятора?

Пусть описана структура struct Tree { struct Tree *left; struct Tree *right; void *value; };и переменые struct Tree *t1, *t2; int m;Укажите все корректные выражения языка Си среди перечисленныхниже:

Указать, чему будет равно значение переменной n в результатевыполнения следующего фрагмента программы: int n = 1000; while (n > 100) { n /= 2; }

Чему равно значение выражения((786 >> 8) | 17)?

Рассмотрим следующий фрагмент программы: double *p; int i; . . . p = (double*) 1000; p += 10; i = (int) p;Чему будет равно значение переменной i в результатевыполнения этого фрагмента?

Что означает описание "char *a[10]"?

Что содержат заголовочные, или h-файлы, в случаеязыка Си?

Пусть регистр EBX содержит адрес массива целыхчисел, регистр ECX — количество элементов массива.Указать, что будет содержать регистр EAXв результате выполнения следующего фрагмента кодана Ассемблере "Masm" для процессора Intel 80x86: 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: ; метка конца цикла

Пусть регистры 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:

Какой регистр процессора содержит текущий адресвершины стека?

Сколько аргументов имеют команды процессоров типа Intel 80x86?

Какой архитектуре соответствует представление целыхчисел в протоколах сети Internet?

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:дано: основание 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;

Какое утверждение является инвариантом для следующегофрагмента программы (т.е. из справедливости утверждениядо выполнения фрагмента программы вытекает справедливость утвержденияпосле выполнения)? Предполагается, что n > 0.вещ r, x; цел n;. . .r := -r * x;r := r * n / (n + 1);n := n + 1;

Функция 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;

В каком алгоритмическом языке — в Паскале или в Си —операция нахождения длины строки реализуется болееэффективно?

В каком алгоритмическом языке текстовая строка представляетсяпоследовательностью байтов, в которой первый байт содержитдлину строки, а далее следуют коды символов, составляющих строку?

Указать, что произойдет с элементами массива aв результате выполнения следующего фрагмента программы:вещ 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;

Пусть x — вещественнаяпеременная типа double.Может ли произойти прерывание из-за переполненияпри вычислении логического выражения1.0 <= x и x <= 1.0e+30 и x*x < 1000.0?

В какой кодировке под символ отводится 2 байта?

Какова точность вычислений с вещественнымичислами типа double?

Сколько двоичных разрядов отводится под знак, порядок и мантиссув двоичном коде вещественного числа типа float длиной 4 байта?

Целочисленная переменная xпредставляет короткое целое число со знакомв диапазоне -32768...32767 и занимает 2 байта.Чему равно значение x после выполнения приведенногониже фрагмента программы?x := 32760;x := x + 10;

Чему равно значение целочисленной переменной xв результате выполнения приведенного ниже фрагмента программы?x := 1;цикл пока x < 11| x := -2*x + 11;конец цикла

Указать, чему может быть равно значение переменной zв результате выполнения следующего фрагмента программы:z := 0;цикл пока x < y| . . .| если z > 100| | то| | z := 10; x := y;| | иначе| | z := 20; x := y - 1;| конец есликонец цикла

Какой механизм применяется для выполнения программы,написанной на языке C++?

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

Указать, что произойдет с элементами массива aв результате выполнения следующего фрагмента программы:вещ a[100]; вещ t; цел i;. . .i := 0;цикл пока i < 50| t := a[i];| a[i] := a[99 - i]; a[99 - i] := t;| i := i+1;конец цикла

В хеш-реализации множества хеш-функция принимает 5 различныхзначений с равной вероятностью, т.е. множество представляетсяв виде объединения пяти непересекающихся подмножеств. Пустьмножество содержит 3 элемента. Какова вероятность того,что все они попадут в разные подмножества?

Указать, чему будет равно значение переменной n в результатевыполнения следующего фрагмента программы: int n = 33; switch (n % 4) { case 1: n += 3; case 2: n += 2; case 3: ++n; break; default: ++n; }