CITB308 - Тест 3

Отбележете верни и грешни твърдения за речник АТД.
(да) Речник с пълна наредба на ключовете наричаме нареден речник.
(не) Реализация на речник АТД с наредена редица се нарича log файл.
Даден е нареден речник АТД с n елемента. Отбележете вярно/невярно ли е даденото съответствие:
реализация - функция - асимптотична оценка.
(да) Log File - keys - O(n)
(не) Lookup Table - findAll - O(1)
Даден е нареден речник АТД с n елемента, реализиран с хеш таблица. Отбележете вярно/невярно ли е даденото съответствие: функция - асимптотична оценка.
(да) keys - O(n)
(не) elements - O(1)
Прост алгоритъм за разрешаване на колизии в хеш таблици 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

Двойно хеширане е метод за решаване на колизии в хеш таблици.  Дадена е следната редица от ключове: 18, 11, 4, 10, 8, 15, клетъчен масив с дължина N,
хеш функция h(x) = x mod N и втора хеш функция d(k) = M - k mod M.
При зададени стойности на N и M определете дали правилно са разположени дадените ключове в клетъчния масив.
(да) N = 7, M = 5  - 8 11 0 10 18 4 15
(не) N = 14, M = 5 - 15 0 0 0 18 4 0 0 8 0 10 11 0 0

Класът 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 дърво:
  44(17(-,32),78(50(48,62),88)).
Външните възли не са включени в представянето. Определете дали даденото след операцията AVL дърво е получено като резултат от прилагане на операцията.
(да) insertItem(54) 44(17(-,32),62(50(48,54),78(-,88)))
(не) removeElement(32) 44(17,78(50(48,62),88))

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

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

Разгледайте частта от реализацията на AVL дървета, дадена в Code Fragment: AVLTree1 и определете следните твърдения като "верни" или "грешни".
(да) Всеки обект от клас AVLTree<K,E> е обект от клас BinarySearchTree<K,E,Item<K,E> >.
(не) Функцията height(p) връща височината на двоичното дърво.

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

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

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

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

Разгледайте кода от Code Fragment: RBTree3 и определете дали следните твърдения са верни.
(да) Функцията parent е дефинирана в класа, реализиращ двоично дърво АТД.
(не) Функцията setBlack е дефинирана в базовия клас.