ADT Klausuraufgabe 13.Juli.2008

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

ADT Klausuraufgabe 13.Juli.2008
Moin,

hat die Aufgabe jemand gemacht und kann mir sagen wie intensiv ich mir ADTs noch anschauen muss :smiley:

Meine Lösungen

a)

create und add (Primärkonstruktoren)
remove und removeAll (Hilfskonstruktoren)

b)

T: (Typ) M
x: (Typ) T
y: (Typ) T

A1: contains (x, create) = 0
A2: contains (x, add(y,T)) = 1 + contains (x, T) wenn x = y
= contains(x, T) sonst

c)

A3: remove (x, create) = create
A4: remove (x, add(y,T)) = T wenn x = y
= remove(x,T) sonst

d)

A5: removeAll (x, T) = T wenn contains(x, T) = 0
A6: removeAll (x, add(y,T)) = remove (x, add(y,T)) wenn contains (x, T) = 1
= removeAll(x, remove(x, add(y,T))) sonst

Edit: Achja und bei Aufgabe 3 wird eine Ausgabe erwartet…die korrekte Antwort wäre wohl der code compilt nicht, weil die Sichtbarkeit von void i(); eingeschränkt wird…

Edit2: Außerdem soll man in der Klausur den Spannbaum mit Hilfe vom Dijkstra Algorithmus angeben o.O? Wie geht man da vor?
Also kürzester Weg mit Dijkstra, und minimale Spannbäume mit Kruskal und Prim sind mir klar, mit Dijkstra hab ich das aber noch nicht gesehen.

3

Dijkstra erzeugt einen Spannbaum aber nicht zwingend den minimalsten. Du musst halt alle Pfade vom Startknoten zu den anderen Knoten einzeichnen

4

K danke, da hätte man draufkommen können

5

die removeAll-Axiome sind übrigens Grütze

6

Ja ich dachte mir, dass da was nicht stimmt, weiß aber nach wie vor nicht genau was

removeAll(x, remove(x, T))

So ähnlich muss es doch gehen, ich rufe rekursiv die Methode removeAll auf, nur dass die betrachtete Liste jetzt ein x weniger enthält weil das gelöscht wurde.
Das mache ich so lange bis contains 0 ist.
Also vllt so?

A5: removeAll (x, T) = T wenn contains(x, T) = 0
removeAll(x, remove(x, T)) sonst

7

Vorschlag für die removeAll Axiome:

[m]removeAll(x,create()) = create()[/m]
[m]removeAll(x,add(y,M)) = removeAll(x,M) falls x == y
add(y,removeAll(x,M)) sonst[/m]

8

so ist es

9

Hm achso, dann “verliere” ich die Elemente dadurch, dass ich sie einfach überspringe wenn ich sie nicht remove, wenn ich das richtig sehe.

Danke auf jedenfall, bis zur nächsten ADT Aufgabe :smiley:

10

So nächster Versuch: Klausuraufgabe vom 19.03.2007 Seite 6

a)

  • 1
  • bin (create, 6, bin (create, 4, create))
  • 4

b) height

A8: height (create) = -1
A9: height (bin (t1, x, t2)) = 1 + max (height(t1), height(t2))

c)

	public static int height (BT tree) {
		if (tree == null) {
			return -1;
		}
		else {
			return 1 + max(height(tree.left), height(tree.right)); 
		}
	}

d) diameter

A10: diameter (create) = -1
A11: diameter (bin (t1, x, t2)) = max (height(t1) + height(t2) + 1, max (diameter(t1), diameter(t2))

e) Zentrale Eigenschaft eines Suchbaumes

Es herrscht eine Ordnungsrelation, so dass für jeden Knoten gilt, dass das linke Kind kleiner (wenn vorhanden) und das rechte Kind größer als der Vaterknoten ist. (Oder andersrum)

f)

A12: isST (create) = true
A13: isST (bin (t1, x, t2)) = false wenn value(t1) >= x oder value(t2) <= x
= isST(t1) && isST(t2) sonst (keine Ahnung wie das sonst gehen soll :D)

g)

An das Minimum von Baum B2 wird B1 als linkes Kind hinzugefügt

Diameter war hart, über Fehlerkorrekturen freue ich mich wie immer :slight_smile:

Edit: Bin ich eigentlich der einzige der AuD lernt und dazu Fragen im Forum hat? :smiley: so still hier

11

[quote=ri31hoky]
Edit: Bin ich eigentlich der einzige der AuD lernt und dazu Fragen im Forum hat? :smiley: so still hier
[/quote]Zumindest ich bin im Moment eher mit KonzMod beschaeftigt…

12

[quote=MalteM]

ebenfalls. Hab immer noch nicht alle folien durch :confused:

13

Passen die so? Braucht nicht auch ein rekursiv definiertes Axiom irgendwie eine Abbruchbedingung oder so?

14

Also meines Erachtens sind das hier die Abbruchbedingungen:

A8: height (create) = -1
A10: diameter (create) = -1

Zur Korrektheit hat sich bisher noch niemand geäußert

15

Solte es bei der d) in A11 nicht height(t1) + height(t2) + 2 heißen??

bei f) für A13 hab ich: isST(Bin(t1,x,t1)) = true falls x>maximunm(t1) && x>maximum(t2)
false sonst
Ist das auch möglich?