Prüfungsaufgaben. Wer kann helfen?

[eatupyourgreens]

Hallo! Nun, es geht um eine Datenstrukturen Prüfung. Ich bin im 2 Versuch, ein Kollege ist im 3 Versuch. Die meisten Aufgaben verstehen wir zwar, aber bei denen wissen wir echt nicht weiter Eventuell kann ja von euch einer helfen?

(das rote sind mal meine Lösungen, die sind aber eventuell nicht richtig.. )

3) Ein Freund von Ihnen berichtet, er hätte einen neuen Sortieralgorithmus entwickelt. Sein Verfahren würde zu Sortierenden Zahlen so geschickt miteinander vergleichen und umordnen, dass im schlechtesten Fall eine Laufzeit T mit T = 8n+23 erreicht werden könnte. Kann seine Aussage richtig sein? Begründen Sie! (6 Punkte)

Unsere Lösung wäre die hier (aber ich bin mir nicht sicher, ob das stimmt -.-):
Die beiden besten uns bekannten Sortierverfahren sind Merge Sort und Heap Sort. Sie erreichen im schlechtesten Fall T = 0 (n log2 n). Die Aussagen ist also nicht richtig, da mit einer mindest Laufzeit von log2 gerechnet werden muss.


Und:

a) Nennen Sie die Vorraussetzung, die eine Folge von Datenobjekten erfüllen muss, damit sie unter Verwendung des Verfahrens Countingsort sortiert werden kann.

Antwort: Countingsort ist ein nicht vergelichendes Sortierverfahren und die voraussetzung ist das sortieren von natürlichen Zahlen (nur natürliche zahlen werden sortiert).

b) Geben Sie eine Erweiterung des Verfahrens Countingsort an, die es ermöglicht mit diesem Verfahren eine beliebige endliche Menge ganzer Zahlen zu sortieren.

c) Geben Sie eine scharfe asymptotische Schranke für die Laufzeit T des modifizierten Verfahrens an. Begründen Sie!

Antwort: 0 = (n + k - 1) (Ist das richtig? Wie wäre dann die Begründung?)


Ich würde mich echt über eure Hilfe freuen! Die Klausur hat's leider echt in sich