Einführung in die imperative Programmierung

WS 2016/17

Klausuraufgabe HK10 Aufgabe 1

program aufg1;

 type 
   tRefListe=^tListe; 
   tListe=record 
   Wert:integer; 
   next:tRefListe 
   end;
   
   var kopf,zeiger,neu,umgedreht: tRefListe;
   
   procedure anzeigen(inKopf : tRefListe);
   
   var zeiger: tRefListe;
   begin
   zeiger:=inKopf;
   while zeiger<>nil do
   begin
   write(zeiger^.Wert, ' ');
   zeiger:= zeiger^.next;
   end;
   writeln();
   end;
   
   procedure NachVorn(inWert: integer; var ioRefAnfang:  tRefListe);
   
   var
   vor,lauf: tRefListe;
   
   begin
   vor:=nil;
   lauf:=ioRefAnfang;
   while lauf^.Wert<>inWert do
   begin
   vor:=lauf;
   lauf:= lauf^.next;
   end;
   if vor<>nil then
   begin
   vor^.next:= lauf^.next;
   lauf^.next:=ioRefAnfang;
   ioRefAnfang:= lauf;
   end;
   
   end;

BEGIN
   new(neu);
   neu^.Wert:=7;
   neu^.next:=nil;
   zeiger:= neu;
   kopf:=neu;
   
   new(neu);
   neu^.Wert:=3;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.Wert:=5;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.Wert:=3;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.Wert:=1;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   anzeigen(kopf);
   
   NachVorn(1, kopf);
   
   anzeigen(kopf);
   
   END.

Klausuraufgabe HK10 Aufgabe 2

program aufg2;

 type tRoemZiff = (I, V, X, L, C, D, M);
   tRefRoemZahlStelle = ^tRoemZahlStelle;
   tRoemZahlStelle = record
   ziffer: tRoemZiff;
   links: tRefRoemZahlStelle;
   end;
   
   var
   neu,zeiger,kopf: tRefRoemZahlStelle;
   
   procedure anzeigen(inKopf: tRefRoemZahlStelle);
   var
   lauf:tRefRoemZahlStelle;
   begin
   lauf:= inKopf;
   while lauf<>nil do
   begin
   write(lauf^.ziffer);
   lauf:= lauf^.links;
   end;
   writeln();
   end;

function RoemZiffWert(inZiff: tRoemZiff): integer;
   {Gibt den Wert einer römischen Ziffer zurück,
   z.B. RoemZiffWert(L)=50.}
   begin 
   case inZiff of
   I: RoemZiffWert:=1;
   V: RoemZiffWert:=5;
   X: RoemZiffWert:=10;
   L: RoemZiffWert:=50;
   C: RoemZiffWert:=100;
   D: RoemZiffWert:=500;
   M: RoemZiffWert:=1000;
   end;

end;

function RoemZahlWert(inRoemZahl: tRefRoemZahlStelle): integer;
   var 
   kopf,next:tRefRoemZahlStelle;
   sum:integer;
   begin
   sum:=0;
   kopf:=inRoemZahl;
   while kopf<>nil do
   begin
   next:=kopf^.links;
   if next<>nil then
   begin
   if kopf^.ziffer > next^.ziffer then
   begin
   sum:= sum + RoemZiffWert(kopf^.ziffer)-RoemZiffWert(next^.ziffer);
   kopf:=next^.links;
   end
   else
   begin
   sum:= sum + RoemZiffWert(kopf^.ziffer);
   kopf:=next;
   end;
   end;
   end;
   sum:= sum + RoemZiffWert(kopf^.ziffer);
   RoemZahlWert:= sum;
   end;

{
   function RoemZahlWert(inRoemZahl: tRefRoemZahlStelle): integer;
   var 
   zahl: tRefRoemZahlStelle;
   sum:integer;
   begin
   zahl:= inRoemZahl;
   sum:= RoemZiffWert(zahl^.ziffer);
   while zahl^.links<>nil do
   begin
   if zahl^.links^.ziffer < zahl^.ziffer then
   begin
   sum:= sum - RoemZiffWert(zahl^.links^.ziffer);
   zahl:= zahl^.links;
   end
   else
   begin
   sum:= sum + RoemZiffWert(zahl^.links^.ziffer);
   zahl:= zahl^.links;
   end;
   end;
   RoemZahlWert:= sum;
   end;
   }

{
   function RoemZahlWert(inRoemZahl: tRefRoemZahlStelle): integer;
   var 
   lauf: tRefRoemZahlStelle;
   sum,alt:integer;
   begin
   alt:=0;
   sum:=0;
   lauf:= inRoemZahl;
   while lauf<>nil do
   begin
   if RoemZiffWert(lauf^.ziffer) < alt then
   sum := sum - RoemZiffWert(lauf^.ziffer)
   else 
   sum := sum + RoemZiffWert(lauf^.ziffer);
   alt:= RoemZiffWert(lauf^.ziffer);
   lauf:= lauf^.links;
   end;
   RoemZahlWert:=sum;
   end;
   }

