TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Antworten zum Einführungstest SS2014

Antworten zum Einführungstest SS2014

• Weblink: https://tuwel.tuwien.ac.at/
  

Vorwort

Dieser Eingangstest dient dazu, Ihnen unter Umständen vorhandene Schwächen in einzelnen Teilbereichen aufzuzeigen, die für diese LVA absolut notwendige Grundlagen darstellen, u.a. Vergleich von Funktionen, Modulorechnung und Rechenregeln für Potenzen und Logarithmen.

Der elektronische Eingangstest besteht aus 10 Multiple Choice Fragen, davon müssen Sie mindestens 80% (entspricht 8 Fragen bzw. 8 Punkten) korrekt beantworten, um den Test erfolgreich abzuschließen. Solange der Test freigeschaltet ist, können Sie diesen aber beliebig oft wiederholen. Es zählt immer Ihr bestes Ergebnis; nachdem Sie mindestens 80% der Fragen korrekt beantwortet haben, können Sie versuchen, noch ein besseres Resultat zu erreichen, müssen es aber nicht!

Mathematische Grundlagen

Rechenregeln für Exponenten

Wie kann man den angegebenen Term anders darstellen?

$\sqrt[4]{x^3}$

Richtige Antwort:

• $x^{\frac{3}{4}}$

Wie kann man den angegebenen Term anders darstellen?

$\frac{1}{x^3}$

Richtige Antwort:

• $x^{-3}$

Wie kann man den angegebenen Term anders darstellen?

$\frac{x^2+x^3}{\sqrt{x^3}}$

Richtige Antworten:

• $x^{\frac{1}{2}}+x^{\frac{3}{2}}$
• $\frac{x+x^2}{\sqrt{x}}$

Rechenregeln für Logarithmen

Wie kann man ${\log }_3(x)$ anders darstellen?

Richtige Antwort:

• $\frac{\ln (x)}{\ln (3)}$

Wie kann man $\log (x^3)$ anders darstellen?

Richtige Antwort:

• $3\cdot \log (x)$

Wie kann man $\log (\sqrt{\frac{a\cdot b}{c}})$ umformen?

Richtige Antworten:

• $(\log (a^{\frac{1}{2}})+\log (b^{\frac{1}{2}})-\log (c^{\frac{1}{2}}))$
• $\frac{1}{2}\ast (\log (a)+\log (b)-\log (c))$

Reihen

Wie lautet das Ergebnis folgender Summe?

$S(n)=\sum _{i=1}^{n}i$

Richtige Antworten:

• $S(n)=\frac{n^2+n}{2}$
• $S(n)=\frac{n(n+1)}{2}$

Wie lautet das Ergebnis folgender Summe?

$S=\sum _{i=0}^{\mathrm{\infty }}\frac{1}{2^i}$

Richtige Antwort:

• $S=2$

Rechenregeln für Modulorechnung

Welche Aussagen sind korrekt?

Richtige Antworten:

• $-4mod7=3mod7$
• $-4mod7=(7+3)mod7$

Welche Aussagen sind korrekt?

Richtige Antworten:

• $22mod4=(16mod4)+(6mod4)$
• $22mod4=(-11mod4)\ast (-2mod4)$

Laufzeitfunktionen

Laufzeitfunktionsgraphen

Welche ist die richtige, aufsteigende Reihenfolge folgender Laufzeiten:

$\mathrm{O}(n^2),\mathrm{O}({\log }_2(n)),\mathrm{O}(n!),\mathrm{O}(4^n),\mathrm{O}(\sqrt[4]{(}n)),\mathrm{O}(2^n),\mathrm{O}({\log }_4(n))$

Richtige Antwort:

• $\mathrm{O}({\log }_2(n))=\mathrm{O}({\log }_4(n))<\mathrm{O}(\sqrt[4]{(}n))<\mathrm{O}(n^2)<\mathrm{O}(2^n)<\mathrm{O}(4^n)<\mathrm{O}(n!)$

Welche ist die richtige, aufsteigende Reihenfolge folgender Laufzeiten:

$\mathrm{O}(n^3),\mathrm{O}(n\log (n)),\mathrm{O}(n),\mathrm{O}(3^n),\mathrm{O}(\sqrt[3]{(}n)),\mathrm{O}(5^n),\mathrm{O}(3\log (n))$

Richtige Antwort:

• $\mathrm{O}(3\log (n))<\mathrm{O}(\sqrt[3]{(}n))<\mathrm{O}(n)<\mathrm{O}(n\log (n))<\mathrm{O}(n^3)<\mathrm{O}(3^n)<\mathrm{O}(5^n)$

Laufzeitabschätzung

Welche Laufzeitabschätzung gilt für die beiden linearen Laufzeitfunktionen $l(n)$ und $m(n)$?

Richtige Antworten:

• $l(n)=\Theta (m(n))$
• $m(n)=\mathrm{O}(l(n))$
• $l(n)=\Omega (m(n))$
• $m(n)=\Omega (l(n))$

Schätzen Sie folgende Summe mit Hilfe der $\Theta$-Notation ab:

$S(n)=\sum _{i=1}^n{i}^2$

Richtige Antwort:

• $S(n)=\Theta (n^3)$

Laufzeiten von Algorithmen

Welche Laufzeit hat folgender Algorithmus in Abhängigkeit von n?

k = 2 * n;
for (a = 1 ... 30) {
    while (k > 0) {
        k = k - 1;
        z = z * 2;
    }
}

Richtige Antwort:

• $\Theta (n)$

Welche Laufzeit hat folgender Algorithmus in Abhängigkeit von n?

l = n * 3;
while( l > 1 ){
   a = a + 2;
   l = $\lfloor$ l / 3 $\rfloor$;
}

Richtige Antwort:

• $\Theta (lo{g}_3(n))$

Welche Laufzeit hat folgender Algorithmus in Abhängigkeit von n?

o = 2 * n;
while( o > 1 ){
   o = $\lfloor$ o / 2 $\rfloor$;
   for(p = 1...(n/2)){
      k = k + 1;
   }
}

Richtige Antwort:

• $\Theta (n\log (n))$

Welche Laufzeit hat folgender Algorithmus in Abhängigkeit von n?

z = n / 3;
while( z > 0 ){
   for(a = n...1){
      k = k - 1;
   }
   z = z - 1;
}

Richtige Antwort:

• $\Theta (n^2)$

Notationen

Welche der folgenden Definitionen ist korrekt?

Richtige Antworten:

• $\Theta (h(n))=\{j(n)|(\mathrm{\exists }{c}_1,c_2,n_0>0),(\mathrm{\forall }n\ge n_0):0\le c_{1}h(n)\le j(n)\le c_{2}h(n)\}$
• $\mathrm{O}(h(n))=\{j(n)|(\mathrm{\exists }c,n_0>0),(\mathrm{\forall }n\ge n_0):0\le j(n)\le ch(n)\}$
• $\Omega (h(n))=\{j(n)|(\mathrm{\exists }c,n_0>0),(\mathrm{\forall }n\ge n_0):0\le ch(n)\le j(n)\}$