Основы программирования



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

  • Значение s приблизительно равно 0.866
    (корню из трех пополам).
  • Значение s приблизительно равно 0.5.
  • (Правильный ответ) Значение s приблизительно равно 1.41421
    (корню из двух).
  • Значение s приблизительно равно 1.

Всегда ли равны выражения

(x + y) + y, x + (y * 2.0)

для произвольных вещественных переменных x, y
типа double?

  • (Правильный ответ) Нет, могут быть неравными.
  • Да, всегда равны.

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

  • (Правильный ответ) компиляция
  • непосредственное выполнение машинных команд
  • интерпретация

Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?

x := 1;цикл пока x < 100| x := -(x * 2);конец цикла

  • (Правильный ответ) Значение x = 256.
  • Значение x = 64.
  • Значение x = 128.

Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?

x := 1;цикл пока x < 11| x := -2*x + 11;конец цикла

  • Значение x = 39.
  • (Правильный ответ) Значение x = 25.
  • Значение x = 11.
  • Значение x = 15.

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

  • (Правильный ответ) когда условие после слова «пока» в заголовке цикла истинно
  • когда условие после слова «пока» в заголовке цикла ложно

Что представляет собой двоичный код мантиссы
вещественного числа 1.5 типа double?

  • Двоичный код мантиссы содержит единицы в двух старших
    разрядах и нули в остальных разрядах: 110000…000.
  • (Правильный ответ) Двоичный код мантиссы содержит единицу в старшем
    разряде и нули в остальных разрядах: 100000…000.

Всегда ли равны выражения

(x — y) + (y * 2.0), x + y

для произвольных вещественных переменных x, y
типа double?

  • Да, всегда равны.
  • (Правильный ответ) Нет, могут быть неравными.

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

  • (Правильный ответ) В Паскале.
  • Нет существенной разницы.
  • В Си.

Пусть значения целочисленных переменных x и y
равны 100 и 10 соответственно.
Указать значение логического выражения

(x > 1 и y <= 10) или x == 0

  • (Правильный ответ) Истина.
  • Ложь.

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

  • Нет существенной разницы.
  • В Си.
  • (Правильный ответ) В Паскале.

Какой диапазон кодов символов используется в кодировке ASCII (стандарт ISO-646)?

  • От 0 до 65535.
  • От 0 до 255.
  • (Правильный ответ) От 0 до 127.

Чему равен минимум пустой последовательности
целых чисел?

  • Минус бесконечности.
  • (Правильный ответ) Плюс бесконечности.
  • Невозможно дать разумное определение.
  • Нулю.

Чему равен максимум пустой последовательности
вещественных чисел?

  • (Правильный ответ) Минус бесконечности.
  • Нулю.
  • Невозможно дать разумное определение.
  • Плюс бесконечности.

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

  • (Правильный ответ) Можно.
  • Нельзя.

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

  • (Правильный ответ) да, является
  • да, является только для многочленов степени 1
  • нет, не является

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел x, y;x := 1; y := 4;цикл пока y <= n| инвариант: y = (x + 1)2;| x := x + 1;| y := y + 2*x + 1;конец циклаответ := x;

  • (Правильный ответ) Целую часть квадратного корня из n.
  • Целую часть от log2 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;

  • Время работы не больше, чем
    C·max(m, n),
    где C — некоторая константа
    (т.е. время пропорционально максимальному из чисел m, n).
  • (Правильный ответ) Время работы не больше, чем
    C·log2 max(m, n),
    где C — некоторая константа
    (т.е. время пропорционально количеству цифр в двоичной или
    десятичной записи максимального из чисел m, n).
  • Время работы не больше, чем
    C·r, где C — некоторая константа,
    r
    квадратный корень из max(m, n)
    (т.е. время пропорционально квадратному корню из максимального
    числа).

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

  • (Правильный ответ) Не обязательно.
  • Да, выполняется.

