Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Tölvunarfræði 2 > Alls konar > Flashcards

Alls konar Flashcards

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)

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

Hver er munurinn á stafla og kös?

A

Stafla er stjórnað af fallaköllum en við berum ábyrgð á kösinni

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

Hvað á heima á stafla í forritskóða?

A

POD (plain old datatype), char, short, int, long, float, double, boolean

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

Hvað á heima í kös í forritskóða?

A

Hlutir og fylki

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

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

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

Tilvísanir á hluti taka hvað mörg bæti?

A

8 bytes

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

Gagnagrindur hafa hvaða Operations?

A

insert, remove, iterate, test if empty.

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

Hvað þýðir LIFO?

A

Last in first out

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

Er Stack LIFO Eða FIFO ?

A

LIFO, eins og diskar

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

Hvað þýðir FIFO?

A

First in first out

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

Queue LIFO eða FIFO?

A

FIFO, eins og röð

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

A stack with N items uses how many bytes?

A

~ 40 N bytes

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

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

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

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

Hvað er Iterable?

A

Hefur aðferð sem heitir Iterator, sem skilar Itorator hlut

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

hvað er Itarator hlutur?

A

Hefur has next aðferð og next aðferð

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

Hvernig getum við látið forritið mæla hversu langan tíma það tekur?

A

Með því að nota klasann Stopwatch

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

Hvað tekur langan tíma að hoppa á random stað í fylki’

A

Fastan tíma

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

Hvað kostar strengjasamsetning?

A

Strengjasamsetning kostar í réttum hlutföllum við lengd á streng

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

Er hægt að breyta strengjum í Java?

A

Nei bara hægt að búa til nýja strengi

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

Hvenær var helmingunarleit (binary search) fyrst birt?

A

1946

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

Fyrsta bug free binary search?

A

1962

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

Hvað tekur binary search langan tíma ?

A

Log N

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

Union-find notar ekki bara algorithma heldur?

A

Líka gagnagrind

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

Ef við ætlum að svara spurningunni er til leið á milli a og b, í neti t.d. þá þurfum við bara að vita?

A

Hvort a og b séu í sama samhengisþætti

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

Gallar við quick-find?

A

Union of dýrt, find er hægvirk aðgerð ef tréð er með mikla dýpt, viljum að tréið sé breytt.

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

Weighted quick-union keyrslutími?

A

lg N

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

Selection sort

A

Förum í gegnum nokkrar ítranir, leitum af minnsta staki, og skiptum við fyrsta stakið

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

Hvenær borgar sig að nota selection sort?

A

Lágmarka fjölda flutninga, ef það kostar að færa hlyti þeas

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

Hvað er vandamálið við selection sort?

A

Fjöldi samanburða er óháður inntakinu, alltaf n í 2 deilt með tveimur, þó að fylkið sé raðað nú þegar

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

Insertion sort

A

Berum saman fyrstu 2 og swap, svo næstu 2, svo næstu 2, berum alltaf saman við öll stökin á undan

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

Hvað er vandamálið við selection sort?

A

Fjöldi samanburða er óháður inntakinu, alltaf (N^2)/2, þó að fylkið sé raðað nú þegar

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

Tímaflækja insertion sort?

A

O(N^2)

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

Tímaflækja insertion sort?

A

O(N^2)

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

Hvað er betra við insertion sort vs selection sort?

A

Það fattar þegar það má hætta aðeins fyrr

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

Hvernig væri hægt að bæta insertion sort?

A

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

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

Leið til að gera shuffle?

A

Láta hvern einasta hlut fá einhverja slembi tölu, og röðum svo hlutum eftir slembitölunum

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

Ein leið til að gera shuffle?

A

Láta hvern einasta hlut fá einhverja slembi tölu, og röðum svo hlutum eftir slembitölunum

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

Betri umröðunarreiklniritið?

A

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

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

Selection og insertion taka bæði hvað langan tíma?

A

N^2

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

Tvö klassískt röðunarreiknirit?

A

Merge-sort og quick-sort

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

Merge-sort byggist á hvaða hugmynd?

A

Skipta vandamáli í tvennt, röðum hverjum helming endurkvæmt, merge-a báða helminga

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

