2019年北京科技大學(xué)碩士研究生《計(jì)算機(jī)綜合一》考試大綱

　　一、考試性質(zhì)與范圍

　　本考試科目是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科碩士研究生入學(xué)的專(zhuān)業(yè)基礎(chǔ)課程考試，旨在考察考生對(duì)計(jì)算機(jī)組成原理與數(shù)據(jù)結(jié)構(gòu)基本原理和方法的掌握程度以及運(yùn)用基本原理和方法分析、解決問(wèn)題的能力。考試范圍包括計(jì)算機(jī)組成原理和數(shù)據(jù)結(jié)構(gòu)。

　　二、考試基本要求

　　計(jì)算機(jī)組成原理要求考生掌握：

　　1.掌握計(jì)算機(jī)硬件系統(tǒng)的基本組成及工作機(jī)理，包括運(yùn)算器的構(gòu)成及工作原理；控制器的設(shè)計(jì)與實(shí)現(xiàn)方法；存儲(chǔ)器及層次存儲(chǔ)體系的概念及工作原理；輸入/輸出系統(tǒng)及工作方式。并建立整機(jī)概念，各基本部件如何協(xié)調(diào)工作完成指定任務(wù)；

　　2.理解計(jì)算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識(shí)和基本實(shí)現(xiàn)方法；

　　3.能夠運(yùn)用計(jì)算機(jī)組成的基本原理和基本方法，對(duì)有關(guān)計(jì)算機(jī)硬件系統(tǒng)中的理論和實(shí)際問(wèn)題進(jìn)行計(jì)算、分析，并能對(duì)一些基本部件進(jìn)行簡(jiǎn)單設(shè)計(jì)。

　　數(shù)據(jù)結(jié)構(gòu)要求考生掌握：

　　1.數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；

　　2.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度分析；能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問(wèn)題分析與求解，具備采用C或C++語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。

　　三、考試形式與分值

　　答題方式為閉卷、筆試。

　　考試時(shí)間為180分鐘，試卷滿(mǎn)分為150分，其中：

　　計(jì)算機(jī)組成原理 75分

　　數(shù)據(jù)結(jié)構(gòu)75分

　　四、考試內(nèi)容

　　I計(jì)算機(jī)組成原理

　　1.計(jì)算機(jī)系統(tǒng)概述

　　1）電子計(jì)算機(jī)與存儲(chǔ)程序控制。了解計(jì)算機(jī)的發(fā)展歷史，掌握數(shù)字化概念、存儲(chǔ)程序工作方式和馮諾依曼體制。

　　2）計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu)

　　計(jì)算機(jī)硬件的基本組成、計(jì)算機(jī)軟件的分類(lèi)、計(jì)算機(jī)的工作過(guò)程

　　（1）計(jì)算機(jī)系統(tǒng)。熟悉計(jì)算機(jī)硬件系統(tǒng)的組織、硬件與軟件間的關(guān)系、計(jì)算機(jī)系統(tǒng)軟硬件的邏輯等效性。

　?。?）掌握計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)概念，了解系列機(jī)和軟件兼容。

　　3）計(jì)算機(jī)性能指標(biāo)

　　吞吐量、響應(yīng)時(shí)間；CPU時(shí)鐘周期、主頻、CPI、CPU執(zhí)行時(shí)間；MIPS、MFLOPS。

　　2.數(shù)據(jù)的機(jī)器層次表示

　　1）數(shù)值數(shù)據(jù)的表示。熟悉進(jìn)位計(jì)數(shù)制基本概念，掌握原碼、補(bǔ)碼表示方法及其相互轉(zhuǎn)換。

