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

Дадено е двоично дърво. Да се провери дали редицата (след ;) е част от inorder обхождане на дървото.
(да) c(b(a,d),e);bdc
(не) a(e,b(f,c(g,d)));bgd

Да се построи двоично дърво, представящо дадения аритметичен израз и да се провери дали редицата x2y e част от postorder обхождане на полученото дърво.
(да) (x+2*(y-2))/2
(не) (x-2)*y

Нека n е броят на върховете, e - броят на външните върхове, i - броят на вътрашните върхове на правилно двоично върво, и h е неговата височина. Отбележете правилните и грешни равенства и неравенства.
(да) i = e - 1
(не) 2e = n

Отбележете верните и грешните дефиниции и твърдения за приоритетна опашка и хип.
(да) Хип 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.

Разгледайте Code Fragment: SSPQ2. Отбележете грешни и верни твърдения.
(да) Обектът \verb|S| е реализация на редица АТД.
(не) comp е име на компаратор клас.

---