Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Tölvunarfræði 2 > Fyrirlestraræfingar > Flashcards

Fyrirlestraræfingar Flashcards

(96 cards)

Start Studying
1
Q

Hvernig finnur maður stærð á fylki a í Java?

A

a.length

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

Hvernig breytir maður stærð á fylki í Java?

A

Ekki hægt

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

Hvar eru fylki geymd í minni Java?

A

Á kösinni (heap)

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

Afhverju er Node klasinn merktur sem private inni í LinkedStackOfStrings klasanum?

A

Viljum ekki leyfa notanda að hafa aðgang, má ekki vita hvernig hann er útfærður

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

Hvað gerist ef kallað er á pop() aðferðina á tómum stafla í

FixedCapacityStackOfStrings klasanum?

A

N verður neikvætt og við fáum ólöglega tilvísun í fylkið

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

Afhverju er ekki gott að stækka fylkið um eitt stak í stack útfærslu

A

Minnisnotkun verður ca N^2 → og kostnaðarsamt

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

Hvað heitir klasinn sem geymir heiltölur?

A

Integer

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

Afhverju verður Iterator að vera hluti af stack útfærslu?

A

Því iterator klasinn verður að hafa aðgang að private breytum

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

Er postscript forritunarmál?

A

Já

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

Hvert er gildið á postfix segðinni 1 2 + 3 4 * *

A

1+2 = 3, 34 = 12, 312 = 36

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

Hve langan tíma (sem fall af N) tekur að leysa three-sum með útfærslunni sem er á glærunum?

A

N^3

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

Afhverju á ekki að mæla println með stopwatch?

A

Getur tekið meiri tíma að prenta á skjá heldur en að reikna út

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

Hver er veldisvísirinn á N ef tvöföldunargreining hefur hlutfallið 16

A

4

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

Hvaða heiltöluaðgerðir eru hægvirkastar

A

Modulus og deiling

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

Hve lengi tekur að leggja saman N stafi ‘a’ í streng s í for lykkju?

A

N^2

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

Hver er munur á “~” og “O” rithætti?

A

~ tekur tillit til stuðuls á þeim þætti sem vex hraðast á meðan O rithátthur felur hann

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

Hve lengi tekur helmingunarleit að finna stak í N staka lista í versta tilfelli?

A

O(log(N))

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

Hve lengi tekur helmingunarleit að finna stak í N staka lista í besta tilfelli

A

O(1)

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

Hver er munurinn á spurningunni “er til leið á milli p og q” og “hver er leiðin á milli p og q(ef hún er til)”

A

Fyrri spurningu er hægt að svara með já eða nei og hægt að svara henni án þess að finna leið, ein seinni spurningunni þarf að segja leiðina

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

Hvaða gagnagrind er notuð fyrir quick find

A

Tré (eða skógur)

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

Hvaða hnútur er notaður sem fulltrúi fyrir samhengisþátt

A

Rótin á hverju tré

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

Hve lengi tekur Find aðgerðin með quick union aðferðinni?

A

O(N)

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

Hve lengi tekur Find aðgerðin með weighted-quick union aðferðinni

A

O(log(N))

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

