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

Grafą sudaro:

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

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

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

Kas yra medžio šaknis?

1. AViršutinis mazgas, neturintis tėvo
2. BBet kuris mazgas viduryje
3. CMazgas su didžiausia reikšme
4. DMazgas be vaikų

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

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

Kiek atminties naudoja gretimumo sąrašas grafui su V viršūnių ir E briaunų?

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E²)

Kodėl dvejetainę krūvą galima saugoti masyve be jokių rodyklių?

1. AKrūvose niekada nebūna daugiau kaip 100 elementų
2. BVisi krūvos raktai lygūs
3. CTai pilnas dvejetainis medis, todėl pozicijas nusako paprastos indeksų formulės
4. DMasyvai automatiškai laiko raktus surikiuotus, todėl rodyklių nereikia

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

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

Kodėl maišos lentelėje su atviruoju adresavimu šalinimas dažnai atliekamas naudojant „antkapio“ (tombstone) žymę?

1. ADėl to lentelė tampa surikiuota
2. BIštuštinus vietą, galėtų nutrūkti kitų raktų zondavimo seka
3. CPašalinti raktai saugumo sumetimais turi būti laikomi amžinai, todėl vietų niekada negalima naudoti pakartotinai
4. DAntkapiai pagreitina maišymą