Тест 2 Отбележете верните и неверни дефиниции и твърдения за дървета. (да) Ако върхът u е родител на върха v, казваме, че v е дете на u. (no) Двоично дърво е наредено дърво в което всеки възел има най-малко две деца. Дадено е дърво АТД с n елементи. Нека v и w са позиции от дървото. Отбележете верните и неверните съответствия между функцията на този АТД и изискванията за асомптотичната й оценка. (да) isRoot(v) (no) (no) O(1) (no) children(v) - (no) O(1) Дадено е наредено дърво АТД T = A(B(H,E(I,J),F),C(G),D). Определете верните и неверните наредени двойки: извикване на функция, върната стойност от тази функция. p(X) означава позицията на елемента X. (да) root(), p(A) (no) root(), p(D) Дадено е наредено дърво АТД T = A(B(H,E(I,J),F),C(G),D). Определете дали дадената редица е част от preorder traversal за това дърво. (да) ABH (no) CGDA Дадено е наредено дърво АТД T = A(B(H,E(I,J),F),C(G),D). Определете дали дадената редица е част от postorder traversal за това дърво. (да) FBGC (no) CGDA Дадено е двоично дърво АТД T = a(b(d(h,i),e),c(f,g(j(l,m),k)). Определете дали дадената редица е част от inorder traversal за това двоично дърво. (да) jmgk (no) hdie Дадено е двоично дърво АТД T = a(b(d(h,i),e),c(f,g(j(l,m),k)). Определете дали дадената редица е част от Euler tour traversal за това двоично дърво. (да) gkgca (no) abcde Да се построи двоично дърво за следния аритметичен израз: (9 * (5 + a) + b) / 2. Определете дали дадената редица е част от preorder traversal за това двоично дърво. (да) ab2 (no) 5+a Да се построи двоично дърво за следния аритметичен израз: (9 * (5 + a) + b) / 2. Определете дали дадената редица е част от postorder traversal за това двоично дърво. (да) b+2 (no) ab2 Отбележете верните и грешните дефиниции и твърдения за приоритетна опашка и хип. (да) Хип T съдържащ n ключа има височина h = [log(n + 1)]. (no) За всеки вътрешен възел на хип v, който не е корен key(parent(v)) >= key(v). Дадена е приоритетна опашка АТД P = {(5,A),(7,D),(9,C)}. За функция от този АТД определете върнатата стойност и ефекта й за P. (no) minElement() - 5 - {(5,A),(7,D),(9,C)} (да) minKey() - 5 - {(5,A),(7,D),(9,C)} Дадена е приоритетна опашка АТД с n елементи, реализирана с ненаредена редица. Отбележете верните и неверни съответствия между функция от този АТД и асимпотичната оценка за времето за изпълнение на функцията. (да) minKey() - \Theta(n) (no) minKey() - O(1) Дадена е приоритетна опашка АТД с n елементи, реализирана с наредена редица. Отбележете верните и неверни съответствия между функция от този АТД и асимпотичната оценка за времето за изпълнение на функцията. (да) minElement() - O(1) (no) minElement() - O(n) Дадена е приоритетна опашка АТД с n елементи, реализирана с хип. Отбележете верните и неверни съответствия между функция от този АТД и асимпотичната оценка за времето за изпълнение на функцията. (да) minElement() - O(1) (no) minElement() - O(n) Даден е вектор, реализация на хип. Посочете верните и неверни представяния на хипа след изпълнение на операцията InsertItem(1,1). (да) 2,5,6,9,7 -> 1,5,2,9,7,6 (no) 2,5,6,9,7 -> 1,2,5,6,9,7 Даден е вектор, реализация на хип. Посочете верните и неверни представяния на хипа след изпълнение на операцията RemoveMin(). (да) 2,5,6,9,7 -> 5,7,6,9 (no) 2,5,6,9,7 -> 5,6,9,7 Посочете верни и неверни твърдения за следната дефиниция на член-функция Element& element(const Position& p) { return p.element().element(); } в класа HeapPriorityQueue (виж html-7.8 (HPQ1)). (да) Върнатата стойност е псевдоним на данна на обект от клас Item. (no) p е член-данна в класа Position.