專升本/專轉(zhuǎn)本/專接本
當(dāng)前位置: 易學(xué)仕在線> 考試資訊> 報考> 大綱> 江西> 上饒師范學(xué)院2020年專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

上饒師范學(xué)院2020年專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

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

摘要:上饒師范學(xué)院2020年專升本《數(shù)據(jù)結(jié)構(gòu)》考試大綱

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

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

 

一、考試范圍及要求

(一)緒論

1、數(shù)據(jù)結(jié)構(gòu)概念;數(shù)據(jù)的邏輯結(jié)構(gòu)(線性結(jié)構(gòu),樹型結(jié)構(gòu),網(wǎng)狀結(jié)構(gòu),集合結(jié)構(gòu)),存儲結(jié)構(gòu)(順序存儲結(jié)構(gòu),鏈式存儲結(jié)構(gòu),索引存儲結(jié)構(gòu),散列存儲結(jié)構(gòu));數(shù)據(jù)的運算。

2、抽象數(shù)據(jù)類型的表示與實現(xiàn)。

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

(二)線性表

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

2、線性的順序表示和算法實現(xiàn)。

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

4、一元多項式的表示及數(shù)學(xué)運算的實現(xiàn)。

(三)棧和隊列

1、棧的抽象數(shù)據(jù)類型定義;順序棧、鏈棧的表示和實現(xiàn)。

2、棧的應(yīng)用舉例:數(shù)制轉(zhuǎn)換問題;迷宮問題;表達式求值問題;遞歸算法的實現(xiàn)問題。

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

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

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

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

(五)數(shù)組

1、數(shù)組的定義,抽象數(shù)據(jù)類型。

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

(六)、樹和二叉樹

1、樹型結(jié)構(gòu)的基本概念。

2、樹的存儲結(jié)構(gòu)。

3、二叉樹的定義、性質(zhì)及存儲結(jié)構(gòu)。

4、二叉樹與樹、森林之間的轉(zhuǎn)換;樹的運算的實現(xiàn)。

5、遍歷二叉樹。

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

7、哈夫曼樹及其應(yīng)用,哈夫曼編碼。

(七)圖

1、圖的定義和術(shù)語;圖的鄰接矩陣存儲結(jié)構(gòu)、鄰接表存儲結(jié)構(gòu)。

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

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

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

(八)查找

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

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

3、哈希表的概念,哈希函數(shù)的構(gòu)造方法,沖突的解決方法。

(九)內(nèi)部排序

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

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

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

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

 

二、考試形式與試卷結(jié)構(gòu)

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

(二) 試卷結(jié)構(gòu)

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

(三)命題原則

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

(四)試題難易比例

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

 

三、樣題示例

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

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

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

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

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

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

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

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

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

 

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

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

#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;

                            ;

           }

     }

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

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

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

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

 

推薦閱讀

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

公眾號

抖音

bilibili

微博

聯(lián)系我們

服務(wù)熱線:023-68141520
返回頂部
請選擇培訓(xùn)項目
專升本/專轉(zhuǎn)本/專接本 等級職稱/考研

操作成功

關(guān)閉