Algorithmen & Datenstrukturen Programmieren 1 von Prof. Jürgen Plate

Musterprüfung Algorithmen & Datenstrukturen/Programmieren 1

Beispielfragen zu Teil 1 (ohne Unterlagen)

1. Was versteht man unter einer Vorwärtsdeklaration ?
2. Was sind wesentliche Aufgaben des Preprozessors, nennen sie wenigstens zwei davon.
3. Was bedeutet die Preprozessoranweisung #include <stdlib.h> und wofür steht in diesem Zusammenhang das "h"?
4. Wozu ist die Angabe eines Datentyps für eine Variable in einer Programmiersprache nötig bzw. was wird durch einen Datentyp festgelegt. Nennen Sie zumindest 2 Festlegungen, die durch die Angabe des Datentyps gemacht werden!
5. Was ist der Unterschied zwischen den Schreibweisen "a" und 'a' in der Programmiersprache C?
6. Was versteht man unter einem rekursiven Algorithmus? Was versteht man unter einem Algorithmus ? Wozu dient ein Struktogramm ? Zeichnen Sie das Struktogrammm für die nichtabweisende Wiederholung (while-Schleife) Nennen Sie zumindest 2 Festlegungen, die durch die Angabe des Datentyps gemacht werden! Was versteht man unter einer Variablen ? Nennen Sie die Art der Anweisung, die in der folgenden Zeile formuliert wird!

   #define  MAX  10
   

7. Kann eine Konstante auf der linken Seite einer Zuweisung stehen? Antwort mit Begründung.
8. Vereinbaren Sie ein Array mit Elementen vom Typ "char" und initialisieren Sie es mit der Stringkonstanten "Dies ist ein String"!
9. Nennen Sie 3 Fälle, bei denen implizite Typumwandlung stattfinden kann!
10. Wie heisst der Operator für explizite Typumwandlung?
11. Erläutern Sie den Unterschied zwischen Funktionsdefinition und Funktionsdeklaration?
12. Was vesteht man unter dynamischer Speicherallokation? Wozu wird sie verwendet?
13. Schreiben Sie die Definition in C-Code der Datenstruktur für einen Knoten einer doppelt verketteten Liste (Vorwärts- und Rückwärtsverkettung), deren Nutzkomponente von Typ "Zeichenkette mit maximal 80 Zeichen" ist. Zeichnen Sie die durch diese Datenstruktur beschriebene Liste mit 3 Elementen.
14. Der Zahlenwert für Pi kann in C folgendermaßen festgelegt werden:

    #define Pi 3.1415 oder: const float Pi = 3.1415;

    Was ist der fundamentale Unterschied zwischen diesen beiden Anweisungen?

15. Welche Zeile wird gedruckt und wie sieht der Ausdruck aus, wenn folgendes Programmsegment durchlaufen wird? Begründen Sie Ihre Antwort.

    ...
    i=0;
    if (i=1) printf("Zeile 1, i = %d \n",i);
        else printf("Zeile 2, i = %d \n",i);
    ...

16. Welchen Wert hat die Variable a nach Durchlaufen des folgenden Programmsegments - was wird also ausgegeben? Begründen Sie Ihre Antwort.

    ....
    float a=0;
    float pi=3.14;
    a=1/2*pi;
    printf(" a hat den Wert: %f\n",a);
    ....

17. Gegeben ist der folgende Inhalt einer "Header-Datei" in ANSI-C:

    1.      #define MAXCHAR 40
    
    2.      struct artikel_t {
    3.      int   nummer;
    4.      char  name[MAXCHAR];
    5.      float preis;
    6.      int   anzahl;
    7.      };
    
    8.      extern struct artikel_t sArtikel;
    9.     extern int openLager(void);
    10.     extern int readNext(struct artikel_t *data);
    

    Geben Sie zu jeder Zeile an, um welche Art von Anweisung es sich handelt und erläutern Sie deren Zweck (Bitte jeweils die Zeilennummer anführen!)
18. Schreiben Sie eine Definition in C-Code der Datenstruktur für einen Knoten einer doppelt verketteten Liste (Vorwärts- und Rückwärtsverkettung), deren Nutzkomponente von Typ "Zeichenkette mit maximal 80 Zeichen" ist. Zeichnen Sie die durch diese Datenstruktur beschriebene Liste mit 3 Elementen.

Beispielaufgaben zu Teil 2 (mit Unterlagen)

1. Aufgabe:

      
     int sig(double X);

Die Aufgabe der Funktion besteht darin, die folgenden Werte zrückzugeben:

     X > 0: sig(X) = 1
     X = 0: sig(X) = 0
     X < 0: sig(X) = -1

1. Realisieren Sie sig() als C-Quelle.
2. Können die aktuellen Übergabeparameter vom Typ "int" oder "unsigned long" sein? Was geschieht in diesem Fall?

2. Aufgabe:

struct item 
  {
  int Satznummer;
  char *Name;   
  char *Message;
  struct item *Next;
  }

