- Член од
- 4 септември 2010
- Мислења
- 31
- Поени од реакции
- 0
Во одговорот напишете го редниот број на прашањето кое се одговара.
1.Да се скицира метода (може и во Java) f(n,k), која има сложеност O(nk).
2.Користејќи ја Java подршката за полиморфизам, да се скицира кои од следните елементи во дадениот проблем ќе бидат интерфејси, апстрактни класи и класи.
Банката “YZ” во работи со населението преку нивните сметки. Сметките можат да бидат кредити или депозити. Секоја сметка има единствен број, сопственик и салдо. Кредитите можат да бидат наменски или ненаменски. Сите кредити имаат износ, камата и број на рати. За наменските се чува само моментално салдо. За ненаменските се чува салдо и име на човек- жирант. За кредитите може да се додаваат средства и да се пресметува камата. На депозитите може да се додаваат и вадат пари, како и да се пресметува камата.Постојат два вида на депозити: штедни книшки и тековни сметки. Тековните сметки содржат информации за број на издадени чекови и дозволен минус. Вадењето на пари од тековна сметка е исклучиво преку чек, при што се намалува бројот на издадени чекови. За тековните сметки можно е и давање на чекови, при што се ажурира бројот на издадени чекови. Штедните книшки содржат информации за бројот на страница во книшката каде последно се печатело. Овој број се зголемува за 1 при секоја трансакција со книшката.
Пресметувањето на каматата зависи од типот на сметката и е различно за кредити и депозити. За сите кредити камата се пресметува по иста формула. За депозитите, зависи од типот на депозитот (значи различно за штедни книшки, а различно за тековни сметки). При уписот на камата, кај кредити и тековни сметки се додава износ, додека кај штедни книшки се додава износ и се зголемува бројот на страница.
3.Да се скицира изгледот на AVL дрво во секој чекор при вменувањето на следната секвенца на елементи: 5, 10, 15, 3, 1, 7, 2.
4.Дадена е листа на зависности на настани, од типот: Б се извршува после А. Потребно е да се најде еден можен линеарен распоред на активностите така што ќе се запазат нивните активности. Заради едноставност, не постојат циклични зависности(на пр. Б после А, В после Б А после В). Која структура може да се искористи за решавање? Да се скицира алгоритмот за наоѓање на бараната линеарна секвенца. Пример: Б после А, В после А, Г после Б, Ѓ после Г, Ѓ после В. Една можна секвенца е: А, Б, Г, В, Ѓ.
5.На АПТ стек да и се додаде нова метода која се вика findMaximum и која го враќа најголемиот во стекот. Дали може да се направи оваа метода да има сложеност O(1) во најлош случај? Ако може, што треба да се промени (додаде) на АПТ за да се овозможи ваква метода.
6.Да се напише алгоритам базиран на Quicksort кој за дадена низа податоци и број k ќе го врати k-тиот по големина елемент. Пример, за низата [1, 5, 3, 2, 7, 4] и k=2 ќе врати 5, бидејќи 5 е втор по големина. Дали може да се дефинира и друг алгоритам за истата намена, но кој ќе гарантира подобра сложеност во најлош случај? Ако може, да се напише истиот.
7.Во податочен тип AVL дрво се додава следната секвенца од елементи: 40, 20, 30, 45, 70, 50, 60, 10 (при што секако во секое вметнување се врши ребалансирање). Кој е конечниот изглед на дрвото?
8.Да се скицира податочна структура во која ќе може да се запише низа од карактери, а потоа да се провери дали низата е палиндром (читана од лево кон десно и од десно кон лево низата е иста, на пр, АВИВА). Каква е сложеноста на методата за проверка на палиндромот? Со која фундаментална структура би се решил проблемот (и зошто)?
9.Опишете ги сите чекори на алгоритмот на Дијкстра за наоѓање на најкраток пат во следниот граф, при што почетно теме е a. Каква е сложеноста на овој алгоритам?
10.Опиши алгоритам кој ќе врши Преордер обиколка на следниот тип на графови:
a.Едно теме е корен.
b.Секое теме има покажувач кон својот родител.
c.Секое теме има покажувач на најлевото свое дете (Null ако нема деца).
d.Секое теме има има десен покажувач кон уште едно дете од истиот родител (Null ако е најдесно).
11.Дадена е следната низа од елементи: 20, 30, 25, 15, 45, 35, 55, 60, 70. Да се опишат чекор по чекор вметнувањата на секој од елементите во AVL дрво (иницијално дрвото е празно).
12.Дадена е OBHT (отворена хаш табела) со капацитет од 13 елементи, природни броеви. Да се најде една можна хаш функција. Да се покажат чекорите при вметнувањето и бришењето на следните елементи во табелата (+ значи вметнување, - значи бришење): +2, +15, +23, +7, +20, +33, -2, -20, +46.
13.Дадени се 12 тегови, наизглед исти. Една од нив има маса различна од останатите (помала или поголема). На располагање имате само една терезија. Во колку најмалку чекори можете да го најдете различниот тег? Опишете ја постапката.
14.Да се скицира податочна структура која ќе овозможи преставување на семејно дрво. Елементите на структурата се луѓе кои можат да бидат во следните релации: брак, родител-дете, брат-брат (или брат-сестра или сестра-сестра).
15.Да се најде сложеноста на алгоритмите за собирање и множење на две n * n матрици.
16.Користејќи ја Java поддршката за полиморфизам, да се скицира кои од следните елементи на дадениот проблем ќе бидат интерфејси, апстрактни класи и класи.
Да се конструира објектен модел на персонална евиденција на еден факултет. На факултетот постоја лица, кои можат да бидат вработени или студенти. Вработените можат да бидат технички персонал или академски персонал. Академискиот персонал се состои од наставници и соработници. Студентите можат да бидат запишани на некоја година на студии. Студентите исто така можат да бидат и демонстратори. На факултетот можат да се додаваат и вадат лица, како и да се печатат нивните лични карактеристики (ЕМБГ, име и презиме). За вработените се чува датумот на вработување, а можат да се вработуваат и отпуштаат од работа. За техничкиот персонал се чува име на службата во која работи. За наставниот персонал треба да може да се постави (и секако промени) степенот на образование. Наставниците можат да станат и шефови. Соработниците можат да добиваат и губат стипендии. Студентите запишуваат предмети. На демонстраторите можат да им се доделуваат предмети за вежби.
17.Да се опише метода која за дадено бинарно дрво проверува дали истото е пребарувачко бинарно дрво. Каква е сложеноста на оваа метода.
18.Дадена е поврзана листа. Да се утврди дали во листата има јамка (loop), со O
временска сложеност и O(1) просторна сложеност.
19.Да се скицира постапка за решавање на проблемот: Дадено е множество од цели броеви и вредност S. Да се најде подмножество од множеството чија сума на елементите е еднаква на S.
20.Напишете алгоритам за одредување дали едно бинарно дрво е heap? Каква е сложеноста на овој алгоритам?
21.Дадена е следната секвенца на броеви која треба да се вметне во AVL дрво: 1, 2, 3, 4, 5, 7, 8. Да се скицира конечниот изглед на дрвото, ако во секој чекор се врши балансирање (доколку има потреба).
22.Наведи барем по еден алгоритам кој има комплексност: О(1), O(log n), O, O(n2), O(n3), O(2n).
23.Наведи ги чекорите со кои ќе биде обработен математичкиот израз: (2 + 9x3) + (10 - 27/3) + 1 со помош на структурата “стек”.
24.Што е тоа сортирање без споредување?
1.Да се скицира метода (може и во Java) f(n,k), која има сложеност O(nk).
2.Користејќи ја Java подршката за полиморфизам, да се скицира кои од следните елементи во дадениот проблем ќе бидат интерфејси, апстрактни класи и класи.
Банката “YZ” во работи со населението преку нивните сметки. Сметките можат да бидат кредити или депозити. Секоја сметка има единствен број, сопственик и салдо. Кредитите можат да бидат наменски или ненаменски. Сите кредити имаат износ, камата и број на рати. За наменските се чува само моментално салдо. За ненаменските се чува салдо и име на човек- жирант. За кредитите може да се додаваат средства и да се пресметува камата. На депозитите може да се додаваат и вадат пари, како и да се пресметува камата.Постојат два вида на депозити: штедни книшки и тековни сметки. Тековните сметки содржат информации за број на издадени чекови и дозволен минус. Вадењето на пари од тековна сметка е исклучиво преку чек, при што се намалува бројот на издадени чекови. За тековните сметки можно е и давање на чекови, при што се ажурира бројот на издадени чекови. Штедните книшки содржат информации за бројот на страница во книшката каде последно се печатело. Овој број се зголемува за 1 при секоја трансакција со книшката.
Пресметувањето на каматата зависи од типот на сметката и е различно за кредити и депозити. За сите кредити камата се пресметува по иста формула. За депозитите, зависи од типот на депозитот (значи различно за штедни книшки, а различно за тековни сметки). При уписот на камата, кај кредити и тековни сметки се додава износ, додека кај штедни книшки се додава износ и се зголемува бројот на страница.
3.Да се скицира изгледот на AVL дрво во секој чекор при вменувањето на следната секвенца на елементи: 5, 10, 15, 3, 1, 7, 2.
4.Дадена е листа на зависности на настани, од типот: Б се извршува после А. Потребно е да се најде еден можен линеарен распоред на активностите така што ќе се запазат нивните активности. Заради едноставност, не постојат циклични зависности(на пр. Б после А, В после Б А после В). Која структура може да се искористи за решавање? Да се скицира алгоритмот за наоѓање на бараната линеарна секвенца. Пример: Б после А, В после А, Г после Б, Ѓ после Г, Ѓ после В. Една можна секвенца е: А, Б, Г, В, Ѓ.
5.На АПТ стек да и се додаде нова метода која се вика findMaximum и која го враќа најголемиот во стекот. Дали може да се направи оваа метода да има сложеност O(1) во најлош случај? Ако може, што треба да се промени (додаде) на АПТ за да се овозможи ваква метода.
6.Да се напише алгоритам базиран на Quicksort кој за дадена низа податоци и број k ќе го врати k-тиот по големина елемент. Пример, за низата [1, 5, 3, 2, 7, 4] и k=2 ќе врати 5, бидејќи 5 е втор по големина. Дали може да се дефинира и друг алгоритам за истата намена, но кој ќе гарантира подобра сложеност во најлош случај? Ако може, да се напише истиот.
7.Во податочен тип AVL дрво се додава следната секвенца од елементи: 40, 20, 30, 45, 70, 50, 60, 10 (при што секако во секое вметнување се врши ребалансирање). Кој е конечниот изглед на дрвото?
8.Да се скицира податочна структура во која ќе може да се запише низа од карактери, а потоа да се провери дали низата е палиндром (читана од лево кон десно и од десно кон лево низата е иста, на пр, АВИВА). Каква е сложеноста на методата за проверка на палиндромот? Со која фундаментална структура би се решил проблемот (и зошто)?
9.Опишете ги сите чекори на алгоритмот на Дијкстра за наоѓање на најкраток пат во следниот граф, при што почетно теме е a. Каква е сложеноста на овој алгоритам?
10.Опиши алгоритам кој ќе врши Преордер обиколка на следниот тип на графови:
a.Едно теме е корен.
b.Секое теме има покажувач кон својот родител.
c.Секое теме има покажувач на најлевото свое дете (Null ако нема деца).
d.Секое теме има има десен покажувач кон уште едно дете од истиот родител (Null ако е најдесно).
11.Дадена е следната низа од елементи: 20, 30, 25, 15, 45, 35, 55, 60, 70. Да се опишат чекор по чекор вметнувањата на секој од елементите во AVL дрво (иницијално дрвото е празно).
12.Дадена е OBHT (отворена хаш табела) со капацитет од 13 елементи, природни броеви. Да се најде една можна хаш функција. Да се покажат чекорите при вметнувањето и бришењето на следните елементи во табелата (+ значи вметнување, - значи бришење): +2, +15, +23, +7, +20, +33, -2, -20, +46.
13.Дадени се 12 тегови, наизглед исти. Една од нив има маса различна од останатите (помала или поголема). На располагање имате само една терезија. Во колку најмалку чекори можете да го најдете различниот тег? Опишете ја постапката.
14.Да се скицира податочна структура која ќе овозможи преставување на семејно дрво. Елементите на структурата се луѓе кои можат да бидат во следните релации: брак, родител-дете, брат-брат (или брат-сестра или сестра-сестра).
15.Да се најде сложеноста на алгоритмите за собирање и множење на две n * n матрици.
16.Користејќи ја Java поддршката за полиморфизам, да се скицира кои од следните елементи на дадениот проблем ќе бидат интерфејси, апстрактни класи и класи.
Да се конструира објектен модел на персонална евиденција на еден факултет. На факултетот постоја лица, кои можат да бидат вработени или студенти. Вработените можат да бидат технички персонал или академски персонал. Академискиот персонал се состои од наставници и соработници. Студентите можат да бидат запишани на некоја година на студии. Студентите исто така можат да бидат и демонстратори. На факултетот можат да се додаваат и вадат лица, како и да се печатат нивните лични карактеристики (ЕМБГ, име и презиме). За вработените се чува датумот на вработување, а можат да се вработуваат и отпуштаат од работа. За техничкиот персонал се чува име на службата во која работи. За наставниот персонал треба да може да се постави (и секако промени) степенот на образование. Наставниците можат да станат и шефови. Соработниците можат да добиваат и губат стипендии. Студентите запишуваат предмети. На демонстраторите можат да им се доделуваат предмети за вежби.
17.Да се опише метода која за дадено бинарно дрво проверува дали истото е пребарувачко бинарно дрво. Каква е сложеноста на оваа метода.
18.Дадена е поврзана листа. Да се утврди дали во листата има јамка (loop), со O
временска сложеност и O(1) просторна сложеност.19.Да се скицира постапка за решавање на проблемот: Дадено е множество од цели броеви и вредност S. Да се најде подмножество од множеството чија сума на елементите е еднаква на S.
20.Напишете алгоритам за одредување дали едно бинарно дрво е heap? Каква е сложеноста на овој алгоритам?
21.Дадена е следната секвенца на броеви која треба да се вметне во AVL дрво: 1, 2, 3, 4, 5, 7, 8. Да се скицира конечниот изглед на дрвото, ако во секој чекор се врши балансирање (доколку има потреба).
22.Наведи барем по еден алгоритам кој има комплексност: О(1), O(log n), O
, O(n2), O(n3), O(2n).23.Наведи ги чекорите со кои ќе биде обработен математичкиот израз: (2 + 9x3) + (10 - 27/3) + 1 со помош на структурата “стек”.
24.Што е тоа сортирање без споредување?
))
