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

Kas yra svorinis grafas?

1. AGrafas, turintis daugiau briaunų nei viršūnių
2. BGrafas, saugomas diske
3. CGrafas, kurio kai kurios viršūnės sunkesnės už kitas, nes turi daugiau briaunų
4. DGrafas, kurio kiekviena briauna turi skaitinę reikšmę, pvz., kainą ar atstumą

Kaip vadinama steko operacija, kuri prideda elementą į viršų?

1. APop
2. BEnqueue
3. CPeek
4. DPush

Ką maišos lentelėje atlieka maišos funkcija?

1. ASurikiuoja lentelės raktus
2. BUžšifruoja lentelės reikšmes
3. CSuskaičiuoja, kiek raktų saugoma
4. DSusieja raktą su lentelės indeksu

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

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

Dvejetainio paieškos medžio mazgas turi dešinįjį pomedį. Kur yra jo in-order įpėdinis?

1. AVisada jo dešinysis vaikas
2. BVisada jo tėvas
3. CKairiausias jo dešiniojo pomedžio mazgas
4. DDešiniausias jo kairiojo pomedžio mazgas

Eilė įgyvendinta dviem stekais: push atliekamas į steką „in“, o pop – iš steko „out“, kuris, ištuštėjęs, papildomas iš „in“. Kokia amortizuota vienos operacijos kaina?

1. AO(1)
2. BO(n²)
3. CO(log n)
4. DO(n)

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 iš standartinio Bloomo filtro elementų negalima tiesiog pašalinti išvalant jų bitus?

1. ABloomo filtrai saugo visus elementus, o suhešavus jų vėl neįmanoma rasti
2. BTie bitai gali priklausyti ir kitiems elementams, todėl atsirastų klaidingai neigiami atsakymai
3. CBloomo filtro bitų negalima keisti po sukūrimo
4. DŠalinimas padidintų klaidingai teigiamų atsakymų dažnį iki 100%