ChiefExam

Page information

Bei den folgenden Aufgaben werden richtige Kreuze positiv (+) und falsche oder fehlende Kreuze entsprechend negativ (–) bewertet. Jede Teilaufgabe wird mit mindestens 0 Punkten bewertet. Pro Teilaufgabe ist mind. eine Aussage wahr. Kreuzen Sie alle richtigen Aussagen an.

Task 1

(2 points, multiple response)

Welche der folgenden Aussagen zu Datentypen in Java ist/sind korrekt?

Arrays haben eine garantierte Zugriffszeit von \(\mathcal{O}(1)\) auf ein Element bei einem gegebenen Index.

Eine LinkedList in Java implementiert sowohl das Interface List als auch das Interface Queue.

Eine LinkedList ist im wahlfreien Zugriff in der Regel schneller als eine ArrayList.

Die Überprüfung, ob ein Element in einer Liste liegt, ist bei einer LinkedList asymptotisch aufwendiger als bei einer ArrayList.

Task 2

(2 points, multiple response)

Gegeben sei folgender, noch nicht fertig ausformulierter ADT:

adt Nat
// ADT for comparisons between natural numbers
sorts Nat, Boolean
ops
zero: \(\rightarrow\) Nat // creates the number 0
suc: Nat \(\rightarrow\) Nat // gives the successor of a natural number
greater: Nat \(\times\) Nat \(\rightarrow\) Boolean // indicates, if the first number is greater than second number
axs
// TODO
end Nat

Welche der folgenden Axiome passen zu dem gegebenen ADT?

greater(zero, x) = false

greater(suc(x), zero) = true

greater(suc(x), suc(y)) = greater(x, y)

suc(greater(x, y)) = greater(x, y)

Task 3

(3 points, multiple response)

Der folgende Quellcode zeigt eine Implementierung einer Queue, welche auf der Verwendung zweier Stacks basiert:

public class Queue<T> {
	private Stack<T> in = new Stack<T>(), out = new Stack<T>();

	public void push(T ele) { in.push(ele); }
	public void T pop() {
		if(out.isEmpty()) {
			while(!in.isEmpty()) out.push(in.pop());
		}
		return out.pop();
	}
}

Gehen Sie im Folgenden davon aus, dass alle Funktionen eines Stacks eine Laufzeit \(\mathcal{O}(1)\) besitzen. Welche der folgenden Aussagen ist/sind dann korrekt?

Das Erzeugen einer Queue mittels new Queue<boolean>(); ist gültiger Java-Code.

Die Laufzeit für das Einfügen von \(n\) Elementen und das anschließende Herausnehmen eines Elementes liegt in \(\mathcal{O}(n)\).

Die Laufzeit für das Einfügen von \(n\) Elementen und das anschließende Herausnehmen von \(n\) Elementen liegt in \(\mathcal{O}(n)\).

Die Laufzeit für das Einfügen von \(2n\) Elementen und das anschließende Herausnehmen von \(n\) Elementen liegt in \(\Theta (n^2)\).

Overview

Page 1 of 3: Wissensfragen