Brainscape's Knowledge GenomeTM

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


See full index

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

Fyrirlestraræfingar Flashcards

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
Q

Hve langan tíma tekur að leysa percolation vandamálið á NxN borði

A

O(N^2)

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

Hvaða aðferð notar Java til að leyfa endurnýtingu á röðunarkóða

A

Comparable skilin

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

Hver er keyrslutíminn á Selection Sort

A

O(N^2)

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

Hver er keyrslutími á insertion sort í besta falli

A

O(N)

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

Hver er keyrslutími á insertion sort þegar fylkið er í öfugri röð

A

O(N^2)

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

Hver er keyrslutíminn fyrir merge aðgerðina ef listarnir eru af lengd n

A

O(N)

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

Hver er keyrslutíminn á merge sort

A

O(Nlog(N))

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

Hversu mikið auka minni notar merge sort ef inntakið er af lengd n

A

O(N)

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

Hvaða röðunaraðferð er ekki stöðug

A

Selection sort

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

Hver er keyrslutíminn fyrir partion aðgerðina ef listarnir eru af lengd n

A

O(N)

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

Hver er keyrslutíminn á quick sort þegar inntakið er slembið

A

O(Nlog(N))

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

Hver er versti keyrslutími á quicksort

A

O(N^2)

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

Hver er keyrslutíminn á select að meðaltali

A

O(N)

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

Hver er keyrslutíminn á insert í forgangsbiðröð ef notuð eru óröðuð fylki

A

O(1)

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

Hver er keyrslutíminn á insert í forgangsbiðröð ef notuð er kös

A

