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

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

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

Укажите верные высказывания

• (Правильный ответ) объем рекурсии равен количеству вершин полного рекурсивного дерева без единицы
• (Правильный ответ) количество элементов полных рекурсивных обращений всегда не меньше глубины рекурсивных вызовов
• у дерева рекурсии может быть пустое множество листьев
• одни и те же наборы параметров однозначно соответствуют одной вершине дерева рекурсии

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

• (Правильный ответ) 9
• 11
• 8
• 7

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

abcde0,40,150,220,050,18

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

Дан программный код. Какое значение возвращает функция Search?

int Search(int *x, int k, int key){ int i; for (i = k-1; i >=0 ; i—) if ( x[i] == key ) break; return i > 0 ? i : -1;}

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

Укажите порядок вершин при обходе графа в глубину, начиная с вершины 1

• 1 2 4 5 7 3 6 8
• 1 2 3 4 5 6 7 8
• 1 2 3 4 6 4 5 1 7 8
• (Правильный ответ) 1 2 3 4 6 5 7 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 ;}

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

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

int f (int k,int x[max]) { int i,m=x[0]; for (i=1;i<k;i++) if (m>x[i]) m=x[i]; return m;}

• минимальный элемент двумерного массива
• (Правильный ответ) минимальный элемент одномерного массива
• максимальный элемент одномерного массива
• максимальный элемент двумерного массива

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

• pt = new int;
• pt = new int (15);
• (Правильный ответ) pt = new int [];
• pt = new int [15];

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

• matr[i] = new int [m];
• int n=5, m=6,**matr;
• for (int i=0; i<n; i++)
• matr = new int * [n];

 

• 2134
• (Правильный ответ) 2431
• 2341
• 2314

В программном коде выполнено объявление динамической структуры стека:

struct Single_List { int Data; Single_List *Next; };struct Stack { Single_List *Top; }; . . . . . . . . . . . . . . .Stack *Top_Stack; Какое значение содержит Top_Stack->Top?

• адрес конца стека
• значение элемента из вершины стека
• адрес элемента внутри стека
• (Правильный ответ) адрес вершины стека

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

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

Укажите результат вывода на экран после выполнения фрагмента кода, если с клавиатуры введена строка: Я скоро завершу тестирование.

char str[100];cin >> str;cout << str;

• Я скоро завершу тестирование\0
• «Я скоро завершу тестирование»
• (Правильный ответ) Я
• Я скоро завершу тестирование

Укажите в байтах размер памяти, занимаемой массивом, который объявлен так:

int m[][5][3]={{{1,2,3},{1}},{{4},{7,8}}};

• (Правильный ответ) 120
• для безразмерного массива размер не определен
• 32
• 28

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

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

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

• float *const cpi;
• const float ci=1;
• const float *const cpc;
• (Правильный ответ) const float *pci;

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

• 16
• (Правильный ответ) данная операция над указателями не определена
• 0025FEAC
• 4

Даны следующие объявления и инициализации:

int x, *p, **q, ***r;x=5;p = &x;q = &p;r = &q; Укажите истинные высказывания:

• (Правильный ответ) значением переменой r является адрес адреса переменной p
• значением переменой p является число 5
• значением переменой q является число 5
• (Правильный ответ) значением переменой p является адрес, по которому хранится число 5

Укажите представление дерева во входном потоке, если каждой вводимой пустой связи соответствует символ звездочка ‘*’:

• (Правильный ответ) AB*D**CE*G**F**
• ABC*DEF***G**F**
• ABD*CEG*F*
• ABD**CEG**F**

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

int *n;*n=34;

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

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

if(…) perror(«»int.txt»»);

• «int.txt».is_open()
• (Правильный ответ) (f=fopen(«int.txt»,»w»))==0
• f=fopen(«int.txt»,»w»)==0
• feof(«int.txt»)

Сколькими способами можно расставить 4 ферзей на доске размера 44?

• 4
• (Правильный ответ) 2
• расстановок не существует
• 1

Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?

int Rec(int n) { if (n<3) return n; return Rec(n-1)*Rec(n-2);}

• 1, 2, 2, 4, 4, 8, 8, …
• (Правильный ответ) 1, 2, 2, 4, 8, 32, …
• 1, 1, 2, 2, 3, 3, …
• 1, 2, 3, 4, 5, 6, …

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

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

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

• child->book[]
• (Правильный ответ) child->book[1]
• *(child.book[1])
• child.book

Укажите последовательности, которые не являются бинарными пирамидами

• 7, 5, 7, 4, 2, 6, 5, 3, 2
• (Правильный ответ) 7, 5, 7, 4, 6, 2, 5, 3, 2
• (Правильный ответ) 8, 6, 8, 3, 0, 7, 6, 1, 3, 1
• 8, 6, 8, 3, 0, 7, 6, 1, 3

