Тест 2

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

Дадено е дърво АТД с n елементи. Нека v и w са позиции от дървото. Отбележете верните и неверните съответствия между функцията на този АТД и изискванията за асомптотичната й оценка.
 (да) isRoot(v) - O(1)
 (не) children(v) - O(1)

Дадено е наредено дърво АТД T = A(B(H,E(I,J),F),C(G),D). Определете верните и неверните наредени двойки: извикване на функция, върната стойност от тази функция. p(X) означава позицията на елемента X.
 (да) root(), p(A)
 (не) root(), p(D)

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

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

Дадено е двоично дърво АТД T = a(b(d(h,i),e),c(f,g(j(l,m),k)). Определете дали дадената редица е част от inorder traversal за това двоично дърво.
 (да) jmgk
 (не) hdie

Дадено е двоично дърво АТД T = a(b(d(h,i),e),c(f,g(j(l,m),k)). Определете дали дадената редица е част от Euler tour traversal за това двоично дърво.
 (да) gkgca
 (не) abcde

Да се построи двоично дърво за следния аритметичен израз: (9 * (5 + a) + b) / 2. Определете дали дадената редица е част от preorder traversal за това двоично дърво.
 (да) ab2
 (не) 5+a

Да се построи двоично дърво за следния аритметичен израз: (9 * (5 + a) + b) / 2. Определете дали дадената редица е част от postorder traversal за това двоично дърво.
 (да) b+2
 (не) ab2

Отбележете верните и грешните дефиниции и твърдения за приоритетна опашка и хип.
 (да) Хип T съдържащ n ключа има височина h = [log(n + 1)].
 (не) За всеки вътрешен възел на хип v, който не е корен key(parent(v)) >= key(v).

Дадена е приоритетна опашка АТД P = {(5,A),(7,D),(9,C)}. За функция от този АТД определете върнатата стойност и ефекта й за P.
 (не) minElement() - 5 - {(5,A),(7,D),(9,C)}
 (да) minKey() - 5 - {(5,A),(7,D),(9,C)}

Дадена е приоритетна опашка АТД с n елементи, реализирана с ненаредена редица. Отбележете верните и неверни съответствия между функция от този АТД и асимпотичната оценка за времето за изпълнение на функцията.
 (да) minKey() - \Theta(n)
 (не) minKey() - O(1)

Дадена е приоритетна опашка АТД с n елементи, реализирана с наредена редица. Отбележете верните и неверни съответствия между функция от този АТД и асимпотичната оценка за времето за изпълнение на функцията.
 (да) minElement() - O(1)
 (не) minElement() - O(n)

Дадена е приоритетна опашка АТД с n елементи, реализирана с хип. Отбележете верните и неверни съответствия между функция от този АТД и асимпотичната оценка за времето за изпълнение на функцията.
 (да) minElement() - O(1)
 (не) minElement() - O(n)

Даден е вектор, реализация на хип. Посочете верните (и грешни представяния на хипа след изпълнение на операцията InsertItem(1,1).

 (да) 2,5,6,9,7 -> 1,5,2,9,7,6
 (не) 2,5,6,9,7 -> 1,2,5,6,9,7

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

Посочете верни и неверни твърдения за следната дефиниция на член-функция
 Element& element(const Position& p)
 {
     return p.element().element();
 }
в класа HeapPriorityQueue (виж html-7.8 (HPQ1)).
 (да) Върнатата стойност е псевдоним на данна на обект от клас Item.
 (не) p е член-данна в класа Position.