Informatik-Treff: Abiturklausur (1997 LK 3. Klausur) 

(Von dieser Klausur liegt nur die Aufgabe 1 vor.)

Aufgabe 1:

Die Anlage zeigt den Graphen G, das Programm 'graphen - durchlauf' und eine Schnittstellenbeschreibung der UNIT 'keller'.

a) Zur sinnvollen Speicherplatznutzung ist es wichtig, Graphen geeignet zu implementieren. Möglichkeiten zur Verwaltung eines Graphen bieten die Adjazenzmatrix und die Adjazenzliste. Beschreiben Sie die genannten Strukturen anhand des Vereinbarungsteils der Programmvorgabe! Beurteilen Sie den jeweiligen Speicherbedarf!

b) Erstellen Sie die Prozedur 'umwandeln' , die aus der Adjazenzmatrix die Adjazenzlisten gewinnt! Die Knoten sind aufsteigend sortiert in die Listen einzubringen. Wie lauten die Adjazenzlisten?

c) Die Prozedur 'tiefensuche_1' zeigt einen Algorithmus, der vom Startknoten 1 aus einen Weg durch den Graphen ermittelt. Erläutern Sie an ihm das Verfahren der Tiefensuche! Zeigen Sie, wie dabei der Pfad 1, 2 , 3 , 6 , 4 , 5 , 7 entsteht! In welcher Situation kommt es zum Backtracking?

d) Alternativ zur in c) gezeigten Methode besteht die Möglichkeit, durch Stapelanwendung die Rekursion zu umgehen. Demonstrieren Sie diese Variante für den Startknoten 1 ! Das Ergebnis stimmt nicht mit der Vorgabe in c) überein! Wie ist das zu erklären?

e) Wie lautet die Prozedur 'besuche-2', die unter Verwendung der UNIT 'keller' das in d) vorgetragene Konzept realisiert! (Hinweis: Es ist zu beachten, daß bereits im Stapel vorhandene Knoten geeignet gekennzeichnet werden müssen.)

f) Verwaltet man die unbesuchten Knoten in einer Warteschlange statt in einem Stapel, ergibt sich die Breitensuche. Demonstrieren Sie dieses Verfahren für Startknoten 1 !

Anlage zur Aufgabe 1:

Graph G:
 

PROGRAM graphen_durchlauf;

USES Crt, keller;

CONST knotenzahl = 7;

TYPE t_KnIndex   = 1..knotenzahl;
     t_AdjMatrix = ARRAY[t_KnIndex,t_KnIndex] OF 0..1;
     t_Zeiger    = ^t_Knoten;
     t_Knoten    = RECORD 
                     inhalt: t_KnIndex;
                     next  : t_Zeiger
                   END; 
     t_AdjListe  = ARRAY[t_KnIndex] OF t_Zeiger;

CONST AdjMatrix : t_AdjMatrix = ((0, 1, 1, 0, 0, 1, 1),
                                 (1, 0, 0, 0, 0, 0, 0),
                                 (1, 0, 0, 0, 0, 0, 0),
                                 (0, 0, 0, 0, 1, 1, 0),
                                 (0, 0, 0, 1, 0, 1, 1),
                                 (1, 0, 0, 1, 1, 0, 0),
                                 (1, 0, 0, 0, 1, 0, 0));

VAR AdjListe: t_AdjListe;

PROCEDURE umwandeln (VAR matrix: t_AdjMatrix; VAR liste: t_AdjListe);
BEGIN {s. Aufgabe b)} END;

PROCEDURE tiefensuche_l (VAR liste: t_AdjListe); 
VAR besucht         : ARRAY[t_KnIndex] OF INTEGER;
    i, j            : t_KnIndex;
    besuchter_knoten: INTEGER;

  PROCEDURE besuche_l (knotennummer: INTEGER); 
  VAR zAktuell: t_Zeiger;
  BEGIN
    Write(knotennummer: 2);
    besucht[knotennummerj := besuchterknoten; 
    zAktuell := liste[knotennummer]; 
    WHILE (zAktuell <> NIL) DO
      BEGIN 
        IF besucht[zAktuell^.inhalt] = 0 
          THEN besuche_1(zAktuell^.inhalt);
        zAktuell := zAktuell^.next;
      END;
  END; {besuche_1}

BEGIN {tiefensuche_1}
  FOR i := 1 TO knotenzahl DO besucht[i] := 0;
  besuche_1(1);
END; {tiefensuche_1}

PROCEDURE tiefensuche_2 (VAR liste: t_AdjListe);
{Vereinbarungsteil wie in tiefensuche_l}

  PROCEDURE besuche_2 (knotennummer: INTEGER); 
  BEGIN {s. Aufgabe e)} END; {besuche_2}

BEGIN {tiefensuche_2}
  FOR i := 1 TO knotenzahl DO besucht[i] := 0;
  besuche_2(1);
END; {tiefensuche_2}

BEGIN {HP}
  umwandeln (AdjMatrix,AdjListe); {s. b)}
  tiefensuche_1 (AdjListe);       {s. c)} 
  tiefensuche_2 (AdjListe);       {s. e)}
END.

UNIT Keller;

INTERFACE

TYPE t_inhalt        = INTEGER; 
     t_keller        = ^t_kellerelement;
     t_kellerelement = RECORD
                         inhalt: t_inhalt; 
                         next  : t_keller
                       END;

FUNCTION empty (stapel: t_keller): BOOLEAN;
  {Prüft, ob der Stapel leer ist}

FUNCTION top (stapel: t_keller): t_inhalt;
  {Greift auf den Stapelkopf zu}

PROCEDURE create (VAR stapel: t_keller);
  {Legt einen leeren Stapel an}

PROCEDURE push (VAR stapel; t-keller; w: t_inhalt); 
  {Bringt Element auf den Stapel}

PROCEDURE pop (VAR stapel; t_keller; VAR w: t_inhalt);
  {holt Element vom Stapel}