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



Авторы специализируются на тестах по любым дисциплинам! Средний балл по тестам 4,6.
 
Любые вопросы по дистанционному обучению. Тесты, письменные работы, сессия под ключ.
 
Известный интернет сайт, помощь по любым учебным вопросам - от теста до дипломной работы. Личный менеджер.
 
Крупная биржа студенческих работ. Закажи напрямую у преподавателя. Низкие цены, стена заказов.
 
Биржа студенческих работ. Потребуется самостоятельная выгрузка работ.
 

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

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

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

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

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

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

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

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

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

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