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

Kuri operacija masyvui yra O(1), o vienkrypčiam susietajam sąrašui – O(n)?

1. APirmojo elemento pašalinimas
2. BPirmojo elemento skaitymas
3. CĮterpimas į pradžią
4. DPrieiga prie elemento su indeksu i

Koks yra aibės, kaip abstrakčiojo duomenų tipo, apibrėžiantis bruožas?

1. AJi saugo elementus surikiuota tvarka
2. BJi leidžia prieigą tik viename gale
3. CJi saugo elementus be pasikartojimų
4. DJi saugo raktų ir reikšmių poras

Ką saugo atvaizdis (žodynas, map)?

1. ATik reikšmes įterpimo tvarka
2. BVienodų raktų poras
3. CPagal dydį surikiuotas reikšmes
4. DRaktų ir reikšmių poras su unikaliais raktais

Kokia kaina įterpti elementą į n elementų masyvo vidurį?

1. AO(1), nes indeksas žinomas
2. BO(log n), dėl dvejetainės paieškos
3. CO(n²), nes kiekvienas elementas pajuda n kartų
4. DO(n), nes vėlesnius elementus reikia pastumti

Kaip žiedinėje eilėje, saugomoje n talpos masyve, apskaičiuojama kita pozicija po indekso i?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Kurį abstraktųjį duomenų tipą Dijkstros algoritmas naudoja kitai apdorojamai viršūnei parinkti?

1. ASteką
2. BNesutvarkytą aibę
3. CMin prioritetinę eilę
4. DFIFO eilę

Kuri duomenų struktūra leidžia LRU (least recently used) podėlį su O(1) get ir put operacijomis?

1. AVienas surikiuotas masyvas
2. BTik stekas
3. CTik dvejetainis paieškos medis
4. DMaišos žemėlapis kartu su dvikrypčiu susietuoju sąrašu

Kiekvienam masyvo elementui norite rasti artimiausią didesnį elementą į dešinę, iš viso per O(n). Kuri struktūra padeda?

1. AKiekvienam elementui iš naujo sudaromas dvejetainis paieškos medis
2. BEilė, laikanti kiekvieną elementų porą
3. CStekas, kuriame laikomi atsakymo laukiantys elementai
4. DVisų elementų maišos lentelė