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) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | Vad 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). | ||
| 2 | Varfö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. | ||
| 3 | Vilka 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). | ||
| 4 | Vad ä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). | ||
| 5 | Hur 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. | ||
| 6 | Vad ä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. | ||
| 7 | Vilken 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. | ||
| 8 | Jä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. | ||
| 9 | Hur 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. | ||
| 10 | Hur 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. | ||
| 11 | Var 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. | ||
| 12 | Vad ger en inorder-traversering av ett BST med olika nycklar? | Alla nycklar i strikt stigande ordning; n noder besöks på O(n) tid. | ||
| 13 | Ordna 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!. | ||
| 14 | Varfö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. | ||
| 15 | Hur 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. | ||
| 16 | Hur 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. | ||
| 17 | Vad 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. | ||
| 18 | Vilka 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). | ||
| 19 | Vad 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₀. | ||
| 20 | Hur 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). | ||
| 21 | Hur 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. | ||
| 22 | Vilka 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. | ||
| 23 | Vad ä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). | ||
| 24 | Vilka ä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). | ||
| 25 | Vad 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. | ||
| 26 | Vad 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. | ||
| 27 | Vilka 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. | ||
| 28 | Vilken å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). | ||
| 29 | Vad ä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. | ||
| 30 | Vad ä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. | ||
| 31 | Hur 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. | ||
| 32 | Vilka 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. |