Hemtal 3

1. Kommer en postorder-utskrift av noderna i ett binärträd att ge noderna i omvänd ordning mot en preorder-utskrift?
2. Ett binärträds noder är antingen löv eller inre noder. Kan ett binärträd ha fler inre noder än löv? Rita och förklara!
3. Kan man använda parametrar i rekursiva funktioner?
4. Ett matrisproblem tar tid T(n)=k*n3 att lösa, där n är matrisens storlek. Om n ökar med en faktor tio, kan vi då kompensera det genom att köpa en dator som är tio gånger snabbare?
5. Är komplexiteten för binärsökning i en vektor/lista alltid densamma som komplexiteten för sökning i ett binärt sökträd?
6. Ordna följande funktioner efter hur snabbt dom växer:
   N, N2, Nlog(N), Nlog(N2), 1/N, 3N, 2N/5, 1009, N3, N2log(N)
7. Hur skiljer sig breddenförstsökning från djupetförstsökning? Rita och berätta!

• Föreslå en metod för att lösa följande problem:
  Vilka ord kan man bilda av bokstäverna i ordet "komplexitet"? Några exempel är orden "lim", "textil" och "tio".
  Rita och berätta hur man skulle kunna lösa problemet ovan med ett program (men skriv inte programkoden).

En av Pythons inbyggda datastrukturer är dictionary. Läs om den i en Python-bok eller på docs.python.org och svara på följande frågor:

1. Hur skapar man en tom dictionary?
2. Hur lägger man in nya värden?
3. Hur hämtar man ett lagrat värde?
4. Vad gör metoden keys()?
5. Vad gör metoden values()?
6. Vad skulle du använda en dictionary till?