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

作者簡(jiǎn)介

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

書(shū)籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

評(píng)論、評(píng)分、閱讀與下載

---

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

---