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

Godusis algoritmas:

  1. AVisada pateikia optimalų sprendinį
  2. BKiekviename žingsnyje priima lokaliai geriausią sprendimą
  3. CNaudoja tik rekursiją
  4. DIšbando kiekvieną galimą sprendinį
2.Algoritmai ir sudėtingumasSunkus

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

  1. AJis neišsprendžiamas
  2. BJis priklauso P, nes jį išsprendžia Dijkstros algoritmas aplankydamas kiekvieną miestą vieną kartą
  3. CSprendimo versija priklauso P, bet optimizavimo versija yra NP-pilna
  4. DSprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
3.Duomenų struktūrosVidutinis

Kurią duomenų struktūrą naudoja paieška į gylį (DFS, iteracinė versija)?

  1. AKrūvą
  2. BEilę
  3. CSteką
  4. DTik maišos lentelę
4.Duomenų struktūrosSunkus

Žiediniame buferyje front == rear gali reikšti, kad jis tuščias arba pilnas. Koks dažnas būdas juos atskirti?

  1. ALaikyti atskirą elementų skaitiklį arba visada palikti vieną vietą nenaudojamą
  2. BBuferio dydį padaryti dvejeto laipsniu
  3. CVisada išvalyti buferį, kai front lygus rear, kad būsena būtų tuščia
  4. DFront ir rear saugoti tame pačiame kintamajame
5.Grafų teorijaVidutinis

Medis turi 2 viršūnių, kurių laipsnis 3, 2 viršūnių, kurių laipsnis 4, 3 viršūnių, kurių laipsnis 5, o visos kitos jo viršūnės yra lapai (laipsnis 1). Kiek lapų L jis turi?

2 × deg 32 × deg 43 × deg 5
L =
6.Grafų teorijaSunkus
915148118511ABCDEF

Primo algoritmas sudaro minimalų karkasinį medį pradėdamas nuo viršūnės D. Spustelėkite briauną, kurią jis prideda kaip briauną numeris 4.

pradžia: Dk = 4
  1. 1briauna AB
  2. 2briauna AC
  3. 3briauna BC
  4. 4briauna BD
  5. 5briauna CE
  6. 6briauna DE
  7. 7briauna DF
  8. 8briauna EF

3Tirpalai

1.Algoritmai ir sudėtingumas

Atsakymas: B · Kiekviename žingsnyje priima lokaliai geriausią sprendimą

Kodėl tai yra atsakymas

Godieji algoritmai yra greiti ir kai kuriems uždaviniams optimalūs (pvz., Dijkstros algoritmas, Hafmano kodavimas), bet ne bendruoju atveju (pvz., grąžos atidavimo uždavinys su kai kuriomis monetų sistemomis).

Atsakymas

B · Kiekviename žingsnyje priima lokaliai geriausią sprendimą
2.Algoritmai ir sudėtingumas

Atsakymas: D · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki

Kodėl tai yra atsakymas

„Ar yra maršrutas, kurio ilgis ne didesnis kaip k?“ yra NP-pilnas; trumpiausio maršruto radimas yra NP-sunkus, nes jis bent tiek pat sunkus.

Atsakymas

D · Sprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
3.Duomenų struktūros

Atsakymas: C · Steką

Kodėl tai yra atsakymas

DFS eina kuo giliau, natūraliai naudodama steką (arba rekursijos iškvietimų steką); BFS naudoja eilę.

Atsakymas

C · Steką
4.Duomenų struktūros

Atsakymas: A · Laikyti atskirą elementų skaitiklį arba visada palikti vieną vietą nenaudojamą

Kodėl tai yra atsakymas

Su skaitikliu tuščias reiškia count = 0, o pilnas – count = talpa; palikus vieną tuščią vietą, pilnas apibrėžiamas kaip (rear + 1) mod n == front.

Atsakymas

A · Laikyti atskirą elementų skaitiklį arba visada palikti vieną vietą nenaudojamą
5.Grafų teorija

Atsakymas: L = 17

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ų.

Rankų paspaudimo lema medžiui

L + 29 = 2(L + 7) − 2
L = 17

Atsakymas

L = 17

Trumpesnis kelias: L = 2 + Σ (d − 2) pagal viršūnes, kurių laipsnis d ≥ 3.

6.Grafų teorija

Atsakymas: briauna EF

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ą.

Primo algoritmas

1. DF (5)
2. BD (8)
3. AB (9)
4. EF (11)
5. CE (1)

briaunos numeris 4

EF

Atsakymas

briauna EF

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