{"id":574,"date":"2019-08-14T20:52:56","date_gmt":"2019-08-14T18:52:56","guid":{"rendered":"https:\/\/fsr.cs.uni-potsdam.de\/?p=574"},"modified":"2019-08-14T20:52:56","modified_gmt":"2019-08-14T18:52:56","slug":"grundlagen-der-programmierung-ii-2011","status":"publish","type":"post","link":"https:\/\/fsr.cs.uni-potsdam.de\/?p=574","title":{"rendered":"Grundlagen der Programmierung II 2011"},"content":{"rendered":"\n

Aufgabe 1 (8+5 Punkte)<\/h1>\n\n\n\n
  1. Schreiben sie ein Programm in PASCAL, das die Zahlen in einem File
    \nf: file of integer<\/code>
    \nin umgekehrter Reihenfolge ausgibt. (Bemerkung: Das File ist gro\u00df, d.h.\nsie k\u00f6nnen den Fileinhalt nicht in den Hauptspeicher einlesen)\n<\/li>
  2. Bestimmen sie die Ordnung der Laufzeit ihres Programms im schlimmsten Fall.\n<\/li><\/ol>\n\n\n\n

    Aufgabe 2 (4 Punkte)<\/h1>\n\n\n\n

    \nF\u00fcr die Schl\u00fcssefolge\n<\/p>\n\n\n\n

    \nA, B, C, D, E, F, G\n<\/p>\n\n\n\n

    \nkonstruiere man einen AVL-Suchbaum (mit maximaler H\u00f6he), dessen Knoten\nnur die Balancen 0 und +1 besitzen. Anschlie\u00dfend entferne man den\nSchl\u00fcssel A aus diesem AVL-Baume (bitte Zwischenschritte angeben).\n<\/p>\n\n\n\n

    Aufgabe 3 (2+2+2+2 Punkte)<\/h1>\n\n\n\n

    \nBeantworten sie die folgenden Fragen und begr\u00fcnden sie ihre Antwort\njeweils mit ein\/zwei S\u00e4tzen. Ohne Begr\u00fcndung gibt es keine Punkte.\n<\/p>\n\n\n\n

    1. Wahr oder falsch? Mit einer einfach verketteten Liste kann man einen Stack nicht so realisieren, dass die Operationen push<\/code> und pop<\/code> in konstanter Zeit laufen.\n<\/li>
    2. Wahr oder falsch? Beim L\u00f6schen eines Elements v<\/code> – wobei als Eingabe nur ein Zeiger auf v<\/code>\n gegeben ist – in einer linearen Liste ist die Verwendung von doppelt\nverketteten Listen gegen\u00fcber der Verwendung von einfach verketteten\nListen von Vorteil.\n<\/li>
    3. Wahr oder falsch? Das Maximum eines bin\u00e4ren Suchbaums kann keinen linken Sohn haben.\n<\/li>
    4. Wahr oder falsch? Bei einem bin\u00e4ren\nSuchbaum steht in der Wurzel immer der Median der Elemente, die in dem\nBaum gespeichert sind.\n<\/li><\/ol>\n\n\n\n

      Aufgabe 4 (2+2+2+2 Punkte)<\/h1>\n\n\n\n

      \nWelche Aussagen sind richtig, welche falsch? Es ist jeweils eine Begr\u00fcndung anzugeben.\n<\/p>\n\n\n\n

      1. 5 n log n = O(n)<\/code>\n<\/li>
      2. 5n + 2n2<\/sup>+7n3<\/sup> = O(n3<\/sup> log n)<\/code>\n<\/li>
      3. n * 2n<\/sup> = O(3n<\/sup> * log n)<\/code>\n<\/li>
      4. 4n log n - 3n + 17 sqrt(n) = O(n log n)<\/code>\n<\/li><\/ol>\n\n\n\n

        Aufgabe 5 (8 Punkte)<\/h1>\n\n\n\n

        \nGegeben sei folgender Graph:\n<\/p>\n\n\n\n

        \n(\u2026 Graph ist noch zu migrieren \u2026 )\n<\/p>\n\n\n\n

        \nBestimmen sie mit dem Algorithmus von Dijkstra alle k\u00fcrzesten Wege von A zu allen anderen Knoten.\n<\/p>\n\n\n\n

        Aufgabe 6 (3+3+3 Punkte)<\/h1>\n\n\n\n

        \nVerwenden sie das Master-Theorem zur L\u00f6sung der folgenden\nRekursionsgleichungen. Geben sie dabei jeweils an, welcher Fall des\nMaster-Theorems angewendet werden kann und weisen sie nach, dass die\nVoraussetzungen zur Anwendung dieses Falls erf\u00fcllt sind.\n<\/p>\n\n\n\n

        1. T(n) = 3 T(n\/2)+n2<\/sup><\/code>\n<\/li>
        2. T(n) = 4 T(n\/3)+n<\/code>\n<\/li>
        3. T(n) = 8 T(n\/2)+n3<\/sup><\/code>\n<\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"

          Aufgabe 1 (8+5 Punkte) Schreiben sie ein Programm in PASCAL, das die Zahlen in einem File f: file of integer in umgekehrter Reihenfolge ausgibt. (Bemerkung: Das File ist gro\u00df, d.h. sie k\u00f6nnen den Fileinhalt nicht in den Hauptspeicher einlesen) Bestimmen sie die Ordnung der Laufzeit ihres Programms im schlimmsten Fall. Aufgabe 2 (4 Punkte) F\u00fcr weiterlesen…<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-574","post","type-post","status-publish","format-standard","hentry","category-altklausur"],"_links":{"self":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts\/574","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=574"}],"version-history":[{"count":0,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts\/574\/revisions"}],"wp:attachment":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=574"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=574"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=574"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}