必胜高考网_全国高考备考和志愿填报信息平台

必勝高考網 > 計算機類 > 計算機等級 > 資訊 >

全國計算機等級考試四級復習綱要:圖的概念

時間: 家輝2 資訊

 ?、谏种械谝豢脴涞母Y點就是轉換后二叉樹的根結點,依次將后一棵樹作為前一棵樹根結點的右子樹。

  二叉樹轉換為森林的步驟是:

 ?、偕值谝豢脴涞母褪嵌鏄涞母?

 ?、诙鏄涞淖笞訕滢D換為森林的第一棵樹,二叉樹的右子樹對應于森林中其余的樹;③二叉樹右子樹的根結點作為余下樹中第一棵樹的根結點……,以此類推。

  五、圖

  圖的概念

  圖是一種較線性表和樹形結構更為復雜的數據結構。在線性表中每個數據元素只有一個(直接)前驅和后繼,即各數據元素之間僅有線性關系。在樹形結構中,數據元素之間有明顯的層次關系,每一層中的數據元素只和上一層中的一個元素(即雙親結點)相關。而在圖中,任意兩個數據元素之間均有可能相關。

  圖(graph)是圖型結構的簡稱。它是一種復雜的非線性數據結構。圖在各個領域都有著廣泛的應用。圖的二元組定義為:

  G=(V,E)

  其中,V是非空的頂點集合,即

  V={v i |1≤i≤n,n≥1,v i ∈elemtype,n為頂點數}

  E是V上二元關系的集合,一般只討論僅含一個二元關系的情況,且直接用E表示這個關系。這樣,E就是V上頂點的序偶或無序對(每個無序對(x,y)是兩個對稱序偶和的簡寫形式)的集合。對于V上的每個頂點,在E中都允許有任意多個前驅和任意多個后繼,即對每個頂點的前驅和后繼個數均不加限制。回顧一下線性表和樹的二元組定義,都是在其二元關系上規定了限制條件,線性表的限制條件是只允許每個結點有一個前驅和一個后繼,樹的限制條件是只允許每個結點有一個前驅。因此,圖比線性表和樹更具有廣泛性,它包含線性表和樹在內,線性表和樹可以認為是圖的簡單情況。

  快速排序的基本思想是把表中某元素作為基準,將表劃分為大于該值和小于該值的兩部分,然后用遞歸的方法處理這兩個子表,直到完成整個表的排序??焖倥判虻谋容^次數為(n-1)+(n-2)+…+1=n(n-1)/2,移動次數最多也是n(n-1)/2。如果每次的基準元素剛好是表的中值,使表分為大小相等的兩個子表,則比較次數為nlog 2 n;如果表已排好序,則移動次數為0。

  6.常用排序方法的性能比較如下表所示:

  常用排序方法的性能比較

  排序方法 平均時間 最壞情況的時間 輔助存儲

  冒泡法、直接選擇法、直接插入法 O(n2 ) O(n2 ) O(1)

  快速排序 O(nlog2 n) O(n2 ) O(log2 n)

  堆排序 O(nlog2n) O(nlog2 n) O(1)

  歸并排序 O(nlog2 n) O(nlog2 n) O(n)

  注:在上表中,我們將n(n-1)/2也記為O(n2 )。如果在待排序的表中含有多個碼值相同的記錄,經過排序后,這些記錄的相對次序不變,則稱這種排序方法是穩定的,否則是不穩定的。根據上述說法,可以看出直接插入法、歸并法是穩定的;而直接選擇法、冒泡法、快速排序法、堆排序法是不穩定的。

  七、檢索

  1.順序檢索

  檢索又稱為查找。順序檢索是將待查找的關鍵碼值與線性表中個結點的關鍵碼值逐一比較,直到找到所需的記錄,檢索成功;或者在表中找不到所需記錄而檢索失敗。順序檢索不要求線性表事先排序。設線性表有n個元素,則最多檢索次數為n,最少檢索次數為1。

  2.二分法檢索

  二分法檢索要求線性表結點按關鍵排序且以順序方式存儲。在查找時,首先與表的中間位置上結點的關鍵值比較,若相等則檢索成功;否則根據比較結果確定下一步在表的前半部或后半部中繼續進行。二分法檢索的效率較主動,設線性表有n個元素,則最多的檢索次數為大于log 2 n的最小整數,最少的檢索次數為1。

  3.分塊檢索

  分塊檢索把線性表分成若干塊,塊內結點不必有序,但塊與塊之間必須有序,即每一塊中各結點的關鍵值必須大于(或小于,與此類推)前一塊最大關鍵值。為加快查找,還要建立一個索引表,表中給出每一塊的最大關鍵值和指向塊內第一個結點位置的指針。分塊檢索分兩步進行,先查索引表,確定要找的記錄在哪一塊;然后再在相應的塊中檢索。分塊檢索適合于線性表很大,數據又是動態變化的情況。在查索引表時,可采用順序法或二分法;在塊內查找所求記錄時,采用順序法。由于分塊而縮小了查找范圍,從而加快檢索速。

  4.散列表檢索

  根據關鍵值,就可以迅速找到該記錄所對應的存儲位置,這就是建立在散列函數基礎上的散列檢索。設記錄的關鍵值為k,則該記錄的存儲位置可用散列函數H來計算H=H(k)。常用來產生的散列函數的方法是除余法,即取H(k)=k mod p設散列表長度為n,取p為小于n的最大素數。一般說來,關鍵碼值的集合比散列表存儲位的數目大得多,這正是體現散列表的優勢所在,但同時帶來了沖突問題,即不同的關鍵值經散列函數計算,可能得到相同的存儲位置。一個好的散列函數應該使沖突的可能性盡量小。最常用的解決沖突的方法是線性探測法,就是在發生沖突時,從H(k)以后的位置逐一探測,直至找到一個空位置,將新記錄插入;在檢索時,如果H(k)中不是所需關鍵值的記錄,也是從H(k)往下逐一搜索,直到找到所需關鍵值或查找失敗為止。應注意查找次序是:H(k),H(k)+1,H(k)+2,…n-1,0,1,2,…,H(k)-1即在n-1以后,又從0開始,因為在位置上是循環的。雙重散列技術是對線性探測法的改進。它使用兩個散列函數H1和H2。對關鍵值k,計算H1(k),求得0到n-1之間的一個散列地址;若在這個地址上沖突,下一個被探測的地址為(H1(k)+H2(k))mod n,關于選擇H2的方法在此不做討論。