O(log(N)

40
Q

Er heapsort stöðug

A

Nei

41
Q

Hver er versti keyrslutíminn á heap sort

A

O(Nlog(N))

42
Q

Hvað tekur langan tíma að búa til löglega kös úr N stökum

A

O(N)

43
Q

Hvaða 3 röðunaraðferðir notar introsort?

A

Quicksort, heapsort og insertion sort

44
Q

Hver er keyrslutíminn fyrir insert aðgerina í raðaðan lista af lengd n

A

O(N)

45
Q

Nefnið þrjú dæmi um notkun á uppflettitöflu

A

Vefsíðuleit, orðabók, file system

46
Q

Afhverju þurfa lyklar að vera óbreytanlegir (immutable)

A

Staðsetning lykla í töflu er háð innihaldinu, ef lyklar eru breytanlegir þá er hætta að þeir finnist ekki aftur

47
Q

Hvaða aðferð þurfa lyklar að hafa til að vera notaðir í uppflettitöflu

A

compareTo eða hashCode

48
Q

Hver er versti mögulegi keyrslutími fyrir leit í BST

A

O(N)

49
Q

Hver er meðaltals tími fyrir leit í BST

A

O(log(N))

50
Q

Hvaða röðunaraðferð líkist BST

A

Quicksort

51
Q

Hvar er minnsta gildi að finna í BST

A

Lengst til vinstri

52
Q

Hver er versti mögulegi keyrslutími fyrir leit í 2-3 tré

A

O(log(N))

53
Q

Hver er versta mögulega dýpt á llrbt (Left-leaning Red-Black trees)

A

O(log(N))

54
Q

Hvar er minnsta gildi að finna í llrbt

A

Lengst til vinstri

55
Q

Hver eru tengslin á milli 2-3 trjáa og vinstri hallandi rauð-svartra trjáa (llbrt)

A

2-hnútar eru hnútar, 3-hnútar eru 3 hnúta tré með rauðan legg til vinstri

56
Q

Hver er versta dýpt á llrbt tré með N hnúta

A

O(log(N))

57
Q

Hver er fjöldi aðgerða sem þarf að framkvæma fyrir vinstri snúning í BST tré með n hnútum

A

O(1)

58
Q

Hve stór er in síða(page) á disk

A

4k

59
Q

Hver er sóknartími til að sækja bæti úr minni tölvu (RAM)

A

100 ns

60
Q

Hvernig þurfa equals og hashCode aðferðirnar að passa saman

A

hashCode þarf að skila sama gildi fyrir tvo hluti ef þau eru equals

61
Q

Hver er tíminn sem það tekur að reikna út hashCode fyrir String hlut af lengd N

A

O(N)

62
Q

Hver er meðaltalstími fyrir leit í hakkatöflu með tengdum lista

A

O(1)

63
Q

Hver er versti mögulegi keyrslutími fyrir leit í hakkatöflu með tengdum lista

A

O(N)

64
Q

Hvert er versti mögulegi keyrslutími fyrir leit í hakkatöflu með open addressing?

A

O(N)

65
Q

Hver er meðaltals keyrslutími fyrir leit í hakkatöflu með open addressing?

A

O(1)

66
Q

Hvernig er hægt að redda eyðingu á stökum í hakkatöflu með fylki (linear probing)?

A

Með því að að setja inn lykil fyrir eyðingu (e. tombstone) eða með því

67
Q

Af hverju er það slæmt ef hægt er að búa til mörg gildi sem fá sama hakkagildi?

A

Opnar á algoriþmískar árásir á gagnagrindur

68
Q

Hver er ókostur við að geyma netið sem tvívítt 0-1 fylki

A

Minnisnotkun O(N^2)

69
Q

Hver er ókostur við að geyma netið sem mengi af leggjum

A

Engin auðveld leið til að fletta upp þeim leggjum sem tengjast ákveðnum hnúti

70
Q

Hvaða gagnagrind notar BFS við leit

A

Biðröð (FIFO, queue)

71
Q

Hvaða gagnagrind notar DFS við leit

A

Stafla eða fallaköll

72
Q

Hve langan tíma tekur BFS að skoða allt netið

A

O(E+V)

73
Q

Hvaða reiknirit er hægt að nota til að finna samhengisþætti neta

A

Union find, BFS, DFS

74
Q

Hvaða reiknirit er hægt að nota til að finna hvort net hafi hring

A

DFS og BFS

75
Q

Hvaða gagnagrind notar BFS við leit í stefndu neti

A

Biðröð (FIFO, queue)

76
Q

Hvaða grunnleitaraðferð notar grannfræðileg röðun (topological sort)

A

DFS

77
Q

Hvaða skilyrði eru fyrir því að hægt sé að finna grannfræðilega röðun í stefndu neti

A

Netið þarf að vera laust við stefnda hringi, þarf að vera DAG

78
Q

Hvaða leitarreiknirit gefur stystu leið í stefndum netum

A

BSF

79
Q

Hvað er spannandi tré (spanning tree)?

A

Hlutnet sem er samanhangandi, án hringja (tré) og inniheldur alla hnúta netsins

80
Q

Hvað er skurður (e. cut)

A

Skipting á hnútum netsins í tvö hlutmengi.

81
Q

Hvernig velur reiknirit Kruskals næsta legg til að bæta við MST?

A

Minnsta óskoðaða legg sem myndar ekki hring í því MST s

82
Q

Hvaða gagnagrind nota reiknirit Prims til að halda utan um leggi sem gætu bæst við MST?

A

Forgangsbiðröð með vísi (e. Indexed Priority Queue)

83
Q

Hvernig er stysta leið reiknuð þegar allir leggir eru jafnlangir

A

BFS eða Dijkstra

84
Q

Hvaða gagnagrind notar Dijkstra reikniritið til að halda utan um fjarlægðir

A

Forgangsbiðröð með vísi

85
Q

Hver er keyrslutíminn á reikniriti Djikstra með V hnúta og E leggi

A

E log(V)

86
Q

Í hvaða röð eru hnútar skoðaðir í reikniritinu fyrir stystu leið í DAG

A

grannfræðilegri röð (topological order)

87
Q

Hvernig er lengsta leið fundin í DAG?

A

stysta leið notuð með neikvæðar vigtir

88
Q

Hver er tímakeyrslan á stystu leið í DAG?

A

E+V

89
Q

Skrifið reglulega segð sem passar við strengi af 0 og 1 sem innihalda amk tvö 0

A

010.*

90
Q

Afhverju er ekki praktískt að breyta reglulegri segð í löggenga stöðuvél(DFA)

A

Fjöldi ástanda getur verið veldisfall af lengd segðarinnar

91
Q

Hvaða netareiknirit er notað til að finna út hvort brigðgeng stöðuvél (NFA) samþykki strengi

A

DFS, BFS eða reachability

92
Q

Hver er tímaflækjan á að athuga hvort brigðgeng stöðuvél samþykki streng sem fall af lengd strengs N

A

O(N)

93
Q

Hver er munurinn a löggengri stöðuvél (DFA) og brigðgengri stöðuvél (NFA)

A

Brigðgeng stöðuvél hefur marga leggi með sömu tákn úr sama ástandi

94
Q

Ef regluleg segð hefur M tákn hversu mörg ástönd mun brigðgenga stöðuvélin hafa

A

M+1

95
Q

Hvaða tákn í reglulegum segðum frá svartar örvar sem benda frá sér

A

Stafir og .

96
Q

Fyrir reglulegu segðina A* afhverju kemur bæði rauð og svört ör úr ástandinu sem táknar A

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.
© 2024 Bold Learning Solutions. Terms and Conditions