　　2）機(jī)器數(shù)的定點(diǎn)表示和浮點(diǎn)表示。掌握定點(diǎn)整數(shù)、定點(diǎn)小數(shù)表示。掌握浮點(diǎn)數(shù)的表示方法和表示范圍、規(guī)格化和隱藏位等技術(shù)、階碼的移碼表示法及IEEE754標(biāo)準(zhǔn)。了解定點(diǎn)、浮點(diǎn)表示法的區(qū)別，定點(diǎn)、浮點(diǎn)計(jì)算機(jī)。

　　3）非數(shù)值數(shù)據(jù)的表示。了解字符和字符串的表示、漢字的編碼及統(tǒng)一代碼（Unicode）。

　　4）十進(jìn)制數(shù)和數(shù)串的表示。掌握常見(jiàn)的十進(jìn)制數(shù)的編碼方法以及十進(jìn)制數(shù)串的存儲(chǔ)方法。了解現(xiàn)代微型計(jì)算機(jī)系統(tǒng)中各種數(shù)據(jù)的表示方法。

　　5）數(shù)據(jù)校驗(yàn)碼。掌握數(shù)據(jù)校驗(yàn)碼的概念和實(shí)現(xiàn)原理，了解奇偶校驗(yàn)、海明校驗(yàn)的校驗(yàn)原理與實(shí)現(xiàn)方法。

　　3.指令系統(tǒng)

　　1）指令格式：掌握擴(kuò)展操作碼指令集設(shè)計(jì)的基本方法。

　　指令的基本格式、定長(zhǎng)操作碼指令格式、擴(kuò)展操作碼指令格式。

　　2）指令的尋址方式

　　有效地址的概念、數(shù)據(jù)尋址和指令尋址、常見(jiàn)尋址方式、堆棧的結(jié)構(gòu)和堆棧操作

　　3）CISC和RISC的基本概念

　　4.數(shù)值的機(jī)器運(yùn)算

　　1）定點(diǎn)數(shù)的運(yùn)算

　　1.定點(diǎn)數(shù)的移位運(yùn)算和舍入操作。

　　2.定點(diǎn)數(shù)的加/減運(yùn)算；溢出概念和判別方法。

　　3.定點(diǎn)數(shù)的乘/除運(yùn)算；掌握一位乘法及其實(shí)現(xiàn)邏輯。

　　2）規(guī)格化浮點(diǎn)運(yùn)算

　　1.浮點(diǎn)數(shù)的運(yùn)算方法與流程

　　2.浮點(diǎn)運(yùn)算器的組成及實(shí)現(xiàn)

　　3）算術(shù)邏輯單元ALU

　　1.串行加法器、并行加法器和快速進(jìn)位鏈

　　2.算術(shù)邏輯單元ALU的基本組成與實(shí)現(xiàn)

　　5.存儲(chǔ)系統(tǒng)和結(jié)構(gòu)

　　1）存儲(chǔ)器的分類(lèi)

　　2）存儲(chǔ)器的層次化結(jié)構(gòu)

　　3）半導(dǎo)體隨機(jī)存取存儲(chǔ)器

　　1.SRAM存儲(chǔ)器的工作原理

　　2.DRAM存儲(chǔ)器的工作原理

　　3.只讀存儲(chǔ)器

　　4.Flash存儲(chǔ)器

　　4）主存儲(chǔ)器與CPU的連接

　　5）雙口RAM和多模塊存儲(chǔ)器

　　6）高速緩沖存儲(chǔ)器（Cache）

　　1.程序訪問(wèn)的局部

　　2.Cache的基本工作原理

　　3.Cache和主存之間的映射方式

　　4.Cache中主存塊的替換算法

　　5.Cache寫(xiě)策略

　　6.中央處理器（CPU）

　　1）CPU的功能和基本結(jié)構(gòu)

　　2）數(shù)據(jù)通路的功能和基本結(jié)構(gòu)

　　3）時(shí)序系統(tǒng)與控制方式

　　4）指令執(zhí)行過(guò)程

　　5）控制器的功能和工作原理

　　1.組合邏輯控制器

　　2.微程序控制器：微程序、微指令和微命令；微指令的編碼方式；微地址的形式方式。

