Datastrukturer, Komplexitetsanalys (Big-O) och Kärnalgoritmer

Repetition på grundnivå vid högskolan som kräver grundläggande programmeringskunskaper: 32 kort om arrayer, listor, hashning, träd, heapar, tries, Union–Find, Bloomfilter och komplexitet.

Category
Computer Science
Level
basic
Languages
sv → sv
Cards
32
Markdown
Datastrukturer, Komplexitetsanalys (Big-O) och Kärnalgoritmer (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Vad kostar insättning, borttagning av roten och avläsning av roten i en binär heap?O(log n), O(log n) respektive O(1), om arraystorleken inte behöver ändras. En storleksändring kan kosta O(n).
2Varför kan en dubbellänkad lista ta bort en given nod i O(1)?Länkarna till föregående och nästa nod låter grannarna kopplas ihop direkt. Huvud/svans uppdateras vid behov; föregångaren behöver inte sökas upp.
3Vilka egenskaper bör en hashfunktion för tabellsökning ha?Den ska vara deterministisk och fördela de förväntade nycklarna väl. Hashning av nycklar med fast storlek kan kosta O(1); hashning av en ny sträng med L tecken kostar oftast O(L).
4Vad är den amorterade kostnaden för att lägga till sist i en dynamisk array när kapaciteten fördubblas?O(1) per tillägg. En storleksändring kan kosta O(n), men n tillägg från en tom array kostar totalt O(n).
5Hur löser separat kedjning hashkollisioner?Varje hink innehåller en samling poster med det hinkindexet, ofta en länkad lista. Olika nycklar i samma hink förblir separata poster.
6Vad är en hashtabells belastningsfaktor och varför kan storleken ändras?α = n/m: n lagrade poster och m hinkar eller platser. Överskrids implementationens tröskel kan tabellen utökas och hashas om; 0,75 är ingen universell gräns.
7Vilken ordningsinvariant definierar ett binärt sökträd (BST) med olika nycklar?Vid varje nod är alla nycklar i vänster delträd mindre och alla i höger delträd större. Regeln gäller rekursivt.
8Jämför insättning först och indexåtkomst i en enkellänkad lista och en dynamisk array.Lista: insättning först O(1), indexåtkomst O(n). Array: insättning först O(n), indexåtkomst O(1); insättning först förskjuter elementen.
9Hur undviker en kö i en cirkulär array förskjutningar efter uttag?Fram- och bakindex går runt modulo kapaciteten. Uttag flyttar fram främre index, så lediga platser kan återanvändas utan att andra element flyttas.
10Hur beror sökning, insättning och borttagning i ett BST på höjden h?De tar O(h). Ett balanserat träd har h = O(log n), en kedja h = O(n). Förväntat O(log n) kräver antaganden, exempelvis slumpmässig insättningsordning.
11Var finns förälder och barn till nod i i en nollindexerad heaparray av längd n?Förälder: ⌊(i−1)/2⌋ för i>0. Barn: 2i+1 och 2i+2, endast om indexen är mindre än n. Index 0 har ingen förälder.
12Vad ger en inorder-traversering av ett BST med olika nycklar?Alla nycklar i strikt stigande ordning; n noder besöks på O(n) tid.
13Ordna tillväxthastigheterna från långsammast till snabbast när n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.Asymptotiskt: 1 < log n < n < n log n < n² < 2ⁿ < n!.
14Varför kostar indexåtkomst i en array med fast storlek O(1)?Lika stora platser ligger sammanhängande: adress(i) = bas + i·platsstorlek. Adressberäkningar antas ta konstant tid.
15Hur skiljer sig linjär och kvadratisk sondering vid öppen adressering?Posterna ligger kvar i arrayen. Med tabellstorlek m och startindex h provas (h+i) mod m respektive (h+c₁i+c₂i²) mod m. Kvadratisk sondering kräver lämpliga parametrar.
16Hur rättas en vänster-höger-obalans efter en AVL-insättning?Rotera först vänster barn åt vänster och sedan den obalanserade noden åt höger.
17Vad skiljer O, Ω och Θ åt?De anger asymptotiska övre, undre respektive skarpa gränser. De beskriver en angiven kostnadsfunktion; O betyder inte i sig värsta fall.
18Vilka färgregler håller ett rödsvart BST balanserat?Noder är röda eller svarta; roten och NIL-löven är svarta. Röda noder har inga röda barn. Varje väg från en nod till ett underordnat NIL-löv innehåller lika många svarta noder. Reglerna begränsar höjden till O(log n).
19Vad betyder f(n) ∈ O(g(n)) för icke-negativa funktioner f och g?Det finns konstanter c > 0 och n₀ ≥ 0 så att f(n) ≤ c·g(n) för alla n ≥ n₀.
20Hur fungerar en stack och när kostar dess operationer O(1)?LIFO: det senast inlagda elementet tas ut först. Vid en länkad listas huvud kostar inläggning, uttag och avläsning av toppen O(1); ändrad arraystorlek kan göra en inläggning O(n).
21Hur skiljer sig vägkomprimering, union efter rang och union efter storlek?Komprimering riktar om besökta noder till roten. Efter rang läggs roten med lägre rang under den med högre; efter storlek läggs den mindre mängden under den större. Rang behöver inte vara samma som aktuell höjd.
22Vilka besöksordningar har preorder, inorder och postorder i ett binärt träd?Preorder: nod → vänster → höger. Inorder: vänster → nod → höger. Postorder: vänster → höger → nod.
23Vad är en trie och när kostar sökning efter en nyckel med L tecken O(L)?Ett prefixträd lagrar nycklar längs teckenvägar, med markeringar för fullständiga nycklar. Sökningen kostar O(L) om varje övergång till nästa tecken kostar O(1).
24Vilka är de förväntade och värsta operationskostnaderna för en hashtabell med separat kedjning?Med begränsad belastning, välfördelade hashvärden och konstanta nyckeloperationer kostar sökning/borttagning förväntat O(1). Insättning med geometrisk tillväxt kostar förväntat amorterat O(1). En kedja med n kolliderande nycklar kan ge O(n).
25Vad kostar det att bygga en heap nedifrån och upp av n element?O(n). De flesta noder ligger nära löven och behöver bara sjunka lite; summering av arbetet efter nodhöjd ger en linjär totalsumma.
26Vad gör find och union i en struktur för disjunkta mängder?find(x) returnerar representanten för x:s mängd. union(x,y) slår ihop deras mängder om de skiljer sig; tillhör de redan samma mängd ändras inte partitionen.
27Vilka två egenskaper definierar en binär min-heap?Den är ett komplett binärt träd, och varje förälders nyckel är högst lika stor som barnens. Roten innehåller därför ett minimum.
28Vilken åtkomstregel och vilka vanliga operationskostnader har en kö?FIFO: lägg till sist, ta ut först. Båda kostar O(1) med huvud-/svanslänkar eller en ringbuffert med fast kapacitet; förskjutning i en array gör uttaget O(n).
29Vad är den amorterade kostnaden för union/find med vägkomprimering och union efter rang?O(α(n)) per operation, där α är inversen till Ackermannfunktionen och n antalet element. Initiering kostar O(n); gränsen gäller en följd, inte konstant värstafallskostnad för varje anrop.
30Vad är AVL-trädets balansvillkor?Vid varje nod gäller höjd(vänster) − höjd(höger) ∈ {−1, 0, 1}. Trädet uppfyller också BST:s ordningsinvariant.
31Hur besöker en nivåvis traversering ett binärt träd?En FIFO-kö används för en djupnivå i taget. Lägg in vänster barn före höger för att få ordningen från vänster till höger.
32Vilka svar kan ett Bloomfilter som bara tillåter insättningar ge?Ett negativt svar betyder att elementet inte har lagts in; ett positivt att det kan ha lagts in. Hashvärden sätter bitar i en bitarray: falska positiva är möjliga, men inga falska negativa om tillståndet är intakt.