Какое значение возвращает рекурсивная функция Rec(108,72), код которой приведен ниже?

int Rec(int n,int k) { if (n%k==0) return k; return Rec(k,n%k);}

• (Правильный ответ) 36
• 72
• 12
• 1

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

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

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

• 0012FF54
• (Правильный ответ) 0012FF50
• 0012FF53
• данная операция над указателями не определена

Какое действие над списком выполняет следующая функция:

bool List(Single_List* Head){ if (Head!=NULL) return false; else return true; }

• поиск элемента в списке
• удаление элемента из списка
• (Правильный ответ) проверка списка на пустоту
• вставка элемента в конец списка

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

• *(man.name)
• *man.name
• man<-name
• (Правильный ответ) man->name

Охарактеризуйте смещение в двоичном файле f, задаваемое функцией

fseek(f,-sizeof(int),SEEK_END);

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

Что возвращает функция, фрагмент кода которой приведен ниже?

long int Rec(int n) { if (n<2) return 1; return Rec(n-1)*n;}

• количество делителей числа n
• количество цифр числа n
• произведение цифр числа n
• (Правильный ответ) факториал числа n

Дана последовательность n вещественных чисел. Необходимо найти число по ключу key с точностью e алгоритмом бинарного поиска. Оцените время выполнения алгоритма

• O(n)
• O(1+log n)
• O(n/e)
• (Правильный ответ) O(log 1/e)

Хеш-таблица формируется методом середин квадратов. Определите хеш-коды для первых пяти двузначных простых чисел, сформированные функцией Hash

int Hash(int Key) { return ((Key*Key)/10)%10 ;}

• 1, 1, 2, 3, 5
• 1, 9, 9, 1, 9
• 12, 16, 28, 36, 52
• (Правильный ответ) 2, 6, 8, 6, 2

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

• *s3=*s1+*s2
• s3=s1; s3=s3+s2;
• s3=s1+s2;
• (Правильный ответ) s3= strcat(s1,s2);

Укажите верные аналогичные обращения к элементу одномерного массива в присваивании mas[i]=3.

• &mas+i=3;
• mas+i=3;
• *mas+i=3;
• (Правильный ответ) *(mas+i)=3;

Укажите верное описание прототипа функции, если ее вызов осуществляется как gen(n,0,10,&mass); и объявлена переменная int **mass

• (Правильный ответ) void gen(int nn, int a, int b, int ***mas)
• void gen(int nn, int a, int b, int **mas)
• void gen(int nn, int a, int b, int *mas)
• void gen(int nn, int a, int b, int &mas)

Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите длину кода символа ‘b’. Считать, что очередной бит кода начинает формироваться с единицы

abcde0,40,150,220,050,18

• 3
• 2
• 1
• (Правильный ответ) 4

Что является результатом выполнения фрагмента кода: int *(*f)(char);?

• объявление функции c именем f типа указатель на int
• объявление указателя на функцию f типа int
• (Правильный ответ) объявление указателя на функцию f типа указатель на int
• объявление функции с именем f типа int

Объявлено объединение с битовыми полями и выполнено присваивание 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
• 18
• 1
• 2

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

• 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0
• 9, 7, 7, 6, 5, 4, 3, 2, 2, 0, 0
• (Правильный ответ) 7, 9, 7, 6, 5, 4, 2, 3, 2, 0, 0
• 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0

Укажите верное освобождение динамической памяти, занятой всеми элементами массива mass.

• (Правильный ответ) free (mass);
• free (*mass);
• (Правильный ответ) delete [] mass;
• delete mass;

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

• (Правильный ответ) pf = new float [15];
• pf = new float [];
• *pf = new float;
• pf = new sizeof(float);

Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?

int Rec(int n) { if (n<4) return n; return Rec(Rec(n-3));}

• 1, 2, 3, 4, 5, 6, 7, 8, 9, …
• (Правильный ответ) 1, 2, 3, 1, 2, 3, 1, 2, 3, …
• 1, 2, 3, 3, 3, 3, 3, 3, 3, …
• 1, 2, 3, 3, 2, 1, 1, 2, 3, …

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

• указатель на указатель
• объединение
• (Правильный ответ) файл
• указатель на объединение

В программном коде выполнено объявление динамической структуры дека:

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?

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

Какой объект объявлен следующим образом: float **nb;?

• (Правильный ответ) указатель на указатель на вещественное число
• указатель на функцию вещественного типа
• указатель на вещественное число
• переменная вещественного типа

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

float a (int k, float x[max]) { int i; float s=0.0; for (i=0;i<k;i++) s+=x[i]; return s/k;}

