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 maišos lentelės užpildymo koeficientas (load factor)?

  1. AKibirų skaičius, padalytas iš vidutinio saugomų raktų ilgio
  2. BSaugomų elementų skaičius, padalytas iš kibirų skaičiaus
  3. CIki šiol įvykusių kolizijų skaičius
  4. DLaikas, reikalingas lentelei įkelti iš disko
2.Lengvas

Mazgo gylis medyje yra:

  1. ATo mazgo vaikų skaičius
  2. BBriaunų skaičius nuo to mazgo iki giliausio lapo
  3. CJo pomedžio mazgų skaičius
  4. DBriaunų skaičius nuo šaknies iki to mazgo
3.Lengvas

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

  1. ASuskaičiuoja, kiek raktų saugoma
  2. BUžšifruoja lentelės reikšmes
  3. CSusieja raktą su lentelės indeksu
  4. DSurikiuoja lentelės raktus
4.Vidutinis

Kiek atminties naudoja gretimumo sąrašas grafui su V viršūnių ir E briaunų?

  1. AO(E²)
  2. BO(V²)
  3. CO(V + E)
  4. DO(V × E)
5.Vidutinis

Žiedinis buferis (ring buffer) dažniausiai naudojamas įgyvendinti:

  1. AGrafo apėjimą
  2. BFiksuoto dydžio eilę
  3. CDvejetainį paieškos medį
  4. DMaišos funkciją
6.Vidutinis

Kas teisinga apie nekryptinio grafo gretimumo matricą?

  1. AKiekvienoje eilutėje yra lygiai vienas 1
  2. BJos pagrindinėje įstrižainėje visada yra vienetai
  3. CJi simetriška pagrindinės įstrižainės atžvilgiu
  4. DJi visada viršutinė trikampė
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(1)
  3. CO(log n)
  4. DO(α(n))
8.Sunkus

Struktūros union-find (nesikertančios aibės) su jungimu pagal rangą ir kelio suspaudimu amortizuota vienos operacijos kaina yra:

  1. AO(n²)
  2. BO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
  3. CO(n)
  4. DTiksliai O(log n)

Atsakymai

  1. 1. B · Saugomų elementų skaičius, padalytas iš kibirų skaičiaus
  2. 2. D · Briaunų skaičius nuo šaknies iki to mazgo
  3. 3. C · Susieja raktą su lentelės indeksu
  4. 4. C · O(V + E)
  5. 5. B · Fiksuoto dydžio eilę
  6. 6. C · Ji simetriška pagrindinės įstrižainės atžvilgiu
  7. 7. A · O(n)
  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.