Hver var með fyrstu hugmyndina um merge-sort?

A

John van Neumann

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

Tímaflækja merge-sort?

A

O(N log N)

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

Hvernig er gott að einfalda merges-sort?

A

Notum merge-sort, nema ef fylkið er orðið nógu lítið þá notum við eitthvað einfalara, eins og insertion sort

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

Hvað þurfum við marga samanburði fyrir hvaða röðunarreiknirit sem er ?

A

N log N

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

Stöðug röðun er?

A

Raðar í rétta röð, en þegar það er jafntefli þá varðveitar það innbyrgðis röðun

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

Hvaða reiknirit eru stöðug?

A

Insertion sort og merge sort

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

Er Selection sort er stöðug?

A

Selection sort er ekki stöðug

52
Q

Notar merge-sort auka minni?

A

Já

53
Q

Hægt er að gera quick-sort í einu falli?

A

Já

54
Q

Hugmyndin á bakvið quick-sort?

A

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
Q

Hver fann upp quick-sort?

A

Tony Hoare fann upp quick sort, á algol 60

56
Q

Hver gerði quick-sort vinsælt?

A

Bob Sedgewick

57
Q

Hvenær fáum við worst case í quick-sort?

A

Þegar stökin eru ekki shuffled, eru öll í röð

58
Q

Worst case fyrir quick-sort?

A

1/2 N^2

59
Q

quick-sort er In-place, hvað þýðir það?

A

Notar ekkert auka minni

60
Q

Er quick-sort stöðugt ?

A

Nei

61
Q

Hvernig útfærum við Dijkstra 3-way partitioning í quick-sort?

A

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
Q

Hvenær er 3-way quick sort betra?

A

Þegar það eru mörg gildi eins

63
Q

hvað er dual-pivot quick-sort?

A

Tvö skiptistök en ekki eitt, endum með þrjú fylki, köllum svo á quick-sort á öll þrjú fylkin

64
Q

Afhverju er betra að vera með fleiri en eitt skiptistak?

A

Hversu vel erum við að nýta skyndi minnið

65
Q

Priority queue data structure?

A

Binary heap

66
Q

í Priority queue eða forgangsbiðröð tökum við hvað út?

A

Tökum út stærsta gildið (eða minnsta)

67
Q

tvíundartré, binary tree

A

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
Q

complete tree

A

perfectly balanced, vinstri jafnað

69
Q

hæðin á tré með N nodes?

A

lg N

70
Q

Binary heap

A

Fylkjaframsetning á binary tré, hugsa um tré, vinna með það sem fylki

71
Q

Til að finna foreldri hnúts?

A

Parent of node k is at k/2

72
Q

hvar eru börn hnúts k?

A

í 2k og 2k+1

73
Q

Til að bæta við hnút?

A

Setja út á enda (aftast í fylkið) og gera svo swim up

74
Q

Remove maximum?

A

Skipta á rót og enda staki, Sink down

75
Q

Immutable data type (óbreytanlegt gagnatag)

A

Can’t change the data type value once created

76
Q

Ef það er ekki hægt að erfa frá klasa þá skrifum við

A

final (public final class)

77
Q

Dæmi um immuateble hluti

A

String, Integer, Double, Color, Vector, Transaction, Point2D

78
Q

Dæmi um mutable hluti

A

StringBuilder, Stack, Counter, Java array

79
Q

Heapsort er röðunaraðferð, hver er hugmyndin á bakvið heapsort?

A

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
Q

Heapsort er með svipaða hugmynd og ?

A

Selection sort, nema betri útfærsla

81
Q

symbol tables/ uppflettitöflur

A

erum með lykil og erum með gildi (Key og value), erum með insert og search

82
Q

Symbol tables eru líka kallaðar

A

maps, dictionaries, associative arrays

83
Q

Í Symbol tables hvað mega key og value vera?

A

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
Q

hvaða klasar eru með equals() í java?

A

Allir klasar erfa aðferðina equals()

85
Q

Binary search tree, BST, tvíleitartré

A

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
Q

Hvernig er BST líkt helmingunarleit?

A

Rótin er eins og miðjan í helmingunarleit, svo förum við alltaf til vinstri eða hægri

87
Q