• (Правильный ответ) среднее арифметическое элементов одномерного массива
• сумму элементов одномерного массива, равных заданному
• результат деления каждого элемента одномерного массива на k
• сумму элементов одномерного массива

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

• разыменование
• сравнение
• приведение типов
• (Правильный ответ) сложение с вещественным числом

Что является результатом выполнения фрагмента кода: int *f(char);?

• объявление указателя на функцию f типа int
• объявление указателя на функцию f типа указатель на int
• объявление функции с именем f типа int
• (Правильный ответ) объявление функции c именем f типа указатель на int

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

• 0012FF49
• 0012FF48
• (Правильный ответ) 0012FF52
• данная операция над указателями не определена

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

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

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

float g(int a, int b, int c,int d){ return float(a+b+c)/4;}float g(float a, float b, float c){ return a+b+c;}

• ошибка вызова функции
• 8.5
• (Правильный ответ) 6.5
• 8

Функция Аккермана задана формулой:

Найдите объем рекурсии при вызове А(2, 2)

• 27
• 4
• 18
• (Правильный ответ) 26

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

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

Определите размер структуры, которая объявлена следующим образом:

struct Book { int number; union { char titl[30]; char x; } info; };

• 30
• 50
• (Правильный ответ) 36
• 32

Что возвращает функция, фрагмент кода которой приведен ниже?

int Rec(int n) { if (n<10) return n; return Rec(n/10)+n%10;}

• сумму всех делителей числа n
• количество цифр числа n
• количество всех делителей числа n
• (Правильный ответ) сумму цифр числа n

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

• *woman.name
• (Правильный ответ) (*woman).name
• name<-woman
• *(woman.name)

Укажите порядок освобождения динамической памяти, выделенной ранее под двумерный массив

• free (matr[i]);
• free (matr);
• for (int i=0; i<n; i++)

 

• 231
• (Правильный ответ) 312
• 213
• 321

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

• 4, 3, 3, 2, 5, 6, 7, 7, 8, 6, 8
• 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8
• 3, 4, 5, 7, 8, 2, 3, 6, 6, 7, 8
• (Правильный ответ) 3, 2, 4, 3, 5, 6, 6, 7, 7, 8, 8

Укажите случаи допустимого неявного преобразования типов в выражениях, если выполнено объявление int s;:

• (Правильный ответ) s=20/6;
• s=int(48.6/4);
• s=4.5%8;
• (Правильный ответ) s=48.6/4;

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

while(…) { ch=getc(ofs); printf(«»%c»»,ch); }

• feof(ofs)
• (Правильный ответ) !feof(ofs)
• ofs
• !ofs.is_open()

Что является результатом выполнения фрагмента кода: int (*f)(char);?

• объявление функции с именем f типа int
• (Правильный ответ) объявление указателя на функцию f типа int
• объявление функции c именем f типа указатель на int
• объявление указателя на функцию f типа указатель на int

Укажите, что характерно для динамической структуры данных

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

Укажите вид функции временной трудоемкости для следующей функции в зависимости от размера массива

void out (int str,int slb, int m[max_x][max_y]){ int i,j; for (i=0;i<str;i++) { for (j=0;j<slb;j++) printf(«»%4d»»,m[i][j]); printf(«»\n»»); }}

• O(n)
• (Правильный ответ) O(n2)
• O(n log n)
• O(log n)

Укажите вид обхода дерева, представленного на рисунке, если порядок просмотра вершин следующий: A B D E C F

• (Правильный ответ) прямой
• симметричный
• этот путь не является обходом
• обратный

Какие действия со строками происходят в ходе выполнения фрагмента кода:

char * str (char *s1, char *s2){ char *ps1 = s1; while ((*s1++ = *s2++) != 0); return ps1; }

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

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

• const float ci=1;
• float *const cpi;
• (Правильный ответ) const float *const cpc;
• const float *pci;

Укажите верное условие вместо многоточия, чтобы выполнялась проверка на корректность открытия файла ofs:

if (…) cout << «»Файл не открыт\n»»;

• (Правильный ответ) !ofs.is_open()
• feof(ofs)
• (Правильный ответ) !ofs
• ofs

Какое значение возвращает функция

fgets(buf, 8, fp);, если указатель установлен на начало файла fp, который имеет вид: ЯзыкПрограммированияС++

• Язык Про
• ЯзыкПрог
• Я
• (Правильный ответ) Язык

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

int *p,i=55;p=&i;delete p;

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

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

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

Укажите вид обхода дерева, представленного на рисунке, если порядок просмотра вершин следующий: D B E A C F

• (Правильный ответ) симметричный
• прямой
• обратный
• этот путь не является обходом

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

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

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

• многопутевая
• (Правильный ответ) двухпутевая
• однофазная
• (Правильный ответ) двухфазная