首頁 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實用文檔 繽紛校園 英語學習 | ||
2010考研 | 2010高考 | 2010中考 | 自學考試 | 成人高考 | 專升本 | 法律碩士 | MBA/MPA | 中科院 | ||
四六級 | 商務(wù)英語 | 公共英語 | 職稱日語 | 職稱英語 | 博思 | 口譯筆譯 | GRE GMAT | 日語 | 托福 | ||
雅思 | 專四專八 | 新概念 | 自考英語 | 零起點英、法、德、日、韓語 | 在職申碩英語 | ||
在職攻碩英語 | 成人英語三級 | ||
等級考試 | 水平考試 | 微軟認證 | 思科認證 | Oracle認證 | Linux認證 | ||
公務(wù)員 | 報關(guān)員 | 報檢員 | 外銷員 | 司法考試 | 導游考試 | 教師資格 | 國際商務(wù)師 | 跟單員 | ||
單證員 | 物流師 | 價格鑒證師 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 人力資源管理師 | 管理咨詢師 | ||
期貨從業(yè)資格 | 社會工作者 | ||
會計職稱 | 注會CPA | 經(jīng)濟師 | 統(tǒng)計師 | 注冊稅務(wù)師 | 評估師 | 精算師 | 高會 | ACCA | 審計師 | ||
法律顧問 | 會計證 | ||
一級建造師 | 二級建造師 | 造價師 | 監(jiān)理師 | 安全師 | 咨詢師 | 結(jié)構(gòu)師 | 建筑師 | 安全評價師 | ||
房地產(chǎn)估價師 | 土地估價師 | 設(shè)備監(jiān)理師 | 巖土工程師 | 質(zhì)量資格 | 房地產(chǎn)經(jīng)紀人 | 造價員 | ||
投資項目管理 | 土地代理人 | 環(huán)保師 | 環(huán)境影響評價 | 物業(yè)管理師 | 城市規(guī)劃師 | 公路監(jiān)理師 | ||
公路造價工程師 | 招標師 | ||
執(zhí)業(yè)護士 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 衛(wèi)生資格 |
1.5線性鏈表
數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元,這種存儲單元稱為存儲結(jié)點,簡稱結(jié)點。
結(jié)點由兩部分組成:
(1)用于存儲數(shù)據(jù)元素值,稱為數(shù)據(jù)域;
(2)用于存放指針,稱為指針域,用于指向前一個或后一個結(jié)點。
在鏈式存儲結(jié)構(gòu)中,存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù),各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。
鏈式存儲方式即可用于表示線性結(jié)構(gòu),也可用于表示非線性結(jié)構(gòu)。
線性鏈表,HEAD稱為頭指針,HEAD=NULL(或0)稱為空表,如果是兩指針:左指針(Llink)指向前件結(jié)點,右指針(Rlink)指向后件結(jié)點。
線性鏈表的基本運算:查找、插入、刪除。
1.6樹與二叉樹
樹是一種簡單的非線性結(jié)構(gòu),所有元素之間具有明顯的層次特性。
在樹結(jié)構(gòu)中,每一個結(jié)點只有一個前件,稱為父結(jié)點,沒有前件的結(jié)點只有一個,稱為樹的根結(jié)點,簡稱樹的根。每一個結(jié)點可以有多個后件,稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。
在樹結(jié)構(gòu)中,一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度,所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹的特點:
(1)非空二叉樹只有一個根結(jié)點;
(2)每一個結(jié)點最多有兩棵子樹,且分別稱為該結(jié)點的左子樹與右子樹。
二叉樹的基本性質(zhì):
(1)在二叉樹的第k層上,最多有2k-1(k≥1)個結(jié)點;
(2)深度為m的二叉樹最多有2m-1個結(jié)點;
(3)度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個;
(4)具有n個結(jié)點的二叉樹,其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分;
(5)具有n個結(jié)點的完全二叉樹的深度為[log2n]+1;
(6)設(shè)完全二叉樹共有n個結(jié)點。如果從根結(jié)點開始,按層序(每一層從左到右)用自然數(shù)1,2,…,n給結(jié)點進行編號(k=1,2….n),有以下結(jié)論:
、偃鬹=1,則該結(jié)點為根結(jié)點,它沒有父結(jié)點;若k>1,則該結(jié)點的父結(jié)點編號為INT(k/2);
②若2k≤n,則編號為k的結(jié)點的左子結(jié)點編號為2k;否則該結(jié)點無左子結(jié)點(也無右子結(jié)點);
、廴2k+1≤n,則編號為k的結(jié)點的右子結(jié)點編號為2k+1;否則該結(jié)點無右子結(jié)點。
滿二叉樹是指除最后一層外,每一層上的所有結(jié)點有兩個子結(jié)點,則k層上有2k-1個結(jié)點深度為m的滿二叉樹有2m-1個結(jié)點。
完全二叉樹是指除最后一層外,每一層上的結(jié)點數(shù)均達到最大值,在最后一層上只缺少右邊的若干結(jié)點。
二叉樹存儲結(jié)構(gòu)采用鏈式存儲結(jié)構(gòu),對于滿二叉樹與完全二叉樹可以按層序進行順序存儲。
二叉樹的遍歷:
(1)前序遍歷(DLR),首先訪問根結(jié)點,然后遍歷左子樹,最后遍歷右子樹;
(2)中序遍歷(LDR),首先遍歷左子樹,然后訪問根結(jié)點,最后遍歷右子樹;
(3)后序遍歷(LRD)首先遍歷左子樹,然后訪問遍歷右子樹,最后訪問根結(jié)點。
1.7查找技術(shù)
順序查找的使用情況:
(1)線性表為無序表;
(2)表采用鏈式存儲結(jié)構(gòu)。
二分法查找只適用于順序存儲的有序表,對于長度為n的有序線性表,最壞情況只需比較log2n次。
1.8排序技術(shù)
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。
交換類排序法:(1)冒泡排序法,需要比較的次數(shù)為n(n-1)/2;(2)快速排序法。
插入類排序法:(1)簡單插入排序法,最壞情況需要n(n-1)/2次比較;(2)希爾排序法,最壞情況需要O(n1.5)次比較。
選擇類排序法:(1)簡單選擇排序法,
最壞情況需要n(n-1)/2次比較;(2)堆排序法,最壞情況需要O(nlog2n)次比較。
相關(guān)推薦:2010年9月計算機等級考試精華備考資料匯總北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |