隴東學院2020年專升本計算機科學與技術專業(yè)課考試大綱

《數據結構》

一、考試目的

考核普通高等學校?？疲ê呗殻獙卯厴I(yè)生對于《數據結構》課程基本知識掌握是否達到教學大綱所規(guī)定的要求。

二、考試要求及內容

第1章 緒論

1、掌握數據、數據元素、數據項、數據結構等基本概念。

2、掌握數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系。

3、掌握數據結構的兩大類邏輯結構和四種常用的存儲表示方法。

4、理解算法、算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。

5、掌握算法描述和算法分析的方法，對于一般算法能分析出時間復雜度。  

第2章 線性表

1、理解線性表的邏輯結構特征。

2、理解線性表上定義的基本運算，并能利用基本運算構造出較復雜的運算。

線性表的順序存儲結構，要求達到“綜合利用”層次?！?/span>

3、 理解順序表的含義及特點，即順序表如何反映線性表中元素之間的邏輯關系。

4、掌握順序表上的插入、刪除操作及其平均時間性能分析?！?/span>

5、理解利用順序表設計算法解決簡單的應用問題。　　

6、掌握鏈表如何表示線性表中元素之間的邏輯關系。　　

7、掌握鏈表中頭指針和頭結點的使用。　

8、理解單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別?！?/span>

9、 掌握單鏈表上實現的建表、查找、插入和刪除等基本算法，并分析其時間復雜度。  

10、理解循環(huán)鏈表上尾指針取代頭指針的作用，以及單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。  

11、理解雙鏈表的定義及其相關的算法?！　?/span>

12、掌握利用鏈表設計算法解決簡單的應用問題。　

13、理解順序表和鏈表的主要優(yōu)缺點。

14、掌握針對線性表上所需要執(zhí)行的主要操作，知道選擇順序表還是鏈表作為其存儲結構才能取得較優(yōu)的時空性能。

第3章 棧和隊列

1、理解棧的邏輯結構特點，棧與線性表的異同。

2、掌握順序棧和鏈棧上實現的進棧、退棧等基本算法。

3、理解棧的“上溢”和“下溢”的概念及其判別條件。

4、掌握利用棧設計算法解決簡單的應用問題。

5、理解隊列的邏輯結構特點，隊列與線性表的異同。

6、掌握順序隊列（主要是循環(huán)隊列）和鏈隊列上實現的入隊、出隊等基本算法。

7、理解隊列的“上溢”和“下溢”的概念及其判別條件。

8、了解使用數組實現的循環(huán)隊列取代普通的順序隊列的原因。

9、掌握循環(huán)隊列中對邊界條件的處理方法。

10、掌握利用隊列設計算法解決簡單的應用問題。

第4章 串

1、掌握串的有關概念及基本運算。

2、理解串與線性表的關系。

3、掌握串的兩種存儲表示。

4、掌握使用C語言提供的串操作函數構造與串相關的算法解決簡單的應用問題。

第5章 數組和廣義表

1、掌握數組的邏輯結構特征。

2、掌握數組的順序存儲結構及地址計算方式。

3、掌握數組是一種隨機存取結構的原因。

4、理解特殊矩陣和稀疏矩陣的概念。

5、理解特殊矩陣和壓縮存儲時的下標變換方法。

6、理解稀疏矩陣的三元組表表示方法及有關算法。

7、掌握廣義表的有關概念及其與線性表的關系。

8、掌握廣義表的括號表示和圖形表示之間的轉換。

第6章  樹

1、掌握樹的邏輯結構特征。

2、掌握樹的不同表示方法。

3、掌握樹的常用術語及含義。

4、二叉樹的遞歸定義及樹與二叉樹的差別。

5、掌握二叉樹的性質，了解相應的證明方法。

6、掌握二叉樹的兩種存儲方法、特點及適用范圍。

7、掌握二叉樹的三種遍歷算法，理解其執(zhí)行過程。

8、掌握確定三種遍歷所得到的相應的結點訪問序列。

9、理解以遍歷算法為基礎，設計有關算法解決簡單的應用問題。

