首頁(yè) 考試吧論壇 Exam8視線(xiàn) 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實(shí)用文檔 求職招聘 論文下載
2011中考 | 2011高考 | 2012考研 | 考研培訓(xùn) | 在職研 | 自學(xué)考試 | 成人高考 | 法律碩士 | MBA考試
MPA考試 | 中科院
四六級(jí) | 職稱(chēng)英語(yǔ) | 商務(wù)英語(yǔ) | 公共英語(yǔ) | 托福 | 雅思 | 專(zhuān)四專(zhuān)八 | 口譯筆譯 | 博思 | GRE GMAT
新概念英語(yǔ) | 成人英語(yǔ)三級(jí) | 申碩英語(yǔ) | 攻碩英語(yǔ) | 職稱(chēng)日語(yǔ) | 日語(yǔ)學(xué)習(xí) | 法語(yǔ) | 德語(yǔ) | 韓語(yǔ)
計(jì)算機(jī)等級(jí)考試 | 軟件水平考試 | 職稱(chēng)計(jì)算機(jī) | 微軟認(rèn)證 | 思科認(rèn)證 | Oracle認(rèn)證 | Linux認(rèn)證
華為認(rèn)證 | Java認(rèn)證
公務(wù)員 | 報(bào)關(guān)員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問(wèn) | 導(dǎo)游資格
報(bào)檢員 | 教師資格 | 社會(huì)工作者 | 外銷(xiāo)員 | 國(guó)際商務(wù)師 | 跟單員 | 單證員 | 物流師 | 價(jià)格鑒證師
人力資源 | 管理咨詢(xún)師考試 | 秘書(shū)資格 | 心理咨詢(xún)師考試 | 出版專(zhuān)業(yè)資格 | 廣告師職業(yè)水平
駕駛員 | 網(wǎng)絡(luò)編輯
衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護(hù)士
會(huì)計(jì)從業(yè)資格考試會(huì)計(jì)證) | 經(jīng)濟(jì)師 | 會(huì)計(jì)職稱(chēng) | 注冊(cè)會(huì)計(jì)師 | 審計(jì)師 | 注冊(cè)稅務(wù)師
注冊(cè)資產(chǎn)評(píng)估師 | 高級(jí)會(huì)計(jì)師 | ACCA | 統(tǒng)計(jì)師 | 精算師 | 理財(cái)規(guī)劃師 | 國(guó)際內(nèi)審師
一級(jí)建造師 | 二級(jí)建造師 | 造價(jià)工程師 | 造價(jià)員 | 咨詢(xún)工程師 | 監(jiān)理工程師 | 安全工程師
質(zhì)量工程師 | 物業(yè)管理師 | 招標(biāo)師 | 結(jié)構(gòu)工程師 | 建筑師 | 房地產(chǎn)估價(jià)師 | 土地估價(jià)師 | 巖土師
設(shè)備監(jiān)理師 | 房地產(chǎn)經(jīng)紀(jì)人 | 投資項(xiàng)目管理師 | 土地登記代理人 | 環(huán)境影響評(píng)價(jià)師 | 環(huán)保工程師
城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價(jià)師 | 安全評(píng)價(jià)師 | 電氣工程師 | 注冊(cè)測(cè)繪師 | 注冊(cè)計(jì)量師
繽紛校園 | 實(shí)用文檔 | 英語(yǔ)學(xué)習(xí) | 作文大全 | 求職招聘 | 論文下載 | 訪(fǎng)談 | 游戲

軟考軟件設(shè)計(jì)師專(zhuān)題講義九:數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

考試吧整理了軟考軟件設(shè)計(jì)師專(zhuān)題講義,幫助考生備考軟考軟件設(shè)計(jì)師考試。
第 1 頁(yè):3.1排序算法
第 15 頁(yè):3.2查找算法

  兩路歸并的遞歸算法:

  【算法10.13】

  void MSort(ElemType *p,ElemType *p1,int s,int t)

  { /*將p[s…t]歸并排序?yàn)閜1[s…t]*/

  if(s==t) p1[s]=p[s]

  else

  { m=(s+t)/2; /*平分*p表*/

  MSort(p,p2,s,m); /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/

  MSort(p,p2,m+1,t); /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/

  Merge(p2,p1,s,m+1,t); /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/

  }

  }

  void MergeSort(S_TBL *p)

  { /*對(duì)順序表*p作歸并排序*/

  MSort(p->elem,p->elem,1,p->length);

  }

  【效率分析】

  需要一個(gè)與表等長(zhǎng)的輔助元素?cái)?shù)組空間,所以空間復(fù)雜度為O(n)。

  對(duì)n個(gè)元素的表,將這n個(gè)元素看作葉結(jié)點(diǎn),若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn),則歸并過(guò)程對(duì)應(yīng)由葉向根生成一棵二叉樹(shù)的過(guò)程。所以歸并趟數(shù)約等于二叉樹(shù)的高度-1,即log2n,每趟歸并需移動(dòng)記錄n次,故時(shí)間復(fù)雜度為O(nlog2n)。

  基數(shù)排序:

  基數(shù)排序是一種借助于多關(guān)鍵碼排序的思想,是將單關(guān)鍵碼按基數(shù)分成“多關(guān)鍵碼”進(jìn)行排序的方法。

  多關(guān)鍵碼排序:

  設(shè)n個(gè)元素的待排序列包含d個(gè)關(guān)鍵碼{k1,k2,…,kd},則稱(chēng)序列對(duì)關(guān)鍵碼{k1,k2,…,kd}有序是指:對(duì)于序列中任兩個(gè)記錄r[i]和r[j](1≤i≤j≤n)都滿(mǎn)足下列有序關(guān)系:

  其中k1稱(chēng)為最主位關(guān)鍵碼,kd稱(chēng)為最次位關(guān)鍵碼。

  多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序,分兩種方法:

  最高位優(yōu)先(Most Significant Digit first)法,簡(jiǎn)稱(chēng)MSD法:先按k1排序分組,同一組中記錄,關(guān)鍵碼k1相等,再對(duì)各組按k2排序分成子組,之后,對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組,直到按最次位關(guān)鍵碼kd對(duì)各子組排序后。再將各組連接起來(lái),便得到一個(gè)有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD法。

  最低位優(yōu)先(Least Significant Digit first)法,簡(jiǎn)稱(chēng)LSD法:先從kd開(kāi)始排序,再對(duì)kd-1進(jìn)行排序,依次重復(fù),直到對(duì)k1排序后便得到一個(gè)有序序列。撲克牌按花色、面值排序中介紹的方法二即是LSD法。

  相關(guān)推薦:2010年軟件水平考試軟件設(shè)計(jì)師專(zhuān)題講義匯總

       計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請(qǐng)與我們聯(lián)系800@exam8.com,我們將會(huì)及時(shí)處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請(qǐng)注明出處。