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. AĮterpimas į pradžią
  2. BPirmojo elemento pašalinimas
  3. CPirmojo elemento skaitymas
  4. DPrieiga prie elemento su indeksu i
2.Lengvas

Kuo apibrėžiamas dvejetainis medis?

  1. AMedis turi lygiai du lygmenis
  2. BKiekvienas mazgas turi lygiai du vaikus
  3. CKiekvienas mazgas turi daugiausia du vaikus
  4. DKiekvienas mazgas saugo dvejetainį skaičių
3.Lengvas

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

  1. ALygios mazgo reikšmei
  2. BAtsitiktine tvarka
  3. CMažesnės už mazgo reikšmę
  4. DDidesnės už mazgo reikšmę
4.Vidutinis

Koks yra blogiausio atvejo dvejetainio paieškos medžio su n mazgų aukštis, jei raktai įterpiami surikiuota tvarka?

  1. A1
  2. Blog₂ n
  3. Cn (medis tampa susietuoju sąrašu)
  4. D√n
5.Vidutinis

Dvejetainėje min krūvoje, saugomoje masyve (indeksai nuo 0), mazgo su indeksu i vaikai yra pozicijose:

  1. Ai + 1 ir i + 2
  2. Bi/2 ir i/2 + 1
  3. C2i ir 2i + 1
  4. D2i + 1 ir 2i + 2
6.Vidutinis

Prefiksų medis (trie) ypač efektyvus:

  1. AMatricų saugojimui
  2. BSkaičių rikiavimui
  3. CTrumpiausių kelių paieškai
  4. DPrefiksų paieškai, pavyzdžiui, automatiniam užbaigimui
7.Sunkus

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

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

Operacijos decrease-key dvejetainėje krūvoje (žinant elemento poziciją) laiko sudėtingumas yra:

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

Atsakymai

  1. 1. D · Prieiga prie elemento su indeksu i
  2. 2. C · Kiekvienas mazgas turi daugiausia du vaikus
  3. 3. C · Mažesnės už mazgo reikšmę
  4. 4. C · n (medis tampa susietuoju sąrašu)
  5. 5. D · 2i + 1 ir 2i + 2
  6. 6. D · Prefiksų paieškai, pavyzdžiui, automatiniam užbaigimui
  7. 7. B · Jis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus
  8. 8. D · O(log n)

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