10、理解二叉樹線索化的目的及實質。

11、理解在中序線索樹中查找給定結點的中序前趨和中序后繼的方法。

12、掌握樹和森林與二叉樹之間的轉換方法。

13、掌握樹的各種存儲結構及其特點。

14、掌握樹的兩種遍歷方法。

15、掌握最優(yōu)二叉樹和最優(yōu)前綴碼的概念及特點。

16、掌握哈夫曼算法的思想。

17、掌握根據給定的葉結點及其權值構造出相應的最優(yōu)二叉樹。

18、掌握根據最優(yōu)二叉樹構造對應的哈夫曼編碼。

第7章  圖

1、理解圖的邏輯結構特征。

2、理解圖的常用術語及含義。

3、掌握鄰接矩陣和鄰接表這兩種存儲結構的特點及適用范圍。

4、掌握根據應用問題的特點和要求選擇合適的存儲結構。

5、理解連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法,其執(zhí)行過程以及時間分析。

6、掌握確定兩種遍歷所得到的頂點訪問序列。

7、掌握圖的兩種遍歷與樹的遍歷之間的關系。

8、 理解兩種遍歷所使用的輔助數據結構（棧或隊列）在遍歷過程中所起的作用。

9、理解利用圖的兩種遍歷設計算法解決簡單的應用問題。

10、掌握生成樹和最小生成樹的概念。

11、掌握對遍歷給定的圖，畫出深度優(yōu)先和廣度優(yōu)先生成樹或生成森林。

12、掌握Prim和Kruskal算法的基本思想、時間性能及這兩種算法各自的特點。

13、掌握要求對給定的連通圖，根據Prim和Kruskal算法構造出最小生成樹。

14、了解最短路徑的含義。

15、了解求單源最短路徑的Dijkstra算法的基本思想和時間性能。

16、掌握對于給定的有向圖，根據Dijkstra算法畫出求單源最短路徑的過程示意圖。

17、掌握拓撲排序的基本思想和步驟。

18、理解拓撲排序不成功的原因。

19、了解對給定的有向圖，若拓撲序列存在，則要求寫出一個或多個拓撲序列。

第9章  查找

1、了解查找在數據處理中的重要性。

2、理解查找算法效率的評判標準。

3、掌握順序查找、二分查找、分塊查找的基本思想、算法實現和查找效率分析。

4、理解順序查找中哨兵的作用。

5、理解二分查找對存儲結構及關鍵字的要求。

6、理解通過比較線性表上三種查找方法的優(yōu)缺點，能根據實際問題的要求和特點，選擇出合適的查找方法。

7、掌握二叉查找樹和B-樹的定義和特點以及用途。

8、掌握二叉查找樹的插入、刪除、建樹和查找算法及時間性能。

9、掌握建立一棵二叉查找樹的過程實質上是對輸入實例的排序過程，輸入實例對所建立的二叉查找樹形態(tài)的影響。

10、了解B－樹的插入、刪除及查找方法的基本思想。

11、掌握散列表、散列函數、散列地址和裝填因子等有關概念。

12、掌握散列函數的選取原則及產生沖突的原因。

13、掌握幾種常用的散列函數構造方法。

14、理解兩類解決沖突的方法及其優(yōu)缺點。

15、了解產生“堆積”現象的原因。

16、理解采用線性探測法和拉鏈法解決沖突時，散列表的建表方法、查找過程以及算法實現和時間分析。

17、了解散列表和其它表的本質區(qū)別。

第10章  排序

1、了解排序在數據處理中的重要性。

2、掌握排序方法的“穩(wěn)定”性含義。

3、理解排序方法的分類及算法好壞的評判標準。

4、掌握直接插入排序的基本思想和算法實現，以及在最好、最壞和平均情況下的時間性能分析。

5、理解直接插入排序中哨兵的作用。

6、掌握針對給定的輸入實例，要能寫出直接插入排序的排序過程。

7、掌握冒泡排序的基本思想。

