Basics

Question 1

Was besagt der euklidsche Algorithmus?

Answer 1

Der GGT zweier Zahlen ist auch GGT ihrer Differenz.

Question 2

Beschreibe den euklidschen Algorithmus iterativ.

Answer 2

while(a != b){
  if(a > b){
    a = a - b;
  }
  else{
    b = b - a;
  }
  ggT = a;
}

Question 3

Definition Algorithmus

Answer 3

Eine Anleitung zur Lösung einer Aufgabenstellung, die so präzise formuliert ist, dass sie “mechanisch” ausgeführt werden kann.

Question 4

Definition algorithmisches Problem

Answer 4

Problem, das mit einem Algorithmus gelöst werden kann.

Question 5

Eigenschaften von Algorithmen

Answer 5

• Determiniertheit: identische Eingaben führen stets zu identischen Ergebnissen
• Determinismus: Ablauf stets klar definiert (keine Wahlfreiheit)
• Terminierung: für jede Eingabe liegt ein Ergebnis nach endlich vielen Schritten vor.
• Effizienz: Aufwand relativ zu vorgegebenen Massstab

Question 6

Wie hängt ein Programm mit einem Algorithmus zusammen?

Answer 6

Jedes Programm repräsentiert einen bestimmten Algorithmus. Kein Programm ohne Algorithmus.

Question 7

Programm als Zustandstransformator. Hoare Triple

Answer 7

{Eingangszustand} Anweisung {Ausgangszustand}

Beispiel euklidscher Algorithmus: {a = 15, b = 12} c = ggt(a,b) {a = 15, b = 12, c = ggt(a,b)}

Question 8

Was ist die Aufgabe eines Datentyps in einer Methode?

Answer 8

Definition der gültigen Wertemenge, z.B. für die Precondition (Vorbedingung / Eingangswert)

Question 9

Was ist die Nachbedingung / Postcondition in einer Methode?

Answer 9

Die Wertebreiche der Rückgabeparameter.
Fehlerfälle werden formal durch checked Exceptions oder durch einen Spezialwert signalisiert. Informell durch einen Kommentar.

Question 10

Was ist die Vorbedingung / Precondition in einer Methode?

Answer 10

Die Anzahl und Wertebereiche der Parameter, die durch den Datentyp formal bestimmt sind und vom Compiler überprüfbar sind. Weitere informelle Einschränkungen des Wertebereichs im Kommentar.

Question 11

Wann wird ein Programm (= Folge von Anweisungen) als korrekt bezeichnet?

Answer 11

Wenn unter der Annahme, dass die Vorbedingung erfüllt ist, unter Anwendung des Programms die Nachbedingung erfüllt wird. “Die Vorbedingung impliziert die Nachbedingung”

Question 12

Nenne einige primitive / einfache Datentypen von Java

Answer 12

byte, short, int, long
float, double
char
boolean

Question 13

Nenne einige Referenzdatentypen von Java

Answer 13

array
string
objects

Question 14

Welche Datenstrukturen stellt der JDK zur Verfügung?

Answer 14

List
Hashtable
Collections
…

Question 15

Welche Datenstrukturen muss man z.T. selber implementieren bzw. gut verstehen?

Answer 15

Stacks
Queues
Trees
…

Question 16

Was sind ADT?

Answer 16

Abstrakte Datentypen

Question 17

Was ist das Konzept von Information Hiding?

Answer 17

Nur gerade soviel wie für die Verwendung einer Klasse nötig ist, wird auch für andere sichtbar gemacht.

Question 18

Ergänze die Lücken:

Jede Klasse besteht aus einer von aussen sichtbaren ……., und aus einer ausserhalb des Moduls unsichtbaren …………….

Answer 18

• Schnittstelle

- Implementation

Question 19

Wie werden Schnittstelle und Implementation von ADTs in Java umgesetzt?

Answer 19

• das interface beschreibt die Schnittstelle (enthält keine Implementation)
• die class implementiert die Schnittstelle

Beispiel: 
interface Stack {
     void push(Object obj);
     Object pop();
}

class MyStack implements Stack {

    void push(Object obj) {
           // Implementation
}
Stack stack = new MyStack();
}

• > Die Variable stack ist vom Typ des Interfaces
• > in Java kann eine Klasse mehrere Interfaces implementieren aber nur von einer Klasse erben

Question 20

Nenne eine “last in - first out” Datenstruktur

Answer 20

Stack

Question 21

Welche Operationen können auf einem Stack ausgeführt werden?

Answer 21

void push (Object x)
Object pop ()
Object peek() 
boolean isEmpty()
boolean isFull()
void removeAll()
size()

Question 22

Was macht die Methode peek() auf einem Stack?

Answer 22

Gibt das oberste Element als Rückgabewert zurück ohne es zu entfernen.

Question 23

What does LIFO stand for?

Answer 23

Last In First Out

Question 24

What causes a StackOverflowError?

Answer 24

Thrown when an application recurses too deeply.

Question 25

What’s postfix notation?

Answer 25

In a postfix expression, an operator is written after its operands. the infix expression 2+3 is 23+ in postfix notation. For postfix expressions, operations are performed in the order in which they are written (left to right).

Question 26

Nenne einige Anwendungen von Stacks

Answer 26

• Auswertung eines Ausdrucks in Postfix-Notation
• Überprüfung / Test auf korrekte Klammersetzung
• XML Wohlgeformtheit (each opening tag needs an closing tag)

Question 27

What’s the difference between a LinkedList and a ArrayList in Java? What would you use a LinkedList for?

Answer 27

An ArrayList internally stores the data in Arrays a LinkedList uses a doubly linked list. To simply store and access data an ArrayList is more efficient. To manipulate data the LinkedList is more efficient.

Question 28

What type of datastructure is a queue? LIFO or FIFO?

Answer 28

FIFO - die Objekte werden in derselben Reihenfolge entfernt wie sie eingefügt werden.

Question 29

Was sind die 3 minimalen Operationen einer Queue?

Answer 29

void enqueue (Obect x) throws Overflow;
-> legt ein neues Objekt in die Queue, falls noch nicht voll.
Object dequeue()
-> entfernt das zuerst eingefügte Objekt von der Queue. Gibt “null” zurück wenn das Objekt leer ist
boolean isEmpty()

Question 30

Was sind zusätzliche Operationen einer Queue?

Answer 30

Object peek()
void removeAll()
boolean isFull()

Question 31

Nenne einige praktische Anwendungen einer Queue

Answer 31

Warteschlangen werden in der Informatik oft eingesetzt. Beispiele: Drucker, der von mehreren Anwendern geteilt wird. CPU tasks scheduling. Call center phone system.

Question 32

What are the following variables: outIdx, inId?

Answer 32

outIdx: zeigt auf das älteste Element in der Queue in einer Array Implementation
inIdx: zeigt auf die nächste freie Stelle

Question 33

How is a ring buffer usually implemented?

Answer 33

Queue using an Array.

Question 34

Explain in 1-2 sentences how a priority queue works.

Answer 34

a priority queue basically functions like a queue (FIFO data structure) where the objects in the queue can be assigned a priority. Objects with higher priority move forward in the queue, objects of the same priority are removed in the order they came into the queue.