Til að finna minnsta gildi í BST

A

Fara eins langt til vinstri og ég get

88
Q

hvað er rank()

A

Númer hvað er lykillinn í röðinni

89
Q

Erfitt að gera delete á BST, hvað er lazy approach á delete?

A

Tombstone, skilið lykilinn eftir en value er null

90
Q

Hvernig er betra að delete-a í BST

A

Betra að taka hnútinn út og laga tréð

91
Q

2-3 tré

A

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
Q

Rauð svört BST tré

A

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
Q

Hakkaföll

A

Saving items in a key-indexed table, hver hlutur fær tölu, talan notuð sem tilvísun

94
Q

Árekstur í hakkatöflu

A

Þegar tveir ólíkir lyklar fá sama hash

95
Q

Linear-proping eða open addressing

A

Í staðin fyrir að vera með fylki af tengdum listum, erum við með fylki af lyklum og samsvarandi fylki af gildum,

96
Q

Árekstur í Linear-proping í innsetningu?

A

Finna næsta slot og setja þangað

97
Q

Hvernig deletar maður úr linear-proping hakkatöflum ?

A

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
Q

one-way hash functions?

A

Meira notað í dulkóðun, aldrei árekstrar en mjög hægvirk

99
Q

Vegur er þegar

A

það er leið í netinu frá einum hnút til annars

100
Q

Gráða fyrir hnúta

A

HVersu margir leggir tengjast honum,

101
Q

Samhengisþáttur

A

Þegar það er hægt að fara frá hnúti til hnúts, í neti þá eru þeir í sama samhengisþætti

102
Q

Euler hringur

A

Fer í gegnum netið og notar hvern einasta legg nákvæmlega einu sinni

103
Q

Hamilton hringur

A

Fer í gegnum hnút nákvæmlega einu sinni

104
Q

depth first search eða DFS samsvarar

A

Völundarhúsi

105
Q

Ein hagnýting á DFS

A

Flood fill, eins og í myndvinnslu

106
Q

BFS - breadth first search

A

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
Q

topological search / grannfræðileg röðun

A

hraða hnútum í röð, ef við myndum teikna fra´botnu og upp þá myndu allar örvarnar snúa upp, lausnin er dfs

108
Q

DAG - directed acyclic graph

A

ekki til neinn stefndur hringur í netinu

109
Q

ef það er ekki til stefndur hringur, s.s. dag

A

þá er til grannfræðileg röðun

110
Q

ef það er stefndur hringur

A

þá er grannfræðileg röðun ekki hægt

111
Q

Spannandi tré

A

hlutnet sem er saman hangandi með enga hringi og alla hnútana

112
Q

Minnsta spanndi tré

A

setjum vigt á leggina, og finnum spannandi tréð með minnstu mögulega vigt

113
Q

Skurður í neti

A

Skipting á hnútum í tvö mengi

114
Q

crossing edge

A

leggir sem fara á milli hnúta í ólíkum mengjum

115
Q

sá sem er með minnstu vigtina í crossing edge er þá líka?

A

í minnsta spannandi tré

116
Q

tré sem hefur V hnúta er með hvað marga leggi í minnstu spannandi trjám

A

V-1

117
Q

Hver er hugmyndin bakvið Kruskal reikniritið?

A

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
Q

Prim’s reikniritið

A

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
Q

Getum fundið lengstu leið í gegnum netið ef við erum með

A

DAG

120
Q

Hvernig finnum við lengstu leið

A

Setjum allar vigtirnar sem neikvæðar, skiptum um formerki á öllu og finnum svo styðstu leið

121
Q

Pattern matching

A

Finna strengi í texta

122
Q

Pattern matching

A

Finna strengi í texta, ákveðið mengi af strengjum í texta

123
Q

Stöðuvelar

A

Mengi af ástöndum, net sem segir hvernig þú hoppar úr einu ástandi yfir í annað

124
Q

Stöðuvelar og reglulegar segðir

A

Fyrir hverja stöðuvel DFA er til RE regluleg segð sem lýsir sama mengi af strengjum og öfugt

125
Q

NFA non determenistic finate state automata

A

brigðgengar stöðuvelar, hraðvirkara

Tölvunarfræði 2 (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions