(科目：代碼829，名稱程序設計與數(shù)據(jù)結(jié)構(gòu))
一、考查目標
本復試題目包括計算機科學與技術專業(yè)兩門主要課程：程序設計、數(shù)據(jù)結(jié)構(gòu)，希望了解考生對該兩門課程掌握的情況，主要考查：
1、掌握結(jié)構(gòu)化程序設計的基本方法，了解面向?qū)ο蟪绦蛟O計的基本思路，對兩種方法編寫的程序有讀、改、寫的能力，能實現(xiàn)計算機常用算法的編制。
2、對計算機語言有較好的了解，能識別程序語言中的語法錯誤，能用像C++等語言編程，知道程序設計技巧和程序設計風格。
3、掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。
4、各類數(shù)據(jù)結(jié)構(gòu)的特征、操作、存儲表示和應用。
5、查找、內(nèi)部排序與文件。
6、各種算法性能的分析與評價。
7、使用C(或C++)語言的風格描述算法和進行程序設計，具備綜合應用相關知識分析問題和解決問題的能力。
二、考試形式與試卷結(jié)構(gòu)
(一)試卷成績及考試時間
本試卷滿分為150分?？荚嚂r間為180分鐘。
(二)答題方式
筆試
(三)試卷內(nèi)容結(jié)構(gòu)
程序設計內(nèi)容占50分，其中程序設計基本知識約10分、讀程序和分析程序的能力約25分、寫程序的能力約15分。
數(shù)據(jù)結(jié)構(gòu)內(nèi)容占100分，其中數(shù)據(jù)結(jié)構(gòu)基本知識約30分、算法分析與評價約30分、算法設計與綜合應用約40分。
(四)試卷題型結(jié)構(gòu)
選擇題和填空題：共40分
簡答題和綜合應用題(含讀程序)：共60分
設計與應用分析題(含編寫程序)：共50分
三、考查范圍
《程序設計部分》
1、像程序設計語言C/C++的發(fā)展，程序設計語言詞、句子的組成，數(shù)據(jù)類型與表達式等概念，程序的基本組成，算法的概念和表示。
2、程序設計的上機過程，運行調(diào)試中常見錯誤的鑒別。
3、順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)語句的語法規(guī)定，能運用三種結(jié)構(gòu)編寫程序。
4、了解常用的程序風格和規(guī)范。
5、掌握函數(shù)組裝程序的意義，對庫函數(shù)、自定義函數(shù)、局部變量和全程變量有正確的知識，并能用函數(shù)進行程序設計，了解遞歸函數(shù)。
6、對批量數(shù)據(jù)的處理，能正確運用數(shù)組或結(jié)構(gòu)體進行程序設計，能熟練處理字符數(shù)據(jù)。
7、了解指針、文件和異常處理、類與對象、封裝、重載、繼承的概念，能讀懂面向?qū)ο蟪绦颉?/p>
《數(shù)據(jù)結(jié)構(gòu)部分》
1、抽象數(shù)據(jù)類型，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，算法基本特性與算法分析方法。
2、線性表的定義、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、基本操作、基本算法性能的分析。
3、棧的定義、特性、存儲結(jié)構(gòu)、基本操作、基本算法性能的分析，棧與遞歸算法及其基本應用。
4、隊列的定義、特性、存儲結(jié)構(gòu)、基本操作、基本算法性能的分析以及基本應用。
5、串的定義、基本概念、存儲結(jié)構(gòu)、基本操作及基本應用;
6、數(shù)組的類型定義、存儲結(jié)構(gòu)與基本操作;特殊矩陣和稀疏矩陣的壓縮存儲及運算的實現(xiàn);廣義表的定義、基本性質(zhì)與存儲結(jié)構(gòu)。
7、樹的基本概念和基本操作;二叉樹的基本概念、性質(zhì)及存儲結(jié)構(gòu);遍歷二叉樹和線索二叉樹;樹的存儲結(jié)構(gòu)、樹與二叉樹之間的轉(zhuǎn)換、森林與二叉樹之間的轉(zhuǎn)換、樹和森林的遍歷;哈夫曼樹(Huffman)及其應用。
8、圖的基本概念和基本操作;圖的存儲結(jié)構(gòu);圖的遍歷、圖的連通性問題;有向無環(huán)圖、最短路徑。
9、查找的概念;靜態(tài)查找表、動態(tài)查找表、哈希表;各種查找算法的性能分析及其應用。
10、內(nèi)部排序的概念;插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序;各種排序算法的評價(穩(wěn)定性、時間復雜度、空間復雜性度)及其應用。
11、文件的基本概念;順序文件、索引文件。
四、樣題
一、單項選擇題：
1.對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是：【】
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)))的長度是【】
三、簡答題：
1.請解釋赫夫曼樹與赫夫曼編碼。
四、綜合應用題
1.仔細閱讀下列程序，然后回答問題
上述程序的功能(或作用)是什么?
答：
四、算法設計與分析(含程序設計)：
1.設線性表的存儲定義如下：
#defineMAX100
typedefstructrec
{
KeyTypekey;
ElemTypedata;
}elemnode[MAX];
這里的KeyType和ElemType可以是任何相應的數(shù)據(jù)類型。
請寫出實現(xiàn)直接選擇排序(即簡單選擇排序)的函數(shù)(這里的排序結(jié)果為升序)：
注意：如出現(xiàn)函數(shù)的調(diào)用，請將被調(diào)用函數(shù)的算法一起寫出。
voidselectsort(elemnoder，intn)
公眾號
事業(yè)單位
當前位置：
公考類
招聘類
各類考試