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

Kas yra svorinis grafas?

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

Kaip masyvo elementai saugomi atmintyje?

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

Dvejetainiame paieškos medyje mazgo kairiojo pomedžio reikšmės yra:

  1. AAtsitiktine tvarka
  2. BMažesnės už mazgo reikšmę
  3. CDidesnės už mazgo reikšmę
  4. DLygios mazgo reikšmei
4.Vidutinis

Kiek laiko užtrunka L ilgio žodžio paieška Trie medyje su fiksuota abėcėle?

  1. AO(n), kur n yra žodžių skaičius
  2. BO(L × n)
  3. CO(L), nepriklausomai nuo saugomų žodžių skaičiaus
  4. DO(log n), kur n yra žodžių skaičius
5.Vidutinis

Kaip naujas elementas įterpiamas į dvejetainę krūvą?

  1. APadedamas šaknyje ir leidžiamas žemyn
  2. BVisa krūva perstatoma iš naujo
  3. CPadedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę
  4. DĮterpiamas į surikiuotą poziciją, pastumiant visus didesnius elementus viena vieta į dešinę
6.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. BIšskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  3. CEsami raktai surikiuojami vietoje
  4. DĮ naują perpildos sąrašą lentelės gale perkeliami tik susidūrę raktai
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. AAtvaizdis išmeta klaidą tą akimirką, kai laukas pasikeičia
  2. BAtvaizdis automatiškai perkelia raktą į naują kibirą
  3. CObjekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
  4. DNiekas nepasikeičia, nes rakto maišos reikšmė skaičiuojama tik vieną kartą programai pasileidus
8.Sunkus

Kuris teiginys apie rikiavimą krūva (heapsort) teisingas?

  1. AJis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus
  2. BSu bet kokia įvestimi jis veikia per O(n)
  3. CJis stabilus ir jam reikia O(n) papildomos atminties
  4. DJam reikia dvejetainio paieškos medžio kaip papildomos atminties, todėl jis naudoja O(n) papildomos atminties

Atsakymai

  1. 1. A · Grafas, kurio kiekviena briauna turi skaitinę reikšmę, pvz., kainą ar atstumą
  2. 2. B · Viename vientisame bloke, vienas po kito
  3. 3. B · Mažesnės už mazgo reikšmę
  4. 4. C · O(L), nepriklausomai nuo saugomų žodžių skaičiaus
  5. 5. C · Padedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę
  6. 6. B · Išskiriama didesnė lentelė, ir kiekvienas raktas įterpiamas iš naujo
  7. 7. C · Objekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
  8. 8. A · Jis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus

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