Informatik (Fach) / DAP1 (Lektion)

Datenstrukturen, Algorithmen und Programmierung 1

Diese Lektion wurde von checko erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Sortiere die nachstehenden Zahlen in dieser Reihenfolge in einen binären Suchbaum ein. 41, 23, 59, 29, 47, 31, 15, 22 41 -r-> 59 -l-> 47      -l-> 23 -r-> 29 -r-> 31             23 -l-> 15 -r-> 22
• Sortiere die nachstehenden Zahlen in dieser Reihenfolge in einen binären Suchbaum ein. 22, 27, 32, 25, 31, 15, 62 22 -r-> 27 -r-> 32 -r-> 62                         32 -l-> 31             27 -l-> 25 22  -l-> 15
• Konstruiere einen Moore-Automaten, der in einer Folge von Zeichen folgendes Muster erkennt: aababa (tabellarische Notation, d.h.: Spalten = Zustände, Zeilen gleich Zeichen) Zust. 0: a -> 1, b -> 0, sonst -> 0 Zust. 1: a -> 2, b -> 0, sonst -> 0 Zust. 2: a -> 2, b -> 3, sonst -> 0 Zust. 3: a -> 4, b -> 0, sonst -> 0 Zust. 4: a -> 2, b -> 5, sonst -> 0 Zust. 5: a -> 6, b -> 0, sonst -> 0 Zust. 6: a -> 2, b -> 0, sonst -> 0
• Konstruiere einen Moore-Automaten, der in einer Folge von Zeichen folgendes Muster erkennt: xyzxy (tabellarische Notation, d.h.: Spalten = Zustände, Zeilen gleich Zeichen) Zust. 0: x -> 1, y -> 0, z -> 0, sonst -> 0 Zust. 1: x -> 1, y -> 2, z -> 0, sonst -> 0 Zust. 2: x -> 1, y -> 0, z -> 3, sonst -> 0 Zust. 3: x -> 4, y -> 0, z -> 0, sonst -> 0 Zust. 4: x -> 1, y -> 5, z -> 0, sonst -> 0 Zust. 5: x -> 1, y -> 0, z -> 3, sonst -> 0
• Bestimme die Codierung der nachstehenden Zeichen mit Hilfe des Huffman-Algorithmus a (15), b(20), c(30), d(100), e(105), f(110), g(120) a: 11010, b: 11011, c: 1100, d: 111, e: 00, f: 01, g: 10
• Bestimme die Codierung der nachstehenden Zeichen mit Hilfe des Huffman-Algorithmus a (30), b(20), c(10), d(15), e(80) a: 00, b: 010, c: 0110, d: 0111, e: 1
• Polymorphie: Lösen der Aufgabe 3 (Klausur vom 21.1.13) Y Y L L E L M D
• Schreibe die Klasse box, die einen Quader beschreibt. Die Attribute sind die Länge, Breite und Höhe des Quaders, welche durch einen gegeben Konstruktur definiert werden. Implementieren Sie drei Methoden, die das Volumen (getVolumeSize), die Oberfläche (getAreaSize) und die Summe der Kantenlängen (getEdgesLength) berechnen und zurückgeben. public double getVolumeSize() { return width * height * depth; } public double getAreaSize() { return 2 * (width * height + width * depth + height * depth); } public double getEdgesLength() { return 4 * (width + height + depth); }
• Schreibe die Klasse box, die einen Quader beschreibt. Die Attribute sind die Länge, Breite und Höhe des Quaders, welche durch einen gegeben Konstruktur definiert werden. Implementiere die Methode "boolean isCube()", welche den Wert true zurückgeben soll, falls es sich um einen Würfel handelt, also alle Kanten die gleiche Länge besitzen. public boolean isCube() { return (width == height) && (width == depth); }
• Schreibe die Klasse box, die einen Quader beschreibt. Die Attribute sind die Länge, Breite und Höhe des Quaders, welche durch einen gegeben Konstruktur definiert werden. Implementiere die Methode "int compareTo( Box f )", welche dazu dient, zwei Kisten miteinander zu vergleichen, das aufrufende Objekt und das als Parameter übergebene Objekt. Als Ergebnis soll zurückgegeben werden: – einen Wert größer als 0, falls die aufrufende Box ein größeres Volumen als die als Parameter übergebene Box besitzt, – der Wert 0, falls beide Kisten das gleiche Volumen besitzen, – einen Wert kleiner als 0, falls die aufrufende Box ein kleineres Volumen als die als Parameter übergebene Box besitzt. (Die Methode getVolume, welche das Quadervolumen berechnet, ist gegeben.) public int compareTo(Box f) {  double v1 = getVolumeSize();  double v2 = f.getVolumeSize();  if (v1 > v2)  {   return 1;  }  else if (v1 == v2)  {   return 0;  }  else  {   return -1;  } }
• Schreibe die Klasse box, die einen Quader beschreibt. Die Attribute sind die Länge, Breite und Höhe des Quaders, welche durch einen gegeben Konstruktur definiert werden. Implementiere eine Methode "encloses", die bestimmt, ob eine als Parameter übergebene Kiste bei parallel liegenden Seitenflächen vollständig in das aufrufende Objekt echt eingepasst werden kann, und einen entsprechenden Wahrheitswert zurückliefert. Beachten Sie bei der Implementierung, dass Kisten gedreht werden können: Eine Kiste 30x20x10 passt echt in eine Kiste 11x31x21. public boolean encloses(Box f) { // teste alle moeglichen Kombinationenreturn (width >= f.width && height >= f.height && depth >= f.depth)   || (width >= f.width && height >= f.depth && depth >= f.height)   || (width >= f.height && height >= f.width && depth >= f.depth)   || (width >= f.height && height >= f.depth && depth >= f.width)   || (width >= f.depth && height >= f.width && depth >= f.height)   || (width >= f.depth && height >= f.height && depth >= f.width); }
• Implementieren eine Methode, die die Quersumme einer Zahl berechnet. - iterativ - public static int digitSum( int y ) {  int x = abs(y);  int sum = 0;  while (x > 0)  {    sum = sum + x%10;    x = x/10;  }  return sum; }
• Implementieren eine Methode, die die Quersumme einer Zahl berechnet. - rekursiv - public static int digitSum( int n ) {   n = Math.abs(n);   if (n < 10)   {      return n;   }   else   {       return n%10 + digitSum(n/10);   } }
• Implementieren eine Methode, die prüft, ob die drei übergebenen Zahlen ein pythagoreisches Zahlentriple sind. public static boolean isPythaTriple( int a, int b, int c ) {   int aSquare = a*a;   int bSquare = b*b;   int cSquare = c*c;   return (aSquare + bSquare == cSquare || (aSquare + cSquare == bSquare)     || (bSquare + cSquare == aSquare);}
• Implementiere eine Methode, die die nte harmonische Zahl berechnet, d.h. die Brüche 1/1 bis 1/n aufsummiert. -rekursiv- public static double harm( int n ) {   if (n < 1) throw new RuntimeException();    if (n == 1)     return 1.0;   else     return 1.0/n + harm(n-1); }
• Implementiere eine Methode, die die nte harmonische Zahl berechnet, d.h. die Brüche 1/1 bis 1/n aufsummiert. -iterativ- public static double harm( int n ) {   if (n < 1) {throw new RuntimeException()};    if (n == 1) {   int sum = 0;   for (int i = 0; i <= n; i++) {     sum = sum + 1/i;   }   return sum; }
• Implementiere eine Methode, die den Binärcode eines Integer-Werte ermittelt und als String zurückgibt. (rekursiv) Hinweis: Die Binärdarstellung einer Dezimalzahl ergibt sich aus den rückwärts zusammengefassten Resten einer wiederholt ausgeführten Division der Zahl durch 2. public static String binaryCode(int i) {   if (i < 0) throw new RuntimeException();    if (i < 2)   {      return ""+ i;   }   else   {      return binaryCode(i/2) + i%2;   } }
• Entwickele eine Methode "int maximum( int[] arr, int i )", die für ein Feld arr das Maximum im Bereich von arr[0] bis arr[i] mit 0<=i<arr.length bestimmt und zurückgibt. -rekursiv- public static int maximum(int[] arr, int i) {  if (i<0 || i>=arr.length)   {    throw new RuntimeException();   }   if (i == 0)  {    return arr[0];   }  else  {    int max = maximum(arr, i-1);    if (arr[i] > max)     return arr[i];    else    return max;  } }
• Entwickele eine Methode "int maximum( int[] arr, int i )", die für ein Feld arr das Maximum im Bereich von arr[0] bis arr[i] mit 0<=i<arr.length bestimmt und zurückgibt. -iterativ- public static int maximum( int[] arr ) {  if (arr.length == 0)   {     return 0;  }  int max = arr[0];  for (int number : arr)  {     if (max < number)     {        max = number;     }  }   return max; }
• Implementiere eine Methode "checkArray", die überprüft, ob das übergebene Feld ein Palindrom ist. D.h. das Feld ist vorwärts und rückwärts gelesen identisch. -iterativ- public static boolean checkArray(int[] f) {  if (f.length == 0) {return false};  int i = 0;  int n = f.length-1;   while ( i < n )  {    if (f[i] != f[n]) return false;    i++;    n--;  }  return true; }
• Implementiere eine Methode "checkArray", die überprüft, ob das übergebene Feld ein Palindrom ist. D.h. das Feld ist vorwärts und rückwärts gelesen identisch. -rekursiv- public static boolean checkArray(int[] arr, int i) {  if (i<0 || i>arr.length-1)  {  return false;}  else  {     int j=arr.length-1-i; /* rechter Index */     if (i > j)     {       return true;     }     else     {       return arr[i] == arr[j] && palindromCheck(arr, i+1);     }  } }
• Welche drei Möglichkeiten gibt es einen binären Suchbaum zu durchlaufen? Worin unterscheiden sie sich? Betrachte dabei den folgenden binären Suchbaum: 10 -l-> 5 -l-> 2; 10 -l-> 5 -r-> 7; 10 -r-> 15 -r-> 20; 10 -r-> 15 -l-> 12 (Reihenfolge der Zahlen für jede Variante angeben) PreOrder: Wurzel-links-rechts (10, 5, 2, 7, 15, 12, 20) InOrder: links-Wurzel-rechts (2, 5, 7, 10, 12, 15, 20) PostOrder: links-rechts-Wurzel (2, 7, 5, 12, 20, 15, 10)
• Implementiere die Methode "showPreOrder", die die Inhalte der Knoten des Baums in der Folge eines PreOrder-Durchlaufs anzeigt. Die Methode "toString" von der Klasse "HuffmanTriple" muss dabei für die Ausgabe verwendet werden. (Hinweis: Diese Aufgabe bezieht sich auf die Klasse CharacterSearchTree. Die Methoden isLeaf() und isEmpty() sind gegeben.) public void showPreorder() {  if ( !isEmpty() ) {     if ( isLeaf() ) {        System.out.print( '*' );     }     System.out.println( content.toString() );     leftChild.showPreorder();     rightChild.showPreorder(); } }
• Implementiere eine Methode "containsCharacter", die prüft, ob ein als Parameter übergebenes Zeichen im Baum als Wert des Attributs token eines HuffmanTriple-Objekts auftritt. In diesem Fall soll true zurückgegeben werden, sonst false. Ein leerer Baum soll false liefern. (Hinweis: Diese Aufgabe bezieht sich auf die Klasse CharacterSearchTree. Die Methoden isLeaf() und isEmpty() sind gegeben.) public boolean containsCharacter( char t ) {  if ( !isEmpty() ) {     if ( content.getToken() > t ) {        return leftChild.containsCharacter( t );     }     else if ( content.getToken() < t ) {        return rightChild.containsCharacter( t );     }     else {        return true;     }  }  return false; }
• Implementiere eine Methode "equalStructure", die einen Parameter des Typs CharacterSearchTree besitzt. Die Methode soll true zurückgeben, falls der aufrufende Baum und der als Argument übergebene Baum die gleiche Struktur besitzen, also an den gleichen Positionen in den Bäumen Knoten bzw. Nachfolger auftreten. Die Inhalte der Knoten sollen dabei unberücksichtigt bleiben. (Hinweis: Diese Aufgabe bezieht sich auf die Klasse CharacterSearchTree. Die Methoden isLeaf() und isEmpty() sind gegeben.) public boolean equalStructure( CharacterSearchTree cst ) {   if ( isEmpty() ) {      return cst.isEmpty();   } else if ( cst.isEmpty() ) {      return false;   } else { return leftChild.equalStructure( cst.leftChild ) && rightChild.equalStructure( cst.rightChild );   } }
• Implementiere die Methode "contains( Object o )", welche true zurückgeben soll, wenn der Inhalt o in den Elementen der Liste vorkommt. Dabei soll die Gleichheit mit der Methode equals (von der Klasse object) überprüft werden. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public boolean contains( Object o ) {   Element current = first;   while ( current != null ) {      if (    ( o == null && current.getContent() == null )                 || ( o != null && o.equals( current.getContent() ) )   ) {         return true;      }      current = current.getNext();   }   return false; }
• Implementiere die Methode "count( Object o )", welche die Häufigkeit zurückgeben soll, mit der der Inhalt o in den Elementen der Liste vorkommt. Dabei soll die Gleichheit mit der Methode equals überprüft werden. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public int count( Object o ) {  int tally = 0;  Element current = first;  while ( current != null ) {     if ( ( o == null && current.getContent() == null )            || ( o != null && o.equals( current.getContent() ) )    ) {     tally++;  }   current = current.getNext();  }  return tally; }
• Implementiere die Methode "insert( int n, Object o )", welche ein neues Element mit dem Inhalt o hinter dem Element am Index n in die Liste einfügt. Hat die Liste weniger als n Elemente, so soll eine RuntimeException geworfen werden. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public void insert( int n, Object o ) {   Element pre = elementAt( n );   Element suc = pre.getNext();   Element elm = new Element( o );   pre.connectAsNext( elm );   if ( suc == null )  {      last = elm;   } else {      suc.connectAsPrevious( elm );    }   size++; } private Element elementAt( int index ) {   if ( index >= 0 && index < size ) {      Element current = first;      for ( int i = 0; i < index; i++ ) {           current = current.getNext();      }      return current;   } else {      throw new RuntimeException();   } }
• Implementiere die Methode "remove( Object o )" soll alle Elemente aus der Liste löschen, die den Inhalt o besitzen. Dabei soll die Gleichheit mit der Methode "equals" (von der Klasse "object") überprüft werden. Beachten Sie die Sonderfälle, dass das einzige, das erste oder das letzte Element gelöscht wird. Tritt kein Element mit dem Inhalt o auf, soll nichts geschehen. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public void remove( Object o ) {  Element candidate = first;  Element nextCandidate;  while ( candidate != null ) {     nextCandidate = candidate.getNext();     if ( ( o == null && candidate.getContent() == null )           || ( o != null && o.equals( candidate.getContent() ) )    ) {        if ( candidate == first && candidate == last ) {           first = last = null;        }         else if ( candidate == first ) {           first = candidate.getNext();           first.disconnectPrevious();        }         else if ( candidate == last ) {           last = last.getPrevious();           last.disconnectNext();        }       else {           candidate.getPrevious().connectAsNext( candidate.getNext() );        }     size--;     }   candidate = nextCandidate;   } }
• Welche drei Strategie-Klassen sind aus der Vorlesung bekannt? Welche abstrakte Methode enthalten sie? Wie verhalten sich die Klassen gegenüber einer doppelt-verlinkten Liste? a) SubstitutingStrategy; Methode: subsitute; Verhalten: Ersetzt den Inhalt eines Objekte durch einen Anderen. b) TraversingStrategy; Methode: inspect; Verhalten: Benutzt den Inhalt eines Objektes für weitere Befehle. Das Listenelement bleibt dabei unverändert. c) FilteringStrategy; Methode: select; Verhalten: Löscht das ausgewählte Objekt aus der Liste.
• Implementiere die Strategie "DoubleAllInIntervalStrategy", welche in einer Liste alle int-Werte aus einem (geschlossenen) Intervall [bottom,top] verdoppeln soll. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public class DoubleAllInIntervalStrategy extends DoublyLinkedList.SubstitutingStrategy<Integer> {   private int lowerBound, upperBound;   public DoubleAllInIntervalStrategy( int low, int up ) {     lowerBound = low;     upperBound = up;   }    public Integer substitute( Integer ref ) {     if ( ref >= lowerBound && ref <= upperBound ) {        return 2 * ref;     } else {        return ref;     }   }}
• Implementiere die Strategie "CountInIntervalStrategy", welche zählen soll, wie häufig die int-Werte aus einem (geschlossenen) Intervall [bottom,top] in einer Liste vorkommen. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public class CountInIntervalStrategy extends DoublyLinkedList.TraversingStrategy<Integer> {   private int lowerBound, upperBound;   private int quantity;    public CountInIntervalStrategy( int low, int up ) {     lowerBound = low;     upperBound = up;     quantity = 0;   }    public void inspect( Integer ref ) {     if ( ref >= lowerBound && ref <= upperBound ) {        quantity++;     }   }    public int getQuantity() {     return quantity;   } }
• Implementiere die Strategie "RemoveAndCountAllInIntervalStrategy", welche alle Elemente mit einem int-Wert aus einem (geschlossenen) Intervall [bottom,top] aus einer Liste löschen soll. Zusätzlich soll die Strategie zählen, wie viele Elemente gelöscht worden sind. (Hinweis: Die Methoden "isEmpty()", "size()" und die Klasse "Element" inkl. ihrer Methoden sind gegeben.) public class RemoveAndCountAllInIntervalStrategy extends DoublyLinkedList.FilteringStrategy<Integer> {   private int lowerBound, upperBound;   private int quantity;    public RemoveAndCountAllInIntervalStrategy( int low, int up ) {     lowerBound = low;     upperBound = up;     quantity = 0;   }    public boolean select( Integer ref ) {     if( ref >= lowerBound && ref <= upperBound ) {       quantity++;       return true;     } else {       return false;     }   }    public int getQuantity() {     return quantity;   } }

zurück  |  weiter 1 / 1