{"id":579,"date":"2019-08-14T21:00:13","date_gmt":"2019-08-14T19:00:13","guid":{"rendered":"https:\/\/fsr.cs.uni-potsdam.de\/?p=579"},"modified":"2019-08-14T21:00:13","modified_gmt":"2019-08-14T19:00:13","slug":"grundlagen-der-programmierung-ii-2012","status":"publish","type":"post","link":"https:\/\/fsr.cs.uni-potsdam.de\/?p=579","title":{"rendered":"Grundlagen der Programmierung II 2012"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\" id=\"aufgabe_1_2_2_2_punkte\">Aufgabe 1 (2+2+2 Punkte)<\/h1>\n\n\n\n<ol class=\"wp-block-list\"><li> Rekonstruieren sie auf folgenden <code>inorder<\/code> und <code>postorder<\/code> Durchl\u00e4ufen den bin\u00e4ren Baum.\n<ul><li> Inorder: F, A, D, E, K, H, B, I, G, J, L\n<\/li><li> Postorder: F, D, A, K, H, I, L, J, G, B, E\n<\/li><\/ul>\n<\/li><li> K\u00f6nnen sie auch aus einem Preorder und Postorder Durchlauf einen bin\u00e4ren Baum rekonstruieren? Begr\u00fcndung.\n<\/li><li> Gegeben sei ein bin\u00e4rer Baum. Welche Schl\u00fcsselfolge kann bei der Suche nach der 42 <strong>nicht<\/strong> auftreten?\n<ul><li> 50, 25, 37, 43, 42\n<\/li><li> 5, 66, 21, 22, 67, 30\n<\/li><li> 53, 10, 15, 52, 24\n<\/li><li> 60, 49, 30, 34, 41, 46\n<\/li><li> 1, 100, 2, 3, 99, 42\n<\/li><\/ul>\n<\/li><\/ol>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"aufgabe_2_5_punkte\">Aufgabe 2 (5 Punkte)<\/h1>\n\n\n\n<p>\nErweitern sie die Implementierung eines Stacks (Pascal) asu dem Skript,\nsodass bei einem \u201eoverflow\u201c das \u00e4lteste Element aus dem Stack gek\u00f6scht\nwird, damit das hinzugef\u00fcgte Element auf den Stack passt.\n<\/p>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"aufgabe_3_punkte\">Aufgabe 3 (? Punkte)<\/h1>\n\n\n\n<p>\nGegeben sei ein B-Baum der Ordnung eins. F\u00fcgen sie zun\u00e4chst den Schl\u00fcssel 17 ein. L\u00f6schen sie anschlie\u00dfend den Schl\u00fcssel 30.\n<\/p>\n\n\n\n<p>\n(\u2026 B-Baum muss noch migriert werden \u2026)\n<\/p>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"aufgabe_4_3_1_3_punkte\">Aufgabe 4 (3+1+3 Punkte)<\/h1>\n\n\n\n<p>\nGegeben sei ein Graph mit 9 Knoten und 10 Kanten. Mittels des Algorithmus von Kruskal ist der minimale Spannbaum zu bestimmen.\n<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li> Schreiben sie der Reihe nach auf (die Kosten sind eindeutig)\n<\/li><li> Welches Gewicht hat der minimale Spannbaum?\n<\/li><li> Zeichnen sie den Wurzelgraph mit Hilfe des Union-Find-Algorithmus und Pfadkompression.\n<\/li><\/ol>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"aufgabe_5_punkte\">Aufgabe 5 (? Punkte)<\/h1>\n\n\n\n<p>\nZeichnen sie den AVL-Baum zu den Knoten\n<\/p>\n\n\n\n<p>\n7, 4, 3, 10, 6, 5, 2.\n<\/p>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"aufgabe_6_2_2_2_punkte\">Aufgabe 6 (2+2+2+? Punkte)<\/h1>\n\n\n\n<ol class=\"wp-block-list\"><li> Erl\u00e4utern sie die Vorteile von Quicksort, Mergesort und Bucketsort.\n<\/li><li> Ist das Array <code>A  = {17, 15, 13, 10, 7, 9, 12, 11)<\/code> ein Heap? Begr\u00fcndung!\n<\/li><\/ol>\n\n\n\n<h1 class=\"wp-block-heading\" id=\"aufgabe_7_8_punkte\">Aufgabe 7 (8 Punkte)<\/h1>\n\n\n\n<p>\nGegeben sei eine Codierung von nat\u00fcrlichen Zahlen in einem Bin\u00e4rcode, in dem jedoch keine aufeinanderfolgende Einsen (11) sind.\n<\/p>\n\n\n\n<p>\nDaraus ergibt sich: 1, 10, 100, 101, 1000, \u2026\n<\/p>\n\n\n\n<p>\nWelche nat\u00fcrliche Zahl wird durch 100100001001000 dargestellt?\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Aufgabe 1 (2+2+2 Punkte) Rekonstruieren sie auf folgenden inorder und postorder Durchl\u00e4ufen den bin\u00e4ren Baum. Inorder: F, A, D, E, K, H, B, I, G, J, L Postorder: F, D, A, K, H, I, L, J, G, B, E K\u00f6nnen sie auch aus einem Preorder und Postorder Durchlauf einen bin\u00e4ren Baum rekonstruieren? Begr\u00fcndung. Gegeben sei <a class=\"more-link\" href=\"https:\/\/fsr.cs.uni-potsdam.de\/?p=579\">weiterlesen&#8230;<\/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-579","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\/579","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=579"}],"version-history":[{"count":0,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts\/579\/revisions"}],"wp:attachment":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=579"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=579"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=579"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}