Hve lengi tekur Find aðgerðin með weighted-quick union aðferðinni í besta mögulega tilfelli

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Hve langan tíma tekur að leysa percolation vandamálið á NxN borði
O(N^2)
26
Hvaða aðferð notar Java til að leyfa endurnýtingu á röðunarkóða
Comparable skilin
27
Hver er keyrslutíminn á Selection Sort
O(N^2)
28
Hver er keyrslutími á insertion sort í besta falli
O(N)
29
Hver er keyrslutími á insertion sort þegar fylkið er í öfugri röð
O(N^2)
30
Hver er keyrslutíminn fyrir merge aðgerðina ef listarnir eru af lengd n
O(N)
31
Hver er keyrslutíminn á merge sort
O(Nlog(N))
32
Hversu mikið auka minni notar merge sort ef inntakið er af lengd n
O(N)
33
Hvaða röðunaraðferð er ekki stöðug
Selection sort
34
Hver er keyrslutíminn fyrir partion aðgerðina ef listarnir eru af lengd n
O(N)
35
Hver er keyrslutíminn á quick sort þegar inntakið er slembið
O(Nlog(N))
36
Hver er versti keyrslutími á quicksort
O(N^2)
37
Hver er keyrslutíminn á select að meðaltali
O(N)
38
Hver er keyrslutíminn á insert í forgangsbiðröð ef notuð eru óröðuð fylki
O(1)
39
Hver er keyrslutíminn á insert í forgangsbiðröð ef notuð er kös
O(log(N)
40
Er heapsort stöðug
Nei
41
Hver er versti keyrslutíminn á heap sort
O(Nlog(N))
42
Hvað tekur langan tíma að búa til löglega kös úr N stökum
O(N)
43
Hvaða 3 röðunaraðferðir notar introsort?
Quicksort, heapsort og insertion sort
44
Hver er keyrslutíminn fyrir insert aðgerina í raðaðan lista af lengd n
O(N)
45
Nefnið þrjú dæmi um notkun á uppflettitöflu
Vefsíðuleit, orðabók, file system
46
Afhverju þurfa lyklar að vera óbreytanlegir (immutable)
Staðsetning lykla í töflu er háð innihaldinu, ef lyklar eru breytanlegir þá er hætta að þeir finnist ekki aftur
47
Hvaða aðferð þurfa lyklar að hafa til að vera notaðir í uppflettitöflu
compareTo eða hashCode
48
Hver er versti mögulegi keyrslutími fyrir leit í BST
O(N)
49
Hver er meðaltals tími fyrir leit í BST
O(log(N))
50
Hvaða röðunaraðferð líkist BST
Quicksort
51
Hvar er minnsta gildi að finna í BST
Lengst til vinstri
52
Hver er versti mögulegi keyrslutími fyrir leit í 2-3 tré
O(log(N))
53
Hver er versta mögulega dýpt á llrbt (Left-leaning Red-Black trees)
O(log(N))
54
Hvar er minnsta gildi að finna í llrbt
Lengst til vinstri
55
Hver eru tengslin á milli 2-3 trjáa og vinstri hallandi rauð-svartra trjáa (llbrt)
2-hnútar eru hnútar, 3-hnútar eru 3 hnúta tré með rauðan legg til vinstri
56
Hver er versta dýpt á llrbt tré með N hnúta
O(log(N))
57
Hver er fjöldi aðgerða sem þarf að framkvæma fyrir vinstri snúning í BST tré með n hnútum
O(1)
58
Hve stór er in síða(page) á disk
4k
59
Hver er sóknartími til að sækja bæti úr minni tölvu (RAM)
100 ns
60
Hvernig þurfa equals og hashCode aðferðirnar að passa saman
hashCode þarf að skila sama gildi fyrir tvo hluti ef þau eru equals
61
Hver er tíminn sem það tekur að reikna út hashCode fyrir String hlut af lengd N
O(N)
62
Hver er meðaltalstími fyrir leit í hakkatöflu með tengdum lista
O(1)
63
Hver er versti mögulegi keyrslutími fyrir leit í hakkatöflu með tengdum lista
O(N)
64
Hvert er versti mögulegi keyrslutími fyrir leit í hakkatöflu með open addressing?
O(N)
65
Hver er meðaltals keyrslutími fyrir leit í hakkatöflu með open addressing?
O(1)
66
Hvernig er hægt að redda eyðingu á stökum í hakkatöflu með fylki (linear probing)?
Með því að að setja inn lykil fyrir eyðingu (e. tombstone) eða með því
67
Af hverju er það slæmt ef hægt er að búa til mörg gildi sem fá sama hakkagildi?
Opnar á algoriþmískar árásir á gagnagrindur
68
Hver er ókostur við að geyma netið sem tvívítt 0-1 fylki
Minnisnotkun O(N^2)
69
Hver er ókostur við að geyma netið sem mengi af leggjum
Engin auðveld leið til að fletta upp þeim leggjum sem tengjast ákveðnum hnúti
70
Hvaða gagnagrind notar BFS við leit
Biðröð (FIFO, queue)
71
Hvaða gagnagrind notar DFS við leit
Stafla eða fallaköll
72
Hve langan tíma tekur BFS að skoða allt netið
O(E+V)
73
Hvaða reiknirit er hægt að nota til að finna samhengisþætti neta
Union find, BFS, DFS
74
Hvaða reiknirit er hægt að nota til að finna hvort net hafi hring
DFS og BFS
75
Hvaða gagnagrind notar BFS við leit í stefndu neti
Biðröð (FIFO, queue)
76
Hvaða grunnleitaraðferð notar grannfræðileg röðun (topological sort)
DFS
77
Hvaða skilyrði eru fyrir því að hægt sé að finna grannfræðilega röðun í stefndu neti
Netið þarf að vera laust við stefnda hringi, þarf að vera DAG
78
Hvaða leitarreiknirit gefur stystu leið í stefndum netum
BSF
79
Hvað er spannandi tré (spanning tree)?
Hlutnet sem er samanhangandi, án hringja (tré) og inniheldur alla hnúta netsins
80
Hvað er skurður (e. cut)
Skipting á hnútum netsins í tvö hlutmengi.
81
Hvernig velur reiknirit Kruskals næsta legg til að bæta við MST?
Minnsta óskoðaða legg sem myndar ekki hring í því MST s
82
Hvaða gagnagrind nota reiknirit Prims til að halda utan um leggi sem gætu bæst við MST?
Forgangsbiðröð með vísi (e. Indexed Priority Queue)
83
Hvernig er stysta leið reiknuð þegar allir leggir eru jafnlangir
BFS eða Dijkstra
84
Hvaða gagnagrind notar Dijkstra reikniritið til að halda utan um fjarlægðir
Forgangsbiðröð með vísi
85
Hver er keyrslutíminn á reikniriti Djikstra með V hnúta og E leggi
E log(V)
86
Í hvaða röð eru hnútar skoðaðir í reikniritinu fyrir stystu leið í DAG
grannfræðilegri röð (topological order)
87
Hvernig er lengsta leið fundin í DAG?
stysta leið notuð með neikvæðar vigtir
88
Hver er tímakeyrslan á stystu leið í DAG?
E+V
89
Skrifið reglulega segð sem passar við strengi af 0 og 1 sem innihalda amk tvö 0
*01*0.*
90
Afhverju er ekki praktískt að breyta reglulegri segð í löggenga stöðuvél(DFA)
Fjöldi ástanda getur verið veldisfall af lengd segðarinnar
91
Hvaða netareiknirit er notað til að finna út hvort brigðgeng stöðuvél (NFA) samþykki strengi
DFS, BFS eða reachability
92
Hver er tímaflækjan á að athuga hvort brigðgeng stöðuvél samþykki streng sem fall af lengd strengs N
O(N)
93
Hver er munurinn a löggengri stöðuvél (DFA) og brigðgengri stöðuvél (NFA)
Brigðgeng stöðuvél hefur marga leggi með sömu tákn úr sama ástandi
94
Ef regluleg segð hefur M tákn hversu mörg ástönd mun brigðgenga stöðuvélin hafa
M+1
95
Hvaða tákn í reglulegum segðum frá svartar örvar sem benda frá sér
Stafir og .
96
Fyrir reglulegu segðina A* afhverju kemur bæði rauð og svört ör úr ástandinu sem táknar A
Rauða örin samsvarar að passa 0 sinnum við A

Tölvunarfræði 2 (2 decks)

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