int main (void) 
  { 
  char LocName[50], LocMess[50];
  int Nr = 0; 
  int erg;
  struct item *LocPtr, *wurzel=NULL;
  char * phlp;

  struct item *l_alloc(int satznr, char *nam,      /* 5 */ 
                        char *mesg);
 
  char * LookForMess(struct item *wrz, 
                   char *sname);
  do
    {
    printf ("Gib Name und Message: ");
    erg = scanf("%s%s",LocName,LocMess);           /* 1 */
    if (erg == 2) 
      {
      LocPtr = l_alloc(Nr,LocName,LocMess);
      if(LocPtr == NULL) 
        {
        printf("Nicht genuegend Speicher!!\n");
        return EXIT_FAILURE;
        }
      LocPtr->Next = wurzel;                   /* 3 */
      wurzel = LocPtr;                            /* 4 */
      Nr++;
      }
    } while (erg == 2);                          /* 2 */

/*  ............  */

  phlp = LookForMess(wurzel,"Maier");
  if(phlp != NULL)
    printf("Message fuer Maier: %s\n",phlp);
  return EXIT_SUCCESS;
  }

1. Erläutern Sie kurz, was durch die Anweisung bei /* 1 */ bewirkt wird!
2. Welcher Sachverhalt führt zum Abbruch der Schleife bei /* 2 */?

   Die Funktion "l_alloc()" erzeugt einen neuen Listenknoten und liefert als Rückgabewert einen Zeiger auf den neuen Listenknoten. Die Variable "wurzel" ist die Wurzel der Liste.

3. Erläutern Sie die in den mit /* 3 */ und /* 4 */ markierten Zeilen bezüglich der Liste durchgeführten Operationen!

Durch die Komponenten des Listenknotens "char *Name" und "char *Message" sind Zeiger auf Zeichenketten (Strings) realisiert. Die Funktion "l_alloc()", deren Funktionsprototyp bei /* 5 */ deklariert ist, hat folgendes zu leisten:

• dynamisch Speicherplatz für einen Knoten (Element des Typs "struct item") zu reservieren;
• dynamisch Speicherplatz für die beiden übergeben Zeichenketten zu reservieren, der an die Größe der aktuell durch "nam" und "mesg" referenzierten Strings anzupassen ist;
• den Inhalt der Informationskomponenten des Knotens (Satznummer, Name, Message) mit den geeigneten Werten aus zu statten;
• und die Komponente "Next" mit Null vor zu belegen.

Die Funktion "LookForMess()" durchsucht beginnend bei dem Knoten, auf den der erste Übergabeparameter zeigt, die Liste nach der Knotenkomponente "Name" und gibt im Erfolgsfall einen Zeiger auf die "Message" dieses Knotens zurück.

Ein Aufrufbeispiel zeigt Zeile 34 des obigen Programmausschnittes, die Deklaration der Funktion "LookForMess()" ist in Zeile 12 enthalten. Realisieren Sie "LookForMess()" als ANSI-C-Quelle!

ACHTUNG: Alle Teilaufgaben können unabhängig von einander gelöst werden!

3. Aufgabe:

1. alle Tabulatoren ('\t') durch zwei Leerzeichen ersetzen
2. folgende Zeichen ersatzlos entfernen: $_
3. alle Kleinbuchstaben in Grossbuchstaben wandeln

Der Quelltext liegt als beliebige Eingabedatei vor. Die Dateinamen von Quell- und Zieldatei werden als Zeichenketten von der Standardeingabe gelesen. Das Programm konvert erzeugt aus der Quelldatei, die vorhanden sein muß, eine Ausgabedatei in der der Quelltext mit den o. g. Ersetzungen abgelegt wird.

Die beiden Dateinamen müssen unterschiedlich sein, die Quelldatei muß existieren. Existiert die Ausgabedatei bereits so wird sie überschrieben. Im Fehlerfall bricht das Programm mit dem Ausdruck einer entsprechenden Fehlermeldung ab.

Teilen Sie die Aufgabe in zwei Abschnitte:

1. Die Funktion main() (also das Hauptprogramm) des Programms konvert ist zuständig für das Abfragen der Dateinamen, das Öffnen und Schließen der Dateien und die Fehlerbehandlung. Außerdem gibt sie die Anzahl der ersetzten Zeichen auf der Standardausgabe aus (Ergebniswert von ersetze(), siehe unten).
2. Die Funktion ersetze() führt die eigentliche Ersetzung durch. Sie liest ein Zeichen von der Quelldatei und schreibt in die Zieldatei - bis das Ende der Quelldatei erreicht ist. Die beiden Dateizeiger werden als Parameter an ersetze() übergeben. ersetze() gibt die Anzahl der ersetzten Zeichen als int-Wert zurück. Die Funktion hat somit den Prototyp:

       
           int ersetze (FILE *quelle, FILE *ziel);
   

