АСП1/К2 2017

Задаци на сајту предмета

1. задатак

Поставка

Написати у псеудокоду итеративну функцију која одређује ширину бинарног стабла на чији корен показује показивач роот. Ширина стабла се дефинише као највећа ширина свих његових нивоа. Функција треба да испише све чворове на нивоу највеће ширине и врати одређену ширину. Дозвољена је употреба готових линеарних структура података

2. задатак

Поставка

Посматра се једно бинарно стабло.

1. Објаснити шта су екстерни чворови стабла и за задато бинарно стабло одредити број екстерних чворова. Екстерне чворове доцртати на задатом стаблу.
2. Извести и објаснити везу између броја екстерних чворова бинарног стабла е и чворова стабла н.

3. задатак

Поставка

Применом ЛЗW алгоритма, приказати поступак кодирања поруке АНТАНАНАРИВЕ, за дати почетни садржај табеле симбола. Написати кодирану поруку и изглед табеле симбола након поступка кодирања

4. задатак

Поставка

Коришћењем динамичког Хуффман алгоритма декодирати следећу поруку 00001010010001101101 ако је познато да су симболима А, Б и C додељени кодови фиксне дужине 00, 01 и 10 респективно. За добијену секвенцу карактера предложити њихов другачији распоред такав да се при кодирању измењене секвенце добије што већа уштеда у меморији (краћи код). Избор образложити.

5. задатак

Поставка

Ако за неко бинарно стабло преордер обилазак даје поредак НМЦОЛАГФБДПРСХQ, а инордер обилазак ЦОАЛГМБФНПХСРQД, реконструисати задатог стабла.

6. задатак

Поставка

Дато је бинарно стабло на чији корен показује показивач роот. Треба пронаћи чвор који је к-ти по преордер поретку, али тако да се заправо обиђе што мање чворова.

1. Дозвољено је увођење једног додатног поља у чвор стабла, поред постојећих поља лефт и ригхт, ради што ефикаснијег итеративног алгоритма. Укратко објаснити сврху тог поља и алгоритам за налажење к-тог чвора.
2. Написати у псеудокоду функцију која враћа показивач на к-ти чвор по преордер поретку на што је могуће ефикаснији начин.

7. задатак

Поставка

Дато је одговарајуће бинарно стабло добијено конверзијом стабла вишег реда:

1. Предложити како у стабло уградити информацију која омогућава кретање уз стабло од листова ка корену.
2. На основу горњег предлога написати функцију која за чвор са задатом адресом адр враћа његов ниво у стаблу.

8. задатак

Поставка

На крају сваке књиге постоји листа референци на друге књиге.

1. Предложити меморијску представу графа који представља референцирање књига тако да је олакшано налажење броја референци на неку књигу.
2. На основу горњег предлога написати функцију која за задату књигу налази број референци на њу.