TU Wien:Algorithmen und Datenstrukturen VU (Szeider)/Lösung 1. Test 2022-05-20

Ohne Gewähr

Die Veröffentlichung betrifft ausschließlich meine eigenen Lösungen, die als eigenständige geistige Schöpfungen nicht unter das Urheberrecht der Prüfungsangaben fallen und daher nach § 1 Abs 1 sowie § 14 UrhG rechtlich zulässig ist

A1

a)

$3^{-n}\ll \log n\ll {\frac {n}{50}}\ll {\frac {4n^{5}+5n^{4}}{7n^{3}}}\ll 2{\sqrt {5n^{6}}}\ll 1.1^{n}\ll (3n)!$

b)

$n^{2}$. Die äußere for das erste $n$, die erste innere for führt nur zu $n\log n$, die zweite jedoch zu mindestens $n$ und daher insgesamt $n^{2}$

c)

Best case: 1 Worst case: $2^{n}$ (erste for) fall $n>1000$ und z.B. das erste $A[i]=0$

d)

Laufzeit: $\log n$ Rückgabewert: $\log n$ Die 2 for schleifen werden unterbrochen sobald a (also n) lang genug halbiert wird

e)

$f(n)\in O(n^{2})$

$f(n)<<n^{2}$

A2

a)

Q1

Wahr

Q2

Falsch, stark zusammenhängend kann ein DAG gar nicht sein

Q3

Wahr, dann sind alle Knoten im Kreis und jeder knoten von jedem erreichbar.

Q4

Wahr, nur einzelne Knoten können stark ZHK sein, daher genau n.

Q5

Falsch, eine schwache ZHK kann in mehrere starke zerfallen.

A5

a)

i)

Inorder: 3,8,9,10,11,12,20

Postorder: 3,9,11,10,8,20,12

ii)

19/7 Vergleiche

iii)

bal(12) = -2 bal(8) = 1 von allen anderen bal(v) = 0

iv)

Fall 1.2 "Doppelrotation links-rechts"

erster schritt: 12 -> 10, 12 -> 20, 10 -> 8, 10 -> 11, 8 -> 3, 8 -> 9

zweiter schritt / lösung: 10 -> 8, 10 -> 12, 8 -> 3, 8 -> 9, 12 -> 11, 12 -> 20