2014海天計算機-導學班講義

概概2014Turnoffyour12345概概“做事情從根本做起，經(jīng)過短時間必定有收獲；從枝節(jié)做起，就會勞而無功。功名的建立，是由于抓住了事物的根本，得到了賢人教化。不是賢人，誰懂得事情的教化呢？所以說，建立功名的根本在于得到賢人。”劣主要由考官確定，而考官未必都是飽學之士，因此有“場上 此外，“一命二運三，四積陰功五讀書”確是Copyright2013byZhongtao-2/49TypesetbyTroffbuilton概概 課程名稱1 23 Copyright2013byZhongtao-4/49TypesetbyTroffbuilton 1《數(shù)據(jù)結構（C語言版） 等、吳偉民3 標題、大小子目及具體的內(nèi)容，做到事無大小、輕重，均一一過一樣過一遍，不要求將所有的內(nèi)容都回憶出來（其實這也是不可能的），主要是將當天復習過的大小標題及彼此間的關系回憶出來，這樣既能鞏固主干知識，又能充分利用業(yè)余時間。Copyright2013byZhongtao-6/49TypesetbyTroffbuilton突出。主要目的是幫助大家建立整體知識框架并融會貫通 可據(jù)此與前復習過的內(nèi)容進行對比，糾偏歸正，同時檢查自己復習過的內(nèi)容有無遺漏，使知識體系完備化，為鞏固提高打下堅實基礎。同時，詳細講解練習題并選講 重要 ，提高考生的解題技巧。這時，應結合考研大綱，以實戰(zhàn)為第一目標，注重各知識點的相互關個角 含義下午晚上組成原理數(shù)據(jù)結構數(shù)學下午組成原理數(shù)據(jù)結構晚上組成原理數(shù)據(jù)結構政治 沖刺班課程是對復習內(nèi)容作選擇性反芻，將理論、概念與典型例題配對。另一目的是立足將來，即還要根 考試試題 備補缺。你應做的主要應是脫離 自主回憶，自我理清頭緒，具體而言， Copyright2013byZhongtao-8/49TypesetbyTroffbuiltonOCopyright2013byZhongtao-10/49TypesetbyTroffbuilton[1[2[3[4[5.E.Horowitz,etal.FundamentalsofDataStructuresinC.2ndEd.,R.Sedgewick.AlgorithmsinC:Parts1-4.3rdEd.,R.Sedgewick.AlgorithmsinC:Part5.3rdEd.,R.E.Tarjan.DataStructuresandNetworkAlgorithms,[1 [2 [3 [4] [5 ADT ADT push(),pop(put(),get(pre_order_traverse(in_order_traverse(post_order_traverse()dfs_traverse(圖bfs_traverse(Copyright2013byZhongtao-12/49TypesetbyTroffbuiltonPrim算法OV2 Kruskal算法OElogE Dijkstra算法OV2Floyd算法OV3拓撲排序算法OVEO(V+E用于用于O(n的有序表OlognAVL樹OlognBST樹Ologn)OnHash表O1B-樹Ologn計算平均查找長度ASLCopyright2013byZhongtao-14/49TypesetbyTroffbuilton排序分類 O(n2O(n22O(nO(n2(nO(2O(n2O(n2O(n2排O(n4/3O(nlognO(nlognO(nlogn)O(n2O(nlognO(nlognO(nlognO(nlognO(nlogn)O(ndO(ndO(ndn 大O記號Copyright2013byZhongtao-16/49TypesetbyTroffbuilton( ADT大O記號merge(exponent1(),exponent2()fibonacci1(),fibonacci2(空表頭（dummyhead）Copyright2013byZhongtao-18/49TypesetbyTroffbuilton空表頭（dummyhead）Josephus()LIFO&Copyright2013byZhongtao-20/49TypesetbyTroffbuiltonLIFO&rpn_eval()expr_eval()hanoi(),pn_eval(二叉樹的表示樹的表示Copyright2013byZhongtao-22/49TypesetbyTroffbuilton count(),height(copy(),destroy()level_width(),longest_path()rotR(),rotL(),reverse()并查集堆、優(yōu)先級隊列、huffmanAOV與AOECopyright2013byZhongtao-24/49TypesetbyTroffbuiltonbridge(),articulation(prim(),dijkstra(),floyd(dfs_topsort(),AOV與AOEcritical_path(BST平衡BSTHashCopyright2013byZhongtao-26/49TypesetbyTroffbuiltonseq_search(),binary_search(靜態(tài)樹表optimal()BSTbst_search(),bst_insert(),bst_remove()bst_join(),bst_select()平衡BSTAVLinsert(),btree_insert(),insertR(),split(Hashinsert(),search(Copyright2013byZhongtao-28/49TypesetbyTroffbuiltonselection_sort(),insertion_sort()bubble_up_sort(),bubble_down_sort() _sort()merge_sort(),merge_sortBU()quick_sort(),quick_sortNR()kth_element(),heap_sort()radix_sortselection_sort(),quick_sort(-Copyright2013byZhongtao-30/49TypesetbyTroff-Copyright2013byZhongtao-30/49TypesetbyTroffbuilton隨機數(shù) -0000000 0 0 000000000000--Copyright2013byZhongtao-32/49TypesetbyTroffbuilton隨機數(shù) -000000000000000設計 -（）利用B-樹作文件索引，設磁盤頁塊的大小是4000字節(jié)（應為4096字節(jié)，但為計算方便，這里取4000字節(jié)）需要5個字節(jié)。現(xiàn)有200000條記錄構成的文件，每個記錄為200字節(jié)，其中包括關鍵字5個字節(jié)。問此B-樹作索引的文件，B-樹的階數(shù)應為多少？假定文件的數(shù)據(jù)頁塊未按關鍵字有序排列，索引部分需要占用多少磁盤頁Copyright2013byZhongtao-34/49TypesetbyTroffbuilton設計 -根據(jù)B-樹的概念索引結點最大不應超過一個磁盤頁塊的大小。假設B-樹為m階，一個B-樹結點最多可存放m?1個關鍵字和對應的記錄地址，外加m個子樹指針和1個指示結點中實際關鍵字個數(shù)的整數(shù)2個字節(jié)。根據(jù)假設，每個關鍵字和指針都占用5個字節(jié)，則有(2(m?1)+m)×5+2≤計算結果為m≤267一個索引結點最多可存放m1=266個索引項，最少可以存放m21=個索引項?？偣灿衝=2×107條記錄，每條記錄占用空間2007塊可以存放4000200=20個記錄，則全部記錄分布在6個頁= 個磁盤頁塊作B-266=Copyright2013byZhongtao-36/49TypesetbyTroffbuilton淺說Copyright2013byZhongtao-38/49TypesetbyTroffbuilt/