BEGIN
   new(neu);
   neu^.ziffer:=X;
   neu^.links:=nil;
   zeiger:= neu;
   kopf:=neu;
   
   new(neu);
   neu^.ziffer:=I;
   neu^.links:=nil;
   zeiger^.links:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.ziffer:=C;
   neu^.links:=nil;
   zeiger^.links:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.ziffer:=X;
   neu^.links:=nil;
   zeiger^.links:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.ziffer:=M;
   neu^.links:=nil;
   zeiger^.links:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.ziffer:=C;
   neu^.links:=nil;
   zeiger^.links:= neu;
   zeiger:=neu;
   
   anzeigen(kopf);
   
   writeln('Wert: ',RoemZahlWert(kopf));
   
   END.

Klausuraufgabe HK10 Aufgabe 4

program aufg4;

 type
   tRefKnoten = ^tKnoten;
   tKnoten = record
   info: integer;
   links,
   rechts:tRefKnoten
   end;

function istMaxHeap(inRefWurzel: tRefKnoten): Boolean;
   { Gibt true zurück, genau dann wenn der Baum ein Max-Heap ist. }
   var linksGroesser, rechtsGroesser: Boolean;
   begin
   if inRefWurzel = nil then
   {Der leere Baum ist ein (leerer) Max-Heap, da er keinen Knoten
   mit größerem Kind enthält.}
   istMaxHeap := true
   else
   begin
   {Untersuchung des Wurzelknotens und seiner Kinder}
   if inRefWurzel^.links = nil then
   linksGroesser := false
   else
   linksGroesser := inRefWurzel^.links^.info > inRefWurzel^.info;
   if inRefWurzel^.rechts = nil then
   rechtsGroesser := false
   else
   rechtsGroesser := inRefWurzel^.rechts^.info > inRefWurzel^.info;
   if rechtsGroesser or linksGroesser then
   istMaxHeap:= false
   else
   istMaxHeap:= istMaxHeap(inRefWurzel^.links) and istMaxHeap(inRefWurzel^.rechts);
   
   end; 

BEGIN
   
   END.

Klausuraufgabe NK11 Aufgabe 4

program aufg4;

 type 
   tRefListe=^tListe; 
   tListe=record 
   Wert:integer; 
   next:tRefListe 
   end;
   
   var kopf,zeiger,neu,umgedreht: tRefListe;
   
   procedure ListeUmdrehen(var ioKopf: tRefListe);
   var
   lauf,vor,nach: tRefListe;
   begin
   if ioKopf<>nil then
   begin
   vor:=ioKopf;
   lauf:=vor^.next;
   if lauf<>nil then
   begin
   nach:= lauf^.next;
   while (lauf<>nil) do
   begin
   lauf^.next:= vor;
   vor:=lauf;
   lauf:= nach;
   if nach<>nil then
   nach:=nach^.next;
   end;
   ioKopf^.next:=nil;
   ioKopf:= vor;
   end 
   else
   begin
   lauf^.next:= vor;
   vor^.next:=nil;
   ioKopf:= lauf;
   end;
   end;
   end; 
   
   procedure ListeUmdrehen2(var ioKopf: tRefListe);
   var
   lauf,vor,nach: tRefListe;
   begin
   if ioKopf<>nil then
   begin
   vor:=nil;
   lauf:=ioKopf;
   nach:=lauf^.next;
   while lauf<>nil do
   begin
   lauf^.next:=vor;
   vor:=lauf;
   lauf:=nach;
   if nach<>nil then
   nach:=nach^.next;
   end; 
   ioKopf:= vor;
   end; 
   end; 
   
   procedure anzeigen(inKopf : tRefListe);
   
   var zeiger: tRefListe;
   begin
   zeiger:=inKopf;
   while zeiger<>nil do
   begin
   write(zeiger^.Wert, ' ');
   zeiger:= zeiger^.next;
   end;
   writeln();
   end;
   
   procedure RekUmdrehen(inKopf:tRefListe; var outKopf:tRefListe);
   var
   rueckgabe: tRefListe;
   begin
   if inKopf=nil then
   outKopf:=nil
   else
   begin
   RekUmdrehen(inKopf^.next, rueckgabe);
   if rueckgabe=nil then
   begin
   inKopf^.next:= nil;
   outKopf:= inKopf;
   end
   else
   begin
   inKopf^.next^.next:= inKopf;
   inKopf^.next:=nil;
   outKopf:= rueckgabe;
   end;
   end; 
   end;
 

BEGIN
   new(neu);
   neu^.Wert:=7;
   neu^.next:=nil;
   zeiger:= neu;
   kopf:=neu;
   
   new(neu);
   neu^.Wert:=3;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.Wert:=5;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.Wert:=3;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   new(neu);
   neu^.Wert:=1;
   neu^.next:=nil;
   zeiger^.next:= neu;
   zeiger:=neu;
   
   anzeigen(kopf);
   
   RekUmdrehen(kopf, umgedreht);
   
   anzeigen(umgedreht);
   
   END.

Klausuraufgabe NK11 Aufgabe 5

program aufg5;

 
   type 
   tRefBinBaum=^tBinBaum; 
   tBinBaum=record 
   Wert:Integer; 
   links,rechts:tRefBinBaum ;
   end; 
   
   function IstDrin(inZahl:integer; inBaum:tRefBinBaum): boolean;
   
   begin
   if inBaum=nil then
   IstDrin:= false
   else
   begin
   if (inBaum^.Wert=inZahl) then
   IstDrin:=true
   else
   begin
   IstDrin:= IstDrin(inZahl, inBaum^.links) or IstDrin(inZahl, inBaum^.rechts);
   end;
   end;
   end;

BEGIN
   
   END.