Aufgabenstellung:

1. Zeichnen Sie Struktogramme für main() und ersetze().
2. Formulieren Sie die als Struktogramm beschriebenen Algorithmen als C-Quelle.

4. Aufgabe:

#include <stdio.h>
#include <stlib.h>
#include <string.h>

char * Doppelname(char* pcStr1,char* pcStr2);

int main(void)
  {
  printf( "%s\n", Doppelname ("Mueller", "Stahl"));  
                               /*     Sollausgabe: Mueller-Stahl    */
  return EXIT_SUCCESS;
  }

1. Beschreiben Sie stichpunktartig den eingeschlagenen Lösungsweg!
2. Schreiben Sie die Funktion "Doppelname()" in ANSI-C!

5.Aufgabe:

In der Textdatei "umsatz.txt" stehen die aktuellen Umsatzdaten, für jeden Artikel eine Zeile und in jeder Zeile zuerst der Umsatz, dann durch Blanks(' ') bzw. Tabulatoren ('\t') getrennt davon der Aritkelname, z.B.:

"2234.50 Stehlampe, dreiarmig"

Stehlampe, dreiarmig     2234.50 DM
Fernseher               26890.30 DM
             ...

Bestseller:  Fernseher                  26890.30 DM
Ladenhueter: Osterhasen-Hausschuhe       -123.50 DM

1. Die nach der letzten Ziffer des Umsatzes beginnende Artikelbezeichnung ist maximal 25 Zeichen lang.
2. Lesen Sie zuerst die Umsatzzahl mit "fscanf()" und danach mit "fgets()" die Bezeichnung bis zum Zeilenende. Danach erfolgt die Ausgabe auf "stdout". Wiederholen Sie den Einlese- und Ausgabevorgang für jede Zeile bis das Dateiende erreicht ist.
3. Bestseller und Ladenhüter können während des Einlesens ermittelt werden. Überlegen Sie sich geeignete Datentypen und/oder Datenstrukturen zur Speicherung von Umsatzbetrag und Artikelbezeichnung.

6. Aufgabe:

typedef struct elem_t  elTyp; /* Vorwaertsdeklaration von elTyp */

struct elem_t 
  {
  elTyp *next;
  unsigned long Messwert;
  int Anz;
  };

1. Skizzieren Sie die angelegte Liste wenn 3 mal der Messwert 712, 4 mal der Messwert 813 und 1 mal der Messwert 611 eingebracht wurde!

2. Wodurch wird das Ende einer linearen Liste festgelegt?

3. Ehe für einen neu in die Liste aufzunehmenden Wert ein neues Knotenelement erzeugt wird, ist zunächst zu untersuchen ob bereits ein Knotenelement mit gleichem Messwert existiert. Dies ist Aufgabe der Funktion "LstSuchInc()", die die Liste dahingehend untersucht ob der Messwert bereits existiert, die Anzahl erhöht und den Zeiger auf diesen Knoten zurückliefert. Übergabeparameter sind der Messwert und der Zeiger auf das erste Listenelement (Wurzel). Im Misserfolgsfall - die Liste ist leer oder der Messwert befindet sich noch nicht in der Liste - ist der NULL-Zeiger zurückzugeben. Der Prototyp (Funktonsdeklaration) für "LstSuchInc()" lautet:

   elTyp *LstSuchInc(elTyp *wrz, unsigned long ulWert);
   

   Realisieren Sie "LstSuchInc()"!

4. Existiert der Messwert noch nicht, so ist ein neues Knotenelement am Ende der linearen Liste einzufügen. Dazu muss zunächst der Zeiger auf das aktuelle letzte Element ermittelt werden. Dies leistet die Funktion "GetLast()", die die Wurzel der Liste als Übergabeparameter erhält und den Zeiger auf das gesuchte letzte Element zurückliefert. Wie lautet der Prototyp von "GetLast()"?

5. Formulieren Sie "GetLast()" als Funktion in ANSI-C! Ist der Wert des Übergabeparameters NULL, so ist auch der Rückgabewert NULL zu setzen!

6. Unter Anwendung der bisher formulierten Funktionen kann nun die Funktion "WertEin()" konzipiert werden. Diese wird im folgendem Ausschnitt aus dem Hauptprogramm zum Eintragen des Messwertes in die Liste verwendet:

   int main(void) 
     {
     elTyp * wurzel;
     unsigned long ulWert;
     .....
     printf("\nWert: ");
     scanf ("%ld",&ulWert);
     if((wurzel = WertEin(wurzel, ulWert))== NULL)
        return EXIT_FAILURE;
     ..... 
     return EXIT_SUCCESS;
     }
   

   Realisieren Sie "WertEin()" als ANSI-C Funktion!

7. Mittels "CalcMittel()" ist der Mittelwert über alle Messwerte zu bilden. Zeichnen Sie ein geeignetes Struktogramm für diese Funktion! Formulieren Sie "CalcMittel()" in ANSI-C!