北京理工大學(xué)813計算機專業(yè)基礎(chǔ)

1、813計算機專業(yè)基礎(chǔ)參考書目數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏，吳偉民，清華大學(xué)出版社計算機組成原理（第3版），蔣本珊清華大學(xué)出版社885軟件工程專業(yè)基礎(chǔ)綜合參考書目C語言程序設(shè)計 清華大學(xué)出版社，譚浩強,第三版數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社 嚴(yán)蔚敏,2002.09813計算機專業(yè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)（120分）考查內(nèi)容：數(shù)據(jù)結(jié)構(gòu)主要考查考生以下幾個方面：1 .理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以 及各種基本操作的實現(xiàn)。2 .掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計和分析。3 .能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。應(yīng)掌握的具體內(nèi)容為：一、線性表（一）線性表的定義和

2、基本操作（二）線性表的實現(xiàn)1 .順序存儲結(jié)構(gòu)2 .鏈?zhǔn)酱鎯Y(jié)構(gòu)3 .線性表的使用二、棧、隊列和數(shù)組（一）棧和隊列的基本概念（二）棧和隊列的順序存儲結(jié)構(gòu)（三）棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（四）棧和隊列的使用（五）特殊矩陣的壓縮存儲三、樹和二叉樹（一）樹的概念（二）二叉樹1 .二叉樹的定義及其主要特征2 .二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)3 .二叉樹的遍歷4 .線索二叉樹的基本概念和構(gòu)造5 .二叉排序樹6 .平衡二叉樹（三）樹、森林1 .書的存儲結(jié)構(gòu)2 .森林和二叉樹的轉(zhuǎn)換3 .樹和森林的遍歷（四）樹的使用1 .等價類問題2 .哈夫曼（Huffman ）樹和哈夫曼編碼四、圖（一）圖的概念（二）圖的存儲

3、及基本操作1 .鄰接矩陣法2 .鄰接表法（三）圖的遍歷1 .深度優(yōu)先搜索2 .廣度優(yōu)先搜索（四）圖的基本使用及其復(fù)雜度分析1 .最?。ù鷥r）生成樹2 .最短路徑3 .拓?fù)渑判? .關(guān)鍵路徑五、查找（一）查找的基本概念（二）順序查找法（三）折半查找法（四）B-樹（五）散列（Hash）表及其查找（六）查找算法的分析及使用六、內(nèi)部排序（一）排序的基本概念（二）插入排序1 .直接插入排序2 .折半插入排序（三）起泡排序（bubblesort ）（四）簡單選擇排序（五）希爾排序（shellsort ）（六）快速排序（七）堆排序（八）二路歸并排序（mergesort ）（九）基數(shù)排序（十）各種內(nèi)部排序算法

4、的比較（十一）內(nèi)部排序算法的使用題型和分值填空題15%、選擇題20%、問答題40%、算法題25%3 算機組成原理（30分）考查目標(biāo)1 .理解單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連 接方式，具有完整的計算機系統(tǒng)的整機概念。2 .能夠運用計算機組成的基本原理和基本方法，對有關(guān)計算機硬件系統(tǒng)中的 理論和實際問題進(jìn)行計算、分析，并能對一些基本部件進(jìn)行簡單設(shè)計考查內(nèi)容一、概述1 .存儲程序概念2 .計算機硬件的基本組成3 .馮諾依曼結(jié)構(gòu)和哈佛結(jié)構(gòu)的存儲器設(shè)計思想4 .計算機系統(tǒng)的多層次結(jié)構(gòu)5 .計算機的主要性能指標(biāo)二、數(shù)據(jù)的機器層次表示（一）數(shù)值數(shù)據(jù)的表示1 .進(jìn)位計數(shù)制及其相互轉(zhuǎn)

5、換2 .無符號數(shù)3 .帶符號數(shù)（真值和機器數(shù)）（二）機器數(shù)的定點表示和浮點表示1 .定點數(shù)的表示2 .浮點數(shù)的表示三、指令系統(tǒng)（一）指令格式1 .指令的基本格式2 .定長操作碼指令格式3 .擴(kuò)展操作碼指令格式（二）指令的尋址方式1 .有效地址的概念2 .數(shù)據(jù)尋址和指令尋址3 .常見尋址方式（三）CISC和RISC的基本概念四、數(shù)值的機器運算（一）基本算術(shù)運算的實現(xiàn)1 .串行加法器和并行加法器2 .進(jìn)位的產(chǎn)生和傳遞3 .并行加法器的快速進(jìn)位（二）定點數(shù)的運算1 .補碼定點數(shù)的加/減運算2 .溢出概念和判別方法3 .定點數(shù)的移位操作4 .定點數(shù)的乘/除運算（三）浮點數(shù)的運算（四）十進(jìn)制整數(shù)的加法運

