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

Kur dvejetainėje min krūvoje yra mažiausias elementas?

  1. ABet kuriame lape, kurį reikia surasti
  2. BPaskutinėje masyvo pozicijoje
  3. CKairiausiame lape
  4. DŠaknyje
2.Lengvas

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

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

Ką vienkrypčiame susietajame sąraše turi paskutinio mazgo rodyklė next?

  1. APirmojo mazgo adresą
  2. BSąrašo mazgų skaičių
  3. CNull (jokio mazgo)
  4. DAnkstesnio mazgo adresą
4.Vidutinis

Kur yra mazgo su indeksu i tėvas dvejetainėje krūvoje, saugomoje masyve nuo indekso 0?

  1. AIndeksu i − 1
  2. BIndeksu ⌊(i − 1) / 2⌋
  3. CIndeksu 2i + 1
  4. DIndeksu ⌊i / 2⌋ + 1
5.Vidutinis

Kokia sargybinio (fiktyvaus, sentinel) mazgo paskirtis susietajame sąraše?

  1. ANeleisti sąrašui augti virš nustatyto didžiausio mazgų skaičiaus
  2. BSupaprastinti kodą pašalinant specialiuosius atvejus pradžioje ar pabaigoje
  3. CSaugoti elementų skaičių
  4. DPadaryti sąrašą surikiuotą
6.Vidutinis

Kiek mazgų turi tobulas dvejetainis medis, kurio aukštis h (aukštis skaičiuojamas briaunomis)?

  1. A2h
  2. B2h + 1
  3. C2h+1 − 1
  4. Dh2
7.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²)
  3. CO(n)
  4. DO(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
8.Sunkus

Kaip naudojant O(1) papildomos atminties nustatyti, ar vienkrypčiame susietajame sąraše yra ciklas?

  1. AVieną rodyklę stumti vienu žingsniu, kitą – dviem ir tikrinti, ar jos susitinka
  2. BSkaičiuoti mazgus, kol skaičius viršys sąrašo ilgio lauką
  3. CKiekvieną aplankytą mazgą saugoti maišos aibėje
  4. DSurikiuoti sąrašą ir ieškoti pasikartojimų

Atsakymai

  1. 1. D · Šaknyje
  2. 2. A · Susieja raktą su lentelės indeksu
  3. 3. C · Null (jokio mazgo)
  4. 4. B · Indeksu ⌊(i − 1) / 2⌋
  5. 5. B · Supaprastinti kodą pašalinant specialiuosius atvejus pradžioje ar pabaigoje
  6. 6. C · 2h+1 − 1
  7. 7. D · O(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
  8. 8. A · Vieną rodyklę stumti vienu žingsniu, kitą – dviem ir tikrinti, ar jos susitinka

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