Тест 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)