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 operacija masyvui yra O(1), o vienkrypčiam susietajam sąrašui – O(n)?

  1. APrieiga prie elemento su indeksu i
  2. BPirmojo elemento pašalinimas
  3. CPirmojo elemento skaitymas
  4. DĮterpimas į pradžią
2.Lengvas

Kuri duomenų struktūra naudojama medžio apėjimui lygmenimis (level-order)?

  1. AEilė
  2. BPrioritetinė eilė
  3. CMaišos lentelė
  4. DStekas
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

Dvejetainio medžio šaknis yra 1, jos kairysis vaikas 2, dešinysis 3; mazgas 2 turi vaikus 4 (kairįjį) ir 5 (dešinįjį). Koks preorder apėjimas?

  1. A4 2 5 1 3
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D1 2 3 4 5
5.Vidutinis

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

  1. AĮterpiamas į surikiuotą poziciją, pastumiant visus didesnius elementus viena vieta į dešinę
  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. DPadedamas šaknyje ir leidžiamas žemyn
6.Vidutinis

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

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

Kokia blogiausio atvejo vienos find operacijos kaina union-find struktūroje su n elementų, nenaudojant jungimo pagal rangą ir kelio suspaudimo?

  1. AO(n)
  2. BO(log n)
  3. CO(α(n))
  4. DO(1)
8.Sunkus

AVL mazgas nesubalansuotas, nes jo kairiojo vaiko dešinysis pomedis tapo per aukštas (kairė–dešinė atvejis). Koks taisymas taikomas?

  1. AVienas dešinysis posūkis mazge
  2. BDešinysis posūkis kairiajame vaike, tada kairysis posūkis mazge
  3. CKairysis posūkis kairiajame vaike, tada dešinysis posūkis mazge
  4. DVienas kairysis posūkis mazge

Atsakymai

  1. 1. A · Prieiga prie elemento su indeksu i
  2. 2. A · Eilė
  3. 3. B · Viename vientisame bloke, vienas po kito
  4. 4. C · 1 2 4 5 3
  5. 5. C · Padedamas masyvo gale ir keliamas aukštyn (sift up), kol pažeidžia krūvos savybę
  6. 6. A · Kvietimų steką
  7. 7. A · O(n)
  8. 8. C · Kairysis posūkis kairiajame vaike, tada dešinysis posūkis mazge

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