Структуры и алгоритмы компьютерной обработки данных - ответы на вопросы

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

В языке С++ структуры данных, которые при внесении в них каких-либо изменений сохраняют все свои предыдущие состояния и доступ к ним, называются ...

Объект или точка в графе, который является фундаментальным строительным блоком, называется …

Решение задач с использованием динамического программирования обычно осуществляется при помощи …

Дерево, в котором у каждого узла высоты его левого и правого поддеревьев отличаются не более чем на единицу, называется ...

Бинарное дерево, в котором все листья находятся на одном уровне, называется ...

В информатике графом называют …

Основной задачей такого алгоритма является нахождение кратчайших путей от одного узла графа до всех остальных, имеющий название фамилии учёного, и он называется алгоритмом …

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

В основном для поиска минимального остовного дерева в связном графе используется алгоритм …

АВЛ-дерево в программировании — это …

Неверно, что в бинарном дереве листовой узел …

Представление связи или отношения между двумя узлами в графе осуществляется при помощи …

Представлением графа в виде матрицы является …

Общий подход к решению задач с использованием динамического программирования осуществляется при помощи …

Рёбра в направленном графе имеют …

В программе объявлен и проинициализирован объект: std::string error{ “Invalid password!” }; Его значение выводится на экран.Каким будет вывод, если к объекту последовательно применить методы replace(8, 5, “username”, 4), append(“name”) и c_str()?

Каково назначение типа void?

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

В программе объявлен и проинициализирован массив int a[]={9,8,7,6,5,4,3,2,1,0}. Укажите значение a[a[a[9]]].

• 9
• 0
• 1
• элемент с таким индексом в данном массиве не определен

Укажите результат вывода на экран после выполнения фрагмента кода, если с клавиатуры введена строка: Я скоро завершу тестирование. char str[100];gets(str);puts(str);

• Я
• Я скоро завершу тестирование
• "Я скоро завершу тестирование"
• Я скоро завершу тестированиеn

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

• таблица прямого доступа
• закрытое хеширование
• повторное хеширование
• открытое хеширование

