АСП1/Јул 2020
Први колоквијум
1. задатак
Поставка
Дата је ретка квадратна матрица димензије 5. Навести два начина да се прикаже помоћу уланчаних листа.
Решење
2. задатак
Поставка
Написати псеудокод за основне операције са стеком имплементираног помоћу уланчаних листа са заглављем, тако да се у константној сложености може добити максимални елемент. Дозвољено је користити још једну листу.
Решење
3. задатак
Поставка
Пребацити инфиксни израз А*(Б-C)*(А-D!!)+Ф/Г+К у постфиксни и попунити табелу испод.
| Оператор | Улазни приоритет | Стек приоритет | Ранг |
|---|---|---|---|
| +, - | ? | ? | ? |
| *, / | ? | ? | ? |
| ! | ? | ? | ? |
| ( | ? | ? | ? |
| ) | ? | ? | ? |
Решење
4. задатак
Поставка
Имплементирати операције за додавање елемената на почетак и крај реда имплементираног преко кружног вектора.
Решење
INSERT-BEFORE(Q, value)
INSERT-AFTER(Q, value)
Други колоквијум
1. задатак
Поставка
- Прецизно дефинисати повезана стабла. Која нова поља се морају увести у нормално стабло како би постало повезано?
- Написати псеудокод функције која прима чвор и избацује га из стабла повезаног по инордер-у ако је познато да тај чвор нема левог сина.
Решење
2. задатак
Поставка
Написати псеудокод функције која за сваки чвор у стаблу проверава да ли је сума вредности свих потомака тог чвора једнака вредности тог чвора за сваки чвор који има потомке.
Решење
3. задатак
Поставка
Динамички Хафман. (?) Упоредити дужину карактера са динамичким Хафманом и без њега. (??)
Решење
4. задатак
Поставка
- Објаснити поступак конверзије м-арног стабла у бинарно стабло.
- На следећем примеру м-арног стабла приказати поступак конверзије по корацима. (?)
Решење
Трећи колоквијум
1. задатак
Поставка
Написати функцију која из датог графа у матричној репрезентацији и низа чворова проналази све чворове графа недостижне из чворова у датом низу.
Решење
GC(G, n, vars, nvars)
2. задатак
Поставка
Дефинисати јако повезане компоненте. Приказати поступак њиховог налажења на следећем графу и нацртати редуковани граф.
Решење
3. задатак
Поставка
Наћи обухватно стабло датог графа (?) Примовим алгоритмом. Да ли је обухватно стабло јединствено? Ако није, објаснити у којем кораку се може формирати другачије обухватно стабло.
Решење
4. задатак
Поставка
- Дефинисати ексцентричност чвора и средиште графа.
- Написати псеудокод функције која враћа низ ексцентричности сваког чвора графа из дате матрице најкраћих путева.
- Написати псеудокод функције која налази средиште графа из низа из претходне тачке.