Duomenų struktūros ir algoritmai: uždaviniai ir egzamino klausimai

Didžiosios O žymėjimas, įprastų algoritmų vykdymo laikas ir masyvų, susietųjų sąrašų, medžių, maišos lentelių ir grafų kompromisai.

Pasiruošimo paketas (PDF)Formulių lapai, metodų žingsniai ir uždaviniai su pilnais sprendimais, paruošti spausdinti.

Šio kurso temos

Įdėtiniams ciklams iteracijų skaičius dauginamas; vienas po kito einantiems ciklams paliekamas didesnis narys.
Žinokite paieškos, įterpimo ir šalinimo kainą kiekvienai duomenų struktūrai.
Jei kiekviename žingsnyje įvestis sumažinama perpus, gaunamas logaritminis laikas.

Algoritmai ir sudėtingumasLengvas

Kuris žymėjimas apibūdina viršutinį augimo rėžį?

Rodyti užuominas

„Daugiausia“.
Du neteisingi atsakymai dabar išbraukti. Vienas iš likusių dviejų yra teisingas.

Rodyti atsakymą ir paaiškinimą

O nusako viršutinį rėžį, Ω – apatinį rėžį, o Θ – tikslų (asimptotiškai glaudų) rėžį.

C · Didysis O

Duomenų struktūrosVidutinis

Kaip dvejetainėje min krūvoje veikia extract-min?

Rodyti užuominas

Išlaikykite medį pilną, tada sutvarkykite tvarką.
Du neteisingi atsakymai dabar išbraukti. Vienas iš likusių dviejų yra teisingas.

Rodyti atsakymą ir paaiškinimą

Paskutinis elementas užpildo tuščią vietą šaknyje ir keičiamas vietomis su mažesniuoju vaiku, kol galioja krūvos savybė; tai užtrunka O(log n).

B · Paskutinis elementas perkeliamas į šaknį ir leidžiamas žemyn (sift down)

„Praktikuotis šiame kurse“ maišo uždavinius iš visų kurso temų, kaip tikrame egzamine.
Kiekviename uždavinyje naujos reikšmės, todėl išmokstate metodą, o ne atsakymą.
Strigote? Pirmiausia atverkite nedidelę užuominą, o visą paaiškinimą – tik kai jo prireiks.
Bandomieji egzaminai yra riboto laiko ir be užuominų, o pabaigoje gaunate rezultatą ir išsamią peržiūrą.