北航2014考研計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考點(diǎn)速記手冊

作者簡介

崔巍、蔣本珊、孫衛(wèi)真、白龍飛均為重點(diǎn)大學(xué)計算機(jī)專業(yè)一線教師，主講計算機(jī)專業(yè)課程，擁有豐富的計算機(jī)教學(xué)經(jīng)驗。對計算機(jī)專業(yè)碩士研究生專業(yè)課考試有深入研究。自2009年實行考研計算機(jī)專業(yè)課統(tǒng)考以來，已編寫出版多部計算機(jī)專業(yè)考研書，深受廣大考生推崇。

書籍目錄

第一部分?jǐn)?shù)據(jù)結(jié)構(gòu) 第1章緒論 1.1知識結(jié)構(gòu)圖 1.2重點(diǎn)歸納 1.3難點(diǎn)釋疑 1.4真題高頻考點(diǎn)總結(jié) 第2章線性表 2.1知識結(jié)構(gòu)圖 2.2重點(diǎn)歸納 2.3難點(diǎn)釋疑 2.4真題高頻考點(diǎn)總結(jié) 第3章棧、隊列和數(shù)組 3.1知識結(jié)構(gòu)圖 3.2重點(diǎn)歸納 3.3難點(diǎn)釋疑 3.4真題高頻考點(diǎn)總結(jié) 第4章樹和二叉樹 4.1知識結(jié)構(gòu)圖 4.2重點(diǎn)歸納 4.3難點(diǎn)釋疑 4.4真題高頻考點(diǎn)總結(jié) 第5章圖 5.1知識結(jié)構(gòu)圖 5.2重點(diǎn)歸納 5.3難點(diǎn)釋疑 5.4真題高頻考點(diǎn)總結(jié) 第6章查找 6.1知識結(jié)構(gòu)圖 6.2重點(diǎn)歸納 6.3難點(diǎn)釋疑 6.4真題高頻考點(diǎn)總結(jié) 第7章排序 7.1知識結(jié)構(gòu)圖 7.2重點(diǎn)歸納 7.3難點(diǎn)釋疑 7.4真題高頻考點(diǎn)總結(jié) 第二部分計算機(jī)組成原理 第1章計算機(jī)系統(tǒng)概述 1.1知識結(jié)構(gòu)圖 1.2重點(diǎn)歸納 1.3難點(diǎn)釋疑 1.4真題高頻考點(diǎn)總結(jié) 第2章數(shù)據(jù)的表示與運(yùn)算 2.1知識結(jié)構(gòu)圖 2.2重點(diǎn)歸納 2.3難點(diǎn)釋疑 2.4真題高頻考點(diǎn)總結(jié) 第3章存儲層次結(jié)構(gòu) 3.1知識結(jié)構(gòu)圖 3.2重點(diǎn)歸納 3.3難點(diǎn)釋疑 3.4真題高頻考點(diǎn)總結(jié) 第4章指令系統(tǒng) 4.1知識結(jié)構(gòu)圖 4.2重點(diǎn)歸納 4.3難點(diǎn)釋疑 4.4真題高頻考點(diǎn)總結(jié) 第5章中央處理器（CPU） 5.1知識結(jié)構(gòu)圖 5.2重點(diǎn)歸納 5.3難點(diǎn)釋疑 5.4真題高頻考點(diǎn)總結(jié) 第6章總線 6.1知識結(jié)構(gòu)圖 6.2重點(diǎn)歸納 6.3難點(diǎn)釋疑 6.4真題高頻考點(diǎn)總結(jié) 第7章輸入輸出（I／O）系統(tǒng) 7.1知識結(jié)構(gòu)圖 7.2重點(diǎn)歸納 7.3難點(diǎn)釋疑 7.4真題高頻考點(diǎn)總結(jié) 第三部分操作系統(tǒng) 第1章操作系統(tǒng)概述 1.1知識結(jié)構(gòu)圖 1.2重點(diǎn)歸納 1.3難點(diǎn)釋疑 1.4真題高頻考點(diǎn)總結(jié) 第2章進(jìn)程管理 2.1知識結(jié)構(gòu)圖 2.2重點(diǎn)歸納 2.3難點(diǎn)釋疑 2.4真題高頻考點(diǎn)總結(jié) 第3章存儲管理 3.1知識結(jié)構(gòu)圖 3.2重點(diǎn)歸納 3.3難點(diǎn)釋疑 3.4真題高頻考點(diǎn)總結(jié) 第4章文件管理 4.1知識結(jié)構(gòu)圖 4.2重點(diǎn)歸納 4.3難點(diǎn)釋疑 4.4真題高頻考點(diǎn)總結(jié) 第5章輸入輸出（I／O）管理 5.1知識結(jié)構(gòu)圖 5.2重點(diǎn)歸納 5.3難點(diǎn)釋疑 5.4真題高頻考點(diǎn)總結(jié) 第四部分計算機(jī)網(wǎng)絡(luò) 第1章計算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu) 1.1知識結(jié)構(gòu)圖 1.2重點(diǎn)歸納 1.3難點(diǎn)釋疑 1.4真題高頻考點(diǎn)總結(jié) 第2章物理層 2.1知識結(jié)構(gòu)圖 2.2重點(diǎn)歸納 2.3難點(diǎn)釋疑 2.4真題高頻考點(diǎn)總結(jié) 第3章數(shù)據(jù)鏈路層 3.1知識結(jié)構(gòu)圖 3.2重點(diǎn)歸納 3.3難點(diǎn)釋疑 3.4真題高頻考點(diǎn)總結(jié) 第4章網(wǎng)絡(luò)層 4.1知識結(jié)構(gòu)圖 4.2重點(diǎn)歸納 4.3難點(diǎn)釋疑 4.4真題高頻考點(diǎn)總結(jié) 第5章傳輸層 5.1知識結(jié)構(gòu)圖 5.2重點(diǎn)歸納 5.3難點(diǎn)釋疑 5.4真題高頻考點(diǎn)總結(jié) 第6章應(yīng)用層 6.1知識結(jié)構(gòu)圖 6.2重點(diǎn)歸納 6.3難點(diǎn)釋疑 6.4真題高頻考點(diǎn)總結(jié)

