АСП1/Септембар 2020
- Овај рок није решен. Помозите СИ Wики тако што ћете га решити.
Овај чланак је рекреација септембарског рока који није објављен.
1. задатак
Поставка
Трансформисати израз у инфиксном облику (?) у еквивалентни израз у постфиксној форми. Табелу приоритета оператора допунити одговарајућим вредностима, при чему треба усвојити стандардне приоритете и груписање за операције +,-,* и /. Трансформацију израза приказати по корацима. (Недостаје израз)
Решење
2. задатак
Поставка
Наведите начине репрезентације графова и њихове предности и мане.
Решење
3. задатак
Поставка
Написати функцију којој се прослеђује корен стабла и број к, а функција враћа чворове у чијим подстаблима се налази тачно к листова.
Решење
4. задатак
Поставка
Извести међусобну зависност интерне и екстерне дужине пута у бинарном стаблу и кратко образложити. Илустратовати одговор.
Решење
5. задатак
Поставка
Дат је стек С[1:Н] који расте од виших ка нижим адресама. Показивач топ[С] показује на прву слободну локацију. Која од 3 наредне функције је исправна функција ПОП(С)? (Недостају функције)
Решење
6. задатак
Поставка
Хуффман-ов алгоритам: Дати су симболи и вероватноћа њиховог појављивања. Како су симболи кодирани након Хуффман-овог алгоритма? Која је просечна дужина једног кода?
Решење
7. задатак
Поставка
Маша има велику библиотеку књига. За неке је висе заинтересована, а за неке мање. У школи има обавезну литературу коју мора да прочита да би могла да дискутује о лектири на часу. Моделовати Машин начин бирања књиге које ће читати. Написати функцију додавања књиге у библиотеку. (Фале још 2 функције које се траже)
Решење
8. задатак
Поставка
Дата је строго доње троугаона матрица M[1:Н,1:Н] линеаризована по врстама. Колико максимално ненултих елемената може да се нађе у матрици и образложити одговор? Извести формулу за општи члан матрице. Написати функцију дохватања елемената из матрице.
Решење
9. задатак
Поставка
Дата је матрична репрезентација усмереног, тежинског графа. Уз помоћ алгоритма за тополошко сортирање написати функцију која проверава да ли је граф цикличан.
Решење
10. задатак
Поставка
Дијкстра-ин алгоритам: Дат је тежински неусмерени граф на слици. (Недостаје слика). Уз помоћ Дијсктриног алгоритма наћи најкраћа растојања између почетног чвора M и свих осталих чворова.