Prüfungsteilnehmer prüfungstermin Einzelprüfungsnummei Kennzahl: Herbst Kennwort: 2000 46114 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (nicht vertieft studiert) Einzelprüfung: atgorithmen/Datenstrukt./progr.-meth. Anzahlder gestelltenThemen(Aufgaben): z Anzahlder DruckseitendieserVorlase: 5 Bitte wenden! Herbst2000 Einzelprüfungsnumm er: 46I14 Seite:2 Thena Nr. 1 1. Algorithmen und Datenstrukturm Ein binärer Baum ist entwederleer, oder er bestehtauseiner V'ruzst rrnd zwei binärenBäumen als linkem und rechtemUnterbaum. Ein binärersuchbaumfür die schlüsselmenge s : {sr, sz,..., s,} ist ein binärerBaummit z Knoten{ vt, v2,..., v,} und einerbijektivenBeschriftungc(v): v-+ s der Knoten,so dassfürjeden Knoten v folgendeEigenschafterfüllt ist: Für alle Knoten v'im linken Unterbaumund alle Knoteny'' im rechtenUnterbaumgilt: c(v,) < c(v) < c(v,,). (la) BeschreibenSie verbal, ggf. unter Zuhilfenahmeeiner Skizze, das Suchennach einem Knoten mit vorgegebenemSchlüssel! Woran erkenntder Algorithmus, dasskein Elementmit diesemSchlüsselim Baum enthalten ist? WelchecharakteristischeGrößedesBaumesbestimmtdie Suchzeit? (1b) BeschreibenSie genausodas EinfügeneinesneuenKnotens,der durch einenbisher nicht benutztenSchlüsselcharakterisiertist! (lc) Die Reihenfolge,in der Knoten in einenursprünglichleerenSuchbaumeingetragenwerden, kann wesentlichdie spätereSuchzeitbeeinflussen. WelchebeidenExtremfüllekönnenauftreten,und was kann man in beidenFällen über die Suchzeitsagen? (1d) Soll man einenKnoten mit vorgegebenem Schlüsselausdem Baum entfernen,so wird er gesucht. zuerst Handeltes sich um einenKnoten mit maximal einem nichtleerenUnterbaum, so kann er einfachentferntwerden. Was ist zu tun, wenn der zu entfemendeKnoten zwei nichtleereUnterbäumebesitzt? -- 2. Programmiermethodik Mit folgenderDatenstrukturkönnenin C binäre Suchbäumedarsestelltwerden: struct struct int info Node { Node *left, k.y,da!a; *right; /* /* /* linl