章節(jié)摘錄

版權(quán)頁：   插圖：   ①從輸入文件讀k個記錄到工作區(qū)。 ②對工作區(qū)中的k個記錄建立敗者樹。 ③將根結(jié)點(diǎn)對應(yīng)記錄（關(guān)鍵字值最小者）送入當(dāng)前的初始?xì)w并段。 ④從輸入文件取下一個記錄進(jìn)入工作區(qū)以替代剛輸出的記錄的結(jié)點(diǎn)位置。 ⑤對工作區(qū)中關(guān)鍵字大于或等于已輸出記錄的關(guān)鍵字的所有記錄，建立敗者樹（如果新加入記錄的關(guān)鍵字大于或等于已輸出記錄的關(guān)鍵字，只要對原敗者樹進(jìn)行調(diào)整即可）。 ⑥重復(fù)步驟③～⑤直到工作區(qū)的k個記錄關(guān)鍵字都小于剛輸出記錄的關(guān)鍵字為止。此時已產(chǎn)生一個歸并段。 ⑦重復(fù)步驟②～⑥直到工作區(qū)為空。 （2）敗者樹 在磁盤排序的兩個階段中，采用敗者樹進(jìn)行最小關(guān)鍵字的查找可減少比較次數(shù)。 敗者樹是一棵完全二叉樹。其中每個結(jié)點(diǎn)的關(guān)鍵字取它的兩個子結(jié)點(diǎn)的關(guān)鍵字中較小者，因此，根結(jié)點(diǎn)的關(guān)鍵字是這棵樹中所有結(jié)點(diǎn)的關(guān)鍵字中最小的。這就像k個參加淘汰賽的球隊，勝者（值較小者）進(jìn)入下一輪的比賽，根結(jié)點(diǎn)為冠軍（值最小者）。 敗者樹的構(gòu)造過程是：對于具有k個記錄的序列，首先用這k個記錄作為葉子結(jié)點(diǎn)，然后把相鄰的兩個結(jié)點(diǎn)進(jìn)行比較，把關(guān)鍵字小的記錄（優(yōu)勝者）作為這兩個結(jié)點(diǎn)的父結(jié)點(diǎn)，按此方法自下而上一層一層地產(chǎn)生敗者樹的結(jié)點(diǎn)。為了節(jié)約內(nèi)存空間，非葉子結(jié)點(diǎn)可不包含整個記錄，只要存放記錄的關(guān)鍵字及指向該記錄的指針即可。 敗者樹的根結(jié)點(diǎn)的值是構(gòu)成敗者樹的元素中最小的。在后面的應(yīng)用中，往往把根結(jié)點(diǎn)的值輸出，并用一個新的元素替換，要求構(gòu)成新的敗者樹，這時只要在原來的敗者樹的基礎(chǔ)上進(jìn)行調(diào)整即可。調(diào)整僅在從根到新加入的葉子結(jié)點(diǎn)的樹枝j一的結(jié)點(diǎn)及它們的兄弟結(jié)點(diǎn)之間進(jìn)行，自下而上進(jìn)行比較并調(diào)整其父結(jié)點(diǎn)。 （3）k路歸并方法 有了m個初始?xì)w并段（都是有序段），便可以進(jìn)行k路歸并了，即將k個初始?xì)w并段采用某種方法進(jìn)行歸并產(chǎn)生一個段，這樣m個初始?xì)w并段產(chǎn)生多個更大的段，然后對這些段再進(jìn)行歸并，如此下去，直到只生成一個段為止，這個段就是最后生成的歸并段。 在內(nèi)存里進(jìn)行k路歸并的方法有多種。當(dāng)歸并路數(shù)k較大時，為了減少歸并時的比較次數(shù)，常采用敗者樹進(jìn)行歸并的方法，其歸并過程如下： ①用參加歸并的k個有序段的第一個記錄構(gòu)造出一棵初始敗者樹，該樹中的根結(jié)點(diǎn)就是這k個記錄中具有最小關(guān)鍵字的記錄。 ②把敗者樹根結(jié)點(diǎn)所代表的記錄送到輸出緩沖區(qū)。 ③輸出記錄所在的有序段的下一個記錄代替輸出記錄的位置，調(diào)整敗者樹。 ④重復(fù)步驟②和③直到k個有序段的所有記錄都輸出為止。 k路平衡歸并的敗者樹的深度為[log2k]，因此，利用敗者樹在k個記錄中選擇最小者，只需要進(jìn)行[log2k]次關(guān)鍵字比較。若每一趟歸并u個記錄，總共歸并s趟（s=[logkm]），每次的調(diào)整找下一個具有最小關(guān)鍵字的記錄時，最多[log2k]次關(guān)鍵字比較，這時歸并總共需要的比較次數(shù)為。

編輯推薦

《考研計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考點(diǎn)速記手冊(2014)》自出版后以其獨(dú)特的內(nèi)容編排、精辟的要點(diǎn)講解獲得廣大考研學(xué)子的一致推崇。

圖書封面

評論、評分、閱讀與下載

---

    北航2014考研計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考點(diǎn)速記手冊 PDF格式下載

---