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

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

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

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

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

本科考試時(shí)間為 120 分鐘,總分為 150 分。

 

一、考試范圍及要求

(一)緒論

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

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

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

(二)線性表

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

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

3、線性表的鏈?zhǔn)酱鎯?chǔ)和算法實(shí)現(xiàn);包括線性鏈表、循環(huán)鏈表、雙向鏈表。

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

(三)棧和隊(duì)列

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

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

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

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

2、串的表示和實(shí)現(xiàn)(串的定長(zhǎng)順序存儲(chǔ)表示;堆分配存儲(chǔ)表示;串的塊鏈存儲(chǔ)表示)。

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

(五)數(shù)組

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

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

(六)、樹(shù)和二叉樹(shù)

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

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

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

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

5、遍歷二叉樹(shù)。

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

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

(七)圖

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

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

3、圖的最小生成樹(shù)prim算法、Kruskal 算法。

4、拓?fù)渑判蛩惴ǎ粏卧醋疃搪窂絾?wèn)題的Dijstra 算法。

(八)查找

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

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

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

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

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

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

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

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

 

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

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

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

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

(三)命題原則

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

(四)試題難易比例

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

 

三、樣題示例

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

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

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

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

16.高度為h的完全二叉樹(shù)中最少有________個(gè)結(jié)點(diǎn),最多有________個(gè)結(jié)點(diǎn)。

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

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

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

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

 

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

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

#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è)計(jì)題(共17分)

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

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

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

 

推薦閱讀

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

公眾號(hào)

抖音

bilibili

微博

聯(lián)系我們

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

操作成功

關(guān)閉