Užduočių lapas tema Duomenų struktūros su atsakymais

Grafą sudaro:

1. AViršūnės (mazgai), sujungtos briaunomis
2. BEilutės ir stulpeliai
3. CTik raktai ir maišos reikšmės
4. DTik šaknis ir lapai

Kuri operacija masyve lėta, bet susietojo sąrašo pradžioje greita?

1. AFiksuoto masyvo ilgio nustatymas
2. BĮterpimas į pradžią
3. CPaskutinio elemento skaitymas pagal indeksą
4. DPrieiga prie 5-ojo elemento

Kaip vadinama eilės operacija, kuri pašalina priekyje esantį elementą?

1. APush
2. BDequeue
3. CEnqueue
4. DInsert

Kurią duomenų struktūrą vykdoma programa naudoja aktyviems funkcijų kvietimams ir jų lokaliesiems kintamiesiems sekti?

1. ADinaminės atminties (heap) eilę
2. BRėmelių dvejetainį paieškos medį
3. CKvietimų steką
4. DFunkcijų maišos lentelę

Kas nutinka, kai maišos lentelė, jos užpildymo koeficientui viršijus slenkstį, atlieka pakartotinį maišymą (rehash)?

1. AĮ naują perpildos sąrašą lentelės gale perkeliami tik susidūrę raktai
2. BSeniausi raktai pašalinami vietai atlaisvinti
3. CIšskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
4. DEsami raktai surikiuojami vietoje

Kelių tinklas turi 100,000 sankryžų, kurių kiekviena sujungta su maždaug 4 kitomis. Kuris vaizdavimas tinkamiausias?

1. ADvejetainė briaunų krūva
2. BGretimumo sąrašas
3. CVienas surikiuotas viršūnių masyvas
4. DGretimumo matrica

Struktūros union-find (nesikertančios aibės) su jungimu pagal rangą ir kelio suspaudimu amortizuota vienos operacijos kaina yra:

1. AO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
2. BO(n²)
3. CO(n)
4. DTiksliai O(log n)

Kurias operacijas Fenwicko medis (binary indexed tree) n skaičių masyvui palaiko per O(log n)?

1. APrefiksų sumų užklausas ir vieno elemento atnaujinimus
2. BMasyvo rikiavimą ir dvejetainę paiešką
3. CMedianos radimą per O(1)
4. DElementų įterpimą bet kurioje pozicijoje