Главная /
Основы программирования - обучения основам
Основы программирования - обучения основам - ответы на тесты Интуит
Курс предназначен для обучения основам программирования. Рассматриваются основные понятия программирования - алгоритма, исполнителя, алгоритмического языка, переменной, основные типы данных, управляющие конструкции алгоритмического языка и т.п. Излагаются общие приемы программирования, основанные на применении математики, такие, как вычисление функций на последовательностях с помощью применения теории индуктивных функций и схема построения цикла с помощью инварианта.
Список вопросов:
- # Какой механизм применяется для выполнения программы, написанной на языке C++?
- # Какой механизм применяется для выполнения программы, написанной на языке C#?
- # В каком случае выполняется тело цикла "пока"?
- # Что можно сказать об условии, указанном в заголовке цикла "пока", после полного завершения цикла?
- # Сколько раз будет выполнено тело цикла в приведенной ниже программе? Многоточием обозначен фрагмент, не содержащий переменной x. x := 0; цикл пока x < 1000 | . . . | x := x + 1; конец цикла
- # Сколько раз будет выполнено тело цикла в приведенной ниже программе? Многоточием обозначен фрагмент, не содержащий переменной x. x := 100; цикл пока x >= 0 | . . . | x := x - 1; конец цикла
- # Сколько раз будет выполнено тело цикла в приведенной ниже программе? Многоточием обозначен фрагмент, не содержащий переменной x. x := 0; цикл пока x <= 100 | . . . | x := x + 2; конец цикла
- # Пусть A = A(x) — некоторое условие, зависящее только от значения переменной x. Указать, чему может быть равно значение переменной y в результате выполнения следующего фрагмента программы: x := 1; y := 1; цикл пока A(x) | . . . | если y < 0 | | то | | x := 2; | | y := 10; | | иначе | | x := 1; | | y := 20; | конец если конец цикла
- # Указать, чему может быть равно значение переменной z в результате выполнения следующего фрагмента программы: z := 0; цикл пока x < y | . . . | если z > 100 | | то | | z := 10; x := y; | | иначе | | z := 20; x := y - 1; | конец если конец цикла
- # Чему равно значение целочисленной переменной x в результате выполнения приведенного ниже фрагмента программы? x := 1; цикл пока x < 100 | x := -(x * 2); конец цикла
- # Чему равно значение целочисленной переменной x в результате выполнения приведенного ниже фрагмента программы? x := 64; цикл пока x*x > 100 | x := -(x / 2); конец цикла
- # Чему равно значение целочисленной переменной x в результате выполнения приведенного ниже фрагмента программы? x := 1; цикл пока x < 11 | x := -2*x + 11; конец цикла
- # Завершится ли когда-нибудь выполнение цикла в приведенном ниже фрагменте программы (!= - означает "не равно")? x := 1; цикл пока x != 56 | x := x * 11; | если x <= 253 | | то x := x - 253; | конец если конец цикла
- # Завершится ли когда-нибудь выполнение цикла в приведенном ниже фрагменте программы (!= означает "не равно")? x := 1; цикл пока x != 120 | x := x * 7; | если x <= 490 | | то x := x - 490; | конец если конец цикла
- # Завершится ли когда-нибудь выполнение цикла в приведенном ниже фрагменте программы? x := 1; цикл пока x != 144 | x := x * 13; | если x <= 299 | | то x := x - 299; | конец если конец цикла (!= - означает "не равно")
- # Рассмотрим два способа представления матрицы размера 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]. Есть ли существенная разница в эффективности программы в первом и втором случаях при использовании оптимизирующего компилятора?
- # Рассмотрим два способа представления матрицы размера 4×4. В первом случае используется массив из четырех элементов типа «массив из четырех элементов»: double a[4][4]; Во втором случае используется массив из четырех элементов типа «указатель на double»: double *a[4]; при этом элемент a[i] содержит адрес начала i-й строки матрицы. В обоих случаях обращение к элементу матрицы с индексами i, j осуществляется с помощью выражения a[i][j]. Есть ли существенная разница в эффективности программы в первом и втором случаях при использовании оптимизирующего компилятора?
- # Содержит ли язык Си средства ввода-вывода?
- # Является ли тип данных FILE частью языка Си?
- # Обязательно ли при использовании данных типа FILE подключать какие-либо стандартные заголовочные файлы?
- # Что делает следующий фрагмент программы на Си? FILE *f; . . . f = fopen("tmp.dat", "wb+");
- # Что делает следующий фрагмент программы на Си? FILE *f; . . . f = fopen("tmp.dat", "rb+");
- # Пусть в ОС 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" в байтах?
- # В операционной системе 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> . . . int n; char a[32]; strcpy(a, "e2e4"); strcpy(a + 5, "c7c5"); n = strlen(a); Чему будет равно значение переменной n в результате выполнения этого фрагмента?
- # Рассмотрим следующий фрагмент программы: #include <string.h> . . . int n; char a[32]; strcpy(a, "abcdefgh" + 5); strcpy(a + 4, "1234"); n = strlen(a); Чему будет равно значение переменной n в результате выполнения этого фрагмента?
- # Рассмотрим следующий фрагмент программы: #include <string.h> . . . int n; char a[32]; strcpy(a, "e2e4e7e5"); strcpy(a + 2, "e3"); strcpy(a + 6, "e6d2d4"); n = strlen(a); Чему будет равно значение переменной n в результате выполнения этого фрагмента?
- # Рассмотрим следующий фрагмент программы: #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 в результате выполнения этого фрагмента?
- # Рассмотрим следующий фрагмент программы: #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 в результате выполнения этого фрагмента?
- # Рассмотрим следующий фрагмент программы: #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 в результате выполнения этого фрагмента?
- # Какая структура данных обычно используется для сохранения состояния прерванного задания?
- # Какая структура данных обычно используется при передаче параметров подпрограммам и функциям?
- # Какая структура данных обычно используется для передачи заданий драйверу операционной системы?
- # Обозначим через push и pop команды добавления элемента в стек и извлечения элемента из стека. Рассмотрим фрагмент программы на псевдокоде: push x; push y; pop x; pop y; Что происходит с переменными x и y в результате его выполнения?
- # Пусть даны очередь и стек. Рассмотрим фрагмент программы на псевдокоде: сделать стек пустым; цикл пока очередь непуста | x := взять элемент из начала очереди; | добавить (вход: x) в стек; конец цикла цикл пока стек непуст | x := взять элемент из стека; | добавить (вход: x) в конец очереди; конец цикла Что произойдет с очередью в результате его выполнения?
- # Даны очередь и стек элементов одного и того же типа. Можно ли написать программу, которая удаляет из очереди предпоследний элемент и не меняет порядка остальных элементов? При этом разрешается использовать стек как вспомогательную структуру данных; другими структурами (за исключением простых переменных) пользоваться запрещено.
- # Выражение записано с использованием обратной польской записи: 1, 2, 3, +, *, 4, 5, *, - Чему равняется его значение?
- # Выражение записано с использованием обратной польской записи: 0, 1, *, 2, -, 3, 4, *, 5, +, 6, *, + Чему равняется его значение?
- # Выражение записано с использованием обратной польской записи: 1, 2, 3, +, *, 4, *, 5, * Чему равняется его значение?
- # Рассмотрим фрагмент программы на языке PostScript: 10 10 moveto 20 30 lineto 30 10 lineto 15 20 moveto 25 20 lineto stroke Что будет нарисовано в результате его выполнения?
- # Рассмотрим фрагмент программы на языке PostScript: 10 10 moveto 20 30 lineto 10 50 lineto 30 50 moveto 20 30 lineto 30 10 lineto stroke Что будет нарисовано в результате его выполнения?
- # Рассмотрим фрагмент программы на языке PostScript: 10 10 moveto 10 40 lineto 10 20 moveto 30 40 lineto 15 25 moveto 30 10 lineto stroke Что будет нарисовано в результате его выполнения?
- # Рассмотрим следующую реализацию функции 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?
- # Рассмотрим следующую реализацию функции onMul, которая исполняет команду умножения в проекте «Стековый калькулятор»: static void onMul() { double y, x; assert(st_size() >= 2); // утв: глубина стека // не меньше двух y = st_pop(); x = st_pop(); st_push(x * y); display(); } Правильно ли здесь используется конструкция «утверждение», которая в Си реализуется функцией assert?
- # Рассмотрим следующую реализацию функции 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?
- # Выражение содержит числа, переменные, круглые скобки и знаки четырех арифметических операций. Его можно преобразовывать, пользуясь известными свойствами арифметических операций. Значения переменных сообщаются только после того, как выражение преобразовано в удобную для вычисления форму. Какой максимальной глубины стека достаточно, чтобы вычислить значение любого такого выражения с помощью стекового калькулятора (записывать промежуточные результаты на бумаге запрещено)?
- # Выражение содержит числа, переменную x и знаки трех арифметических операций +, -, × (нет операции деления); переменная x может использоваться многократно. Выражение можно преобразовывать, пользуясь известными свойствами арифметических операций. Значение переменной x сообщается только после того, как выражение преобразовано в удобную для вычисления форму. Какой максимальной глубины стека достаточно, чтобы вычислить значение любого такого выражения с помощью стекового калькулятора (записывать промежуточные результаты на бумаге запрещено)?
- # Выражение содержит числа, переменную x и знаки четырех арифметических операций (переменная x может использоваться многократно). Выражение можно преобразовывать, пользуясь известными свойствами арифметических операций. Значение переменной x сообщается только после того, как выражение преобразовано в удобную для вычисления форму. Какой максимальной глубины стека достаточно, чтобы вычислить значение любого такого выражения с помощью стекового калькулятора (записывать промежуточные результаты на бумаге запрещено)?
- # На базе какой структуры данных удобно реализовать стек?
- # На базе какой структуры данных удобно реализовать очередь?
- # Рассмотрим непрерывную реализацию множества с помощью бинарного поиска. Пусть множество содержит миллион элементов. Сколько операций сравнения может быть выполнено при поиске элемента?
- # Элементы множества хранятся в массиве в возрастающем порядке. Пусть множество содержит 12 элементов. Сколько операций сравнения достаточно выполнить, чтобы найти произвольный элемент в множестве или убедиться в его отсутствии?
- # Элементы множества хранятся в массиве в возрастающем порядке. Пусть множество содержит 10 элементов. Сколько операций сравнения достаточно выполнить, чтобы найти произвольный элемент в множестве или убедиться в его отсутствии?
- # Пусть требуется реализовать упорядоченный набор различных элементов, при этом элементы можно добавлять и удалять. Какая структура данных лучше всего подходит для этого?
- # Пусть требуется реализовать упорядоченный набор элементов, причем элемент может повторяться в наборе несколько раз. Элементы можно добавлять к набору и удалять из набора. Какая структура данных лучше всего подходит для этого?
- # Текст представляет собой последовательность строк. При этом строки можно изменять, удалять и добавлять в любое место текста. Какая структура данных лучше всего подходит для хранения и редактирования такого текста?
- # Как оценивается сверху высота h сбалансированного (почти сбалансированного) бинарного дерева в зависимости от числа вершин n?
- # Бинарное дерево называется полным, если длины всех путей к внешним (нулевым) вершинам одинаковы. (Это означает, что у каждой нетерминальной вершины ровно два сына, и длины всех путей от корня к терминальным вершинам одинаковы и равны высоте дерева.) Высотой дерева называется число вершин в пути максимальной длины от корня к некоторой терминальной вершине, включая первую и последнюю вершины пути. Сколько вершин в полном бинарном дереве высоты 10?
- # Пусть у каждой нетерминальной вершины бинарного дерева есть ровно два сына. Пусть в дереве 123 вершины. Какова максимальная высота такого дерева? (Высотой дерева называется число вершин в пути максимальной длины от корня к некоторой терминальной вершине, включая первую и последнюю вершины пути.)
- # Пусть в красно-черном дереве число черных вершин (не включая внешние, или нулевые, вершины) равно 21. Какое максимальное количество красных вершин может быть в дереве?
- # Может ли в красно-черном дереве длина одного пути от корня к терминальной вершине равняться 20, длина другого — 10?
- # Может ли в красно-черном дереве число красных вершин более чем в два раза превышать число черных вершин?
- # В хеш-реализации множества хеш-функция принимает 10 различных значений с равной вероятностью. Пусть множество содержит 3 элемента. Какова вероятность коллизии? (Коллизией называется ситуация, когда у двух элементов значения хеш-функции совпадают.)
- # В хеш-реализации множества хеш-функция принимает 4 различные значения с равной вероятностью, т.е. множество представляется в виде объединения четырех непересекающихся подмножеств. Пусть множество содержит 4 элемента. Какова вероятность того, что все подмножества будут непустыми?
- # В хеш-реализации множества хеш-функция принимает 5 различных значений с равной вероятностью, т.е. множество представляется в виде объединения пяти непересекающихся подмножеств. Пусть множество содержит 3 элемента. Какова вероятность того, что все они попадут в разные подмножества?
- # Содержимое одного байта можно интерпретировать либо как неотрицательное целое число в диапазоне 0...255, либо как число со знаком в диапазоне -128...127. Какое число со знаком имеет тот же двоичный код, что и неотрицательное число 254?
- # Содержимое двухбайтового слова можно интерпретировать либо как неотрицательное целое число в диапазоне 0...65535, либо как число со знаком в диапазоне -32768...32767. Какое число со знаком имеет тот же двоичный код, что и неотрицательное число 65533?
- # Содержимое одного байта можно интерпретировать либо как число со знаком в диапазоне -128...127, либо как неотрицательное целое число в диапазоне 0...255. Какое неотрицательное число имеет тот же двоичный код, что и число со знаком -5?
- # Целочисленная переменная x представляет короткое целое число со знаком в диапазоне -32768...32767 и занимает 2 байта. Чему равно значение x после выполнения приведенного ниже фрагмента программы? x := 32760; x := x + 10;
- # Целочисленная переменная x представляет короткое целое число со знаком в диапазоне -128...127 и занимает 1 байт. Чему равно значение x после выполнения приведенного ниже фрагмента программы? x := 120; x := x + 40;
- # Целочисленная переменная x представляет короткое целое число со знаком в диапазоне -128...127 и занимает 1 байт. Чему равно значение x после выполнения приведенного ниже фрагмента программы? x := 30; x := x * 5;
- # Сколько двоичных разрядов отводится для хранения порядка в двоичном коде вещественного числа типа double длиной 8 байтов?
- # Сколько двоичных разрядов отводится под знак, порядок и мантиссу в двоичном коде вещественного числа типа float длиной 4 байта?
- # Сколько двоичных разрядов отводится для хранения мантиссы в двоичном коде вещественного числа типа double длиной 8 байтов?
- # Что представляет собой двоичный код мантиссы вещественного числа 1.5 типа double?
- # Что представляет собой двоичный код мантиссы вещественного числа 2.5 типа double?
- # Что представляет собой двоичный код мантиссы вещественного числа 0.75 типа double? Мантисса больше или равна 0 и меньше 1.
- # Какова точность вычислений с вещественными числами типа double?
- # Какова точность вычислений с вещественными числами типа float?
- # Можно ли сохранить произвольное целое число длиной в четыре байта в вещественных переменных типа float и типа double без потери точности?
- # Всегда ли равны выражения (x + y) + z, x + (y + z) для произвольных вещественных переменных x, y, z типа double?
- # Всегда ли равны выражения (x + y) + y, x + (y * 2.0) для произвольных вещественных переменных x, y типа double?
- # Всегда ли равны выражения (x - y) + (y * 2.0), x + y для произвольных вещественных переменных x, y типа double?
- # В какой кодировке под символ отводится 2 байта?
- # Какой диапазон кодов символов используется в кодировке ASCII (стандарт ISO-646)?
- # Пусть значения целочисленных переменных x и y равны 1 и 2 соответственно. Указать значение логического выражения (x >= 1 и y < 0) или (x <= 1 и y > 0)
- # Пусть значения целочисленных переменных x и y равны 100 и 10 соответственно. Указать значение логического выражения (x > 1 и y <= 10) или x == 0
- # Пусть значения целочисленных переменных x и y равны 20 и 10 соответственно. Указать значение логического выражения y != 0 и x/y <= 1
- # Пусть x и y — вещественные переменные типа double. Может ли произойти прерывание из-за деления на ноль при вычислении логического выражения y > 0.1 и x / y >= 1.0?
- # Пусть x и y — вещественные переменные типа double. Может ли произойти прерывание из-за деления на ноль при вычислении логического выражения x / y >= 1.0 и y > 0.1?
- # Пусть x — вещественная переменная типа double. Может ли произойти прерывание из-за переполнения при вычислении логического выражения 1.0 <= x и x <= 1.0e+30 и x*x < 1000.0?
- # Указать, что произойдет с элементами массива 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;
- # Указать, что произойдет с элементами массива a в результате выполнения следующего фрагмента программы: вещ a[100]; цел i; . . . i := 0; цикл пока i < 99 | a[i+1] := a[i]; | i := i+1; конец цикла a[0] := a[99];
- # Указать, что произойдет с элементами массива a в результате выполнения следующего фрагмента программы: вещ a[100]; вещ t; цел i; . . . i := 0; цикл пока i < 50 | t := a[i]; | a[i] := a[99 - i]; a[99 - i] := t; | i := i+1; конец цикла
- # В каком алгоритмическом языке текстовая строка представляется последовательностью байтов, в которой первый байт содержит длину строки, а далее следуют коды символов, составляющих строку?
- # Есть ли ограничение на длину текстовой строки в языке Паскаль?
- # Есть ли ограничение на длину текстовой строки в языке Си?
- # В каком алгоритмическом языке — в Паскале или в Си — операция конкатенации (соединения) строк реализуется более эффективно?
- # В каком алгоритмическом языке — в Паскале или в Си — операция нахождения длины строки реализуется более эффективно?
- # В каком алгоритмическом языке — в Паскале или в Си — операция поиска конкретного символа в строке реализуется более эффективно?
- # Чему равен минимум пустой последовательности целых чисел?
- # Чему равен максимум пустой последовательности вещественных чисел?
- # Чему равно произведение пустой последовательности вещественных чисел?
- # Что вычисляет следующий фрагмент программы? вещ последовательность 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; вещ a, s; цел n; . . . s := минус бесконечность; n := 0; встать в начало последовательности p; цикл пока есть непрочитанные элементы в посл-ти p | прочесть очередной элемент посл-ти p в (вых: a); | если a > s | | то | | s := a; n := 1; | иначе если a == s | | то | | n := n + 1; | конец если конец цикла ответ := n;
- # Что вычисляет следующий фрагмент программы? вещ последовательность 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;
- # Является ли индуктивной функция, которая последовательности вещественных чисел ставит в соответствие сумму ее первого и последнего элементов?
- # Является ли индуктивной функция, которая последовательности коэффициентов многочлена по убыванию степеней ставит в соответствие пару чисел: (степень многочлена, интеграл многочлена по отрезку [0, 1])?
- # Является ли индуктивной функция, которая последовательности коэффициентов многочлена по возрастанию степеней ставит в соответствие пару чисел (степень многочлена, интеграл многочлена по отрезку [0, 1])?
- # Рассмотрим функцию F, которая последовательности коэффициентов многочлена по убыванию степеней ставит в соответствие значение второй производной многочлена в точке t. Какая из приведенных ниже функций на последовательностях является индуктивным расширением функции F?
- # Рассмотрим функцию F, которая в последовательности коэффициентов многочлена по возрастанию степеней ставит в соответствие значение второй производной многочлена в точке t. Какая из приведенных ниже функций на последовательностях является индуктивным расширением функции F?
- # Диаметром множества вещественных чисел называется максимум из абсолютных величин попарных разностей его элементов. Рассмотрим функцию F, которая последовательности вещественных чисел ставит в соответствие диаметр множества ее элементов. Какая из приведенных ниже функций на последовательностях является индуктивным расширением функции F?
- # Функция F последовательности цифр в десятичной записи числа n ставит в соответствие единицу, если n делится на 7, и ноль в противном случае. Какая из приведенных ниже функций на последовательности десятичных цифр числа n является индуктивным расширением функции F?
- # Функция F последовательности цифр в десятичной записи числа n ставит в соответствие единицу, если n делится на 15, и ноль в противном случае. Какая из приведенных ниже функций на последовательности десятичных цифр числа n является индуктивным расширением функции F?
- # Функция F последовательности цифр в десятичной записи числа n ставит в соответствие единицу, если n делится на 14, и ноль в противном случае. Какая из приведенных ниже функций на последовательности десятичных цифр числа n является индуктивным расширением функции F?
- # Следующий фрагмент программы вычисляет сумму четырех последних элементов последовательности 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. Можно ли упростить программу, использовав меньшее количество вспомогательных переменных? (Последовательность разрешается читать только один раз.)
- # Следующая программа вычисляет количество вхождений фрагмента "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. Можно ли упростить программу, использовав меньшее количество вспомогательных переменных? (Последовательность разрешается читать только один раз.)
- # На вход следующей программе передается последовательность целых чисел в диапазоне от 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. Можно ли упростить программу, использовав меньшее количество вспомогательных переменных? (Последовательность разрешается читать только один раз.)
- # Рассмотрим следующий фрагмент программы: утверждение: A(x) цикл пока B(x) | инвариант: A(x) | x := T(x) конец цикла Здесь через A(x) и B(x) обозначены условия, зависящие от переменной x. Какое условие выполняется по окончании цикла?
- # Выполняется ли инвариант цикла в процессе выполнения тела цикла?
- # Укажите, в какие моменты работы программы выполняется инвариант цикла.
- # Указать, что вычисляет следующий фрагмент программы: дано: цел n; цел s, k; s := 2; k := 0; цикл пока s <= n | инвариант: s = 2k+1 | s := s * 2; k := k + 1; конец цикла ответ := k;
- # Указать, что вычисляет следующий фрагмент программы: дано: цел n; цел x, y; x := 1; y := 4; цикл пока y <= n | инвариант: y = (x + 1)2; | x := x + 1; | y := y + 2*x + 1; конец цикла ответ := x;
- # Указать, что вычисляет следующий фрагмент программы: дано: цел 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; Какое условие является инвариантом цикла?
- # Рассмотрим следующий фрагмент программы: цел 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); Какое условие является инвариантом цикла? (Через НОД и НОК обозначены наибольший общий делитель и наименьшее общее кратное.)
- # Рассмотрим следующий фрагмент программы, вычисляющей частное q и остаток r от деления целых чисел a, b: дано: целые числа 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 Какое условие является инвариантом цикла?
- # Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что n неотрицательно. вещ r, x; цел n; . . . r := r * x * x; r := r / ((n + 1) * (n + 2)); n := n + 2;
- # Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что 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, 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 надо: вычислить 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;
- # Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма приблизительного вычисления логарифма: дано: 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;
- # Пусть 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;
- # Пусть 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];
- # Пусть 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]
- # Как подключаются внешние устройства к шине?
- # Как нумеруются биты внутри байта или машинного слова?
- # Каков размер машинного слова в компьютерах на базе процессора Intel 80386-80686?
- # Как располагаются разряды двоичного представления целого числа внутри машинного слова в архитектуре Little Endian (процессоры Intel, Alpha и т.п.)?
- # Как располагаются разряды двоичного представления целого числа внутри машинного слова в архитектуре Big Endian (процессоры Motorola, Power PC и т.п.)?
- # Какой архитектуре соответствует представление целых чисел в протоколах сети Internet?
- # Что содержат общие регистры процессора?
- # Что содержит регистр флагов?
- # Что содержат плавающие регистры процессора?
- # Сколько аргументов имеют команды процессоров типа Intel 80x86?
- # Сколько аргументов имеют команды процессоров типа Motorola 68000?
- # В какой аргумент помещается результат команды с двумя аргументами (например, сложения) при использовании Ассемблера "Masm" фирмы Microsoft для процессоров Intel 80x86?
- # Какой регистр процессора содержит адрес инструкции, которая будет выполняться на следующем шаге?
- # Какой регистр процессора содержит текущий адрес вершины стека?
- # Для чего используется регистр FP?
- # Где располагаются элементы аппаратного стека?
- # Как передаются аргументы функций в языке Си?
- # Где хранятся локальные переменные функции в языке Си?
- # Пусть регистры 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:
- # Пусть регистры 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:
- # Пусть регистр 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 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 := EDX L3: ; add EBX, 4 ; EBX := EBX+4 dec ECX ; уменьшить ECX jmp L1 ; переход на метку L1 L2: ; метка конца цикла
- # Пусть регистр EBX содержит адрес массива целых чисел, регистр ECX — количество элементов массива. Указать, что будет содержать регистр EAX в результате выполнения следующего фрагмента кода на Ассемблере "Masm" для процессора Intel 80x86: 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 := ESI L3: ; add EBX, 4 ; EBX := EBX+4 inc ESI ; увеличить ESI jmp L1 ; переход на метку L1 L2: ; метка конца цикла
- # Пусть регистр EBX содержит адрес массива целых чисел, регистр ECX — количество элементов массива. Указать, что будет содержать регистр EAX в результате выполнения следующего фрагмента кода на Ассемблере "Masm" для процессора Intel 80x86: 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: ; метка конца цикла
- # Локальные переменные функции языка Си адресуются относительно регистра FP (Frame Pointer — указатель кадра). Что содержится в ячейке памяти, адрес которой записан в регистре FP, в процессе выполнения тела функции?
- # Функция языка Си имеет прототип int f(int x, int y); (т.е. имеет два целочисленных аргумента и возвращает целочисленное значение). Локальные переменные и аргументы функции адресуются относительно регистра FP, т.е. их адреса равны сумме содержимого FP и константы, задающей смещение. Чему равен адрес аргумента y функции?
- # В функции f языка Си описана одна целочисленная переменная z: int f(int x, int y) { int z; . . . } Локальные переменные и аргументы функции адресуются относительно регистра FP, т.е. их адреса равны сумме содержимого FP и константы, задающей смещение. Чему равен адрес переменной z?
- # Какое прерывание происходит при попытке выполнить деление на ноль?
- # Какое прерывание происходит при нажатии на клавишу на клавиатуре компьютера?
- # Что является причиной асинхронного прерывания?
- # Какой механизм используется для реализации виртуальной памяти в многозадачных операционных системах?
- # Что больше в современных архитектурах: объем физической памяти или объем виртуальной памяти?
- # Может ли задача использовать объем виртуальной памяти, который превышает объем физической памяти компьютера?
- # Являются ли локальные переменные функции общими для разных нитей (threads), работающих параллельно в рамках одного процесса?
- # Какие объекты операционной системы обычно используются для исключения одновременного доступа к критическим данным из разных нитей или процессов?
- # Что происходит при попытке захвата мьютекса нитью, если он уже захвачен другой нитью?
- # Что содержат заголовочные, или h-файлы, в случае языка Си?
- # Где размещаются определения глобальных и статических переменных языка Си?
- # Где размещаются описания прототипов глобальных функций языка Си?
- # Каковы размеры типов short, int и long в 32-разрядной архитектуре?
- # Каковы размеры типов float и double в языке Си?
- # Помещается ли число 80000 в переменную типа short в 32-разрядной архитектуре?
- # Чему равна вещественная константа 1000e-4, записанная в экспоненциальной форме?
- # Чему равна вещественная константа 0.001e+4, записанная в экспоненциальной форме?
- # Чему равно значение выражения 1.5e-2*1000.0?
- # Что означает описание "int *f()"?
- # Что означает описание "double (*a)[10]"?
- # Что означает описание "char *a[10]"?
- # Пусть p и q — два указателя на целочисленное значение: int *p, *q; Укажите все корректные выражения языка Си среди перечисленных ниже:
- # Пусть p и q — указатель на целочисленное значение и целочисленный массив: int *p, q[100]; Укажите все корректные выражения языка Си среди перечисленных ниже:
- # Рассмотрим следующий фрагмент программы: double *p; int i; . . . p = (double*) 1000; p += 10; i = (int) p; Чему будет равно значение переменной i в результате выполнения этого фрагмента?
- # Чему равно значение выражения ((786 >> 8) | 17)?
- # Чему равно значение выражения ((1234 & 255) << 2)?
- # Чему равно значение выражения ((40 & 27) >> 2)?
- # Указать, чему будет равно значение переменной i в результате выполнения следующего фрагмента программы: int i = 10; while (i <= 1000) { i *= 2; }
- # Указать, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int n = 1000; while (n > 100) { n /= 2; }
- # Указать, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int n = 3, k = 5; while (n != k) { n = (n * 2) % 11; k = (k * 7) % 11; }
- # Указать, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int n = 0; int i = 2; switch (i) { case 2: n += 2; case 4: n += 2; break; default: n += 6; }
- # Указать, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int n = 33; switch (n % 4) { case 1: n += 3; case 2: n += 2; case 3: ++n; break; default: ++n; }
- # Указать, чему будет равно значение переменной 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)?
- # Прототип функции, которая вычисляет сумму элементов массива a длины n, выглядит следующим образом: double sum(const double *a, int n); Можно ли в описании этой функции и ее прототипа опустить слово const? (Могут ли при этом в корректной программе возникнуть ошибки или предупреждения на стадии компиляции?)
- # Прототип функции, вычисляющей степень n числа a, выглядит следующим образом: double power(const double a, const double n); Можно ли в описании этой функции и ее прототипа опустить слова const? (Могут ли при этом в корректной программе возникнуть ошибки или предупреждения на стадии компиляции?)
- # Прототип функции, которая ищет вхождение строки 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 List { struct List *next; void *value; }; и переменые struct List e, *p; int m; Укажите все корректные выражения языка Си среди перечисленных ниже:
- # Пусть описана структура struct Tree { struct Tree *left; struct Tree *right; void *value; }; и переменые struct Tree *t1, *t2; int m; Укажите все корректные выражения языка Си среди перечисленных ниже:
- # Пусть описана структура struct Line { int len; char *str; }; и переменые struct Line s1, *s2; int n; char c; Укажите все корректные выражения языка Си среди перечисленных ниже:
- # Пусть описан тип 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?
- # Пусть описан тип 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 извлекает квадратный корень из вещественного числа).
- # Пусть описан тип 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;