Sie befinden sich hier: Termine » JRobots Programmierwettbewerb » forum   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

playground:altklausur [23.09.2012 17:30]
buntfalke angelegt
playground:altklausur [23.09.2012 17:30] (aktuell)
buntfalke angelegt
Zeile 1: Zeile 1:
 +==forum==
 +   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8074-Wissensfragen-24-02-2011]]
 +
 +==== Lösungsversuch ====
 +
 +
 +=== Aufgabe 1 - Wissensfragen (10P) ===
 +**a)** //Da die Klasse AssertionError eine Unterklasse von java.lang.Error ist, können Ausnahmen dieser Art nicht abgefangen und daher nicht behandelt werden.//
 +
 +**falsch**: Alle Fehlertypen,​ auch java.lang.Error und davon abgeleitete können mit catch abgefangen werden, obwohl das u.U. nicht immer sinnvoll ist; Fehler die von java.lang.Error abgeleitet sind, haben meist ein schwerwiegendes Problem als Ursache, so dass es sinnvoller sein kann, das Programm zu beenden als unter unklaren Bedingungen zu versuchen weiterzuarbeiten.
 +
 +**b)** //Ein AssertionError tritt in einer seiteneffektfreien assert-Anweisung auf, wenn die
 +Zusicherung während der Programmausführung nicht erfüllt ist, jedoch nur, falls das Prüfen von Zusicherungen durch die Java-VM beim Programmstart aktiviert wurde.//
 +
 +**wahr**.
 +
 +**c)** //Es kann kein Sortierverfahren für n Schlüssel existieren, das auf Vergleichen von Schlüsselpaaren beruht und dessen Laufzeitkomplexität besser als O(n · log<​sub>​2</​sub>​ n) ist.//
 +
 +**wahr**. Ich (dario) würde sagen, dass da log<​sub>​2</​sub>​ steht, prüft einfach nochmal ab, ob dem Prüfling klar ist dass O(log<​sub>​2</​sub>​ n) = O(log_a n) = O(log n)
 +
 +**d)** FIXME: code eintragen
 +f ∈ O(log n); g ∈ O(n log n);
 +
 +**e)** //Die Suche nach einem Element in einer sortierten doppelt-verketteten Liste der Länge n ohne wahlfreien Zugriff hat eine Laufzeitkomplexität von O(n).//
 +
 +**wahr**: "ohne wahlfreien Zugriff"​ => man muss die Liste entlanglaufen,​ bis man das gesuchte Element gefunden hat, die Tatsache dass die Liste sortiert ist, hilft in demt Moment nicht allzuviel.
 +
 +**f)** //Verwendet man zum Einfügen in einen Streuspeicher (Tabellenlänge n) das sogenannte quadratische Sondieren, so hat die Operation eine Laufzeitkomplexität von O(log(n)).//​
 +
 +**falsch**: Die Reihenfolge wie die Felder der Streutabelle sondiert werden, ist zwar unterschiedlich,​ insgesamt werden im worst case aber trotzdem alle Felder einmal besucht, also ist die Komplexität O(n).
 +
 +**g)** //In einem gerichteten Graphen G = (V, E) repräsentiert der Ausgangsgrad eines Knotens n ∈ V die Anzahl aller Knoten m ∈ V , für die es eine Kante (n, m) ∈ E gibt.//
 +
 +**wahr**.
 +
 +
 +**h)** //​Mehrfachvererbung von mehreren nicht-abstrakten Oberklassen ist in UML-Klassendia-
 +grammen (genau wie in Java) verboten.//
 +
 +**falsch**: Da UML nicht Java-spezifisch ist, und z.B. in C++ Mehrfachvererbung möglich ist, ist auch in UML Mehrfachvererbung erlaubt.
 +
 +
 +**i)** //Folgender Code verwendet Generics korrekt im Sinne der Sprache Java und ist daher
 +gültig und ubersetzbar://​ FIXME: add code
 +
 +**wahr** (ich (dario) kann keinen fehler erkennen ;)
 +
 +**Frage:** Habe gelesen, dass man bei Generics nur die Methoden von Object aufrufen kann, hier wird aber .getTitle() aufgerufen. Ist das nicht ein Fehler? (Dank an dario für die guten Erklärungen)
 +
 +**Antwort:​** Man kann alle Methoden die der generische Typ hat Aufrufen. Im Fall von <T> waere das in der Tat nur Methoden von Object (weil in Java alle Klassen von Object automatisch erben). Hier steht aber <T extends Book>, d.h. es koennen auch Methoden der Klasse Book aufgerufen werden, da der generische Typ von Book erben muss.
 +
 +
 +=== Aufgabe 2 - Bäume (20P) ===
 +
 +**a)**
 +
 +==Adjazenzmatrix==
 +|     ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^
 +^ A |   ​- ​ |  + |   ​- ​ |   ​- ​ |   ​- ​ |  -  |  + |
 +^ B |  +  |  -  |   ​- ​ |  +  | +  |  + |  -  |
 +^ C |  -   ​| ​ -  |   ​- ​ |  +  |  -   ​| ​ -  |  -  |
 +^ D |  -  |  + |  +  |  -  |   ​- ​ |  -  |  -   |
 +^ E |  -  |  + |  -   ​| ​ -  |   ​- ​ |  -  |  -  |
 +^ F |  -  |  +  |  -  |  -  |  -  |  -  |  -  |
 +^ G | + |  -  |  -  |  -  |  -  |  -  |  -  |
 +
 +==Graphische Darstellung==
 +{{:​pruefungen:​bachelor:​audklausur_ws10_aufgabe2.png}}
 +
 +
 +**b)**
 +//Geben Sie zu jedem Knoten des neuen Baums X dessen Höhe in X an://
 +^ A ^ B ^ C ^ D ^ E ^ F ^ G ^
 +|  0  |  1  |  4  |  3  |  3   | 3  |  1  |
 +
 +
 +**c)**
 +//​Betrachten Sie den neuen Baum X als sogenannten Out-Tree“ (bei dem die Kanten gerichtet von der Wurzel ausgehen) und geben Sie ihn in Mengenschreibweise an://
 +
 +**Mengenschreibweise**
 +X = (V, E, r) mit Knotenmenge V , Kantenmenge E und Wurzel r \\
 +V = {A, B, C, D, E, F, G} \\
 +E = {{AB}, {AG}, {BD}, {BE}, {BF}, {DC}} \\
 +r = A \\
 +
 +**d)**
 +//Schreiben Sie eine Methode isUndirected,​ die feststellt ob eine Adjazenzmatrix amx
 +einen ungerichteten Graphen darstellt.//​
 +
 +Zunächst einmal muss man sich klar machen, dass ein Graph genau dann ungerichtet ist, wenn die Adjazenzmatrix sowohl einen Eintrag (AB) als auch einen Eintrag (BA) hat.
 +
 +<code java>
 +/**
 + * die idee is, einfach die ganze adjazenzmatrix durch zu gehen
 + * und zu schaun ob alle einträge mit ihren "​gegenüberliegenden"​
 + * - also an der diagonale gespiegelten (indices vertauscht) -
 + * übereinstimmen. falls nicht, ist der graph gerichtet.
 + **/
 +public boolean isUndirected(boolean[][] amx) {
 + for(int i= 0; i < amx.length; i++) {
 + for(int j= 0; j < amx[0].length;​ j++) {
 + if(amx[i][j] != amx[j][i]) {
 + return false;
 + }
 + }
 + }
 + return true;
 +}
 +</​code>​
 +
 +(dario): ich geb zu, es is nicht der effizienteste code (wer will kann den mal dazuschreiben),​ aber in der klausur kommts erstmal drauf an, dass der code tut was er soll, und nicht ob er dass in O(n) oder O(n<​sup>​2</​sup>​) tut (abgesehen davon, dass es selbst wenn man nur die hälfte vergleicht noch O(n<​sup>​2</​sup>​) bleibt).
 +
 +=== Aufgabe 3 ===
 +**a)** 96
 +
 +**b)** von hinten nach vorne
 +
 +**c)**
 +
 +^ Stelle ^ Reihung ^
 +|  -  |  de  |  com  |  es  |  net   | ch  |  ee   ^
 +|  3 |  de  |  es  |  ch   ​| ​ ee   | com  |  net   ^
 +|  2 |  de  |  ee  |  net   ​|ch ​  ​| ​ com  | es     ^
 +|  1 |  ch  | com | de  |  ee  | es |  net  |
 +
 +**d)**
 +<code java>
 +public static char getChar(String str, int pos){
 + return (pos < str.length()) ? (str.charAt(pos)) : (char) 96;
 + }
 +
 + public static void radixSort(String[] array){
 + ArrayList<​String>​[] buckets = (ArrayList<​String>​ []) new ArrayList[27];​
 +
 + for(int i = 0; i < 3; ++i){
 + for(int j = 0; j < 27; ++j){
 +
 + buckets[j] = new ArrayList<​String>​();​
 +
 +
 + }
 + for(int j = 0; j < array.length;​ ++j){
 + buckets[(int)getChar(array[j],​2-i) - 96].add(array[j]);​
 +
 + }
 + int k = 0;
 + for( int j = 0; j < 27; ++j){
 + for(String str : buckets[j]){
 + array[k++] = str;
 +
 + }
 + }
 + }
 + }
 +</​code>  ​
 +
 +=== Aufgabe 4 ===
 +
 +=== Aufgabe 5 - ADT (11 Punkte) ===
 +
 +**a)** getPublishDate(createPost(s,​ 24.02.2011, b)
 +
 +**b)** 01.01.1970
 +
 +**c)** createPost(s,​ d, true)
 +
 +**d)** ???
 +
 +**e)** ???
 +
 +**f)** ​
 +
 +publish(setSeen(P,​true),​ id2, F) wenn id1 == id2
 +
 +publish(setSeen(P,​ id2, markSeen(id1,​ F)) falls id1 != id2
 +
 +=== Aufgabe 6 ===
 +
 +=== Aufgabe 7 ===
 +
 +=== Aufgabe 8 ===