CITB303 - Тест 4

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

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

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

Отбележете верните и неверни дефиниции и твърдения за дървета
(да) Ако върхът u е родител на върха v, казваме, че v е дете на u.
(не) Двоично дърво е наредено дърво, в което всеки възел има най-малко две деца.

Дадено е наредено дърво АТД T = A(B(H,E(I,J),F),C(G),D). Определете дали дадената редица е част от preorder traversal за това дърво.
 (да) ABH
 (не) CGDA

Дадено е двоично дърво. Да се провери дали редицата (след ;) е част от 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

Прост алгоритъм за разрешаване на колизии в хеш таблици 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

Даден е вектор, реализация на хип. Посочете верните (и грешни) представяния на хипа след изпълнение на дадената операция - I означава insrtItem(1), R означава removeMin().
(да) I  2,5,6,9,7 -> 1,5,2,9,7,6
(не) R 2,5,6,9,7 -> 5,6,9,7

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

Дадено е 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))

Класът 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.isNull(); получаваме синтактична грешка.

Разгледайте частта от реализацията на AVL дървета, дадена в Code Fragment: AVLTree1 и определете следните твърдения като "верни" или "грешни".
(да) Всеки обект от клас AVLTree<K,E> е обект от клас BinarySearchTree<K,E,Item<K,E> >.
(не) Функцията height(p) връща височината на двоичното дърво.
Дадено е (2,4) дърво: T = {10,15,24}({2,8},{12},{18}, {27,32,35}). Външните възли не са включени в представянето. Определете дали даденото  дърво е получено като резултат от  прилагане на дадената операция.
(да) removeElement(24) - T={10,15,27}({2,8},{12},{18},{32,35})
(не) removeElement(2) - T={10,15,24}({8,12},{18},{27,32,35})

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