2019隴東學院專升本計算機科學與技術專業考試大綱歷年真題錄取分數線(二)

第4章串

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

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

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

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

第5章數組和廣義表

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

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

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

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

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

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

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

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

第6章樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第7章圖

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

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

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

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

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

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

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

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

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

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

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

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

13、掌握要求對給定