(科目：代碼829，名稱程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu))

一、考查目標(biāo)

本復(fù)試題目包括計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)兩門(mén)主要課程：程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)，希望了解考生對(duì)該兩門(mén)課程掌握的情況，主要考查：

1、掌握結(jié)構(gòu)化程序設(shè)計(jì)的基本方法，了解面向?qū)ο蟪绦蛟O(shè)計(jì)的基本思路，對(duì)兩種方法編寫(xiě)的程序有讀、改、寫(xiě)的能力，能實(shí)現(xiàn)計(jì)算機(jī)常用算法的編制。

2、對(duì)計(jì)算機(jī)語(yǔ)言有較好的了解，能識(shí)別程序語(yǔ)言中的語(yǔ)法錯(cuò)誤，能用像C++等語(yǔ)言編程，知道程序設(shè)計(jì)技巧和程序設(shè)計(jì)風(fēng)格。

3、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。

4、各類數(shù)據(jù)結(jié)構(gòu)的特征、操作、存儲(chǔ)表示和應(yīng)用。

5、查找、內(nèi)部排序與文件。

6、各種算法性能的分析與評(píng)價(jià)。

7、使用C(或C++)語(yǔ)言的風(fēng)格描述算法和進(jìn)行程序設(shè)計(jì)，具備綜合應(yīng)用相關(guān)知識(shí)分析問(wèn)題和解決問(wèn)題的能力。

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

(一)試卷成績(jī)及考試時(shí)間

本試卷滿分為150分。考試時(shí)間為180分鐘。

(二)答題方式

筆試

(三)試卷內(nèi)容結(jié)構(gòu)

程序設(shè)計(jì)內(nèi)容占50分，其中程序設(shè)計(jì)基本知識(shí)約10分、讀程序和分析程序的能力約25分、寫(xiě)程序的能力約15分。

數(shù)據(jù)結(jié)構(gòu)內(nèi)容占100分，其中數(shù)據(jù)結(jié)構(gòu)基本知識(shí)約30分、算法分析與評(píng)價(jià)約30分、算法設(shè)計(jì)與綜合應(yīng)用約40分。

(四)試卷題型結(jié)構(gòu)

選擇題和填空題：共40分

簡(jiǎn)答題和綜合應(yīng)用題(含讀程序)：共60分

設(shè)計(jì)與應(yīng)用分析題(含編寫(xiě)程序)：共50分

三、考查范圍

《程序設(shè)計(jì)部分》

1、像程序設(shè)計(jì)語(yǔ)言C/C++的發(fā)展，程序設(shè)計(jì)語(yǔ)言詞、句子的組成，數(shù)據(jù)類型與表達(dá)式等概念，程序的基本組成，算法的概念和表示。

2、程序設(shè)計(jì)的上機(jī)過(guò)程，運(yùn)行調(diào)試中常見(jiàn)錯(cuò)誤的鑒別。

3、順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)語(yǔ)句的語(yǔ)法規(guī)定，能運(yùn)用三種結(jié)構(gòu)編寫(xiě)程序。

4、了解常用的程序風(fēng)格和規(guī)范。

5、掌握函數(shù)組裝程序的意義，對(duì)庫(kù)函數(shù)、自定義函數(shù)、局部變量和全程變量有正確的知識(shí)，并能用函數(shù)進(jìn)行程序設(shè)計(jì)，了解遞歸函數(shù)。

6、對(duì)批量數(shù)據(jù)的處理，能正確運(yùn)用數(shù)組或結(jié)構(gòu)體進(jìn)行程序設(shè)計(jì)，能熟練處理字符數(shù)據(jù)。

7、了解指針、文件和異常處理、類與對(duì)象、封裝、重載、繼承的概念，能讀懂面向?qū)ο蟪绦颉?/p>

《數(shù)據(jù)結(jié)構(gòu)部分》

1、抽象數(shù)據(jù)類型，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，算法基本特性與算法分析方法。

2、線性表的定義、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、基本操作、基本算法性能的分析。

3、棧的定義、特性、存儲(chǔ)結(jié)構(gòu)、基本操作、基本算法性能的分析，棧與遞歸算法及其基本應(yīng)用。

4、隊(duì)列的定義、特性、存儲(chǔ)結(jié)構(gòu)、基本操作、基本算法性能的分析以及基本應(yīng)用。

5、串的定義、基本概念、存儲(chǔ)結(jié)構(gòu)、基本操作及基本應(yīng)用;

6、數(shù)組的類型定義、存儲(chǔ)結(jié)構(gòu)與基本操作;特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)及運(yùn)算的實(shí)現(xiàn);廣義表的定義、基本性質(zhì)與存儲(chǔ)結(jié)構(gòu)。

7、樹(shù)的基本概念和基本操作;二叉樹(shù)的基本概念、性質(zhì)及存儲(chǔ)結(jié)構(gòu);遍歷二叉樹(shù)和線索二叉樹(shù);樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)與二叉樹(shù)之間的轉(zhuǎn)換、森林與二叉樹(shù)之間的轉(zhuǎn)換、樹(shù)和森林的遍歷;哈夫曼樹(shù)(Huffman)及其應(yīng)用。

8、圖的基本概念和基本操作;圖的存儲(chǔ)結(jié)構(gòu);圖的遍歷、圖的連通性問(wèn)題;有向無(wú)環(huán)圖、最短路徑。

9、查找的概念;靜態(tài)查找表、動(dòng)態(tài)查找表、哈希表;各種查找算法的性能分析及其應(yīng)用。

10、內(nèi)部排序的概念;插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序;各種排序算法的評(píng)價(jià)(穩(wěn)定性、時(shí)間復(fù)雜度、空間復(fù)雜性度)及其應(yīng)用。

11、文件的基本概念;順序文件、索引文件。

四、樣題

一、單項(xiàng)選擇題：

1.對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：【】

A.{25、23、30、17、21、5、9}

B.{5、9、17、21、23、25、30}

C.{30、25、23、21、17、9、5}

D.{21、25、5、17、9、23、30}

二、填空題：

1.廣義表D=((),(e),(a,(b,c,d)))的長(zhǎng)度是【】

三、簡(jiǎn)答題：

1.請(qǐng)解釋赫夫曼樹(shù)與赫夫曼編碼。

四、綜合應(yīng)用題

1.仔細(xì)閱讀下列程序，然后回答問(wèn)題

上述程序的功能(或作用)是什么?

答：

四、算法設(shè)計(jì)與分析(含程序設(shè)計(jì))：

1.設(shè)線性表的存儲(chǔ)定義如下：

#defineMAX100

typedefstructrec

{

KeyTypekey;

ElemTypedata;

}elemnode[MAX];

這里的KeyType和ElemType可以是任何相應(yīng)的數(shù)據(jù)類型。

請(qǐng)寫(xiě)出實(shí)現(xiàn)直接選擇排序(即簡(jiǎn)單選擇排序)的函數(shù)(這里的排序結(jié)果為升序)：

注意：如出現(xiàn)函數(shù)的調(diào)用，請(qǐng)將被調(diào)用函數(shù)的算法一起寫(xiě)出。

voidselectsort(elemnoder，intn)