　　6）控制單元的設(shè)計(jì)。掌握設(shè)計(jì)模型機(jī)的流程，掌握組合邏輯控制器的組成原理及設(shè)計(jì)方法；掌握微程序控制器的設(shè)計(jì)方法與步驟。

　　7.輸入輸出（I/O）系統(tǒng)

　　1）I/O系統(tǒng)基本概念

　　2）I/O接口（I/O控制器）

　　1.I/O接口的功能和基本結(jié)構(gòu)

　　2.I/O端口及其編址

　　3）I/O方式

　　1.程序查詢(xún)方式

　　2.程序中斷方式

　　中斷的基本概念；中斷響應(yīng)過(guò)程；中斷處理過(guò)程；多重中斷和中斷屏蔽的概念。

　　3.DMA方式

　　DMA控制器的組成；DMA傳送過(guò)程。

　　4.通道方式

　　4）總線技術(shù)

　　1.總線的基本概念、分類(lèi)及性能指標(biāo)

　　2.同步定時(shí)方式，異步定時(shí)方式

　　II 數(shù)據(jù)結(jié)構(gòu)

　　1.數(shù)據(jù)結(jié)構(gòu)緒論

　　1）數(shù)據(jù)結(jié)構(gòu)的基本概念、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

　　2）算法和算法分析

　　2.線性表

　　1）線性表的定義及其基本操作

　　2）線性表的順序存儲(chǔ)結(jié)構(gòu)

　　3）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

　　4）線性表的應(yīng)用

　　3.棧和隊(duì)列

　　1）棧和隊(duì)列的定義及其操作

　　2）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

　　3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

　　4）棧和隊(duì)列的應(yīng)用

　　4. 數(shù)組

　　1）數(shù)組的定義及其操作

　　2）數(shù)組的存儲(chǔ)結(jié)構(gòu)

　　3）矩陣的壓縮存儲(chǔ)

　　5. 樹(shù)

　　1）樹(shù)的基本概念

　　2）二叉樹(shù)的定義及其基本操作、二叉樹(shù)的性質(zhì)與存儲(chǔ)結(jié)構(gòu)

　　3）二叉樹(shù)的遍歷

　　4）線索二叉樹(shù)

　　5）樹(shù)和森林

　　6）Huffman樹(shù)與Huffman編碼

　　7）二叉樹(shù)的應(yīng)用

　　6.圖

　　1）圖的定義及操作

　　2）圖的存儲(chǔ)結(jié)構(gòu)

　　3）圖的遍歷

　　4）最小生成樹(shù)

　　5）最短路徑問(wèn)題

　　6）拓?fù)渑判蚺c關(guān)鍵路徑

　　7）圖的應(yīng)用

　　7.查找

　　1）查找的基本概念

　　2）順序表的查找

　　3）二叉排序樹(shù)(或稱(chēng)二叉查找樹(shù)）和平衡二叉排序樹(shù)

　　4）Hash表及其查找

　　5）查找算法的應(yīng)用

　　8.排序

　　1）排序的基本概念

　　2）插入排序：直接插入排序、折半插入排序、鏈表插入排序、Shell排序

　　3）交換排序：起泡排序、快速排序

　　4）選擇排序：直接選擇排序、堆選擇排序

　　5）二路歸并排序

　　6）基數(shù)排序

　　7）各種內(nèi)排序方法的比較

　　8）內(nèi)排序算法的應(yīng)用

　　參考書(shū)目

　　[1]蔣本珊．計(jì)算機(jī)組成原理（第3版）．清華大學(xué)出版社，2013

　　[2]唐朔飛．計(jì)算機(jī)組成原理（第2版）．高等教育出版社，2008

　　[3]齊悅，夏克儉，姚琳．?dāng)?shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用．清華大學(xué)出版社

　　[4]嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）．清華大學(xué)出版社