Hilfe zur Klausuraufgabe Lösungsvorschlag Klausur WiSe 17/18

Aufgabe 1
a)
F , R , F , F , R , R , R , R , F, R , R
b)
Schichten sind komplexere Komponenten einer Anwendung, die für sich übergeordnete softwaretechnische Funktion darstellen. Diese sind
• Präsentation der Anwendung
• Verarbeitung von Daten
• Datenhaltung zur Speicherung.
Schichten sind ihre Komponenten auf höchster Abstraktionsebene und besitzen keine übergeordneten Komponenten. Alle Komponenten einer Schicht sollen lediglich einen Beitrag zur übergeordneten Aufgabe der Schicht leisten. Um Aufgaben der Schicht zu erfüllen, müssen Schichten kooperieren und kommunizieren. Charakteristisch für Schichten sind die symmetrische Kooperationsbeziehungen sowie die unidirektionalen Abhängigkeitsbeziehungen zwischen den Schichten. Aufgrund der softwaretechnischen Funktionen ergibt sich eine vertikale Richtung mit der Präsentation oben und der Datenhaltung unten. Es können von der oberen Schicht Leistungen von einer tieferen Schicht angefordert und genutzt werden. Dagegen darf von einer tieferen Schicht keine Leistung einer höheren Schicht in Anspruch genommen werden. Während also höhere Schichten von tieferen Schichten abhängig sind, sollen tiefere Schichten unabhängig von höheren Schichten sein. In die Realisierung von tieferen Schichten darf demnach kein Wissen über die Gestaltung einer höheren Schicht einfließen.

Aufgabe 2)
PROCEDURE trav_gef_baum()
DATA
VARIABLE
knotennr : INDEX;
stop: BOOLEAN;
FUNCTION nachf_lwr (knotennr: INDEX):INDEX
DATA
VARIABLE
nachfindex:INDEX;
BEGIN
IF (baum[knotennr].rechts < 0 ) THEN
nachfindex := -baum[knotennr].rechts
ELSE
Nachfindex := baum[knotennr].links
WHILE ( baum[knotennr].links > 0)
Nachfindex := baum[knotennr].links;
ENDWHILE
ENDIF
RETURN nachfindex;
END nachf_lwr;
BEGIN
Stop:=FALSE;
knotennr := kopf;
REPEAT
knotennr:= nachf_lwr(knotennr);
IF (knotenr = kopf) THEN
Stop := TRUE;
ELSE
Bearbeite Datenobjekt baum[knotennr];
ENDIF
UNTIL stop;
END trav_gef_baum;

b)
Zur Laufzeit wird kein Stack benötigt. Damit wird Speicherpatz eingespart und Geschwindigkeit gewonnen. Weiter können von jedem Knoten aus der der Vorgänger und der Nachfolger effektiv bestimmt werden. So ergibt sich ein günstigeres Laufzeitverhalten. Nachteile bringen die Einfüge und Löschoperationen die sich durch die zusätzliche Zeigerpflege aufwendiger gestaltet.
c)
Iterative Prozedur
PROCEDURE qsumme(n:INTEGER;VARIABLE summe:INTEGER)
BEGIN
summe:= 0;
WHILE (n>0) DO
summe:= summe + n*n;
n:= n-1;
ENDWHILE
END qsumme
Recursive Funktion
FUNCTION qsumme(VARIABLE n:INTEGER) : INTEGER
BEGIN
IF (n>0) THEN
RETURN (n*n + qsumme(n-1);
ELSE
RETURN 0;
ENDIF;
END qsumme;
Aufgabe d)
Für n=1 ( Anzahl der Indexeinträge) ergibt sich kein B-Baum sonder eine maximal eine verkettete Liste.
??? Aufgabenstellung wird nicht klar ???