Укажите порядок выделения динамической памяти под двумерный массив matr[i] = new int [m];int n=5, m=6,**matr;for (int i=0; i

2134

2431

2314

2341

Укажите, что разрешено выполнять над указателем, который объявлен int const *pa.

• разыменовывать указатель
• изменять значения указателя
• изменять значение, на которое указывает указатель
• инициализировать указатель

Укажите в байтах размер памяти, занимаемой массивом, который объявлен так: float m[][6]={{6.2},{14.3,0.3},{7.0,1.0,5.5,7.8}};

• 28
• 48
• 72
• для безразмерного массива размер не определен

Охарактеризуйте ошибку при использовании действий с указателями во фрагменте кода: int *p,i=55;p=&i;delete p;

• значение присваивается неинициализированному указателю
• попытка освободить нединамическую память
• указатель неверно объявлен
• несоответствие типов в присваивании

Укажите некорректное выделение динамической памяти, если выполнено объявление int *pt;

• pt = new int;
• pt = new int [15];
• pt = new int [];
• pt = new int (15);

Укажите результат выполнения операции pa++, если выполнено объявление int *pa; и инициализация указателя адресом 0012FF48.

• 0012FF48
• 0012FF49
• 0012FF52
• данная операция над указателями не определена

В какой строке будут выведены одинаковые результаты, если ранее выполнены следующие инициализации: int a=3,*pa,*pb;pa=&a;pb=pa;

• printf ("n%p %p ",pa, pb);
• printf ("n%p %p ",&pb, &a);
• printf ("n%d %d ",*pa, *pb);
• printf ("n%d %d ",pb, a);

Укажите возможные недостатки использования подставляемых функций в программе.

• увеличивается время, затрачиваемое на вызов функции
• увеличивается объем памяти под программный код
• функция доступна для подстановки только один раз
• компилятор не всегда может выполнить подстановку из-за контекста

Укажите обращение, аналогичное обращению (*(arr+i))[j] к элементу двумерного массива размерности MN.

• *(mas+N*i+j)
• mas[i][j]
• *(*(mas+i)+j)
• mas[i,j]

К битовым полям нельзя применять следующие действия:

• объявлять массивы битовых полей
• обращаться через указатель: (*УказательНаСтруктуру).ИмяПоля
• объявлять битовые поля вне структур
• выполнять присваивания значений битовым полям

Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит кратчайший путь из данной вершины до остальных вершин. Построим множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин." Укажите название алгоритма

• алгоритм перебора с возвратом
• волновой алгоритм
• алгоритм Дейкстры
• алгоритм Флойда

Дан массив элементов: 7, 9, 0, 3, 2, 4, 7, 6, 5, 2, 0. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции

• 9, 7, 7, 6, 5, 4, 3, 2, 2, 0, 0
• 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0
• 7, 9, 7, 6, 5, 4, 2, 3, 2, 0, 0
• 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0

Какое решение задачи называется частичным?

• один из вариантов, соответствующий условию задачи
• один из вариантов решения, полностью отличный от остальных
• краевые решения задачи
• часть одного из вариантов, соответствующего условию задачи

Сколько существует основных расстановок 4 ферзей на доске размером 44?

• расстановок не существует
• 1
• 2
• 4

Значение какого выражения возвращает функция Rec(a,x,n), код которой приведен ниже? float Rec(float *a, float x, int n){ if(n==0) return a[0]; return a[n]+x*Rec(a,x,n-1);}

• a0xn+a1xn-1+...an-1x+an
• anxn+an-1xn-1+...a1x+a0
• (a0+a1+...an-1+an)x
• an+an-1x+...a1x+a0x

В программном коде выполнено объявление динамической структуры дека: struct Double_List { Double_List *Prior; int Data; Double_List *Next; };struct Deque { Double_List *Begin; Double_List *End; };. . . . . . . . . . . . . . .Deque *My_Deque; Какого типа значение содержится по адресу: My_Deque->End->Next?

• указатель на информационное поле
• указатель на внутренний элемент дека
• целочисленное значение информационного поля
• указатель на один из концов дека

Укажите верный вызов функции, если объявлен ее прототип void gen(int nn, int a, int b, int ***mas) и переменная int **mass

• gen(n,0,10,**mass);
• gen(n,0,10,*mass);
• gen(n,0,10,&mass);
• gen(n,0,10,mass);

Какие действия выполняет приведенный фрагмент кода? int n=15, i;double *mas; mas = (double *)malloc(sizeof(double)); for (i=0; i

выделяет динамическую память для 15 вещественных элементов и считывает в него элементы с клавиатуры

не выполнено явное преобразование типа указателя при выделении динамической памяти, фрагмент ошибочный

во фрагменте ошибка вследствие неверного обращения к элементам массива

динамическая память выделена только для одного вещественного числа, фрагмент ошибочный

Укажите, какие действия с массивом выполняет функция, фрагмент кода которой представлен ниже: void p(int strslb, int m[max][max]) { int i,buf,t; for (i=0;i

поиск номеров минимальных элементов в каждом столбце двумерного массива

циклический сдвиг столбцов квадратной матрицы

замена значений всех элементов главной диагонали на модуль максимального элемента

обмен значениями элементов диагоналей квадратной матрицы, расположенных в одной строке

Укажите название алгоритма сортировки, фрагмент кода которой представлен ниже. void Sort (int k,int x[max]) {int i,j,min,temp; for (i=0;i

пузырьковая сортировка

шейкерная сортировка

сортировка методом простого выбора

сортировка методом простого включения

Укажите для целого беззнакового 4-байтного типа преобразования к целевому типу без потери информации:

• к плавающему типу
• к целому знаковому 4-байтному типу
• к логическому типу
• к целому беззнаковому 8-байтному типу

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

• обобщить
• увидеть
• найти родственника
• переформулировать

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

• открытое хеширование
• закрытое хеширование
• таблица прямого доступа
• повторное хеширование

Укажите доступ к элементу структуры, эквивалентный обращению (*child).book[1]:

• child->book[]
• child->book[1]
• *(child.book[1])
• child.book

Охарактеризуйте значение указателя в результате выделения памяти для массива из нулевого или отрицательного числа элементов

• будет возвращено значение NULL
• будет возвращено заранее непредсказуемое значение
• программа аварийно завершится с ошибкой сегментации
• будет возвращено значение адреса выделенной области памяти

В алгоритме внешней сортировки используется два вспомогательных файла и совмещены распределение и слияние. Определите характеристики такой сортировки

• однофазная
• двухфазная
• двухпутевая
• многопутевая

Дана последовательность чисел: 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8. Нумерация элементов начинается с нуля. Элемент с каким номером будет найден методом бинарного поиска по ключу key=8?

• 14
• 15
• 16
• 17

Значение какого выражения возвращает функция Rec(1, 1, n), код которой приведен ниже? int Rec(int a,int b,int k){ if(k<2) return b; return Rec(b,a+b,k-1);}

• 1+1+2+3+...+n
• 1+1+2+2+3+3+...+n+n
• сумму n первых чисел последовательности Фибоначчи
• n-ый член последовательности Фибоначчи

Укажите вид функции временной трудоемкости для следующей функции в зависимости от размера массива void out (int str,int slb, int m[max_x][max_y]){ int i,j; for (i=0;i

O(n)

O(n2)

O(log n)

O(n log n)

Какое действие над списком выполняет следующая функция: bool List(Single_List* Head){ if (Head!=NULL) return false; else return true; }

• удаление элемента из списка
• вставка элемента в конец списка
• поиск элемента в списке
• проверка списка на пустоту

Укажите порядок освобождения динамической памяти, выделенной ранее под двумерный массив delete matr [i];for (int i=0; i

123

321

213

231

Какая область динамической памяти, выделенной под одномерный массив mass, будет освобождена следующим действием: delete mass;?

• вся используемая динамическая память
• область, занятая всеми элементами массива mass
• область, занятая только первым элементом массива mass
• к массиву данная операция не применима

Динамическая память явно не освобождена в программе. Тогда:

• она будет занята и после завершения программы
• она автоматически освободится после завершения работы программы
• она освободится только при выходе из среды программирования
• она освободится только после выключения компьютера

Охарактеризуйте смещение в двоичном файле f, задаваемое функцией fseek(f,-sizeof(int),SEEK_END);

• от текущей позиции на 4 байта вперед
• от текущей позиции на 4 байта назад
• от конца файла на 4 байта назад
• от начала файла на 4 байта вперед

Библиотека С++ поддерживает следующие уровни ввода-вывода:

• низкоуровневый
• потоковый
• для консоли и портов
• типизированный

Объявлено объединение с битовыми полями и выполнено присваивание cod.n=18. Укажите значение поля a2 union { unsigned n; struct { unsigned a0 : 1; unsigned a1 : 1; unsigned a2 : 1; unsigned a3 : 1; unsigned a4 : 1; unsigned a5 : 1; unsigned a6 : 1; unsigned a7 : 1; } byte; } cod;

• 0
• 1
• 2
• 18

Прототип функции объявлен так: void STU (struct Student *pst); Данная функция:

• передает указатель на объект структурного типа как параметр
• возвращает структуру как результат
• передает структуру как параметр
• возвращает указатель на структуру как результат

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

• объявляемая структура
• массив указателей
• строка
• указатель на объявляемую структуру

Укажите действия, эквивалентные по значению следующей инициализации: char c=0;

• char c='';
• char c="0";
• char c='0';
• char c[]={'0'};

Какие действия со строками происходят в ходе выполнения фрагмента кода: char * str (char *s1, char *s2){ char *ps1 = s1; while ((*s1++ = *s2++) != 0); return ps1; }

• содержимое строки s1 побайтово копируется в строку s2
• из строки s1 удаляются все вхождения строки s2
• происходит сравнение строк
• содержимое строки s2 побайтово копируется в строку s1

Укажите длину строки char text[]={'Р','е','д','а','к','т','о','р',''};

• 10
• 9
• длина не определена
• 8

Каким образом компилятором происходит контроль конца списка параметров во фрагменте кода: float sum(int k, ...) { int *p=&k; float s=0; for(;k!=0;k--) s+=*(++p); return s;}

• количество параметров у функций при компиляции должно быть фиксировано
• известно количество параметров в списке
• контроль конца списка параметров данной функции проводить не надо
• известен признак конца списка параметров

Укажите операции, запрещенные над указателями:

• разыменование
• приведение типов
• сложение с вещественным числом
• сравнение

Укажите результат выполнения операции pb+pa, если выполнено объявление int *pa,*pb; и инициализация указателей адресами 0012FF48 и 0012FF64 соответственно.

• 16
• 0025FEAC
• 4
• данная операция над указателями не определена

Что возвращает функция, фрагмент кода которой приведен ниже? int Rec(int n, int p) { if (n%p!=0) return 0; return Rec(n/p,p)+1;}

• сумму цифр числа n, кратных p
• количество цифр числа n, кратных p
• p-ичный порядок числа n
• сумму всех делителей числа n, не превосходящих p

Укажите допустимые присваивания для переменной ch символьного типа.

• ch='&&&';
• ch=5.5;
• ch=55;
• ch='&';

Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите среднюю длину кодового слова, которая равна сумме произведений вероятности на длину кода каждого символа соответственно. Считать, что очередной бит кода начинает формироваться с единицы abcde0,40,150,220,050,18

• 4
• 2,8
• 3
• 2,14

Укажите в байтах размер памяти, занимаемой массивом, который объявлен так: int m[][5][3]={{{1,2,3},{1}},{{4},{7,8}}};

• 28
• 32
• 120
• для безразмерного массива размер не определен

Дан массив элементов: 4, 7, 3, 0, 3, 2, 6, 8, 7, 2, 6, 4. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по невозрастанию с шагом h=6

• 7, 4, 3, 0, 3, 2, 8, 6, 7, 2, 6, 4
• 8, 7, 7, 6, 6, 4, 4, 3, 3, 2, 2, 0
• 8, 7, 6, 6, 4, 2, 7, 4, 3, 3, 2, 0
• 6, 8, 7, 2, 6, 4, 4, 7, 3, 0, 3, 2

После распределения по двум файлам были получены данные (серии разделены апострофом) f1: 3 7 2 8 5 9 1 3 f2: 6 9 3 5 7 7 Выполните слияние этих результатов в один файл согласно алгоритму простой сортировки по неубыванию

• 3 7 6 9 2 8 3 5 5 9 7 7 1 3
• 3 7 2 8 6 9 3 5 5 9 1 3 7 7
• 3 7 2 8 5 9 1 3 6 9 3 5 7 7
• 3 6 7 9 2 3 5 8 5 7 7 9 1 3

Укажите корректные способы конкатенации строк s1 и s2 в строку s3. Считать, что размер s3 позволяет выполнить это действие.

• s3=s1+s2;
• s3=s1; s3=s3+s2;
• s3= strcat(s1,s2);
• *s3=*s1+*s2

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

• по достижению символа конца файла
• по количеству считанных из файла байтов
• по количеству считанных из файла строк
• по счетчику ссылок в записи таблицы файлов

Укажите, какое значение возвращает функция f(a,b,c), если объявлены int a=3,b=5,c=18; и функция перегружена следующим образом: float f(int a, int b, int c){ return float((a+b+c)/3);}float f(float a, float b, float c){ return a+b+c;}

• ошибка вызова функции
• 26
• 8.66667
• 8

Укажите, что возвращает функция, фрагмент кода которой представлен ниже: float a (int k, float x[max]) { int i; float s=0.0; for (i=0;i

сумму элементов одномерного массива

среднее арифметическое элементов одномерного массива

результат деления каждого элемента одномерного массива на k

сумму элементов одномерного массива, равных заданному

Укажите объявление указателя на вещественную константу.

• const float ci=1;
• const float *pci;
• float *const cpi;
• const float *const cpc;

Укажите результат выполнения функции сравнения строк в приведенном фрагменте кода (элементы строки – символы латинского алфавита): char ch[]="abd",sh[]="abc";int i;i=strcmp(ch,sh);printf ("%d",i);

• 0
• над строками сравнение не определено
• 1
• -1

Укажите верные аналогичные обращения к указателю на одномерный массив в присваивании int *p; p=mas;

• int *p; p=mas[0];
• int *p; p=&mas[0];
• int *p; p=*mas[0];
• int *p; p=*mas;

Укажите верное условие вместо многоточия, чтобы выполнялась проверка на корректность открытия файла int.txt: if(...) perror("int.txt");

• feof("int.txt")
• (f=fopen("int.txt","w"))==0
• f=fopen("int.txt","w")==0
• "int.txt".is_open()

Укажите, какие действия с массивом выполняет функция, фрагмент кода которой представлен ниже: void z (int k,int x[max]){ int i; for (i=0;i

переставляет отрицательные элементы по убыванию

находит разность всех отрицательных элементов

находит минимальный отрицательный элемент в массиве

заменяет значения отрицательных элементов их модулями

Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании факта о том, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей." Укажите название алгоритма

• алгоритм Дейкстры
• алгоритм Флойда
• волновой алгоритм
• алгоритм перебора с возвратом

Дан массив элементов: 4, 7, 9, 0, 3, 2, 6, 8, 7. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по неубыванию с шагом h=4

• 4, 7, 0, 9, 2, 3, 6, 8, 7
• 3, 2, 6, 0, 4, 7, 9, 8, 7
• 0, 2, 3, 4, 6, 7, 7, 8, 9
• 0, 4, 7, 9, 2, 3, 6, 8, 7

Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения первого прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции

• 8, 8, 7, 7, 6, 6, 5, 4, 3, 3, 2
• 8, 7, 5, 4, 3, 6, 8, 7, 6, 3, 2
• 8, 7, 7, 8, 6, 5, 3, 3, 2, 6, 4
• 7, 4, 8, 3, 6, 5, 7, 3, 6, 2, 8

Дан программный код. Какое значение возвращает функция Search? int Search(int *x, int k, int key){ bool found = false; int high = k - 1, low = 0; int middle = (high + low) / 2; while ( !found && high >= low ){ if (key == x[middle]) found = true; else if (key < x[middle]) high = middle - 1; else low = middle + 1; middle = (high + low) / 2; } return found ? middle : -1 ;}

• значение среднего элемента массива
• номер последнего элемента, совпадающего с ключом поиска
• номер первого элемента, совпадающего с ключом поиска
• номер элемента, совпадающего с ключом поиска

Укажите методы организации исчерпывающего поиска

• перебор с возвратом
• метод ветвей и границ
• метод решета
• метод пошаговой детализации

Укажите вид функции временной трудоемкости для следующей функции в зависимости от параметра n float Step(float p, int n){ if (n==0) return 1; if (n%2==0) return pow(Step(p,n/2),2); return p*Step(p,n-1); }

• O(n2)
• O(log n)
• O(n log n)
• O(n)

В программном коде выполнено объявление однонаправленного списка: struct Single_List { int Data; Single_List *Next; };Single_List *Head; Укажите верно объявленный прототип функции поиска элемента в списке

• bool Find(Single_List* Head, int Data);
• bool Find(Single_List** Head, int Data);
• bool Find(Single_List Head, int Data);
• bool Find((**Single_List) Head, int Data);

Какие действия выполняет приведенный фрагмент кода? int *mas, n=10, i; mas = new int [n]; mas[0]= a[1]=1;for (i=2; i

выделяет динамическую память для 10 целочисленных элементов массива и заполняет его числами Фибоначчи

выделяет динамическую память для 10 целочисленных элементов и заполняет его случайными числами

обращение к элементам массива неверно, фрагмент ошибочный

динамическая память под массив не выделена, фрагмент ошибочный

Чем ограничен размер динамической памяти?

• нет никаких ограничений
• размером оперативной памяти
• размером внешних накопителей
• размером стековой области

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

• редактируемый файл
• дополнительный файл
• массив указателей в памяти программы
• редактирование файла выполняется без дополнительных ресурсов памяти

Охарактеризуйте смещение в двоичном файле f, задаваемое функцией fseek(f,sizeof(float),SEEK_CUR);

• от текущей позиции на 4 байта вперед
• от текущей позиции на 4 байта назад
• от конца файла на 4 байта назад
• от начала файла на 4 байта вперед

Укажите верное условие вместо многоточия, чтобы выполнялась проверка на корректность открытия файла ofs: if (...) cout << "Файл не открытn";

• !ofs
• ofs
• !ofs.is_open()
• feof(ofs)

Какое значение возвращает функция fscanf(fp, "%s %s", buf1, buf2); если указатель установлен на начало файла fp, который имеет вид: ЯзыкПрограммированияС++

• Язык Программирования
• 20
• 2
• ЯзыкПрограммирования

Что будет являться результатом выполнения функции fp=fopen("t.txt","w+");, если файл t.txt не существует?

• создается и открывается файл с именем t.txt
• на диск записывается пустой файл с именем t.txt
• действие игнорируется, программа продолжает выполняться
• выдается ошибка при исполнении программы

В языке С++ файлы делятся на:

• типизированные
• текстовые
• двоичные
• структурированные

Объявлено объединение с битовыми полями и выполнено присваивание cod.n=12. Укажите значение поля a3 union { unsigned n; struct { unsigned a0 : 1; unsigned a1 : 1; unsigned a2 : 1; unsigned a3 : 1; unsigned a4 : 1; unsigned a5 : 1; unsigned a6 : 1; unsigned a7 : 1; } byte; } cod;

• 0
• 1
• 12
• 21

Прототип функции объявлен так: struct Student f (char Name[30]); Данная функция:

• возвращает структуру как результат
• возвращает указатель на структуру как результат
• передает структуру как параметр
• передает указатель на объект структурного типа как параметр

Укажите доступ к элементу структуры, эквивалентный обращению woman->name:

• name<-woman
• *woman.name
• *(woman.name)
• (*woman).name

Укажите, что возвращает функция, фрагмент кода которой представлен ниже: int d(int str,int slb, int m[max_x][max_y]){ int i,j,mm=m[0][0]; for(i=0;imm)) mm=m[i][j]; return mm;}

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

Укажите обращение, аналогичное обращению *(*(mas+i)+j) к элементу двумерного массива размерности MN.

• *(mas+N*i+j)
• mas[i][j]
• mas[0][0]+ N*i+j
• mas[i,j]