CITB303 - Тест 1

Посочете верните и неверни дефиниции и твърдения за линейни структури от данни и абстрактни типове данни (АТД).
(да) Стек АТД е контейнер на обекти, които се добавят към и изваждат от контейнера според правилото: последния добавен, пръв изваден (LIFO).
(не) Едносвързан списък е АТД, състоящ се от съвкупност от възли.

Дадена е опашка АТД с n елемента, рализирана с масив.
Отбележете вярно/невярно ли е даденото съответствие функция -- асимптотична оценка.
(да) size() -- O(1)
(не) enqueue(o) -- O(n²)

Дадена е опашка АТД с n елемента, рализирана с едносвързан списък.
Отбележете вярно/невярно за даденото съответствие функция -- асимптотична оценка.
(не) size() -- O(n)
(да) isEmpty() -- O(1)

Даден е дек АТД с n елемента, рализиран с двойно свързан списък.
Отбележете вярно/невярно за даденото съответствие функция -- асимптотична оценка.
(да) size() -- O(1)
(не) last() -- O(n)

Даден е вектор АТД с n елемента, рализиран с масив.
Отбележете вярно/невярно за даденото съответствие функция -- асимптотична оценка.
(да) elemAtRank(r) -- O(1)
(не) replaceAtRank(r, e) -- O(n)

Даден е списък АТД с n елемента, рализиран с масив, където позициите за индекси на масива.
Отбележете вярно/невярно ли е даденото съответствие функция -- асимптотична оценка.
(да) insertAfter(p,e) -- O(n)
(не) remove(p) -- O(1)

Даден е списък АТД с n елемента, рализирана с двойно свързан списък.
Отбележете вярно/невярно ли е даденото съответствие функция -- асимптотична оценка.
(не) insertLast(e) -- O(log n)
(да) insertBefore(p,e) -- O(1)

Даден е стек АТД  S = (9,7,2) с елемент на върха 2.
За дадената операция вярно ли е определена стойността на операцията и ефекта й за S?
(да) push(5) -- NONE -- S = (9,7,2,5)
(не) push(3) -- 3 -- S = (9,7,3)

Дадена е опашка АТД  Q = (8,7,2) с първи елемент 8.
За дадената операция вярно ли е определена стойността на операцията и ефекта й за Q?
(да) enqueue(5) -- NONE -- Q = (8,7,2,5)
(не) enqueue(7) -- 7 -- Q = (8,7,2,7)

Даден е дек АТД  D = (8,1,2) с първи елемент 8.
За дадената операция вярно ли е определена стойността на операцията и ефекта й за D?
(да) insertFirst(5) -- NONE -- D = (5,8,1,2)
(не) insertFirst(6) -- NONE -- D = (8,1,2,6)

Даден е вектор АТД V = (4,7,2).
За дадената векторна операция вярно ли е определена стойността на операцията и ефекта й за V?
(да) insert 1 at rank 0 -- NONE -- (1,4,7,2)
(не) insert 2 at rank 1 -- NONE -- (2,4,7,2)

Даден е следния списък АТД L = p_1(8) -> p_2(3).
Използваме позициите  p_1, p_2, ..., като в скоби е означен обектът на тази позиция.
За дадената операция вярно ли е определена стойността на операцията и ефекта й за L?
(да) insertFirst(2), p_4(2), p_4(2) -> p_1(8) -> p_2(3)
(не) insertFirst(4), p_3(4), p_3(4) -> p_2(3)

Посочете верните и грешни твърдения за асимптотичната нотация.
(да) f(n) е O(g(n)), ако съществуват положителни константи c и N такива, че f(n) < cg(n) за n > N.
(не) g(n) е O(f(n)),  ако съществуват положителни константи c и N  такива, че f(n) < cg(n) за n > N.

Вярно ли с следното твърдение?
(да) Ако f(n) е полиним от степен d > 0, то f(n) е O(n^d).
(не) Ако f(n) е полиним от степен d < 0, то f(n) е O(dn).

Посочете верните и неверни твърдения относно асимпотичната нотация за конкретни функции.
(да) 2n + 10 е O(n)
(не) n + n² е O(n)

Нека d(n), e(n), f(n) и g(n) са функции, изобразяващи неотрицателните цели числа в неотрицателни числа. Бярно ли е следното твърдение?
(да) Ако d(n) е O(f(n)), то a + d(n) е O(f(n)) за всяка константа a.
(не) Ако d(n) е O(f(n)), то n²d(n) е O(n f²(n)).

Дадена е следната шаблон-функция:
template<typename T>
T maxA(T* arr, int s = 2)
{ T maxVal = arr[0];
  for (int i = 1; i < s; i++)
     if (arr[i] > maxVal) maxVal = arr[i];
  return maxVal;  }
Отбележете верни/неверни твърдения или оператори от блока на main функцията.
(да) int *a = new int[2]; cout << maxA(a);
(не) cout << maxA(10);

Даден е следния фрагмент от програма:
void fun3() { throw runtime_error("RTE" ); }
void fun2() throw(runtime_error) { ... }
void fun1() throw(runtime_error) { fun2(); }
int main()
{ try { fun1(); }
  catch (runtime_error e) { cout<<e.what(); }
  return 0; }
Замесвайки ... с дадените оператори, съобщението RTE ще се отпечати на екрана. Вярно ли е това твърдение?
(да) fun3();
(не) fun1();