Duomenų struktūros ir algoritmai: pasiruošimo paketas

Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 6 uždavinių, o pilni sprendimai pateikti gale.

Nauji uždaviniaiAtgal į kursą

Spausdinimo lange pasirinkite „Išsaugoti kaip PDF“, kad nuosavą kopiją išsaugotumėte savo įrenginyje.

1Formulės ir metodai

Grafų teorija

Rankų paspaudimo lema
Σ deg(v) = 2|E|
Pilnieji grafai
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Reguliarusis grafas
|E| = n·k/2
Medis ir miškas
|E| = n − 1, |E| = n − c
Medžio lapai
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Oileris
ciklas: visų viršūnių laipsniai lyginiai; kelias: lygiai 2 nelyginio laipsnio viršūnės
Hamiltono ciklai grafe Kn
(n − 1)!/2
Dijkstros atnaujinimas
d(v) = min(d(v), d(u) + w(u, v))
L ilgio maršrutai
(Mᴸ)ij

Metodas

  1. Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
  2. Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
  3. Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
  4. Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
  5. Minimaliam karkasiniam medžiui surikiuokite briaunas pagal svorį ir praleiskite kiekvieną briauną, uždarančią ciklą (Kruskalis), arba auginkite vieną medį iš pradinės viršūnės (Primas).

2Uždaviniai

1.Algoritmai ir sudėtingumasVidutinis

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

  1. ASu atsitiktinės tvarkos masyvu
  2. BSu 2 ilgio masyvu
  3. CSu jau surikiuotu masyvu
  4. DSu masyvu, kurio visi elementai skirtingi
2.Algoritmai ir sudėtingumasSunkus

Kuris rėžis teisingas log(n!)?

  1. AΘ(n²)
  2. BΘ(n)
  3. CΘ(n log n)
  4. DΘ(log n)
3.Duomenų struktūrosVidutinis

Raktai 50, 30, 70, 20, 40 šia tvarka įterpiami į tuščią dvejetainį paieškos medį. Koks yra 30 kairysis vaikas?

  1. A40
  2. B50
  3. C70
  4. D20
4.Duomenų struktūrosSunkus

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

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

Kiek skirtingų Hamiltono ciklų H turi pilnasis grafas K5? Ciklai, besiskiriantys tik pradine viršūne ar kryptimi, laikomi tuo pačiu.

K5
H =
6.Grafų teorijaSunkus
ABCDE

Kiek yra 3 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties C? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.

M = gretimumo matricaL = 3
N =

3Tirpalai

1.Algoritmai ir sudėtingumas

Atsakymas: C · Su jau surikiuotu masyvu

Kodėl tai yra atsakymas

Surikiuotoje įvestyje atraminis elementas visada yra minimumas, todėl viena pusė tuščia, o kitoje n − 1 elementų, ir gaunama O(n²).

Atsakymas

C · Su jau surikiuotu masyvu
2.Algoritmai ir sudėtingumas

Atsakymas: C · Θ(n log n)

Kodėl tai yra atsakymas

log(n!) ≤ n log n, o didžiausi n / 2 daugiklių duoda log(n!) ≥ (n / 2) log(n / 2); todėl rikiavimui palyginimais reikia Ω(n log n).

Atsakymas

C · Θ(n log n)
3.Duomenų struktūros

Atsakymas: D · 20

Kodėl tai yra atsakymas

20 mažesnis už 50 ir mažesnis už 30, todėl tampa 30 kairiuoju vaiku; 40 tampa jo dešiniuoju vaiku.

Atsakymas

D · 20
4.Duomenų struktūros

Atsakymas: A · Jis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus

Kodėl tai yra atsakymas

Rikiavimas krūva sudaro max krūvą ir n kartų išima maksimumą tame pačiame masyve; sukeitimai dideliais atstumais gali pakeisti vienodų raktų tvarką.

Atsakymas

A · Jis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus
5.Grafų teorija

Atsakymas: H = 12

Oileris, Hamiltonas ir medžiai: jungus grafas turi Oilerio ciklą (kiekviena briauna vieną kartą, grįžtama į pradžią), kai kiekvienos viršūnės laipsnis lyginis, ir Oilerio kelią, kuris nėra ciklas, kai lygiai dvi viršūnės turi nelyginį laipsnį; tada kelias eina iš vienos nelyginės viršūnės į kitą. Hamiltono ciklas aplanko kiekvieną viršūnę vieną kartą; Kn jų turi (n − 1)!/2. Medis su n viršūnių turi n − 1 briauną, o jungus grafas su m briaunų turi karkasinį medį, pašalinus m − n + 1 briaunų.

Suskaičiuokite

H = (5 − 1)!/2 = 24/2 = 12

Atsakymas

H = 12
6.Grafų teorija

Atsakymas: N = 2

Laipsniai: viršūnės laipsnis yra joje susitinkančių briaunų skaičius. Kiekviena briauna turi du galus, todėl laipsnių suma lygi dvigubam briaunų skaičiui: Σ deg(v) = 2|E| (rankų paspaudimo lema). Todėl nelyginio laipsnio viršūnių skaičius lyginis. Kn turi n(n − 1)/2 briaunų, k-reguliarusis grafas su n viršūnių – nk/2, o medis su n viršūnių – n − 1 briauną.

Gretimumo matrica

A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 0
D: 0 1 0 0 1
E: 0 1 0 1 0

Dar vienas žingsnis

(M³)CC = 1·1 + 1·1 + 2·0 + 1·0 + 1·0 = 2

Atsakymas

N = 2

ExamProblems · examproblems.com/courses/data-structures-and-algorithms