Тест 3
Отбележете верни/грешни твърдения за асимптотична оценка за следните
функции:
(да) 2n + 3n2 e O(n2)
(не) n + n2 e O(n)
Дадени са следните дефиниции:
i = 4, j = 2, k = 1;
Определете дали коментарът е стойност на израза.
(да) i -= j // 2
(не) j *= -j // -2
Посочете верни/неверни дефиниции и твърдения за търсещи дървета.
(да) Търсене в AVL дърво с n члена отнема време O(log
n).
(не) Височината на AVL дърво, съдържащо n ключа е O(n).
Дадено е (2,4) дърво АТД: T = {12}({3,6,9},{15}). Външните възли не
са включени в представянето. Определете дали даденото след
съответната операция (2,4)-дърво е получено като резултат от
прилагане на операцията.
(да) insertItem(1) -
T={6,12}({1,3}, {9},{15})
(не) insertItem(1) -
T={3,12}({1,6,9},{15})
Дадено е червено-черно дърво АТД, като черните
възли са bold, а червените - italic.
Външните възли не са включени в представянето. Определете дали
даденото след операцията червено-черно дърво е
получено като резултат от прилагане на операцията.
(да) 6(8) - insertItem(7)
- 7(6,8) (не) 5(7) - insertItem(6) - 5(6,7)
Прост алгоритъм за разрешаване на колизии в хеш таблици 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
Дадено е двоично дърво АТД:
T =
a(b(c(d,e),f),g(h,i(j(k,l),m)).
Дали дадената редица е част от редицата от възли, получена чрез
Ойлерово обхождане на двоичното дърво?
(да) abcd
(не) bcde
Да се построи двоично дърво, представящо следния аритметичен израз:
(x + 2*(y - 2)) / 2.
Дали дадената редица е част от редицата от възли, получена чрез
preorder обхождане на двоичното дърво?
(да) / + x
(не) 2 - 2
Даден е стек АТД:
S = (5,3,4,9).
Върхът на стека е 5. Посочете
вярно/невярно съответствие "функция -- върната стойност -- стека S"
след изпълнението на функцията.
(да) push(1) -- NONE -- S=(1,5,3,4,9)
(не) push(10) -- NONE -- S=(5,3,4,9,10)
Дадена е опашка АТД:
Q = (8,7,2).
Начало на опашката е елементът 8. Посочете вярно/невярно
съответствие "функция -- върната стойност -- опашката Q" след
изпълнението на функцията.
(да) enqueue(5) -- NONE -- Q=(8,7,2,5)
(не) enqueue(7) -- 7 -- Q=(8,7,2,7)
Даден е дек АТД:
D = (8,1,3).
Начало на дека е елементът 8. Посочете вярно/невярно съответствие
"функция -- върната стойност -- декът D" след изпълнението на
функцията.
(да) insertFirst(5) -- NONE -- D =(5,8,1,3)
(не) insertFirst(6) -- NONE -- D =(8,6,1,3)
Дадено е 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))
Дадено е двоично дърво. Да се провери дали редицата след ; е част от
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
Класът Position e включен в
дефиницията на класа BinarySearchTree
(Code Fragment 9.2). Отбележете верни/неверни твърдения за
член-функцията
Element& element()
{
return btPos.element().element();
}
от class Position.
(да) Върнатата стойност е псевдоним на член-данна на класа Item.
(не) Функцията е рекурсивна.
Посочете верните и неверни дефиниции и твърдения за линейни
структури от данни.
(да) Премахването на елемент от всеки край на двойно свързан списък
се извършва за време O(1).
(не) Опашка е контейнер от обекти, които се добавят и изваждат в
съответствие с принципа LIFO -- "последен влязъл, пръв излязъл".
Отбележете верни/грешни дефиниции за асимптотична нотация.
(да) f(n) e O(g(n)), ако има
положителни константи c и N, такива, че f(n) < c g(n) за n > N.
(не) g(n) e O(f(n)), ако има
положителни константи c и N, такива, че f(n) < c g(n)
за n > N.
Даден е следния код:
void fun1() { throw runtime_error("ERR" ); }
void fun2() throw(runtime_error) { ... }
void fun3() throw(runtime_error) { fun2(); }
int main()
{
try
{ fun3(); }
catch (runtime_error e)
{ cout << e.what(); }
return 0;
}
Като заместим ... с дадения
оператор, дали ERR ще се
отпечата на екрана?
(да) fun1();
(не) fun2();
Посочете верните/неверните дефиниции и твърдения за дървета.
(да) Ако възел u е родител на възел v, казваме, че v е дете на
u.
(не) Всеки възел в двоично дърво има родител и нула, едно или
две деца.
Класът 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(); получаваме синтактична
грешка.