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 е
дефинирана в базовия клас.