CITB308 - Тест 2

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

Дадено е дърво АТД с n елементи. Нека v и w са позиции от дървото. Отбележете верните (и неверни) съответствия между функцията на този АТД и изискванията за асомптотичната й оценка.
(да) isRoot(w) - 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 обхождане на дървото.
(да) ABH
(не) CGDA

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

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

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

Да се построи двоично дърво за следния аритметичен израз: (7 * (1 + a) + b) / 3. Определете дали дадената редица е част от preorder (клд) обхождане на дървото.
(да) ab3
(не) 7*1

Да се построи двоично дърво за следния аритметичен израз: (3 * (4 + a) + b) / 2. Определете дали дадената редица е част от postorder (лдк) обхождане на дървото.
(да) b+2
(не) ab2

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

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

Нека 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 - P{(5,A),(7,D),(9,C)}
(да) minKey() - 5 - P{(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. Отбележете грешни и верни твърдения.
(да) Обектът S е реализация на редица АТД.
(не) comp е име на компаратор клас.

Разгледайте Code Fragment: HPQ2. Отбележете грешни и верни твърдения.
(да) Обектът T е реализация на хип.
(не) comp е име на компаратор клас.