56715 主站蜘蛛池模板: 定制异形重型钢格栅板/钢格板_定做踏步板/排水沟盖板_钢格栅板批发厂家-河北圣墨金属制品有限公司 | 单柱拉力机-橡胶冲片机-哑铃裁刀-江都轩宇试验机械厂 | 细沙回收机-尾矿干排脱水筛设备-泥石分离机-建筑垃圾分拣机厂家-青州冠诚重工机械有限公司 | 甲级防雷检测仪-乙级防雷检测仪厂家-上海胜绪电气有限公司 | 重庆磨床过滤机,重庆纸带过滤机,机床伸缩钣金,重庆机床钣金护罩-重庆达鸿兴精密机械制造有限公司 | 桂林腻子粉_内墙外墙抗裂砂浆腻子粉推荐广西鑫达涂料厂家供应 | 北京公司注册_代理记账_代办商标注册工商执照-企力宝 | 云南外加剂,云南速凝剂,云南外加剂代加工-普洱澜湄新材料科技有限公司 | 胶水,胶粘剂,AB胶,环氧胶,UV胶水,高温胶,快干胶,密封胶,结构胶,电子胶,厌氧胶,高温胶水,电子胶水-东莞聚力-聚厉胶粘 | 超声骨密度仪-动脉硬化检测仪器-人体成分分析仪厂家/品牌/价格_南京科力悦 | 政府园区专业委托招商平台_助力企业选址项目快速落地_东方龙商务集团 | 施工围挡-施工PVC围挡-工程围挡-深圳市旭东钢构技术开发有限公司 | 拉曼光谱仪_便携式|激光|显微共焦拉曼光谱仪-北京卓立汉光仪器有限公司 | 附着力促进剂-尼龙处理剂-PP处理剂-金属附着力处理剂-东莞市炅盛塑胶科技有限公司 | 锻造液压机,粉末冶金,拉伸,坩埚成型液压机定制生产厂家-山东威力重工官方网站 | PC构件-PC预制构件-构件设计-建筑预制构件-PC构件厂-锦萧新材料科技(浙江)股份有限公司 | 两头忙,井下装载机,伸缩臂装载机,30装载机/铲车,50装载机/铲车厂家_价格-莱州巨浪机械有限公司 | 螺旋绞龙叶片,螺旋输送机厂家,山东螺旋输送机-淄博长江机械制造有限公司 | 百方网-百方电气网,电工电气行业专业的B2B电子商务平台 | 胶原检测试剂盒,弹性蛋白检测试剂盒,类克ELISA试剂盒,阿达木单抗ELISA试剂盒-北京群晓科苑生物技术有限公司 | 建大仁科-温湿度变送器|温湿度传感器|温湿度记录仪_厂家_价格-山东仁科 | 篮球架_乒乓球台_足球门_校园_竞技体育器材_厂家_价格-沧州浩然体育器材有限公司 | 珠宝展柜-玻璃精品展柜-首饰珠宝展示柜定制-鸿钛展柜厂家 | 扫地车厂家-山西洗地机-太原电动扫地车「大同朔州吕梁晋中忻州长治晋城洗地机」山西锦力环保科技有限公司 | 防渗膜厂家|养殖防渗膜|水产养殖防渗膜-泰安佳路通工程材料有限公司 | 中高频感应加热设备|高频淬火设备|超音频感应加热电源|不锈钢管光亮退火机|真空管烤消设备 - 郑州蓝硕工业炉设备有限公司 | 岩石钻裂机-液压凿岩机-劈裂机-挖改钻_湖南烈岩科技有限公司 | 众品地板网-地板品牌招商_地板装修设计_地板门户的首选网络媒体。 | 河南彩印编织袋,郑州饲料编织袋定制,肥料编织袋加工厂-盛军塑业 河南凯邦机械制造有限公司 | 耐腐蚀泵,耐腐蚀真空泵,玻璃钢真空泵-淄博华舜耐腐蚀真空泵有限公司 | 动库网动库商城-体育用品专卖店:羽毛球,乒乓球拍,网球,户外装备,运动鞋,运动包,运动服饰专卖店-正品运动品网上商城动库商城网 - 动库商城 | 连栋温室大棚建造厂家-智能玻璃温室-薄膜温室_青州市亿诚农业科技 | 冰晶石|碱性嫩黄闪蒸干燥机-有机垃圾烘干设备-草酸钙盘式干燥机-常州市宝康干燥 | pos机办理,智能/扫码/二维码/微信支付宝pos机-北京万汇通宝商贸有限公司 | 铝镁锰板厂家_进口钛锌板_铝镁锰波浪板_铝镁锰墙面板_铝镁锰屋面-杭州军晟金属建筑材料 | 机构创新组合设计实验台_液压实验台_气动实训台-戴育教仪厂 | 食品无尘净化车间,食品罐装净化车间,净化车间配套风淋室-青岛旭恒洁净技术有限公司 | sus630/303cu不锈钢棒,440C/430F/17-4ph不锈钢研磨棒-江苏德镍金属科技有限公司 | 电磁流量计厂家_涡街流量计厂家_热式气体流量计-青天伟业仪器仪表有限公司 | 泰兴市热钻机械有限公司-热熔钻孔机-数控热熔钻-热熔钻孔攻牙一体机 | 气力输送设备_料封泵_仓泵_散装机_气化板_压力释放阀-河南锐驰机械设备有限公司 |