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);

Разгледайте Code Fragment: NodeSequence2. Верни ли са следните твърдения?
(да) Функцията rankOf връща ранга на елемента, който се намира на позиция p.
(не) trailer е данна, дефинирана в класа NodeSequence<Object>.

---