AUFGABE 3)
a)
Bubblesort in C
#include <stdio.h>
int main()
{
int array[], n, i, j, element;
printf("Anzahl der Elemente eingeben\n");
scanf("%d", &n);
printf("Eingabe von %d Zahlen\n", n);
for (i = 0; i < n; i++)
scanf("%d", &array);
for (i = 0 ; i < n - 1; i++) {
for (j = 0 ; j < n - i - 1; j++)
{
if (array[j] > array[j+1])
{
element = array[j];
array[j] = array[j+1];
array[j+1] = element;
}
}
}
printf("Sortierte Liste in aufsteigender Sortierung:\n");
for (i = 0; i < n; i++)
printf("%d", array);
}
b )
Bei der linearen Suche wird ein Vektor vom ersten Element durchsucht bis der Wert gefunden wurde oder das Listenende erreicht wurde. Die lineare Suche setzt voraus dass ein Feld aufsteigend sortiert wurde. Daher kann eine Suche als Ergebnislos angesehen werden, wenn ein Wert erreicht wurde der größer als der Suchwert ist.
Bei der linearen Suche mit Sentineltechnik wird der gesuchte Wert als künstliches Element am Vektorende eingetragen. Wird der Suchwert vor dem Sentinel gefunden war die Suche erfolgreich; trifft der Suchwert im Sentinel auf war die Suche erfolglos. Es muss lediglich nur der Suchwert verglichen und nicht zusätzlich das Listenende geprüft werden. So erhöht sich die Effizienz der Suche. Ist der Vektor aufsteigend sortiert, so kann eine Suche als Ergebnislos angesehen werden, wenn ein Wert erreicht wurde der größer als der Suchwert ist.
c)
Für die Auflösung eines Binärbaumes ist eine Postorder Traversierung vorteilhaft. Zuerst werden die rechten und linken Knoten aufgelöst und dann die Wurzel. So kommt es zu keinem Zugriff auf bereits aufgelöste Bereiche.
d)
Zur dynamischen Reservierung von Speicherplatz aus dem Heap werden die Funktionen malloc und calloc eingesetzt.
Malloc reserviert einen Block von aufeinanderfolgenden Bytes im Heap und gibt die Adresse des ersten Bytes zurück. Diese Adresse kann in einen Zeigertyp umgewandelt werden. Kann eine Reservierung nicht durchgeführt werden, so wird NULL zurückgegeben.
Calloc reserviert n Blöcke von aufeinanderfolgenden Bytes im Heap und initialisiert alle Bytes mit Null im Heap. Alles andere analog wie bei Malloc.
Zur Freigabe und Rückgabe von mit malloc oder calloc reservierten Speicherplatz wird die Funktion free genutzt.

e)
void main(void){
float *pf;
printf("\nDynamische Reservierung von Speicherplatz mit malloc\n");
pf = (float *) malloc(sizeof(float));
if (pf == NULL)
{
printf("Reservierung von Speicherplatz mit malloc ist fehlgeschlagen!\n");
exit(1);
}
*pf= 10.99;
printf("\Wert von 1 float : %2f",*pf);
free(pf);
}

f)
#include <stdio.h>
struct DATUM
{
int tag;
int monat;
int jahr;
};
struct BESTELLUNG
{
int artikelnr;
int anzahl;
float preis;
struct DATUM datum;
};
void einlesen_bestellung(struct BESTELLUNG *best_zgr);
void ausgeben_bestellung(struct BESTELLUNG *best_zgr);
void main(void)
{
int i, anz;
struct BESTELLUNG bestellung[10];
struct BESTELLUNG *best_zgr;
printf("Bitte Bestelldaten eingeben: (<=10):");
scanf("%d",&anz);
for (i = 0 ; i < anz ; i++)
einlesen_bestellung(&bestellung);
printf("Datenausgabe:");
for (best_zgr = bestellung ; best_zgr < bestellung + anz - 1; best_zgr++)
ausgeben_bestellung(best_zgr);
}
void einlesen_bestellung(struct BESTELLUNG *best_zgr)
{
printf("Eingabe von Artikelnummer:");
scanf("%d",&best_zgr->artikelnr);
printf("Eingabe von Anzahl:");
scanf("%d",&best_zgr->anzahl);
printf("Eingabe des Preises:");
scanf("%f",&best_zgr->preis);
printf("Eingabe des Datums:");
scanf("%d",&best_zgr->datum);
}
void ausgeben_bestellung(struct BESTELLUNG *best_zgr)
{
printf("Artikelnummer Anzahl Preis Datum\n");
printf("%+15d %+6d %+4f %8d\n",
best_zgr->artikelnr,best_zgr->anzahl,best_zgr->preis,best_zgr->datum);
}

Aufgabe 2 d wird mir nicht ganz klar ... für n=1 ergibt sich kein B-Baum sonder eine verkettete Liste oder nicht ??
Wer kann mir helfen??

Hallo zusammen,

für Heiko sicherlich zu spät, aber für den Rest: Die Aufgabe 2d) ist in KE4 die Übungsaufgabe 6.16