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



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

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

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

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

Дана последовательность чисел: 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

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

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

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

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

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