Тест 1
Посочете верните и неверни дефиниции и трърдения за линейни
структури от данни и абстрактни типове данни (АТД).
(yes) Стек АТД е контейнер на обекти, които се добавят и отстраняват
според правилото: последния добавен, пръв изваден (LIFO).
(no) Едносвързан списък е АТД, състоящ се от съвкупност от възли.
Дадена е опашка АТД с n елемента, рализирана с масив.
Отбележете вярно/невярно ли е даденото съответствие функция --
асимптотична оценка.
(yes) size() -- O(1)
(no) enqueue(o) -- O(n2)
Дадена е опашка АТД с n елемента, рализирана с едносвързан
списък. Отбележете вярно/невярно е даденото съответствие функция --
асимптотична оценка.
(no) size() -- O(n)
(yes) isEmpty() -- O(1)
Даден е дек АТД с n елемента, рализиран с двойно свързан
списък. Отбележете вярно/невярно е даденото съответствие функция --
асимптотична оценка.
(yes) size() -- O(1)
(no) last() -- O(n)
Даден е вектор АТД с n елемента, рализиран с масив.
Отбележете вярно/невярно е даденото съответствие функция --
асимптотична оценка.
(yes) elemAtRank(r) -- O(1)
(no) replaceAtRank(r, e) -- O(n)
Даден е списък АТД с n елемента, рализиран с масив, където
позициите за индекси на масива.Отбележете вярно/невярно е даденото
съответствие функция -- асимптотична оценка.
(yes) insertAfter(p,e) -- O(n)
(no) remove(p) -- O(1)
Даден е списък АТД с n елемента, рализирана с двойно свързан списък.
Отбележете вярно/невярно е даденото съответствие функция --
асимптотична оценка.
(no) insertLast(e) -- O(log n)
(yes) insertBefore(p,e) -- O(1)
Даден е стек АТД S = (9,7,2) с елемент на върха 2. За дадена
операция вярно ли е определена стойността на операцията и ефекта й
Р·Р° S?
(yes) push(5) -- NONE -- S=(9,7,2,5)
(no) push(3) -- 3 -- S=(9,7,3)
Дадена е опашка АТД Q = (8,7,2) с първи елемент 8. За дадена
операция вярно ли е определена стойността на операцията и ефекта й
Р·Р° Q?
(yes) enqueue(5) -- NONE -- Q=(8,7,2,5)
(no) enqueue(7) -- 7 -- Q=(8,7,2,7)
Даден е дек АТД D = (8,1,2) с първи елемент 8. За дадена
операция вярно ли е определена стойността на операцията и ефекта
\`{Рё} Р·Р° D?
(yes) insertFirst(5) -- NONE -- D =(5,8,1,2)
(no) insertFirst(6) -- NONE -- D =(8,1,2,6)
Даден е вектор АТД V = (4,7,2). За дадената векторна операция вярно
ли е определена стойността на операцията и ефекта й за V?
(yes) insert 1 at rank 0 -- NONE -- (1,4,7,2)
(no) insert 2 at rank 1 -- NONE -- (2,4,7,2)
Даден е следния списък АТД L = p_1(8) -> p_2(3).
Рзползваме позициите p_1, p_2, ...,като РІ СЃРєРѕР±Рё Рµ означен
обектът на тази позиция. За дадената операция вярно ли е определена
стойността на операцията и ефекта й за L?
(yes) insertFirst(2), p_4(2), p_4(2) -> p_1(8) ->
p_2(3)
(no) insertFirst(4), p_3(4), p_3(4) -> p_2(3)
Посочете верните и грешни твърдения за асимптотичната нотация.
(yes) f(n) е O(g(n)), ако съществуват положителни константи c и N
такива, че f(n)<cg(n) за n>N.
(no) g(n) е O(f(n)), ако съществуват положителни константи c и
N такива, че f(n)<cg(n) за n>N.
Вярно ли с следното твърдение?
(yes) Ако f(n) е полиним от степен d>0, то f(n) е O(n^d).
(no) Ако f(n) е полиним от степен d<0, то f(n) е O(dn).
Посочете верните и неверни твърдения относно асимпотичната нотация
за конкретни функции.
(yes) 2n+10 Рµ O(n)
(no) n + n2 Рµ O(n)
Нека d(n), e(n), f(n) и g(n) са функции, изобразяващи
неотрицателните цели числа в неотрицателни числа. Бярно ли е
следното твърдение?
(yes) If d(n) е O(f(n)), то a+d(n) е O(f(n)) за всяка константа a.
(no) If d(n) е O(f(n)), то n2d(n) е O(n f2(n)).
We have a function template:Дадена е следната шаблон-функция:
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
функцията.
(yes) int *a = new int[2]; cout << maxA(a);
(no) 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 ще се отпечати
на екрана. Вярно ли е това твърдение?
(yes) fun3();
(no) fun1();