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ždaviniai Atgal į 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(K_n)| = n(n − 1)/2, |E(K_m,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 K_n: (n − 1)!/2
Dijkstros atnaujinimas: d(v) = min(d(v), d(u) + w(u, v))
L ilgio maršrutai: (Mᴸ)_ij

Metodas

Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
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

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

ARikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
BRikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
CRikiavimas įterpimu blogiausiu atveju yra O(n log n)
DRekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų

2.Algoritmai ir sudėtingumasSunkus

Ar 2²ⁿ priklauso O(2ⁿ)?

ANe, nes 2²ⁿ auga lėčiau už 2ⁿ
BTaip, nes abu yra eksponentiniai
CTaip, nes didžiajame O pastovūs laipsnio rodiklio daugikliai visada nepaisomi
DNe, nes 2²ⁿ = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai

3.Duomenų struktūrosVidutinis

Kuris kolizijų sprendimo metodas saugo susidūrusius raktus sąraše tame pačiame kibire?

ADvigubas maišymas
BAtskiros grandinės (separate chaining)
CKvadratinis zondavimas
DTiesinis zondavimas

4.Duomenų struktūrosSunkus

Kodėl serveris galėtų savo maišos funkciją atsitiktinai parinkti iš universaliosios šeimos?

AKad būtų labai mažai tikėtina, jog užpuolikas parinks daug raktų, kurie visi susiduria
BKad nebereikėtų keisti lentelės dydžio
CKad maišos lentelė būtų surikiuota
DKad garantuotų, jog jokie du raktai niekada nesusidurs, kokius raktus beišsiųstų užpuolikas

5.Grafų teorijaVidutinis

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

K₈

H =

6.Grafų teorijaSunkus

Kruskalio algoritmas sudaro minimalų karkasinį medį. Spustelėkite briauną, kurią jis prideda kaip briauną numeris 3; praleistos briaunos neskaičiuojamos.

k = 3

1briauna AC
2briauna BC
3briauna BD
4briauna CE
5briauna DE
6briauna DF
7briauna EF
8briauna GB
9briauna GD
10briauna GE

3Tirpalai

1.Algoritmai ir sudėtingumas

Atsakymas: B · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis

Kodėl tai yra atsakymas

Mažiems n paprastas rikiavimo įterpimu ciklas aplenkia greitojo rikiavimo ar rikiavimo suliejimu rekursijos pridėtines sąnaudas, nors jis ir O(n²).

Atsakymas

B · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis

2.Algoritmai ir sudėtingumas

Atsakymas: D · Ne, nes 2²ⁿ = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai

Kodėl tai yra atsakymas

Prie laipsnio rodiklio pridėta konstanta duoda pastovų daugiklį, bet konstanta, iš kurios dauginamas laipsnio rodiklis, pakeičia pagrindą ir augimo greitį.

Atsakymas

D · Ne, nes 2²ⁿ = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai

3.Duomenų struktūros

Atsakymas: B · Atskiros grandinės (separate chaining)

Kodėl tai yra atsakymas

Grandinių metodas kiekvienam kibirui laiko susietąjį sąrašą (ar kitą struktūrą); atvirasis adresavimas ieško kitos laisvos vietos pačioje lentelėje.

Atsakymas

B · Atskiros grandinės (separate chaining)

4.Duomenų struktūros

Atsakymas: A · Kad būtų labai mažai tikėtina, jog užpuolikas parinks daug raktų, kurie visi susiduria

Kodėl tai yra atsakymas

Taikant universalųjį maišymą, tikėtinas kolizijų skaičius bet kuriai raktų aibei mažas, nes užpuolikas nežino, kuri funkcija parinkta.

Atsakymas

A · Kad būtų labai mažai tikėtina, jog užpuolikas parinks daug raktų, kurie visi susiduria

5.Grafų teorija

Atsakymas: H = 2520

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ą; K_n 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 = (8 − 1)!/2 = 5040/2 = 2520

Atsakymas

H = 2520

6.Grafų teorija

Atsakymas: briauna DE

Trumpiausi keliai ir karkasiniai medžiai: Dijkstros algoritmas kiekviename etape užfiksuoja po vieną viršūnę: neužfiksuotą viršūnę su mažiausiu preliminariu atstumu. Tada jos atstumas galutinis, o kiekvienas kaimynas v gauna d(v) = min(d(v), d(u) + w(u, v)). Kruskalio algoritmas sudaro minimalų karkasinį medį imdamas briaunas nuo lengvų iki sunkių ir praleisdamas kiekvieną briauną, kuri uždarytų ciklą; Primo algoritmas augina vieną medį iš pradinės viršūnės visada pridėdamas lengviausią iš jo išeinančią briauną. Karkasinis medis su n viršūnių turi n − 1 briauną.

Kruskalio algoritmas

1. BC (2)

2. GE (3)

3. DE (9)

4. BD (10)

5. DF (14)

6. AC (19)

briaunos numeris 3

Atsakymas

briauna DE

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