Пусть 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];

  • Ошибки нет, фрагмент программы корректный.
  • (Правильный ответ) Фрагмент программы содержит ошибку.

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

  • (Правильный ответ) В первый.
  • Во второй.

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

  • Младшие разряды числа в байтах с младшими адресами.
  • (Правильный ответ) Младшие разряды числа в байтах со старшими адресами.

Что содержат общие регистры процессора?

  • (Правильный ответ) Целые числа.
  • Вещественные числа.

Для чего используется регистр FP?

  • (Правильный ответ) В процессе работы функции регистр FP содержит базовый
    адрес блока локальных переменных функции.
  • При вызове функции в регистре FP сохраняется
    адрес вершины стека в момент вызова.
  • При вызове функции в регистр FP помещается адрес возврата.

Какое прерывание происходит при попытке выполнить
деление на ноль?

  • Acинхронное.
  • (Правильный ответ) Синхронное.

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

  • (Правильный ответ) a — указатель на массив из 10 элементов
    типа double.
  • a — массив из 10 элементов
    типа указатель на double.

Каковы размеры типов float и double в языке Си?

  • (Правильный ответ) 4 байта, 8 байтов.
  • 4 байта, 10 байтов.
  • 2 байта, 4 байта.
  • 8 байтов, 10 байтов.

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

  • (Правильный ответ) a — массив из 10 элементов
    типа указатель на char.
  • a — указатель на массив из 10 элементов
    типа char.

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

  • (Правильный ответ) Описания прототипов функций, внешних переменных,
    констант и типов.
  • Определения функций и статических переменных.

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

  • В заголовочных файлах (h-файлах).
  • (Правильный ответ) В файлах реализации (c-файлах).

Указать, чему будет равно значение переменной n в результате
выполнения следующего фрагмента программы:

int n = 1000; while (n > 100) { n /= 2; }

  • Значение n равно 50.
  • Значение n равно 56.
  • (Правильный ответ) Значение n равно 62.

Прототип функции, которая ищет вхождение строки
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 = s1.len
  • s1 == *s2
  • (Правильный ответ) c = s2->str[2]
  • (Правильный ответ) s1 = *s2

Прототип функции, вычисляющей степень 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; }

  • Значение n равно 6.
  • Значение n равно 10.
  • (Правильный ответ) Значение n равно 4.
  • Значение n равно 2.

Является ли тип данных FILE частью языка Си?

  • Да, этот тип входит в язык и предназначен для
    работы с файлами.
  • (Правильный ответ) Нет, этот тип не входит в язык; он описан в
    стандартной библиотеке ANSI.

Рассмотрим два способа представления матрицы размера
4Ч4. В первом случае используется массив из четырех
элементов типа «массив из четырех элементов»:

double a[4][4];

Во втором случае используется массив из четырех
элементов типа «указатель на double»:

double *a[4];

при этом элемент a[i] содержит адрес
начала i-й строки матрицы.
В обоих случаях обращение к элементу матрицы с индексами
i, j осуществляется с помощью выражения

a[i][j].

Есть ли существенная разница в эффективности программы
в первом и втором случаях при использовании оптимизирующего
компилятора?

  • (Правильный ответ) Да, есть, первый способ эффективнее.
  • Да, есть, второй способ эффективнее.
  • Существенной разницы нет.

Что делает следующий фрагмент программы на Си?

FILE *f; . . . f = fopen(«»tmp.dat»», «»wb+»»);

  • (Правильный ответ) Открывает файл «tmp.dat» в текущей директории
    как бинарный для чтения и записи, при этом старое содержимое
    файла теряется.
  • Открывает файл «tmp.dat» в текущей директории
    как бинарный для записи, при этом старое содержимое
    файла теряется.
  • Открывает файл «tmp.dat» в текущей директории
    как бинарный для чтения и записи, при этом старое содержимое
    файла сохраняется.

В операционной системе 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» в байтах?

  • Размер файла равен 13 байтам.
  • (Правильный ответ) Размер файла равен 10 байтам.
  • Размер файла равен 9 байтам.
  • Размер файла равен 14 байтам.

Рассмотрим следующий фрагмент программы:

