АСП2/К1 2020
Први колоквијум 2020. године одржан је 3. новембра 2020.
1. задатак
Поставка
(10п) Посматра се табела целобројних кључева дата на слици. Приказати изглед табеле у сваком кораку приликом претраге на скуп кључева {25, 40, 25, 40} методом транспозиције као и методом пребацивања на почетак и у оба случаја израчунати просечан број поређења приликом претраживања.
12 | 7 | 3 | 27 | 25 | 78 | 98 | 21 | 22 | 40 | 51 |
---|
Решење
Транспозиција:
12 | 7 | 3 | 25 | 27 | 78 | 98 | 21 | 22 | 40 | 51 |
---|
Број поређења у овом кораку - 5
12 | 7 | 3 | 25 | 27 | 78 | 98 | 21 | 40 | 22 | 51 |
---|
Број поређења у овом кораку - 10
12 | 7 | 25 | 3 | 27 | 78 | 98 | 21 | 40 | 22 | 51 |
---|
Број поређења у овом кораку - 4
12 | 7 | 25 | 3 | 27 | 78 | 98 | 40 | 21 | 22 | 51 |
---|
Број поређења у овом кораку - 9
Просечан број поређења:
Пребацивање на почетак:
25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 40 | 51 |
---|
Број поређења у овом кораку - 5
40 | 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
---|
Број поређења у овом кораку - 10
25 | 40 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
---|
Број поређења у овом кораку - 2
40 | 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
---|
Број поређења у овом кораку - 2
Просечан број поређења:
2. задатак
Поставка
(10п) Укратко објаснити и илустровати примерима случајеве проналажења чвора претходника по инордер поретку за задати чвор у стаблу бинарног претраживања.
Решење
Уколико чвор има лево подстабло, његов претходник је најдешњи потомак његовог левог сина, а уколико нема лево подстабло, његов претходник је његов најнижи предак чији је десни син такође његов предак. У примеру испод, претходник од 3 је 1, а претходник од 6 је 5.
3. задатак
Поставка
(15п) У АВЛ стабло са слике се редом умећу кључеви 44, 72, 19, 22, 21, 5 и 1, након чега се уклањају кључеви 23 и 39. Приказати стања стабла након сваке промене.[1]
Решење
4. задатак
Поставка
(15п) Нека је дата велика, уређена једноструко уланчана листа лист коју треба претражити на задати кључ кеy. Као помоћна структура, расположив је индекс индеx величине сизе.
- (5п) Објаснити и нацртати структуру индекса и начин повезивања са листом која се претражује.
- (10п) Написати у псеудокоду имплементацију функције за секвенцијалну претрагу листе лист уз коришћење индекса индеx на кључ кеy.
Решење
- Структура индеx представља низ чворова који садрже информационо поље са вредношћу пронађених кључева и поље-показивач на тај пронађен кључ. Структура индеx се чува уређеном.
FIND KEY LIST(list, index, size, key) int i=0; for(i<size) if(key<index[i].info) Node poc = index[i]; if(key>=index[i].info) break; while(poc!=nil) if(key==poc.info) return poc; if(key>poc.info) return nil; poc=poc.next end_while end_for
5. задатак
Поставка
(10п) Нека се у дато самоподешавајуће стабло убацује кључ 30, након чега се бришу кључеви 29 и 61, и на крају се убацује кључ 33. Приказати изглед стабла након сваког извршеног корака при уметању и брисању.
Решење
6. задатак
Поставка
(15п) Написати у псеудокоду имплементацију функције која у датом бинарном стаблу на чији корен указује показивач роот проналази и исписује адресе коренова свих подстабала која задовољавају особине стабла бинарног претраживања. Дозвољено је уводити додатна поља у чвор стабла која могу олакшати имплементацију функције.
Решење
У овом решењу су коришћене функције иницијализације, брисања и додавања у ред, као и функција провере да ли је ред празан, које су подразумевано знање са АСП1 и као такве могу да се користе без посебног псеудокода за те операције.
PRINT ALL BST(root)
Q.insert(root)
while(!Q.empty())
tr = Q.delete
CHECK(tr)
if(tr.bst) print(tr)
if(tr.left) Q.insert(tr.left)
if(tr.right) Q.insert(tr.right)
end_while
CHECK(root)
Q.insert(root, -∞,+∞)
while(!Q.empty())
{tr,min.max} = Q.delete
if(tr.left)
if(tr.left.info < min || tr.left.info > tr.info)
root.bst = 0
return
end_if
Q.insert(tr.left,min,tr.info)
end_if
if(tr.right)
if(tr.right.info < key || tr.right.info > tr.info)
root.bst = 0
return
end_if
end_if
end_while
root.bst=1
return
7. задатак
Поставка
(15п) Нека се посматра једна строго монотоно растућа функција ф(x). На пример, или . Коришћењем стратегије бинарног претраживања, написати у псеудокоду итеративну имплементацију функције која проналази вредност н за коју функција ф(x) постаје позитивна први пут, уколико важи да је x ≥ 0. Кратко објаснити поступак.
Решење
У решењу се користи бинарно претраживање у табели непознате величине.
FIND FIRST POSITIVE(f)
int high=1;
while(f(high)<0)
high *= 2;
end_while
int low = high/2;
while(low<=high)
mid = (high+low)/2;
if(f(mid)>=0 && f(mid-1)<0) return mid;
if(f(mid)>0) high = mid-1;
else low=mid+1;
end_while
8. задатак
Поставка
(10п) Анализа перформанси стабла бинарног претраживања.
- (5п) Формално дефинисати и објаснити просечан број поређења Сн приликом успешног претраживања и просечан број поређења Ун приликом неуспешног претраживања у стаблу бинарног претраживања које је настало уметањем н чворова у произвољном поретку.
- (5п) Извести и кратко објаснити везу између Сн и Ун који су дефинисани под а). Одговор илустровати сликом.
Решење
- Сн можемо представити као , јер има за 1 више поређења него чворова, а Ун можемо представити као .
Напомене
- ↑ Преписивач овог рока је заборавио како се поступно ради уметање и брисање, тако да су доступна решења само после свих уметања и после свих брисања (у преводу нисам радио поступно)