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

Nemokamas spausdinamas užduočių lapas tema Duomenų struktūros: 8 uždavinių nuo lengvų iki egzamino lygio, su atsakymais. Atsispausdinkite arba išsaugokite kaip PDF.

Naujas užduočių lapasPraktikuokitės internete su užuominomis

Mokytojams: galima nemokamai spausdinti, kopijuoti ir naudoti per pamokas. Kiekvienas naujas lapas turi naujas reikšmes ir savo atsakymų raktą. Būsime dėkingi už nuorodą į ExamProblems jūsų kurso puslapyje.

Vardas: ____________________   Data: ____________

1.Lengvas

Kuri struktūra paprastai naudojama prioritetinei eilei įgyvendinti?

  1. AStekas
  2. BEilutė
  3. CNesutvarkytas vienkryptis susietasis sąrašas
  4. DKrūva
2.Lengvas

Ką saugo atvaizdis (žodynas, map)?

  1. ARaktų ir reikšmių poras su unikaliais raktais
  2. BTik reikšmes įterpimo tvarka
  3. CPagal dydį surikiuotas reikšmes
  4. DVienodų raktų poras
3.Lengvas

Kaip masyvo elementai saugomi atmintyje?

  1. AIšbarstyti, susieti rodyklėmis
  2. BViename vientisame bloke, vienas po kito
  3. CAtsitiktinėse maišos funkcijos parinktose vietose
  4. DAtminties puslapių medyje
4.Vidutinis

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²)
5.Vidutinis

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

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

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

  1. ANesutvarkytą aibę
  2. BFIFO eilę
  3. CSteką
  4. DMin prioritetinę eilę
7.Sunkus

Objektas saugomas kaip raktas maišos atvaizdyje, o paskui pakeičiamas laukas, kurį naudoja jo maišos funkcija. Koks tikėtinas rezultatas?

  1. AObjekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
  2. BAtvaizdis išmeta klaidą tą akimirką, kai laukas pasikeičia
  3. CAtvaizdis automatiškai perkelia raktą į naują kibirą
  4. DNiekas nepasikeičia, nes rakto maišos reikšmė skaičiuojama tik vieną kartą programai pasileidus
8.Sunkus

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²)

Atsakymai

  1. 1. D · Krūva
  2. 2. A · Raktų ir reikšmių poras su unikaliais raktais
  3. 3. B · Viename vientisame bloke, vienas po kito
  4. 4. A · O(1)
  5. 5. C · Išskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  6. 6. D · Min prioritetinę eilę
  7. 7. A · Objekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
  8. 8. B · O(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi

Išsamūs sprendimai žingsnis po žingsnio: praktikuokite šią temą svetainėje examproblems.com.