發(fā)布時間:2020/02/10 10:20:21 來源:易學仕專升本網(wǎng) 閱讀量:2438
摘要:隴東學院2020年專升本計算機科學與技術(shù)專業(yè)課考試大綱
《數(shù)據(jù)結(jié)構(gòu)》
一、考試目的
考核普通高等學校??疲ê呗殻獙卯厴I(yè)生對于《數(shù)據(jù)結(jié)構(gòu)》課程基本知識掌握是否達到教學大綱所規(guī)定的要求。
二、考試要求及內(nèi)容
第1章 緒論
1、掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本概念。
2、掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關(guān)系。
3、掌握數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。
4、理解算法、算法的時間復雜度和空間復雜度、最壞的和平均的時間復雜度等概念。
5、掌握算法描述和算法分析的方法,對于一般算法能分析出時間復雜度。
第2章 線性表
1、理解線性表的邏輯結(jié)構(gòu)特征。
2、理解線性表上定義的基本運算,并能利用基本運算構(gòu)造出較復雜的運算。
線性表的順序存儲結(jié)構(gòu),要求達到“綜合利用”層次?!?/span>
3、 理解順序表的含義及特點,即順序表如何反映線性表中元素之間的邏輯關(guān)系。
4、掌握順序表上的插入、刪除操作及其平均時間性能分析。
5、理解利用順序表設計算法解決簡單的應用問題?! ?/span>
6、掌握鏈表如何表示線性表中元素之間的邏輯關(guān)系?! ?/span>
7、掌握鏈表中頭指針和頭結(jié)點的使用?!?/span>
8、理解單鏈表、雙鏈表、循環(huán)鏈表鏈接方式上的區(qū)別。
9、 掌握單鏈表上實現(xiàn)的建表、查找、插入和刪除等基本算法,并分析其時間復雜度。
10、理解循環(huán)鏈表上尾指針取代頭指針的作用,以及單循環(huán)鏈表上的算法與單鏈表上相應算法的異同點。
11、理解雙鏈表的定義及其相關(guān)的算法?! ?/span>
12、掌握利用鏈表設計算法解決簡單的應用問題。
13、理解順序表和鏈表的主要優(yōu)缺點。
14、掌握針對線性表上所需要執(zhí)行的主要操作,知道選擇順序表還是鏈表作為其存儲結(jié)構(gòu)才能取得較優(yōu)的時空性能。
第3章 棧和隊列
1、理解棧的邏輯結(jié)構(gòu)特點,棧與線性表的異同。
2、掌握順序棧和鏈棧上實現(xiàn)的進棧、退棧等基本算法。
3、理解棧的“上溢”和“下溢”的概念及其判別條件。
4、掌握利用棧設計算法解決簡單的應用問題。
5、理解隊列的邏輯結(jié)構(gòu)特點,隊列與線性表的異同。
6、掌握順序隊列(主要是循環(huán)隊列)和鏈隊列上實現(xiàn)的入隊、出隊等基本算法。
7、理解隊列的“上溢”和“下溢”的概念及其判別條件。
8、了解使用數(shù)組實現(xiàn)的循環(huán)隊列取代普通的順序隊列的原因。
9、掌握循環(huán)隊列中對邊界條件的處理方法。
10、掌握利用隊列設計算法解決簡單的應用問題。
第4章 串
1、掌握串的有關(guān)概念及基本運算。
2、理解串與線性表的關(guān)系。
3、掌握串的兩種存儲表示。
4、掌握使用C語言提供的串操作函數(shù)構(gòu)造與串相關(guān)的算法解決簡單的應用問題。
第5章 數(shù)組和廣義表
1、掌握數(shù)組的邏輯結(jié)構(gòu)特征。
2、掌握數(shù)組的順序存儲結(jié)構(gòu)及地址計算方式。
3、掌握數(shù)組是一種隨機存取結(jié)構(gòu)的原因。
4、理解特殊矩陣和稀疏矩陣的概念。
5、理解特殊矩陣和壓縮存儲時的下標變換方法。
6、理解稀疏矩陣的三元組表表示方法及有關(guān)算法。
7、掌握廣義表的有關(guān)概念及其與線性表的關(guān)系。
8、掌握廣義表的括號表示和圖形表示之間的轉(zhuǎn)換。
第6章 樹
1、掌握樹的邏輯結(jié)構(gòu)特征。
2、掌握樹的不同表示方法。
3、掌握樹的常用術(shù)語及含義。
4、二叉樹的遞歸定義及樹與二叉樹的差別。
5、掌握二叉樹的性質(zhì),了解相應的證明方法。
6、掌握二叉樹的兩種存儲方法、特點及適用范圍。
7、掌握二叉樹的三種遍歷算法,理解其執(zhí)行過程。
8、掌握確定三種遍歷所得到的相應的結(jié)點訪問序列。
9、理解以遍歷算法為基礎,設計有關(guān)算法解決簡單的應用問題。
10、理解二叉樹線索化的目的及實質(zhì)。
11、理解在中序線索樹中查找給定結(jié)點的中序前趨和中序后繼的方法。
12、掌握樹和森林與二叉樹之間的轉(zhuǎn)換方法。
13、掌握樹的各種存儲結(jié)構(gòu)及其特點。
14、掌握樹的兩種遍歷方法。
15、掌握最優(yōu)二叉樹和最優(yōu)前綴碼的概念及特點。
16、掌握哈夫曼算法的思想。
17、掌握根據(jù)給定的葉結(jié)點及其權(quán)值構(gòu)造出相應的最優(yōu)二叉樹。
18、掌握根據(jù)最優(yōu)二叉樹構(gòu)造對應的哈夫曼編碼。
第7章 圖
1、理解圖的邏輯結(jié)構(gòu)特征。
2、理解圖的常用術(shù)語及含義。
3、掌握鄰接矩陣和鄰接表這兩種存儲結(jié)構(gòu)的特點及適用范圍。
4、掌握根據(jù)應用問題的特點和要求選擇合適的存儲結(jié)構(gòu)。
5、理解連通圖及非連通圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法,其執(zhí)行過程以及時間分析。
6、掌握確定兩種遍歷所得到的頂點訪問序列。
7、掌握圖的兩種遍歷與樹的遍歷之間的關(guān)系。
8、 理解兩種遍歷所使用的輔助數(shù)據(jù)結(jié)構(gòu)(?;蜿犃校┰诒闅v過程中所起的作用。
9、理解利用圖的兩種遍歷設計算法解決簡單的應用問題。
10、掌握生成樹和最小生成樹的概念。
11、掌握對遍歷給定的圖,畫出深度優(yōu)先和廣度優(yōu)先生成樹或生成森林。
12、掌握Prim和Kruskal算法的基本思想、時間性能及這兩種算法各自的特點。
13、掌握要求對給定的連通圖,根據(jù)Prim和Kruskal算法構(gòu)造出最小生成樹。
14、了解最短路徑的含義。
15、了解求單源最短路徑的Dijkstra算法的基本思想和時間性能。
16、掌握對于給定的有向圖,根據(jù)Dijkstra算法畫出求單源最短路徑的過程示意圖。
17、掌握拓撲排序的基本思想和步驟。
18、理解拓撲排序不成功的原因。
19、了解對給定的有向圖,若拓撲序列存在,則要求寫出一個或多個拓撲序列。
第9章 查找
1、了解查找在數(shù)據(jù)處理中的重要性。
2、理解查找算法效率的評判標準。
3、掌握順序查找、二分查找、分塊查找的基本思想、算法實現(xiàn)和查找效率分析。
4、理解順序查找中哨兵的作用。
5、理解二分查找對存儲結(jié)構(gòu)及關(guān)鍵字的要求。
6、理解通過比較線性表上三種查找方法的優(yōu)缺點,能根據(jù)實際問題的要求和特點,選擇出合適的查找方法。
7、掌握二叉查找樹和B-樹的定義和特點以及用途。
8、掌握二叉查找樹的插入、刪除、建樹和查找算法及時間性能。
9、掌握建立一棵二叉查找樹的過程實質(zhì)上是對輸入實例的排序過程,輸入實例對所建立的二叉查找樹形態(tài)的影響。
10、了解B-樹的插入、刪除及查找方法的基本思想。
11、掌握散列表、散列函數(shù)、散列地址和裝填因子等有關(guān)概念。
12、掌握散列函數(shù)的選取原則及產(chǎn)生沖突的原因。
13、掌握幾種常用的散列函數(shù)構(gòu)造方法。
14、理解兩類解決沖突的方法及其優(yōu)缺點。
15、了解產(chǎn)生“堆積”現(xiàn)象的原因。
16、理解采用線性探測法和拉鏈法解決沖突時,散列表的建表方法、查找過程以及算法實現(xiàn)和時間分析。
17、了解散列表和其它表的本質(zhì)區(qū)別。
第10章 排序
1、了解排序在數(shù)據(jù)處理中的重要性。
2、掌握排序方法的“穩(wěn)定”性含義。
3、理解排序方法的分類及算法好壞的評判標準。
4、掌握直接插入排序的基本思想和算法實現(xiàn),以及在最好、最壞和平均情況下的時間性能分析。
5、理解直接插入排序中哨兵的作用。
6、掌握針對給定的輸入實例,要能寫出直接插入排序的排序過程。
7、掌握冒泡排序的基本思想。
8、掌握快速排序的基本思想和算法實現(xiàn),以及在最壞和平均情況下的時間性能分析,了解算法的穩(wěn)定性。
9、了解基準元素(劃分元)對劃分是否平衡的影響。
10、掌握針對給定的輸入實例,能寫出快速排序的排序過程。
11、理解堆、小根堆、大根堆、堆項等有關(guān)概念和定義。
12、理解堆性質(zhì)及堆與完全二叉樹的關(guān)系。
13、掌握直接選擇排序和堆排序的基本思想和算法實現(xiàn),以及時間性能分析。
14、掌握針對給定的輸入實例,寫出堆排序的排序過程。
15、掌握歸并排序的基本思想和算法實現(xiàn),以及時間性能分析。
16、掌握針對給定的輸入實例,能寫出歸并排序的排序過程。
17、掌握通過對被排序的記錄數(shù)目、記錄信息量的大小、關(guān)鍵字的結(jié)構(gòu)及初始狀態(tài)、穩(wěn)定性要求、輔助空間的大小、各種時間性能等方面的比較掌握各種排序的優(yōu)缺點?! ?/span>
參考教材:
1.《數(shù)據(jù)結(jié)構(gòu)用C語言描述》(第二版),耿國華等編寫,高等教育出版社,2015年;
2.《數(shù)據(jù)結(jié)構(gòu)》(C語言版),嚴蔚敏、吳偉民編著,清華大學出版社,2011年。
《計算機組成原理》
一、考試目的
考核普通高等學校專科(含高職)應屆畢業(yè)生對于《計算機組成原理》課程基本知識掌握是否達到教學大綱所規(guī)定的要求。
二、考試要求及內(nèi)容
第1章 計算機系統(tǒng)概論
了解計算機系統(tǒng)的層次結(jié)構(gòu)。
第2章 運算方法與運算部件
1、了解數(shù)據(jù)的表示方法和轉(zhuǎn)化。
2、掌握帶符號的二進制數(shù)據(jù)在計算機中的表示:原碼、反碼、補碼、移碼及其相互轉(zhuǎn)化。
3、掌握補碼加減法,并能判斷溢出。
4、掌握定點數(shù)和浮點數(shù)表示方法。
5、掌握定點原碼、補碼一位乘法運算。
6、掌握定點補碼一位除法運算。
7、了解浮點數(shù)的加減法運算。
8、了解浮點數(shù)的乘除法運算。
9、理解定點運算部件。
第3章 存儲器
1、理解主存儲器處于全機中心地位。
2、了解主存儲器的分類。
3、理解主存儲器的主要技術(shù)指標。
4、理解主存儲器的基本操作。
5、了解SRAM、DRAM以及非易失性半導體存儲器的特點。
6、理解DRAM的刷新。
7、理解多體交叉存儲器。
8、掌握存儲器容量的擴展。
9、掌握存儲系統(tǒng)的層次結(jié)構(gòu)。
10、掌握cache存儲器的工作原理、cache存儲器組織。
11、了解存儲管理部件(MMU)。
12、了解相聯(lián)存儲器、存儲保護。
第4章 指令系統(tǒng)
1、了解指令系統(tǒng)的發(fā)展。
2、掌握指令格式、指令操作碼的擴展技術(shù)、指令長度與字長的關(guān)系。
3、理解數(shù)據(jù)表示。
4、掌握指令和操作數(shù)的尋址方式。
5、理解指令類型。
6、理解RISC產(chǎn)生及其特點。
第5章 中央處理器(CPU)
1、理解計算機的工作過程。
2、理解控制器的功能。
3、掌握控制器的組成。
4、掌握指令的執(zhí)行過程。
5、掌握微程序控制的基本概念、實現(xiàn)微程序控制的基本原理、微程序控制計算機的工作過程。
6、掌握微程序的設計技術(shù):微指令的編譯法、微指令的格式、微程序存儲器。
7、了解硬連線控制的計算機。
8、了解控制器的控制方式。
9、理解流水線工作的原理。
三、試題難易程度
較容易題 約30%
中等難度題 約50%
較難題 約20%
四、參考教材
1.《計算機組成原理》第2版,唐朔飛編著,高等教育出版社,2008年1月第2版,2011年5月第9次印刷;
2.《計算機組成原理》第5版,白中英編著,科學出版社,2015年7月第5版。
五、說明
試卷滿分為200分(計算機組成原理100分+數(shù)據(jù)結(jié)構(gòu)100分),考試時間120分鐘,試卷長度為A4紙8-10版。
推薦閱讀
操作成功