Crowdly
Add to Chrome
Algoritmid ja andmestruktuurid (LTAT.03.005)
Looking for Algoritmid ja andmestruktuurid (LTAT.03.005) test answers and solutions? Browse our comprehensive collection of verified answers for Algoritmid ja andmestruktuurid (LTAT.03.005) at moodle.ut.ee.
Get instant access to accurate answers and detailed explanations for your course questions. Our community-driven platform helps students succeed!
Olgu meil funktsioon f, mis võtab sisendiks arvujärjendi, loob tühja magasini ning niikaua kuni veel järjend ei ole tühi, teeb juhuslikult ühte kolmest tegevusest:
1) eemaldab järjendi esimese elemendi ning lisab selle magasini, 2) eemaldab magasinist ühe elemendi, 3) väljastab ekraanile magasini oleku.
Märgi kõik võimalikud väljundi read, kui funktsioon f kutsutakse välja arvujärjendiga [9, 1, 8, 4, 7, 1, 4, 1, 9, 1]?
Järgneval graafikul on kujutatud sorteerimismeetodi A ja sorteerimismeetodi B ajakulu sõltuvalt sisendiks antud järjendi pikkusest, kusjuures etteantav järjend on juba sorteeritud.
Mis võiksid olla meetodid A ja B? Märgi kõik sobivad variandid.
Sortimisalgoritmide lehel on esitatud levinumate sortimisalgoritmide algoritmid ja animatsioonid. Vaata seda lehte ja uuri neid algoritme.
Märgi järgnevatest kõik meetodid, mille halvima juhu ajaline keerukus on Θ(n2), kus n on sorditavate elementide arv.
Meil on arvuti, millega võtab 10 miljoni elemendilise järjendi sorteerimine kiirmeetodiga aega keskmiselt 16000 sekundit. Umbes mitu sekundit võtab aega 10 tuhande elemendilise järjendi sorteerimine sama meetodiga samal arvutil?
// <![CDATA[ var ulObj = new Object(); ulObj.question = "Henri kirjutas järgneva programmi, mis loeb kokku, mitu erinevat võimalust on tal valida, millises järjekorras tudengid oma kodutööd seletama peavad. 4 tudengi korral leidis programm tema arvutil võimaluste arvu 1 sekundiga. Mitme sekundiga leiab programm Henri arvutil võimaluste arvu 8 tudengi korral?"; ulObj.code_function = order_of_students; document.write(question_with_code(ulObj)); // ]]> Henri kirjutas järgneva programmi, mis loeb kokku, mitu erinevat võimalust on tal valida, millises järjekorras tudengid oma kodutööd seletama peavad. 4 tudengi korral leidis programm tema arvutil võimaluste arvu 1 sekundiga. Mitme sekundiga leiab programm Henri arvutil võimaluste arvu 8 tudengi korral?
def tudengite_järjestused(tudengid, järjestus=[]):
if len(tudengid) == 0:
return 1
else:
summa = 0
for i in range(len(tudengid)):
summa += tudengite_järjestused(tudengid[:i] + tudengid[i+1:],järjestus + [tudengid[i]])
return summa
// <![CDATA[ var ulObj = new Object(); ulObj.question = "Juku ei suutnud uskuda, et 20 elemendilisi bitivektoreid on nii palju, kui õppejõud väidab. Selles veendumiseks kirjutas ta funktsiooni, mille lähtekood on esitatud allpool ja mis luges kokku kõik erinevad bitivektorid. Oma arvutil sai Juku 20 elemendi korral vastuse kätte 10 sekundiga. Kui Jukul on loengu alguseni aega 20 minutit, siis mis on maksimaalne elementide arv, mille puhul Juku saaks vastuse kätte enne loengu algust?"; ulObj.code_function = bit_vector; document.write(question_with_code(ulObj)); // ]]> Juku ei suutnud uskuda, et 20 elemendilisi bitivektoreid on nii palju, kui õppejõud väidab. Selles veendumiseks kirjutas ta funktsiooni, mille lähtekood on esitatud allpool ja mis luges kokku kõik erinevad bitivektorid. Oma arvutil sai Juku 20 elemendi korral vastuse kätte 10 sekundiga. Kui Jukul on loengu alguseni aega 20 minutit, siis mis on maksimaalne elementide arv, mille puhul Juku saaks vastuse kätte enne loengu algust?
def bittvektorite_generaator(n, vektor = ""):
if len(vektor) == n:
return 1
return bittvektorite_generaator(n, vektor + "0") + bittvektorite_generaator(n, vektor + "1")
Mitu funktsiooni fibo_rek väljakutset tehakse Fibonacci jada 17. liikme leidmiseks järgmise, rekursiivse definitsiooni põhjal koostatud funktsiooniga?
(Fibonacci jada esimene ja teine liige on 1 ja 1.)
def fibo_rek(n):
if n < 3:
return 1
return fibo_rek(n-1) + fibo_rek(n-2)
Millis(t)e funktsiooni(de) rekursioonipuuks sobib allpool toodud tasakaalus puu?
Millise järjendi korral on kiirmeetodil sorteerimise, kus valitakse lahkmeks järjendi esimene element ning jaotatakse elemendid kolmeks (väiksemad, võrdsed, suuremad), väljakutsete ahela pikkus maksimaalne?