8、掌握快速排序的基本思想和算法實現，以及在最壞和平均情況下的時間性能分析，了解算法的穩(wěn)定性。

9、了解基準元素（劃分元）對劃分是否平衡的影響。

10、掌握針對給定的輸入實例，能寫出快速排序的排序過程。

11、理解堆、小根堆、大根堆、堆項等有關概念和定義。

12、理解堆性質及堆與完全二叉樹的關系。

13、掌握直接選擇排序和堆排序的基本思想和算法實現，以及時間性能分析。

14、掌握針對給定的輸入實例，寫出堆排序的排序過程。

15、掌握歸并排序的基本思想和算法實現，以及時間性能分析。

16、掌握針對給定的輸入實例，能寫出歸并排序的排序過程。

17、掌握通過對被排序的記錄數目、記錄信息量的大小、關鍵字的結構及初始狀態(tài)、穩(wěn)定性要求、輔助空間的大小、各種時間性能等方面的比較掌握各種排序的優(yōu)缺點。　　

參考教材：

1.《數據結構用C語言描述》（第二版），耿國華等編寫，高等教育出版社，2015年；

2.《數據結構》（C語言版），嚴蔚敏、吳偉民編著，清華大學出版社，2011年。

《計算機組成原理》

一、考試目的

考核普通高等學校?？疲ê呗殻獙卯厴I(yè)生對于《計算機組成原理》課程基本知識掌握是否達到教學大綱所規(guī)定的要求。

二、考試要求及內容

第1章 計算機系統(tǒng)概論

了解計算機系統(tǒng)的層次結構。

第2章 運算方法與運算部件

1、了解數據的表示方法和轉化。

2、掌握帶符號的二進制數據在計算機中的表示：原碼、反碼、補碼、移碼及其相互轉化。

3、掌握補碼加減法，并能判斷溢出。

4、掌握定點數和浮點數表示方法。

5、掌握定點原碼、補碼一位乘法運算。

6、掌握定點補碼一位除法運算。

7、了解浮點數的加減法運算。

8、了解浮點數的乘除法運算。

9、理解定點運算部件。

第3章 存儲器

1、理解主存儲器處于全機中心地位。

2、了解主存儲器的分類。

3、理解主存儲器的主要技術指標。

4、理解主存儲器的基本操作。

5、了解SRAM、DRAM以及非易失性半導體存儲器的特點。

6、理解DRAM的刷新。

7、理解多體交叉存儲器。

8、掌握存儲器容量的擴展。

9、掌握存儲系統(tǒng)的層次結構。

10、掌握cache存儲器的工作原理、cache存儲器組織。

11、了解存儲管理部件（MMU）。

12、了解相聯(lián)存儲器、存儲保護。

第4章 指令系統(tǒng)

1、了解指令系統(tǒng)的發(fā)展。

2、掌握指令格式、指令操作碼的擴展技術、指令長度與字長的關系。

3、理解數據表示。

4、掌握指令和操作數的尋址方式。

5、理解指令類型。

6、理解RISC產生及其特點。

第5章 中央處理器（CPU）

1、理解計算機的工作過程。

2、理解控制器的功能。

3、掌握控制器的組成。

4、掌握指令的執(zhí)行過程。

5、掌握微程序控制的基本概念、實現微程序控制的基本原理、微程序控制計算機的工作過程。

6、掌握微程序的設計技術：微指令的編譯法、微指令的格式、微程序存儲器。

7、了解硬連線控制的計算機。

8、了解控制器的控制方式。

9、理解流水線工作的原理。

三、試題難易程度

較容易題          約30%

中等難度題        約50%

較難題            約20%

四、參考教材

1.《計算機組成原理》第2版,唐朔飛編著,高等教育出版社,2008年1月第2版，2011年5月第9次印刷;

2.《計算機組成原理》第5版,白中英編著,科學出版社,2015年7月第5版。

五、說明

試卷滿分為200分（計算機組成原理100分＋數據結構100分），考試時間120分鐘，試卷長度為A4紙8-10版。

推薦閱讀

隴東學院2020年專升本護理學專業(yè)課考試大綱