Data Structures and Algorithms Flashcards

1
Q

Kas yra duomenų struktūra?

A

Duomenų organizavimo, valdymo ir saugojimo formatas skirtas efektyviai saugoti, pasiekti ir modifikuoti duomenis

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Kas yra algoritmas? Kokios yra jų kategorijos?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Kuo skiriasi duomenų struktūra nuo algoritmo?

A

Duomenų struktūra skirta duomenims saugoti, o algoritmas - tai veiksmų seka, kurią kompiuteris vykdo rezultatui gauti

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Kas yra BigO asimptotinė analizė ir kam jis skirtas?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Koks bus šio algoritmo BigO?

public int addUpTo(n){
return n * (n + 1) / 2;
}

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Koks bus šio algoritmo BigO?

public int  addUpTo(n){
  var total = 0;
  for (int i=0;  i<= n; i++){
  total += i;
  }
  return total;
A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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");
}
A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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);
      }
   }
}
A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Kas yra Node (jungtis)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Kas yra Linked List?

A

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;
  }
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Kas bus jei kažkurį nodą ar Linked Listo elementą neves nei vienas pointeris?

A

Šis nodas skaitysis kaip “orphaned node” ir bus prarastas. Taip pat neteksime ir visos informacijos, į kurią vedė šis nodas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Kaip turėtų būti vykdomas elemento B išėmimas Linked Liste A -> B -> C ?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Kas yra Godus algoritmas?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Kokios galimos operacijos su masyvu?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Kokias operacijas galime atlikti vienkrypčiame (Singly linked) sąraše?

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly