關于易學仕 | 好老師教育官網 |
移動APP下載

掃碼下載易學仕在線APP

專升本/專轉本/專接本
當前位置: 易學仕在線> 考試資訊> 報考> 大綱> 江西> 上饒師范學院2020年專升本《數據結構》考試大綱

上饒師范學院2020年專升本《數據結構》考試大綱

發(fā)布時間:2020/06/17 12:13:43 來源:易學仕專升本網 閱讀量:1988

摘要:上饒師范學院2020年專升本《數據結構》考試大綱

上饒師范學院普通高校專升本招生統(tǒng)一考試《數據結構》試題,以上饒師范學院計算機科學與技術專業(yè)《數據結構》教學大綱和我省相關專業(yè)??瓶忌膶嶋H為依據,主要考查學生的基本類型數據結構和各種基于數據結構的算法,以及運用所學知識組織數據的能力和算法設計的能力。

本科考試時間為 120 分鐘,總分為 150 分。

 

一、考試范圍及要求

(一)緒論

1、數據結構概念;數據的邏輯結構(線性結構,樹型結構,網狀結構,集合結構),存儲結構(順序存儲結構,鏈式存儲結構,索引存儲結構,散列存儲結構);數據的運算。

2、抽象數據類型的表示與實現。

3、算法描述;時間復雜性;空間復雜性;算法分析方法。

(二)線性表

1、線性表的類型和定義。

2、線性的順序表示和算法實現。

3、線性表的鏈式存儲和算法實現;包括線性鏈表、循環(huán)鏈表、雙向鏈表。

4、一元多項式的表示及數學運算的實現。

(三)棧和隊列

1、棧的抽象數據類型定義;順序棧、鏈棧的表示和實現。

2、棧的應用舉例:數制轉換問題;迷宮問題;表達式求值問題;遞歸算法的實現問題。

3、隊列抽象數據類型定義;順序存儲隊列、鏈隊列、循環(huán)隊列的算法實現。(四)串

1、串的抽象類型定義及特性。

2、串的表示和實現(串的定長順序存儲表示;堆分配存儲表示;串的塊鏈存儲表示)。

3、串的模式匹配算法(樸素的模式匹配算法,KMP模式匹配算法)及其改進的算法。

(五)數組

1、數組的定義,抽象數據類型。

2、數組的順序存儲表示和實現。矩陣的壓縮存儲(特殊矩陣的概念;稀疏矩陣的三元組表示法;稀疏矩陣的十字鏈表表示法;稀疏矩陣轉置、加減法等運算的實現)。

(六)、樹和二叉樹

1、樹型結構的基本概念。

2、樹的存儲結構。

3、二叉樹的定義、性質及存儲結構。

4、二叉樹與樹、森林之間的轉換;樹的運算的實現。

5、遍歷二叉樹。

6、線索二叉樹(先序穿線樹;中序穿線樹;后序穿線樹)。

7、哈夫曼樹及其應用,哈夫曼編碼。

(七)圖

1、圖的定義和術語;圖的鄰接矩陣存儲結構、鄰接表存儲結構。

2、圖的兩種遍歷策略:深度優(yōu)先搜索和廣度優(yōu)先搜索。

3、圖的最小生成樹prim算法、Kruskal 算法。

4、拓撲排序算法;單源最短路徑問題的Dijstra 算法。

(八)查找

1、靜態(tài)查找表,順序表的查找;有序表的查找;索引順序表的查找。

2、動態(tài)查找表,二叉排序樹和二叉平衡樹。

3、哈希表的概念,哈希函數的構造方法,沖突的解決方法。

(九)內部排序

1、插入排序(希爾排序不考)的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

2、交換排序(冒泡排序、快速排序)的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

3、選擇排序的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

4、歸并排序(基數排序不考)的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

 

二、考試形式與試卷結構

(一) 考試形式:閉卷筆試。

(二) 試卷結構

試卷為第 I 卷、第 II 卷兩大部分。第 I 卷包括單項選擇題、填空題和判斷題三種題型。第一大題單項選擇題,含15個小題,每小題4分,共60分;第二大題填空題,含10個小題,每小題3分,共30分; 第三大題判斷題,含有5小題,每小題3分,共15分。第 II 卷包括應用題、算法分析題和算法設計題三種題型。第四大題應用題,含2個小題,每小題8分,共16分;第五大題算法分析題,含2個小題,每小題6分,共12分;第六大題算法分析題,含1個小題,每題17分,共17分。試卷總分150分。

(三)命題原則

試題力求覆蓋教材主要內容,知識點分布均勻,保持穩(wěn)定的難易程度。著重考查學生基本知識的掌握程度,是否具備一定的數據組織能力,對具體問題,能抽象思維,并建立數學模型,并能獨立地設計算法,解決實際問題。

(四)試題難易比例

試題不超出教材所學知識,難易度與教材相當。其中,較容易題約占 40%,中等難度題約占 50%,較難題約占 10%。

 

三、樣題示例

一、單項選擇題(每小題4分,15小題共60分)

1.將兩個各有n個元素的有序表歸并成一個有序表,在最好情況下最少的比較次數是(     )。

A.n           B.2n-1         C.2n         D.n-1

二、填空題(每小題3分,10小題共30分)

16.高度為h的完全二叉樹中最少有________個結點,最多有________個結點。

三、判斷題(每小題3分,5小題共15分,對的打“√”,錯的打“×”)

26.拓樸排序方法可以判斷出一個有向圖是否有環(huán)。  (   )

四、應用題(每小題8分,2小題共16分)

31.設無向圖G(如圖1所示),請用prim算法算法圖示求最生成樹的過程,并計算最小生成樹各邊上的權值之和。

 

五、算法分析題(每小題6分,2小題共12分)

33.以下算法是實現將一個不帶頭結點的單鏈表按逆序鏈接,將空白部分補充完整。

#define NULL 0  

    typedef int elemtype;

    typedef struct node

    {  elemtype  data;

       Struct  node *next;

       }linklist;

    Void function( linklist  *head)

    {  linklist  *p,*q;

       p=head;

                        ;

       while(p!=NULL)

         {  q=p;

                            ;

            q->next=head;

                            ;

           }

     }

六、算法設計題(共17分)

35.(本題要求采用C/C++語言描述,寫出以下相應類型定義及算法,不要求寫完整程序。)請用二叉鏈表表示一棵二叉樹的存儲方式;

1)寫出二叉樹的結點的類型定義。(5分)

2)寫出統(tǒng)計一棵二叉樹中葉子結點個數的算法。(12分)

 

推薦閱讀

上饒師范學院2020年專升本《C語言程序設計》考試大綱

公眾號

抖音

bilibili

微博

聯(lián)系我們

服務熱線:023-68141520
返回頂部
請選擇培訓項目
專升本/專轉本/專接本 等級職稱/考研

操作成功

關閉