Тест 3

Отбележете верни/грешни твърдения за асимптотична оценка за следните функции:
(да) 2n + 3n2 e O(n2)
(не) n + n2 e O(n)

Дадени са следните дефиниции:
 i = 4, j = 2, k = 1;
Определете дали коментарът е стойност на израза.
(да) i -= j // 2
(не) j *= -j // -2

Посочете верни/неверни дефиниции и твърдения за търсещи дървета.
(да) Търсене в AVL дърво с n члена отнема време O(log n).
(не) Височината на AVL дърво, съдържащо n ключа е O(n).

Дадено е (2,4) дърво АТД: T = {12}({3,6,9},{15}). Външните възли не са включени в представянето. Определете дали даденото след съответната операция (2,4)-дърво е получено като резултат от прилагане на операцията.
(да) insertItem(1) - T={6,12}({1,3}, {9},{15})
(не) insertItem(1) - T={3,12}({1,6,9},{15})

Дадено е червено-черно дърво АТД, като черните възли са bold, а червените - italic. Външните възли не са включени в представянето. Определете дали даденото след операцията червено-черно дърво е получено като резултат от прилагане на операцията.
(да) 6(8) - insertItem(7) - 7(6,8) (не) 5(7) - insertItem(6) - 5(6,7)

Прост алгоритъм за разрешаване на колизии в хеш таблици e линейно пробване. Даден е клетъчен масив
    A = { 35,14,D,21,E,12,E }
с капацитет N=7, където E означава empty и D означава available елемент на масива. Хеш функцията e h(k) = k mod 7. Посочете верни/неверни съответствия, като след -> е дадено предполагаемото място на добавения елемент в масива.
(да) insrtItem(7) -> A[2] = 7
(не) insrtItem(18) -> A[5] = 18

Дадено е двоично дърво АТД:
   T = a(b(c(d,e),f),g(h,i(j(k,l),m)).
Дали дадената редица е част от редицата от възли, получена чрез Ойлерово обхождане на двоичното дърво?
(да) abcd
(не) bcde

Да се построи двоично дърво, представящо следния аритметичен израз:
  (x + 2*(y - 2)) / 2.
Дали дадената редица е част от редицата от възли, получена чрез preorder обхождане на двоичното дърво?
(да) / + x
(не) 2 - 2

Даден е стек АТД:
   S = (5,3,4,9).
Върхът на стека е 5. Посочете вярно/невярно съответствие "функция -- върната стойност -- стека S" след изпълнението на функцията.
(да) push(1) -- NONE -- S=(1,5,3,4,9)
(не) push(10) -- NONE -- S=(5,3,4,9,10)

Дадена е опашка АТД:
   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,3).
Начало на дека е елементът 8. Посочете вярно/невярно съответствие "функция -- върната стойност -- декът D" след изпълнението на функцията.
(да) insertFirst(5) -- NONE -- D =(5,8,1,3)
(не) insertFirst(6) -- NONE -- D =(8,6,1,3)

Дадено е AVL дърво:
  44(17(-,32),78(50(48,62),88)).
Външните възли не са включени в представянето. Определете дали даденото след операцията AVL дърво е получено като резултат от прилагане на операцията.
(да) insertItem(54) 44(17(-,32),62(50(48,54),78(-,88)))
(не) removeItem(32) 44(17,78(50(48,62),88))

Дадено е двоично дърво. Да се провери дали редицата след ; е част от inorder обхождане на дървото. 
(да) c(b(a,d),e) ; bdc
(не) a(b,c(d(f,g),e)) ; cfe

Да се построи двоично дърво, представящо дадения аритметичен израз и да се провери дали редицата x2y e част от postorder обхождане на полученото дърво.
(да) (x+2*(y-2))/2
(не) (x-2)*y

Класът Position e включен в дефиницията на класа BinarySearchTree (Code Fragment 9.2). Отбележете верни/неверни твърдения за член-функцията
Element& element()
{
 
return btPos.element().element();
}
от class Position.

(да) Върнатата стойност е псевдоним на член-данна на класа Item.
(не) Функцията е рекурсивна.

Посочете верните и неверни дефиниции и твърдения за линейни структури от данни.
(да) Премахването на елемент от всеки край на двойно свързан списък се извършва за време O(1).
(не) Опашка е контейнер от обекти, които се добавят и изваждат в съответствие с принципа LIFO -- "последен влязъл, пръв излязъл".

Отбележете верни/грешни дефиниции за асимптотична нотация.
(да) f(n) e O(g(n)), ако има положителни константи c и N, такива, че f(n) < c g(n) за n > N.
(не) g(n) e O(f(n)), ако има положителни константи c и N, такива, че f(n)  <  c g(n) за n > N.

Даден е следния код:
void fun1() { throw runtime_error("ERR" ); }
void fun2() throw(runtime_error) { ... }
void fun3() throw(runtime_error) { fun2(); }
int main()
{
 
try
 
{ fun3(); }
 
catch (runtime_error e)
 
{ cout << e.what(); }
 
return 0;
}

Като заместим ... с дадения оператор, дали ERR ще се отпечата на екрана?
(да) fun1();
(не) fun2();

Посочете верните/неверните дефиниции и твърдения за дървета.
(да) Ако възел u е родител на възел v, казваме, че v е дете на u.
(не) Всеки възел в двоично дърво има родител и нула, едно или две деца.

Класът BinarySearchTree съдържа следната член-функция (Code Fragment 9.3):
void setItem(const BTPosition& p, const BSTItem& i) const
{
  /*add*/
  p.element().setKey(i.key());
  p.element().setElement(i.element());
}

Отбележете верни/неверни твърдения за тази функция.
(да) Функцията поставя Item от BST (речник) на позиция p в LinkedBinaryTree.
(не) Като заместим /*add*/ с p.eNull(); получаваме синтактична грешка.