игра брюс 2048
Главная / Программирование / Структуры и алгоритмы компьютерной обработки данных / Тест 36

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

Упражнение 1:
Номер 1
Укажите вид функции временной трудоемкости для следующей функции в зависимости от размера массива
		
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");
    }
}
		
		

Ответ:

 (1) O(n) 

 (2) O(n2) 

 (3) O(log n) 

 (4) O(n log n) 


Номер 2
Укажите вид функции временной трудоемкости для следующей функции в зависимости от параметра 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); 
}
		
		

Ответ:

 (1) O(n) 

 (2) O(n2) 

 (3) O(log n) 

 (4) O(n log n) 


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

Ответ:

 (1) O(n) 

 (2) O(n2) 

 (3) O(log n) 

 (4) O(n log n) 


Упражнение 2:
Номер 1
Разработана рекурсивная функция 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);
}
		
		

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
Разработана рекурсивная функция 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);
}
		
		

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
Разработана рекурсивная функция 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);
}
		
		

Ответ:

 (1)

 (2) 10 

 (3) 12 

 (4) 16 


Упражнение 3:
Номер 1
Значение какого выражения возвращает функция 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);
}
		
		

Ответ:

 (1) a0xn+a1xn-1+...an-1x+an 

 (2) anxn+an-1xn-1+...a1x+a0 

 (3) (a0+a1+...an-1+an)x 

 (4) an+an-1x+...a1x+a0x 


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

Ответ:

 (1) 1+2+3+...+n 

 (2) n! 

 (3) 1!+2!+3!+…+n! 

 (4) s+2s+3s+...+ks 


Номер 3
Значение какого выражения возвращает функция 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+1+2+3+...+n 

 (2) 1+1+2+2+3+3+...+n+n 

 (3) сумму n первых чисел последовательности Фибоначчи 

 (4) n-ый член последовательности Фибоначчи 


Упражнение 4:
Номер 1
Функция Аккермана задана формулой:
		
A(m,n)=
\begin{cases}
n+1,\text{ при }m=0 \\
A(m-1,1),\text{ при }m>0,n=0; \\
A(m-1,A(m,n-1)),\text{ при }m>0,n>0.
\end{cases}
		
		Найдите А(3, 2)
		

Ответ:

 (1)

 (2)

 (3) 29 

 (4) 38 


Номер 2
Функция Аккермана задана формулой:
		
A(m,n)=
\begin{cases}
n+1,\text{ при }m=0 \\
A(m-1,1),\text{ при }m>0,n=0; \\
A(m-1,A(m,n-1)),\text{ при }m>0,n>0.
\end{cases}
		
		Найдите общее число вершин рекурсивного дерева при вызове А(2, 1)
		

Ответ:

 (1)

 (2)

 (3) 13 

 (4) 14 


Номер 3
Функция Аккермана задана формулой:
		
A(m,n)=
\begin{cases}
n+1,\text{ при }m=0 \\
A(m-1,1),\text{ при }m>0,n=0; \\
A(m-1,A(m,n-1)),\text{ при }m>0,n>0.
\end{cases}
		
		Найдите объем рекурсии при вызове А(2, 2)
		

Ответ:

 (1)

 (2) 18 

 (3) 26 

 (4) 27 


Упражнение 5:
Номер 1
Укажите верные высказывания

Ответ:

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

 (2) одни и те же наборы параметров однозначно соответствуют одной вершине дерева рекурсии 

 (3) у дерева рекурсии может быть пустое множество листьев 

 (4) объем рекурсии равен количеству вершин полного рекурсивного дерева без единицы 


Номер 2
Укажите верные высказывания

Ответ:

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

 (2) все рекурсивные слои сохраняются в памяти до полного завершения программы 

 (3) операции открытия и закрытия рекурсивного слоя требуют дополнительных временных затрат 

 (4) одноименные переменные различных рекурсивных обращений не накладываются друг на друга 


Номер 3
Укажите верные высказывания

Ответ:

 (1) уменьшить трудоемкость рекурсивного алгоритма невозможно 

 (2) глубина рекурсивных вызовов ограничена максимальным размером стековой области 

 (3) база рекурсии содержит тривиальный случай для задачи 

 (4) трудоемкость рекурсивного алгоритма не зависит от количества параметров функции 


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

Ответ:

 (1) расстановок не существует 

 (2)

 (3)

 (4)


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

Ответ:

 (1) расстановок не существует 

 (2)

 (3)

 (4)


Номер 3
Сколько существует расстановок 5 ферзей на доске размера 55, при которой один из ферзей занимает центр доски?

Ответ:

 (1) расстановок не существует 

 (2)

 (3)

 (4)


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

Ответ:

 (1) метод пошаговой детализации 

 (2) перебор с возвратом 

 (3) метод решета 

 (4) метод ветвей и границ 


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

Ответ:

 (1) один из вариантов, соответствующий условию задачи 

 (2) часть одного из вариантов, соответствующего условию задачи 

 (3) один из вариантов решения, полностью отличный от остальных 

 (4) краевые решения задачи 


Номер 3
Какой способ реализации рекурсивных вычислений относится к возвратной рекурсии?

Ответ:

 (1) соединение рекурсии с динамической базой 

 (2) организация косвенной рекурсии 

 (3) соединение метода перебора с возвратом и рекурсии 

 (4) организация отслеживания рекурсивных возвращений 


Упражнение 8:
Номер 1
Укажите опорную схему рекурсивных вычислений, которая способствует уменьшению трудоемкости алгоритма за счет исключения несущественных случаев

Ответ:

 (1) увидеть 

 (2) характеристическое свойство 

 (3) перенести часть условий в проверку 

 (4) найти родственника 


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

Ответ:

 (1) обобщить 

 (2) увидеть 

 (3) найти родственника 

 (4) переформулировать 


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

Ответ:

 (1) увидеть 

 (2) характеристическое свойство 

 (3) перенести часть условий в проверку 

 (4) найти родственника 




Главная / Программирование / Структуры и алгоритмы компьютерной обработки данных / Тест 36