Data Structures and Algorithms Flashcards
Kas yra duomenų struktūra?
Duomenų organizavimo, valdymo ir saugojimo formatas skirtas efektyviai saugoti, pasiekti ir modifikuoti duomenis
Kas yra algoritmas? Kokios yra jų kategorijos?
Tai yra instrukcijos, kurias kompiuteris seka, kad įvykdytų tam tikras užduotis
1) Paieškos (search) – elemento suradimas duomenų struktūroje.
2) Rikiavimo (sort) – elementų tvarkos perskirstimo duomenų struktūroje.
3) Atnaujinimo (update) – elemento reikšmės pakeitimo duomenų struktūroje.
4) Naikinimo (delete) – elemento pašalinimo iš duomenų struktūros.
Kuo skiriasi duomenų struktūra nuo algoritmo?
Duomenų struktūra skirta duomenims saugoti, o algoritmas - tai veiksmų seka, kurią kompiuteris vykdo rezultatui gauti
Kas yra BigO asimptotinė analizė ir kam jis skirtas?
BigO skaičiuojama norint išsiaiškinti algoritmo teorinį efektyvumą. Iš esmės tai parodo kaip greitai algoritmas bus įgyvendintas turint didelės apimties duomenis.
Koks bus šio algoritmo BigO?
public int addUpTo(n){
return n * (n + 1) / 2;
}
O(1)
Paaiškinimas: kad ir kiek didėtų n dydis, operacijų skaičius visada lieka tas pats ir laikas, per kurį bus atliekamas šis algoritmas taip pat išliks vienodas
Koks bus šio algoritmo BigO?
public int addUpTo(n){ var total = 0; for (int i=0; i<= n; i++){ total += i; } return total;
O(n)
Paaiškinimas: kuo didesnis bus n , analogiškai daugės ir operacijų skaičius. Todėl augant n kiekiui, ilgės ir atlikimo greitis
Koks bus šio algoritmo BigO?
public int addUpTo(n){ Console.WriteLine("Going up!); for (int i = 0; i <= n; i++){ Console.WriteLine(i); } Console.WriteLine("At the top!\nNow going down.."; for (int j = 0;j <= n; j++){ Console.WriteLine(j); } Console.WriteLine("Back down"); }
O(n)
Paaiškinimas: yra du ciklai. Pirmas yra lygus O(n), antras taip pat lygus O(n). Kartu jie yra lygūs O(2n), tačiau kai kalba eina apie labai didelius skaičius tokie daugikliai kaip 2 prieš n nebeturi jokios prasmės, todėl juos galime tiesiog nubraukti. Gauname rezultatą O(n).
Koks bus šio algoritmo bigO?
public int printAllPairs(n){ for( int i = 0; i <= n; i++){ for( int j = 0; j <= n; j++){ Console.WriteLine(i, j); } } }
O(n^2)
Paaiškinimas: turime pirmą ciklą, kuris yra O(n), jame yra antras toks pats ciklas kuris yra taip pat O(n). O(n*n) => O(n^2).
Daugėjant operacijų šio BigO tipo operacijos sulėtės labiausiai.
Kas yra Node (jungtis)?
Node’ai yra pagrindinės sudedamosios dalys kitoms duomenų struktūroms kaip Linked lists, stacks, queues, medžiams (trees) ir kt.
Kiekvienas nodas savyje turi turi dvi informacijos rūšis: data ir nuorodą į kitą nodą. Skirtingos struktūros šiems nodams implementuoja papildomasa funkcijas ar elgseną.
Kas yra Linked List?
Linked listai yra viena iš bazinių duomenų struktūrų naudojamų programavime. Visa informacija (data) yra saugoma noduose ir kiekvienas nodas yra surištas su sekančiu nodu per pointerius (doubly linked listuose ir su prieš tai buvusiu).
Pagrindinis sąrašo sudedamasis yra : Pirmasis mazgas (Node‘as) (vadinamas HEAD).
internal class Node{ internal int data; internal Node next; public Node (int d){ data = d; next = null; } }
Kas bus jei kažkurį nodą ar Linked Listo elementą neves nei vienas pointeris?
Šis nodas skaitysis kaip “orphaned node” ir bus prarastas. Taip pat neteksime ir visos informacijos, į kurią vedė šis nodas.
Kaip turėtų būti vykdomas elemento B išėmimas Linked Liste A -> B -> C ?
Pirmiausiai Nodo A pointerį nukreipiam į C elementą. Šiuo momentų A ir B elementų pointeriai yra nurodyti į C elementą.
Po šio žingsnio galime sėkmingai pašalinti elementą B, o visa susijusi informacija nebus prarasta.
Kas yra Godus algoritmas?
Tai algoritmas, kuris yra kuriamas tam, kad būtų pasiektas optimalus tam tikros problemos sprendimas. Taikant godaus algoritmo metodą, sprendimai priimami iš nurodytos veiklos srities. Paprastai godūs algoritmai nepateikia optimizuotų sprendimų ir yra taikomi pirminiam problemos sprendimui.
Kokios galimos operacijos su masyvu?
- Traverse (pereiti) – pereiti per masyvą iš eilės.
- -Įprastas FOR ciklas per masyvo elementus.
- Insert (įdėti) – įdėti reikšmę į masyvą.
–Operacija remiasi naujo masyvo sukūrimu.
Sukuriant naują masyvą sukuriame jį
vienetu didesnį.
Tuomet dedame į masyvą elementus, kai
prieiname norimą vietą į kurią norime įdėti,
įdedame elementą, o po jo dedame
likusius elementus. - Delete (ištrinti) – ištrinti reikšmę iš masyvo.
–Panašiai kaip ir įdėjimo operacijoje
remiamės perėjimu per masyvą.
Einame per masyvą, randame norimą
trinti elementą, į jo vietą dedame toliau
už jį einančius elementą, ir taip iki
masyvo galo.
PSEUDOKODAS:
Start
Set J = K
Repeat steps 4 and 5 while J < K
Set LA[J] = LA [J + 1]
Set J = J + 1
Set N = N -1
Stop - Search (ieškoti) – vykdyti elemento paiešką masyve.
–Vykdomas FOR ciklas ir tikrinamas
elemento indekso numeris arba
elemento reikšmė
PSEUDOKODAS:
Start
Set J = 0
Repeat steps 4 and 5 while J < N
IF LA[J] is equal ITEM THEN GO TO STEP 6
Set J = J +1
PRINT J, ITEM
Stop - Update (atnaujinti) – atnaujinti masyvo elementą. (pakeisti jo reikšmę).
PSEUDOKODAS:
Start
Set LA[K-1] = ITEM
Stop
Kokias operacijas galime atlikti vienkrypčiame (Singly linked) sąraše?
- Insertion (pridėjimas)
–Norint pridėti duomenis į sąrašo pradžią
pabaigą arba tam tikrą vietą reikalingos
skirtingos operacijos.
Dažnai reikalingas ne tik naujo mazgo
kūrimas, bet ir nuorodų (NEXT) reikšmių
keitimas
PRIDĖJIMAS Į PRADŽIĄ: internal void InsertFront(SingleLinkedList singlyList, int new_data){ Node new_node = new Node(new_data); new_node.next = singlyList.head; singlyList.head = new_node; } PRIDĖJIMAS Į PABAIGĄ: internal Node GetLastNode(SingleLinkedList singlyList){ Node temp = singlyList.head; while (temp.next != null){ temp = temp.next; } return temp; } PRIDĖJIMAS Į TAM TIKRĄ VIETĄ: internal void InsertAfter(Node prev_node, int new_data){ if (prev_node == null){ Console.WriteLine("Error"); return; } Node new_node = new Node(new_data); new node.next = prev_node.next; prev_node.next = new_node; } \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ - Deletion (trynimas) internal void DeleteNodebykey(SingleLinkedList singlyList, int key){ Node temp = singlyList.head; Node prev = null; if (temp != null && temp.data == key){ singlyList.head = temp.next; return; } while (temp != null && temp.data != key){ prev = temp; temp = temp.next; } if (temp == null){ return; } prev.next = temp.next; } - Display (rodymas) - Search (paieška)