Структуры и алгоритмы компьютерной обработки данных - ответы
Количество вопросов - 262
Сколько существует расстановок 5 ферзей на доске размера 55, при которой один из ферзей занимает центр доски?
Выполните кодирование текста "abcaabbaac", к которому применено сжатие по методу Хаффмана. Считать, что очередной бит кода начинает формироваться с единицы
Укажите опорную схему рекурсивных вычислений, в которой совокупность всех или части условий любой задачи оформлена в виде некоторого предиката
Укажите вид функции временной трудоемкости для следующей функции в зависимости от параметра n float G(float p, int n){ if(n==0) return 1; return G(p,n-1)*p;}
Укажите верное описание прототипа функции, если ее вызов осуществляется как gen(n,0,10,&mass); и объявлена переменная int **mass
Какое значение возвращает функция fgets(buf, 8, fp);,
если указатель установлен на начало файла fp, который имеет вид: ЯзыкПрограммированияС++
В программном коде выполнено объявление однонаправленного списка: struct Single_List { int Data; Single_List *Next; };Single_List *Head;
Укажите верно объявленный прототип функции печати списка
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже? int Rec(int n) { if (n<4) return n; return Rec(Rec(n-3));}
Дана последовательность чисел: 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 8. Нумерация элементов начинается с нуля. Элемент с каким номером будет найден методом бинарного поиска по ключу key=5?
Во входном файле дан массив чисел: 5 6 9 3 2 3 4 5 4 7 8 6 0
Выполните первое распределение входных данных по двум вспомогательным файлам f1 и f2, используя сортировку по неубыванию естественным слиянием
Определите размер объединения, которое объявлено следующим образом: union Book { int num[5]; char titl[30]; char x; };
Укажите представление дерева во входном потоке, если каждой вводимой пустой связи соответствует символ звездочка '*':
Разработана рекурсивная функция F(n,k). Определите объем рекурсии без листьев при вызове F(5,9) int F(int n, int k){ if(n==1 || k==1) return 1; if(n<=k) return F (n,n-1)+1; return F(n,k-1)+ F(n-k,k);}
Составьте таблицу смещений при поиске подстроки в строке по алгоритму Бойера и Мура. Строка: АВВОМРАВАВМАВ, подстрока: ВАВ. Нумерация в строке начинается с нуля
Какие действия со строками происходят в ходе выполнения фрагмента кода: char * str (char *s) {int i;char *p; for(i=0; s[i] && s[i]==' '; i++); p = &s[i]; return p;}
В алгоритме внешней сортировки используется три вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки
Укажите ситуации, когда функция со спецификатором inline будет трактоваться как обычная не подставляемая функция.
Укажите, какое значение возвращает функция 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;}
Укажите случаи допустимого неявного преобразования типов в выражениях, если выполнено объявление int s;:
Что возвращает функция, фрагмент кода которой приведен ниже? int Rec(int n) { if (n<10) return n; return Rec(n/10)+n%10;}
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже? int Rec(int n) { if (n<5) return n; return Rec(n-1)+Rec(n%4);}
Какое значение возвращает рекурсивная функция Rec(8), код которой приведен ниже? int Rec(int n) { if (n<1) return 0; if (n%3==0) return n/3; return Rec(n-1)+Rec(n-2);}
В каких строках будут выведены одинаковые результаты, если ранее выполнены следующие инициализации: int a=3,*pa,*pb;pa=&a;pb=pa;
Укажите результат выполнения операции pa--, если выполнено объявление float *pa; и инициализация указателя адресом 0012FF54.
Каким образом компилятором происходит контроль конца списка параметров во фрагменте кода: double rec(double(*pf)(double), double a, double b){ int N, i; double h,s=0.0; printf("\nВведите количество интервалов разбиения: N= "); scanf("%d",&N); printf("\na= "); h=(b-a)/N; for (i=0;i<N;i++) s+=pf(a+h/2+i*h); return h*s;}
Даны следующие объявления и инициализации: int x, *p, **q, ***r;x=5;p = &x;q = &p;r = &q;
Укажите истинные высказывания:
Укажите результат выполнения функции сравнения строк в приведенном фрагменте кода (элементы строки – символы латинского алфавита): char ch[]="aacd",sh[]="abc";int i;i=strcmp(ch,sh);printf ("%d",i);
В каких строках будут выведены разные результаты, если ранее выполнены следующие инициализации: char ch[]="abd",*pch;pch=ch;
Укажите результат вывода на экран после выполнения фрагмента кода, если с клавиатуры введена строка: Я скоро завершу тестирование. char str[100];scanf("%s", str);printf("%s", str);
В программе объявлен и проинициализирован массив int a[]={2,4,6,8,10,12,14,16}. Укажите значение *(a+a[2]).
Укажите название алгоритма сортировки, фрагмент кода которой представлен ниже. void Sort (int k,int x[max]) { int i,j, temp; for (i=0;i<k;i++) { temp=x[i]; for (j=i-1; j>=0 && x[j]>temp; j--) x[j+1]=x[j]; x[j+1]=temp; }}
Укажите в байтах размер памяти, занимаемой массивом, который объявлен так: int m[][7]={{6,2,4,8},{13},{5,6,7}};
Укажите, что возвращает функция, фрагмент кода которой представлен ниже: 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;}
Укажите, какие действия с массивом выполняет функция, фрагмент кода которой представлен ниже: void t(int str,int slb, int m[max][max],int min[max]){ int i,j; for (j=0;j<slb;j++){ min[j]=0; for (i=1;i<str;i++) if (m[i][j]<m[min[j]][j]) min[j]=i; }}
Определите размер структуры, которая объявлена следующим образом: struct Book { int num[5]; char titl[30]; char x; };
Объявлена структура mail. Укажите верные для этой структуры присваивания struct mail { int id; union { struct { char name[30]; char dept[10]; char location[3]; } active; struct { char name[30]; char street[20]; char city_state[3]; char zip[5]; } retired; } info; } preson;
Объявлено объединение с битовыми полями и выполнено присваивание cod.n=14. Укажите значение поля a1 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;
При объявлении union { unsigned a0 : 3; unsigned a1 : 1; unsigned a2 : 2; } byte;
битовые поля располагаются в памяти:
Что будет являться результатом выполнения функции fp=fopen("t.txt","r+");, если файл t.txt не существует?
Какое значение возвращает функция fgetc(fp);,
если указатель установлен на начало файла fp, который имеет вид: ЯзыкПрограммированияС++
Укажите верное условие вместо многоточия, чтобы выполнялось корректно чтение из открытого файла ofs: while(...) { ch=getc(ofs); printf("%c",ch); }
Охарактеризуйте смещение в двоичном файле f, задаваемое функцией fseek(f,sizeof(int)+sizeof(float),SEEK_SET);.
Укажите ошибку при использовании операции выделения динамической памяти, если выполнено объявление char *ph;
Какая область динамической памяти, выделенной под одномерный массив mass, будет освобождена следующим действием: free (mass);?
Какие действия выполняет приведенный фрагмент кода?int n=20, i;float *mas; mas = (float *) calloc(n,sizeof(float)); for (i=0; i<n; i++) mas[i]= exp(i);
Укажите порядок освобождения динамической памяти, выделенной ранее под двумерный массив free (matr[i]); free (matr); for (int i=0; i<n; i++)
Укажите верный вызов функции, если объявлен ее прототип void out(int nn, int **mas) и переменная int **mass
В программном коде выполнено объявление однонаправленного списка: struct Single_List { int Data; Single_List *Next; };Single_List *Head;
Укажите верно объявленный прототип функции формирования списка из n элементов
Какое действие над списком выполняет следующая функция: void List(Single_List* Head){ if (Head != NULL){ List(Head->Next); delete Head; }}
В программном коде выполнено объявление динамической структуры очереди: struct Double_List { Double_List *Prior; int Data; Double_List *Next; };struct Queue { Double_List *Begin; Double_List *End; };. . . . . . . . . . . . . . .Queue *My_Queue;
Укажите примеры правильно выполненной адресации
Укажите представление дерева во входном потоке, если каждой вводимой пустой связи соответствует символ звездочка '*':
Укажите вид обхода дерева, представленного на рисунке, если порядок просмотра вершин следующий: A B D E C F
Разработана рекурсивная функция F(n,k). Определите глубину рекурсии при вызове F(4,7) int F(int n, int k){ if(n==1 || k==1) return 1; if(n<=k) return F (n,n-1)+1; return F(n,k-1)+ F(n-k,k);}
Значение какого выражения возвращает функция Rec(1, n), код которой приведен ниже? int Rec(int s,int k){ if(k==0) return s; return Rec(1+s*k,k-1);}
Укажите опорную схему рекурсивных вычислений, которая способствует уменьшению трудоемкости алгоритма за счет исключения несущественных случаев
Дана последовательность n вещественных чисел. Необходимо найти число по ключу key с точностью e алгоритмом бинарного поиска. Оцените время выполнения алгоритма
Дан программный код. Какое значение возвращает функция Search? int Search(int *x, int k, int key){ x = (int *)realloc(x,(k+1)*sizeof(int)); x[k] = key; int i = 0; while ( x[i] != key ) i++; return i < k ? i : -1;}
Хеш-таблица формируется методом поразрядного сложения двузначных представлений цифр числа с последующим переводом результата в десятичное число. Определите хеш-коды для первых пяти двузначных составных чисел, сформированные функцией хеширования
Если осуществляется попытка поместить элемент х в сегмент с номером h(x), который уже занят другим элементом, то в соответствии с данной методикой выбирается последовательность других номеров сегментов h1(x),h2(x),..., куда можно поместить элемент х. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. О какой методике хеширования идет речь?
Укажите, на какую позицию произойдет пятое смещение начала подстроки при поиске в тексте по алгоритму Бойера и Мура. Строка: АВСССКВАВСМВВВК, подстрока: ВСМ. Нумерация в строке начинается с нуля
Дано упорядоченное бинарное дерево. Укажите позицию вставки элемента с ключом 3 в это дерево, чтобы соблюдалась балансировка дерева
Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите длину кода символа 'b'. Считать, что очередной бит кода начинает формироваться с единицы
a | b | c | d | e |
0,4 | 0,15 | 0,22 | 0,05 | 0,18 |
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по неубыванию. Опорный элемент расположен на средней позиции
Дан массив элементов: 5, 0, 6, 4, 9, 7, 9, 2, 1, 0. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по неубыванию с шагом h=5
В алгоритме внешней сортировки используется два вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки
Во входном файле дан массив чисел: 5 6 9 3 2 3 4 5 4 7 8 6 0
Выполните первое распределение входных данных по двум вспомогательным файлам f1 и f2, используя сортировку по невозрастанию естественным слиянием
Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит оптимальное решение задачи о кратчайшем пути на графе методом проб и ошибок (попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую)." Укажите название алгоритма
Какое значение возвращает рекурсивная функция Rec(108,72), код которой приведен ниже? int Rec(int n,int k) { if (n%k==0) return k; return Rec(k,n%k);}
В каких строках будут выведены одинаковые результаты, если ранее выполнены следующие инициализации: char ch[]="abd",*pch;pch=ch;
Какой тип имеет переменная перечисляемого типа, который объявлен так: enum year {winter, spring, summer, autumn};?
Разработана рекурсивная функция F(n,k). Определите число листьев рекурсии при вызове F(7,5) int F(int n, int k){ if(n==1 || k==1) return 1; if(n<=k) return F (n,n-1)+1; return F(n,k-1)+ F(n-k,k);}
Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите код символа 'е'. Считать, что очередной бит кода начинает формироваться с единицы
a | b | c | d | e |
0,4 | 0,15 | 0,22 | 0,05 | 0,18 |
Дан программный код. Какое значение возвращает функция 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;}
Охарактеризуйте результат, возвращаемый операцией или функцией выделения памяти, если затребованный размер памяти слишком большой
Укажите название алгоритма сортировки, фрагмент кода которой представлен ниже. void Sort (int k,int x[max]) { int i,j,buf; for (i=k-1;i>0;i--) for (j=0;j<i;j++) if (x[j]>x[j+1]) { buf=x[j]; x[j]=x[j+1]; x[j+1]=buf; }}
В программе объявлен и проинициализирован массив int a[]={1,3,8,5,0,4,9,2,13}. Укажите значение a(a[7]+a[1]).
Хеш-таблица формируется методом середин квадратов. Определите хеш-коды для первых пяти двузначных простых чисел, сформированные функцией Hash int Hash(int Key) { return ((Key*Key)/10)%10 ;}
Охарактеризуйте ошибку при использовании действий с указателями во фрагменте кода: int *p;for (i=0;i<32000;i++)p= new int;
Что возвращает функция, фрагмент кода которой приведен ниже? long int Rec(int n) { if (n<2) return 1; return Rec(n-1)*n;}
Укажите вид обхода дерева, представленного на рисунке, если порядок просмотра вершин следующий: D E B F C A
Укажите результат выполнения функции сравнения строк в приведенном фрагменте кода (элементы строки – символы латинского алфавита): char ch[]="abcd",sh[]="abc";int i;i=strcmp(ch,sh);printf ("%d",i);
Определите коэффициент сжатия текста "abcaabbaac", к которому применено сжатие по методу Хаффмана. Размер входной последовательности на 1 байт больше ее длины
В программном коде выполнено объявление динамической структуры стека: struct Single_List { int Data; Single_List *Next; };struct Stack { Single_List *Top; }; . . . . . . . . . . . . . . .Stack *Top_Stack;
Какое значение содержит Top_Stack->Top?
Что будет являться результатом выполнения функции fp=fopen("t.txt","а+");, если файл t.txt существует?
Каким образом можно выполнить редактирование файла, если его целиком нельзя разместить в памяти программы?
Объявлена структура mail. Укажите верные для этой структуры присваивания struct mail { int id; union { struct { char name[30]; char dept[10]; char location[3]; } active; struct { char name[30]; char street[20]; char city_state[3]; char zip[5]; } retired; } info; } preson;
Укажите результат вывода на экран после выполнения фрагмента кода, если с клавиатуры введена строка: Я скоро завершу тестирование. char str[100];cin >> str;cout << str;
Какое действие над списком выполняет следующая функция: bool List(Single_List* Head, int DataItem){ Single_List *ptr; ptr = Head; while (ptr != NULL){ if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } return false;}
Размер хеш-таблицы HashTableSize =7. Определите хеш-коды для первых пяти простых чисел, сформированные функцией Hash int Hash(int Key, int HashTableSize) { return Key % HashTableSize;}
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
Каким образом компилятором происходит контроль конца списка параметров во фрагменте кода: float arifm(int k, ...) { int *p=&k;//настроили указатель на параметр k float s=*p; //значение первого параметра присвоили s int i; for(i=1;(*p)!=0;i++) //пока нет конца списка s+=*(++p); return s/(i-1);}
При объявлении struct { unsigned a0 : 3; unsigned a1 : 1; unsigned a2 : 3; } byte;
битовые поля располагаются в памяти:
Определите размер структуры, которая объявлена следующим образом: struct Book { int number; union { char titl[30]; char x; } info; };
Укажите, на какую позицию произойдет второе смещение начала подстроки при поиске в тексте по алгоритму Кнута, Морриса и Пратта. Строка: АВСКВАВСМКВ, подстрока: ВСМ. Нумерация в строке начинается с нуля
Укажите, какое значение возвращает функция h(a,b,c), если объявлены int a=3,b=6;float c=4.5; и функция перегружена следующим образом: int h(int a, float b, int c){ return int(a+b+c)/3;}float h(float a, int b, float c){ return a+b+c;}
Как получить доступ к значению переменой x, если выполнены объявления и инициализации: int *p, x, **q;x = 10;p = &x;q = &p;
Какие действия со строками происходят в ходе выполнения фрагмента кода: char * str (char *s1, char *s2) { char *p1, *p2; p1 = s1; p2 = s2; while ( *p1) p1++; while ((*p1++ = *p2++) != 0); return s1;}
Укажите корректное усечение начала строки s на n символов и вывод результата. Считать, что такое действие со строкой s возможно.
Укажите обращение, аналогичное обращению *(*(mas+i)+j) к элементу двумерного массива размерности MN.
Укажите, что возвращает функция, фрагмент кода которой представлен ниже: int d(int str,int slb, int m[max_x][max_y]){ int i,j,mm=m[0][0]; for(i=0;i<str;i++) for(j=0;j<slb;j++) if((i==j)&&(m[i][j]>mm)) mm=m[i][j]; return mm;}
Объявлена структура mail. Укажите верные для этой структуры присваивания struct mail { int id; union { struct { char name[30]; char dept[10]; char location[3]; } active; struct { char name[30]; char street[20]; char city_state[3]; char zip[5]; } retired; } info; } preson;
Объявлено объединение с битовыми полями и выполнено присваивание 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;
Что будет являться результатом выполнения функции fp=fopen("t.txt","w+");, если файл t.txt не существует?
Какое значение возвращает функция fscanf(fp, "%s %s", buf1, buf2);
если указатель установлен на начало файла fp, который имеет вид: ЯзыкПрограммированияС++
Укажите верное условие вместо многоточия, чтобы выполнялась проверка на корректность открытия файла ofs: if (...) cout << "Файл не открыт\n";
Что используется в качестве рабочей области при выполнении операций исключения, вставки и замены в файлах?
Какие действия выполняет приведенный фрагмент кода? int *mas, n=10, i; mas = new int [n]; mas[0]= a[1]=1;for (i=2; i<n; i++) mas[i]= mas[i-1]+ mas[i-2];
В программном коде выполнено объявление однонаправленного списка: struct Single_List { int Data; Single_List *Next; };Single_List *Head;
Укажите верно объявленный прототип функции поиска элемента в списке
Укажите представление дерева во входном потоке, если каждой вводимой пустой связи соответствует символ звездочка '*':
Укажите вид обхода дерева, представленного на рисунке, если порядок просмотра вершин следующий: D B E A C F
Укажите вид функции временной трудоемкости для следующей функции в зависимости от параметра 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); }
Дан программный код. Какое значение возвращает функция 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 ;}
Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения первого прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции
Дан массив элементов: 4, 7, 9, 0, 3, 2, 6, 8, 7. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по неубыванию с шагом h=4
Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании факта о том, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей." Укажите название алгоритма
Укажите, какие действия с массивом выполняет функция, фрагмент кода которой представлен ниже: void z (int k,int x[max]){ int i; for (i=0;i<k;i++) if (x[i]<0) x[i]=-x[i];}
Укажите верное условие вместо многоточия, чтобы выполнялась проверка на корректность открытия файла int.txt: if(...) perror("int.txt");
Укажите результат выполнения функции сравнения строк в приведенном фрагменте кода (элементы строки – символы латинского алфавита): char ch[]="abd",sh[]="abc";int i;i=strcmp(ch,sh);printf ("%d",i);
Укажите, что возвращает функция, фрагмент кода которой представлен ниже: 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;}
Укажите, какое значение возвращает функция 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;}
Каким образом происходит контроль пользовательских дескрипторов при распределенном доступе к файлам?
Укажите корректные способы конкатенации строк s1 и s2 в строку s3. Считать, что размер s3 позволяет выполнить это действие.
После распределения по двум файлам были получены данные (серии разделены апострофом) f1: 3 7 2 8 5 9 1 3 f2: 6 9 3 5 7 7
Выполните слияние этих результатов в один файл согласно алгоритму простой сортировки по неубыванию
Функция Аккермана задана формулой:
Найдите общее число вершин рекурсивного дерева при вызове А(2, 1)

При объявлении union { unsigned a0 : 3; unsigned a1 : 1; unsigned a2 : 2; } byte;
битовые поля располагаются в памяти:
Дан массив элементов: 4, 7, 3, 0, 3, 2, 6, 8, 7, 2, 6, 4. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по невозрастанию с шагом h=6
Укажите в байтах размер памяти, занимаемой массивом, который объявлен так: int m[][5][3]={{{1,2,3},{1}},{{4},{7,8}}};
Дана частотность появления символов в тексте. Выполните кодирование символов методом Хаффмана. Укажите среднюю длину кодового слова, которая равна сумме произведений вероятности на длину кода каждого символа соответственно. Считать, что очередной бит кода начинает формироваться с единицы
a | b | c | d | e |
0,4 | 0,15 | 0,22 | 0,05 | 0,18 |