Alls konar Flashcards
(125 cards)
1
Q
Minnið í tölvunni er línulegt, hvaða tvö minnissvæði þurfum við að muna eftir?
A
Stafli (stack) og kös (heap)
2
Q
Hver er munurinn á stafla og kös?
A
Stafla er stjórnað af fallaköllum en við berum ábyrgð á kösinni
3
Q
Hvað á heima á stafla í forritskóða?
A
POD (plain old datatype), char, short, int, long, float, double, boolean
4
Q
Hvað á heima í kös í forritskóða?
A
Hlutir og fylki
5
Q
Fylki og hlutir geta lifað lengur en föllin sem búa þau til, vegna þess að?
A
Minnissvæði fyrir fylki og hluti er tekið er tekið frá í kös (heap) í Java en ekki á stafla (stack).
6
Q
Hvenær skilum við minninu til baka?
A
Ruslasafnari finnur út úr því fyrir okkur hvenær er óhætt að skila minninu til baka.
7
Q
Tilvísanir á hluti taka hvað mörg bæti?
A
8 bytes
8
Q
Gagnagrindur hafa hvaða Operations?
A
insert, remove, iterate, test if empty.
9
Q
Hvað þýðir LIFO?
A
Last in first out
10
Q
Er Stack LIFO Eða FIFO ?
A
LIFO, eins og diskar
11
Q
Hvað þýðir FIFO?
A
First in first out
12
Q
Queue LIFO eða FIFO?
A
FIFO, eins og röð
13
Q
A stack with N items uses how many bytes?
A
~ 40 N bytes
14
Q
Ef við ætlum að setja int á stafla þá verðum við að ?
A
Nota Integer sem er wrapper fyrur int, vegna þess að við verðum að setja eitthvað sem er hlutur og öll POD hafa wrapper object type
15
Q
hvort er betra að fá villu á þýðingartíma eða keyrslutíma?
A
Mun betra að fá villu á þýðingartíma, ekki á keyrslutíma
16
Q
Ef við ætlum að setja int á stafla þá verðum við að ?
A
Nota Integer sem er wrapper fyrir int, vegna þess að við verðum að setja eitthvað sem er hlutur og öll POD hafa wrapper object type
17
Q
Hvað er Iterable?
A
Hefur aðferð sem heitir Iterator, sem skilar Itorator hlut
18
Q
hvað er Itarator hlutur?
A
Hefur has next aðferð og next aðferð
19
Q
Hvernig getum við látið forritið mæla hversu langan tíma það tekur?
A
Með því að nota klasann Stopwatch
20
Q
Hvað tekur langan tíma að hoppa á random stað í fylki’
A
Fastan tíma
21
Q
Hvað kostar strengjasamsetning?
A
Strengjasamsetning kostar í réttum hlutföllum við lengd á streng
22
Q
Er hægt að breyta strengjum í Java?
A
Nei bara hægt að búa til nýja strengi
23
Q
Hvenær var helmingunarleit (binary search) fyrst birt?
A
1946
24
Q
Fyrsta bug free binary search?
A
1962
25
Hvað tekur binary search langan tíma ?
Log N
26
Union-find notar ekki bara algorithma heldur?
Líka gagnagrind
27
Ef við ætlum að svara spurningunni er til leið á milli a og b, í neti t.d. þá þurfum við bara að vita?
Hvort a og b séu í sama samhengisþætti
28
Gallar við quick-find?
Union of dýrt, find er hægvirk aðgerð ef tréð er með mikla dýpt, viljum að tréið sé breytt.
29
Weighted quick-union keyrslutími?
lg N
30
Selection sort
Förum í gegnum nokkrar ítranir, leitum af minnsta staki, og skiptum við fyrsta stakið
31
Hvenær borgar sig að nota selection sort?
Lágmarka fjölda flutninga, ef það kostar að færa hlyti þeas
32
Hvað er vandamálið við selection sort?
Fjöldi samanburða er óháður inntakinu, alltaf n í 2 deilt með tveimur, þó að fylkið sé raðað nú þegar
33
Insertion sort
Berum saman fyrstu 2 og swap, svo næstu 2, svo næstu 2, berum alltaf saman við öll stökin á undan
34
Hvað er vandamálið við selection sort?
Fjöldi samanburða er óháður inntakinu, alltaf (N^2)/2, þó að fylkið sé raðað nú þegar
35
Tímaflækja insertion sort?
O(N^2)
36
Tímaflækja insertion sort?
O(N^2)
37
Hvað er betra við insertion sort vs selection sort?
Það fattar þegar það má hætta aðeins fyrr
38
Hvernig væri hægt að bæta insertion sort?
Nota binary search (helmingunarleit), til að finna rétta staðinn fyrir key, í staðinn fyrir að swapa við hvert stak þangað til rétti staður finnst
39
Leið til að gera shuffle?
Láta hvern einasta hlut fá einhverja slembi tölu, og röðum svo hlutum eftir slembitölunum
40
Ein leið til að gera shuffle?
Láta hvern einasta hlut fá einhverja slembi tölu, og röðum svo hlutum eftir slembitölunum
41
Betri umröðunarreiklniritið?
Knuth, Förum frá i upp í 0, veljum heiltölu r frá 0-i af handahófi, skiptum a[i] og a[r], keyrir á línulegum tíma
42
Selection og insertion taka bæði hvað langan tíma?
N^2
43
Tvö klassískt röðunarreiknirit?
Merge-sort og quick-sort
44
Merge-sort byggist á hvaða hugmynd?
Skipta vandamáli í tvennt, röðum hverjum helming endurkvæmt, merge-a báða helminga
45
Hver var með fyrstu hugmyndina um merge-sort?
John van Neumann
46
Tímaflækja merge-sort?
O(N log N)
47
Hvernig er gott að einfalda merges-sort?
Notum merge-sort, nema ef fylkið er orðið nógu lítið þá notum við eitthvað einfalara, eins og insertion sort
48
Hvað þurfum við marga samanburði fyrir hvaða röðunarreiknirit sem er ?
N log N
49
Stöðug röðun er?
Raðar í rétta röð, en þegar það er jafntefli þá varðveitar það innbyrgðis röðun
50
Hvaða reiknirit eru stöðug?
Insertion sort og merge sort
51
Er Selection sort er stöðug?
Selection sort er ekki stöðug
52
Notar merge-sort auka minni?
Já
53
Hægt er að gera quick-sort í einu falli?
Já
54
Hugmyndin á bakvið quick-sort?
Byrjum á shuffle, veljum stak k, fremsta stakið, segjum svo allir sem eru minni en k fara vinstra megin, og stærri en k hægra megin. Röðum svo endurkvæmt vinstri og hægri.
55
Hver fann upp quick-sort?
Tony Hoare fann upp quick sort, á algol 60
56
Hver gerði quick-sort vinsælt?
Bob Sedgewick
57
Hvenær fáum við worst case í quick-sort?
Þegar stökin eru ekki shuffled, eru öll í röð
58
Worst case fyrir quick-sort?
1/2 N^2
59
quick-sort er In-place, hvað þýðir það?
Notar ekkert auka minni
60
Er quick-sort stöðugt ?
Nei
61
Hvernig útfærum við Dijkstra 3-way partitioning í quick-sort?
Veljum skipti stak, og látum svo allt á milli lt og gt vera jafnt skiptistakinu, svo minni vinstra megin og stærri hægra megin
62
Hvenær er 3-way quick sort betra?
Þegar það eru mörg gildi eins
63
hvað er dual-pivot quick-sort?
Tvö skiptistök en ekki eitt, endum með þrjú fylki, köllum svo á quick-sort á öll þrjú fylkin
64
Afhverju er betra að vera með fleiri en eitt skiptistak?
Hversu vel erum við að nýta skyndi minnið
65
Priority queue data structure?
Binary heap
66
í Priority queue eða forgangsbiðröð tökum við hvað út?
Tökum út stærsta gildið (eða minnsta)
67
tvíundartré, binary tree
gagnagrind, efstri hnútur kallað rót, tilvísin á vinstra barn og tilvísun á hægra barn, þeir sem er ekki með tilvísun á barn eru kölluð lauf
68
complete tree
perfectly balanced, vinstri jafnað
69
hæðin á tré með N nodes?
lg N
70
Binary heap
Fylkjaframsetning á binary tré, hugsa um tré, vinna með það sem fylki
71
Til að finna foreldri hnúts?
Parent of node k is at k/2
72
hvar eru börn hnúts k?
í 2k og 2k+1
73
Til að bæta við hnút?
Setja út á enda (aftast í fylkið) og gera svo swim up
74
Remove maximum?
Skipta á rót og enda staki, Sink down
75
Immutable data type (óbreytanlegt gagnatag)
Can't change the data type value once created
76
Ef það er ekki hægt að erfa frá klasa þá skrifum við
final (public final class)
77
Dæmi um immuateble hluti
String, Integer, Double, Color, Vector, Transaction, Point2D
78
Dæmi um mutable hluti
StringBuilder, Stack, Counter, Java array
79
Heapsort er röðunaraðferð, hver er hugmyndin á bakvið heapsort?
Umröðum fylkinu svo þau myndi heap, skipti svo á stærsta stakinu (rótinni) og síðasta stakinu, geri svo sink til að fá nýju rótina á réttan stað, geri svo del max og þá er það sem ég gerði del, stærsta stakið
80
Heapsort er með svipaða hugmynd og ?
Selection sort, nema betri útfærsla
81
symbol tables/ uppflettitöflur
erum með lykil og erum með gildi (Key og value), erum með insert og search
82
Symbol tables eru líka kallaðar
maps, dictionaries, associative arrays
83
Í Symbol tables hvað mega key og value vera?
Value má vera hvað sem er, en key er með skorður : key er Comperable eða nota equals, og hashcode. Notum immuatable lykla.
84
hvaða klasar eru með equals() í java?
Allir klasar erfa aðferðina equals()
85
Binary search tree, BST, tvíleitartré
Flott gagnagrind, búin til fyrir uppflettitöflur, tvíundatré, rót og hægra barn og vinsta bar, null links þegar það er ekkert
86
Hvernig er BST líkt helmingunarleit?
Rótin er eins og miðjan í helmingunarleit, svo förum við alltaf til vinstri eða hægri
87
Til að finna minnsta gildi í BST
Fara eins langt til vinstri og ég get
88
hvað er rank()
Númer hvað er lykillinn í röðinni
89
Erfitt að gera delete á BST, hvað er lazy approach á delete?
Tombstone, skilið lykilinn eftir en value er null
90
Hvernig er betra að delete-a í BST
Betra að taka hnútinn út og laga tréð
91
2-3 tré
getum verið með þríhnúta (með tvo lykla, vinstra barn, hægra barn og miðjubarn), öll laufin jafn langt frá rót
92
Rauð svört BST tré
rauður leggur þýðir að þetta sé þríhnútur, rauðir leggir hanga vinstra meginn, mega ekki vera tveir rauðir leggir í röð
93
Hakkaföll
Saving items in a key-indexed table, hver hlutur fær tölu, talan notuð sem tilvísun
94
Árekstur í hakkatöflu
Þegar tveir ólíkir lyklar fá sama hash
95
Linear-proping eða open addressing
Í staðin fyrir að vera með fylki af tengdum listum, erum við með fylki af lyklum og samsvarandi fylki af gildum,
96
Árekstur í Linear-proping í innsetningu?
Finna næsta slot og setja þangað
97
Hvernig deletar maður úr linear-proping hakkatöflum ?
Með því að nota tombstone, því tómt pláss hefur merkingu og getur ruglað okkur við að leita, eða taka alla lykla út sem eru á eftir þeim sem við delete-um og setja þá aftur inn
98
one-way hash functions?
Meira notað í dulkóðun, aldrei árekstrar en mjög hægvirk
99
Vegur er þegar
það er leið í netinu frá einum hnút til annars
100
Gráða fyrir hnúta
HVersu margir leggir tengjast honum,
101
Samhengisþáttur
Þegar það er hægt að fara frá hnúti til hnúts, í neti þá eru þeir í sama samhengisþætti
102
Euler hringur
Fer í gegnum netið og notar hvern einasta legg nákvæmlega einu sinni
103
Hamilton hringur
Fer í gegnum hnút nákvæmlega einu sinni
104
depth first search eða DFS samsvarar
Völundarhúsi
105
Ein hagnýting á DFS
Flood fill, eins og í myndvinnslu
106
BFS - breadth first search
Breiddarleit, heimsækjum alla nágranna fyrst hnúts fyrst, fyrst heimsækjum við hnút í fjarlægð 0, svo fjarlægð 1, svo fjarlægð 2 og svo fram vegis
107
topological search / grannfræðileg röðun
hraða hnútum í röð, ef við myndum teikna fra´botnu og upp þá myndu allar örvarnar snúa upp, lausnin er dfs
108
DAG - directed acyclic graph
ekki til neinn stefndur hringur í netinu
109
ef það er ekki til stefndur hringur, s.s. dag
þá er til grannfræðileg röðun
110
ef það er stefndur hringur
þá er grannfræðileg röðun ekki hægt
111
Spannandi tré
hlutnet sem er saman hangandi með enga hringi og alla hnútana
112
Minnsta spanndi tré
setjum vigt á leggina, og finnum spannandi tréð með minnstu mögulega vigt
113
Skurður í neti
Skipting á hnútum í tvö mengi
114
crossing edge
leggir sem fara á milli hnúta í ólíkum mengjum
115
sá sem er með minnstu vigtina í crossing edge er þá líka?
í minnsta spannandi tré
116
tré sem hefur V hnúta er með hvað marga leggi í minnstu spannandi trjám
V-1
117
Hver er hugmyndin bakvið Kruskal reikniritið?
Röðum leggjunum í rétta röð, og skoðum svo hvort ef við bætum leggnum við það myndist nokkuð hringur, ef það myndast ekki hringur þá bætum við leggnum við
118
Prim's reikniritið
Byrjum á einum hnút, og finnum minnsta legg sem tengist honum, næst allir leggir sem tengjast öðrum hvorum þeirra og veljum alltaf minnsta legginn
119
Getum fundið lengstu leið í gegnum netið ef við erum með
DAG
120
Hvernig finnum við lengstu leið
Setjum allar vigtirnar sem neikvæðar, skiptum um formerki á öllu og finnum svo styðstu leið
121
Pattern matching
Finna strengi í texta
122
Pattern matching
Finna strengi í texta, ákveðið mengi af strengjum í texta
123
Stöðuvelar
Mengi af ástöndum, net sem segir hvernig þú hoppar úr einu ástandi yfir í annað
124
Stöðuvelar og reglulegar segðir
Fyrir hverja stöðuvel DFA er til RE regluleg segð sem lýsir sama mengi af strengjum og öfugt
125
NFA non determenistic finate state automata
brigðgengar stöðuvelar, hraðvirkara
