1、813計算機專業基礎參考書目數據結構（C語言版）,嚴蔚敏,吳偉民,清華大學出版社計算機組成原理（第3版）,蔣本珊,清華大學出版社885軟件工程專業基礎綜合參考書目C語言程序設計,清華大學出版社,譚浩強,第三版數據結構,清華大學出版社,嚴蔚敏,2002.09813計算機專業基礎數據結構（120分）考查內容：數據結構主要考查考生以下幾個方面：1.理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現。2.掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。3.能夠選擇合適的數據結構和方法進行問題求解。應掌握的具體內容為：一、線性表（一）線性表的定義和基本操

2、作（二）線性表的實現1.順序存儲結構2.鏈式存儲結構3.線性表的應用二、棧、隊列和數組（一）棧和隊列的基本概念（二）棧和隊列的順序存儲結構（三）棧和隊列的鏈式存儲結構（四）棧和隊列的應用（五）特殊矩陣的壓縮存儲三、樹與二叉樹（一）樹的概念（二）二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結構和鏈式存儲結構3.二叉樹的遍歷4.線索二叉樹的基本概念和構造5.二叉排序樹6.平衡二叉樹（三）樹、森林1.書的存儲結構2.森林與二叉樹的轉換3.樹和森林的遍歷（四）樹的應用1.等價類問題2.哈夫曼（Huffman）樹和哈夫曼編碼四、圖（一）圖的概念（二）圖的存儲及基本操作1.鄰接矩陣法2.鄰接表法

3、（三）圖的遍歷1.深度優先搜索2.廣度優先搜索（四）圖的基本應用及其復雜度分析1.最小（代價）生成樹2.最短路徑3.拓撲排序4.關鍵路徑五、查找（一）查找的基本概念（二）順序查找法（三）折半查找法（四）B-樹（五）散列（Hash）表及其查找（六）查找算法的分析及應用六、內部排序（一）排序的基本概念（二）插入排序1.直接插入排序2.折半插入排序（三）起泡排序（bubblesort）（四）簡單選擇排序（五）希爾排序（shellsort）（六）快速排序（七）堆排序（八）二路歸并排序（mergesort）（九）基數排序（十）各種內部排序算法的比較（十一）內部排序算法的應用題型和分值填空題15%、選擇題

4、20%、問答題40%、算法題25%計算機組成原理（30分）考查目標1.理解單處理器計算機系統中各部件的內部工作原理、組成結構以及相互連接方式，具有完整的計算機系統的整機概念。2.能夠運用計算機組成的基本原理和基本方法，對有關計算機硬件系統中的理論和實際問題進行計算、分析，并能對一些基本部件進行簡單設計。考查內容一、概述1.存儲程序概念2.計算機硬件的基本組成3.馮·諾依曼結構和哈佛結構的存儲器設計思想4.計算機系統的多層次結構5.計算機的主要性能指標二、數據的機器層次表示（一）數值數據的表示1.進位計數制及其相互轉換2.無符號數3.帶符號數（真值和機器數）（二）機器數的定點表示與浮點

5、表示1.定點數的表示2.浮點數的表示三、指令系統（一）指令格式1.指令的基本格式2.定長操作碼指令格式3.擴展操作碼指令格式（二）指令的尋址方式1.有效地址的概念2.數據尋址和指令尋址3.常見尋址方式（三）CISC和RISC的基本概念四、數值的機器運算（一）基本算術運算的實現1.串行加法器和并行加法器2.進位的產生和傳遞3.并行加法器的快速進位（二）定點數的運算1.補碼定點數的加/減運算2.溢出概念和判別方法3.定點數的移位操作4.定點數的乘/除運算（三）浮點數的運算（四）十進制整數的加法運算（五）算術邏輯單元ALU的功能和結構五、存儲系統與結構（一）存儲系統的組成（二）主存儲器的組織（三）半

6、導體隨機存儲器和只讀存儲器1.SRAM存儲器的工作原理2.DRAM存儲器的工作原理3.只讀存儲器（四）主存儲器的連接與控制1.主存容量的擴展2.存儲芯片的地址分配和片選3.主存儲器與CPU的連接（六）高速緩沖存儲器（Cache）1.Cache的基本工作原理2.Cache和主存之間的映射方式3.Cache中主存塊的替換算法4.Cache寫策略（七）虛擬存儲器1.虛擬存儲器的基本概念2.頁式虛擬存儲器3.快慢表六、中央處理器（一）CPU的功能和基本結構1.CPU中的主要寄存器2.CPU的組成（二）控制器的組成和實現方法1.控制器的基本組成2.硬布線控制器和微程序控制器的區別（三）時序系統與控制方式

7、（四）數據通路的功能和基本結構（五）微程序控制原理1.微程序2.微指令和微命令3.微指令的編碼方式4.微地址的形式方式。（六）指令流水線1.指令流水線的基本概念2.指令流水線的基本實現題型和分值填空題20%，選擇題30%，綜合應用題50%。885軟件工程專業基礎綜合一、考查目標軟件工程專業基礎綜合涵蓋程序設計、數據結構等學科專業基礎課程。要求考生系統地掌握上述專業基礎課程的概念、基本原理和方法，能夠運用基本原理和基本方法分析和解決有關理論問題和實際問題。二、考試形式和試卷結構試卷滿分及考試時間本試卷滿分為150分，考試時間為180分鐘答題方式閉卷、筆試試卷內容結構程序設計75分數據結構75分試

8、卷題型結構單項選擇題20分程序填空題15分編程題50分簡答題50分算法設計題15分三、考查范圍程序設計部分1.考試內容數據類型：常量、變量、數組、字符串、指針，變量的初始化、變量存儲類型；運算符與表達式：運算符的運算規則和優先級、表達式、類型轉換；程序的控制：程序的三種基本結構、語句、數據的輸入輸出；函數：函數的定義、函數的調用、參數傳遞、帶參數的主函數、函數的遞歸；結構與聯合：構造數據類型的概念、結構的定義與引用、聯合的定義與引用、鏈表；文件：文件的概念、文件指針、文件的打開、關閉及操作；2.考試要求掌握C程序設計語言的基本語法。掌握常見的程序設計方法。掌握基本的數值、排序等算法，以及窮舉、

9、遞推、遞歸等方法。3.分值75分4.題型單項選擇題10分程序填空題15分編程題50分數據結構部分1.考試內容基本概念：數據結構，數據，數據元素，數據對象，抽象數據類型，算法，算法的時間復雜度和空間復雜度。線性表：線性表的邏輯結構和基本操作，順序和鏈式存儲結構，簡單應用與實現。棧和隊列：棧和隊列的基本概念，存儲結構，基本操作，簡單應用與實現。數組和廣義表：數組的定義及順序存儲結構，矩陣的壓縮存儲，數組的簡單應用，廣義表的定義與基本操作。樹和二叉樹：樹的定義和基本操作，二叉樹的概念和基本性質，二叉樹的存儲結構，遍歷二叉樹和線索二叉樹，樹和森林與二叉樹的關系，哈夫曼樹和哈夫曼編碼，樹的簡單應用。圖：圖的基本概念，圖的存儲結構，圖的遍歷，圖的應用，圖的連通性，有向無環圖及其應用，最短路徑，關鍵路徑。查找：順序表的查找，二叉排序樹和平衡二叉樹，B-樹和B+樹，哈希表。排序：插入排序，快速排序，選擇排序，堆排序