6、算（五）算術(shù)邏輯單元ALU的功能和結(jié)構(gòu)五、存儲系統(tǒng)和結(jié)構(gòu)（一）存儲系統(tǒng)的組成（二）主存儲器的組織（三）半導(dǎo)體隨機存儲器和只讀存儲器5 .SRAM存儲器的工作原理2 .DRAM存儲器的工作原理3 .只讀存儲器（四）主存儲器的連接和控制1 .主存容量的擴(kuò)展2 .存儲芯片的地址分配和片選3 .主存儲器和CPU的連接（六）高速緩沖存儲器（Cache ）I.Cache的基本工作原理4 .Cache和主存之間的映射方式5 .Cache中主存塊的替換算法6 .Cache寫策略（七）虛擬存儲器1 .虛擬存儲器的基本概念2 .頁式虛擬存儲器3 .快慢表六、中央處理器（一）CPU的功能和基本結(jié)構(gòu)1 .CPU中的主

7、要寄存器2 .CPU的組成（二）控制器的組成和實現(xiàn)方法1 .控制器的基本組成2 .硬布線控制器和微程序控制器的區(qū)別（三）時序系統(tǒng)和控制方式（四）數(shù)據(jù)通路的功能和基本結(jié)構(gòu)（五）微程序控制原理1 .微程序2 .微指令和微命令3 .微指令的編碼方式4 .微地址的形式方式。（六）指令流水線1 .指令流水線的基本概念2 .指令流水線的基本實現(xiàn)題型和分值填空題20% ,選擇題30% ,綜合使用題50%。885軟件工程專業(yè)基礎(chǔ)綜合一、考查目標(biāo)軟件工程專業(yè)基礎(chǔ)綜合涵蓋程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)等學(xué)科專業(yè)基礎(chǔ)課程。要求 考生系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的概念、基本原理和方法，能夠運用基本原理 和基本方法分析和解決有關(guān)理論

8、問題和實際問題。二、測試形式和試卷結(jié)構(gòu)試卷滿分及測試時間本試卷滿分為150分，測試時間為180分鐘答題方式閉卷、筆試試卷內(nèi)容結(jié)構(gòu)程序設(shè)計75分?jǐn)?shù)據(jù)2片勾75分試卷題型結(jié)構(gòu)單項選擇題20分程序填空題15分編程題50分簡答題50分算法設(shè)計題15分三、考查范圍程序設(shè)計部分1 .測試內(nèi)容數(shù)據(jù)類型：常量、變量、數(shù)組、字符串、指針，變量的初始化、變量存儲類型；運算符和表達(dá)式：運算符的運算規(guī)則和優(yōu)先級、表達(dá)式、類型轉(zhuǎn)換；程序的控制：程序的三種基本結(jié)構(gòu)、語句、數(shù)據(jù)的輸入輸出；函數(shù)：函數(shù)的定義、函數(shù)的調(diào)用、參數(shù)傳遞、帶參數(shù)的主函數(shù)、函數(shù)的遞歸；結(jié)構(gòu)和聯(lián)合：構(gòu)造數(shù)據(jù)類型的概念、結(jié)構(gòu)的定義和引用、聯(lián)合的定義和引用、

9、鏈表；文件：文件的概念、文件指針、文件的打開、關(guān)閉及操作；2 .測試要求掌握C程序設(shè)計語言的基本語法掌握常見的程序設(shè)計方法。掌握基本的數(shù)值、排序等算法，以及窮舉、遞推、遞歸等方法。3 .分值75分4 .題型單項選擇題10分程序填空題15分編程題50分?jǐn)?shù)據(jù)結(jié)構(gòu)部分1 .測試內(nèi)容基本概念：數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)對象，抽象數(shù)據(jù)類型，算法, 算法的時間復(fù)雜度和空間復(fù)雜度。線性表：線性表的邏輯結(jié)構(gòu)和基本操作，順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡單使用 和實現(xiàn)。棧和隊列：棧和隊列的基本概念，存儲結(jié)構(gòu)，基本操作，簡單使用和實現(xiàn)。數(shù)組和廣義表：數(shù)組的定義及順序存儲結(jié)構(gòu)，矩陣的壓縮存儲，數(shù)組的簡 單使用，廣義表的定義和基本操作。樹和二叉樹：樹的定義和基本操作，二叉樹的概念和基本性質(zhì)，二叉樹的 存儲結(jié)構(gòu)，遍歷二叉樹和線索二叉樹，樹和森林和二叉樹的關(guān)系，哈夫曼樹和哈 夫曼編碼，樹的簡單使用。圖：圖的基本概念，圖的存儲結(jié)構(gòu)，圖的遍歷，圖的使用，圖的連通性，有向無環(huán)圖及其使用，最短路徑，關(guān)鍵路徑。查找：順序表的查找，二叉排序樹和平衡二叉樹，B-樹和B+樹，哈希表排序：插入排序，快速排序，選擇排序，堆