#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
в результате выполнения этого фрагмента?

  • Значение n равно 155.
  • Значение n равно 299.
  • (Правильный ответ) Значение n равно 283.
  • Значение n равно 121.

Рассмотрим два способа представления матрицы размера
4Ч4. В первом случае используется массив из четырех
элементов типа «указатель на double»:

double *a[4];

при этом элемент a[i] содержит адрес
начала i-й строки матрицы.
Во втором случае используется линейный массив из шестнадцати
элементов:

double a[16];

В первом случае обращение к элементу матрицы с индексами
i, j осуществляется с помощью выражения

a[i][j],

во втором — с помощью выражения

a[4*i + j].

Есть ли существенная разница в эффективности программы
в первом и втором случаях при использовании оптимизирующего
компилятора?

  • Да, есть, первый способ эффективнее.
  • (Правильный ответ) Да, есть, второй способ эффективнее.
  • Существенной разницы нет.

Пусть в ОС 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» в байтах?

  • Размер файла равен 11 байтам.
  • Размер файла равен 8 байтам.
  • (Правильный ответ) Размер файла равен 12 байтам.
  • Размер файла равен 9 байтам.

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

  • Стек.
  • (Правильный ответ) Очередь.

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

  • Очередь.
  • (Правильный ответ) Стек.

Выражение записано с использованием обратной польской
записи:

0, 1, *, 2, -, 3, 4, *, 5, +, 6, *, +

Чему равняется его значение?

  • Значение выражения равно 104.
  • Значение выражения равно 25.
  • (Правильный ответ) Значение выражения равно 100.
  • Значение выражения равно 136.

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

  • Число вершин равно 511.
  • (Правильный ответ) Число вершин равно 1023.
  • Число вершин равно 1024.
  • Число вершин равно 512.

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

  • Динамический массив.
  • (Правильный ответ) Линейный двунаправленный список.
  • Нагруженное множество.

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

  • Вероятность равна 0.75
  • Вероятность равна 0.90625
  • (Правильный ответ) Вероятность равна 0.09375
  • Вероятность равна 0.25

Как оценивается сверху высота h сбалансированного (почти
сбалансированного) бинарного дерева в зависимости от числа
вершин n?

  • Справедливо неравенство h <= n/2.
  • (Правильный ответ) Справедливо неравенство h <= C log2 n,
    где C — константа.

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

  • максимальная высота равна 61
  • (Правильный ответ) максимальная высота равна 8
  • максимальная высота равна 63
  • максимальная высота равна 62
  • максимальная высота равна 60

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

  • (Правильный ответ) двоичный код мантиссы содержит единицы в двух старших разрядах и нули в остальных разрядах: 110000…000
  • двоичный код мантиссы содержит три единицы в старшем разряде и нули в остальных разрядах: 111000…000
  • двоичный код мантиссы содержит единицу в старшем разряде и нули в остальных разрядах: 100000…000

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

  • (Правильный ответ) Пара (максимум, диаметр) множества
    элементов последовательности.
  • Пара (среднее арифметическое, диаметр) множества
    элементов последовательности.

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

  • (Правильный ответ) Объем виртуальной памяти.
  • Объем физической памяти.

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

  • Произведение x y.
  • (Правильный ответ) Степень xy.

Какой регистр процессора содержит адрес инструкции,
которая будет выполняться на следующем шаге?

  • Регистр SP.
  • (Правильный ответ) Регистр PC.
  • Регистр FP.

Где хранятся локальные переменные функции в языке Си?

  • (Правильный ответ) В аппаратном стеке.
  • В ячейках оперативной памяти с фиксированными адресами.

Рассмотрим следующий фрагмент программы:

#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 равно 253.
  • Значение n равно 245.
  • Значение n равно 293.
  • Значение n равно 315.

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

  • Достаточно стека максимальной глубины 3.
  • (Правильный ответ) Достаточно стека максимальной глубины 2.
  • Достаточно стека максимальной глубины 4.
  • Достаточно стека максимальной глубины 5.
Узнать сколько стоит решение этого задания
(ответ в течение 5 мин.)
X