(科目：代碼829，名稱程序設計與數據結構)
一、考查目標
本復試題目包括計算機科學與技術專業兩門主要課程：程序設計、數據結構，希望了解考生對該兩門課程掌握的情況，主要考查：
1、掌握結構化程序設計的基本方法，了解面向對象程序設計的基本思路，對兩種方法編寫的程序有讀、改、寫的能力，能實現計算機常用算法的編制。
2、對計算機語言有較好的了解，能識別程序語言中的語法錯誤，能用像C++等語言編程，知道程序設計技巧和程序設計風格。
3、掌握數據結構的基本概念、基本原理和基本方法。
4、各類數據結構的特征、操作、存儲表示和應用。
5、查找、內部排序與文件。
6、各種算法性能的分析與評價。
7、使用C(或C++)語言的風格描述算法和進行程序設計，具備綜合應用相關知識分析問題和解決問題的能力。
二、考試形式與試卷結構
(一)試卷成績及考試時間
本試卷滿分為150分。考試時間為180分鐘。
(二)答題方式
筆試
(三)試卷內容結構
程序設計內容占50分，其中程序設計基本知識約10分、讀程序和分析程序的能力約25分、寫程序的能力約15分。
數據結構內容占100分，其中數據結構基本知識約30分、算法分析與評價約30分、算法設計與綜合應用約40分。
(四)試卷題型結構
選擇題和填空題：共40分
簡答題和綜合應用題(含讀程序)：共60分
設計與應用分析題(含編寫程序)：共50分
三、考查范圍
《程序設計部分》
1、像程序設計語言C/C++的發展，程序設計語言詞、句子的組成，數據類型與表達式等概念，程序的基本組成，算法的概念和表示。
2、程序設計的上機過程，運行調試中常見錯誤的鑒別。
3、順序結構、選擇結構和循環結構語句的語法規定，能運用三種結構編寫程序。
4、了解常用的程序風格和規范。
5、掌握函數組裝程序的意義，對庫函數、自定義函數、局部變量和全程變量有正確的知識，并能用函數進行程序設計，了解遞歸函數。
6、對批量數據的處理，能正確運用數組或結構體進行程序設計，能熟練處理字符數據。
7、了解指針、文件和異常處理、類與對象、封裝、重載、繼承的概念，能讀懂面向對象程序。
《數據結構部分》
1、抽象數據類型，數據的邏輯結構與存儲結構，算法基本特性與算法分析方法。
2、線性表的定義、邏輯結構、存儲結構、基本操作、基本算法性能的分析。
3、棧的定義、特性、存儲結構、基本操作、基本算法性能的分析，棧與遞歸算法及其基本應用。
4、隊列的定義、特性、存儲結構、基本操作、基本算法性能的分析以及基本應用。
5、串的定義、基本概念、存儲結構、基本操作及基本應用;
6、數組的類型定義、存儲結構與基本操作;特殊矩陣和稀疏矩陣的壓縮存儲及運算的實現;廣義表的定義、基本性質與存儲結構。
7、樹的基本概念和基本操作;二叉樹的基本概念、性質及存儲結構;遍歷二叉樹和線索二叉樹;樹的存儲結構、樹與二叉樹之間的轉換、森林與二叉樹之間的轉換、樹和森林的遍歷;哈夫曼樹(Huffman)及其應用。
8、圖的基本概念和基本操作;圖的存儲結構;圖的遍歷、圖的連通性問題;有向無環圖、最短路徑。
9、查找的概念;靜態查找表、動態查找表、哈希表;各種查找算法的性能分析及其應用。
10、內部排序的概念;插入排序、快速排序、選擇排序、歸并排序、基數排序;各種排序算法的評價(穩定性、時間復雜度、空間復雜性度)及其應用。
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可以是任何相應的數據類型。
請寫出實現直接選擇排序(即簡單選擇排序)的函數(這里的排序結果為升序)：
注意：如出現函數的調用，請將被調用函數的算法一起寫出。
voidselectsort(elemnoder，intn)
版權所有:易賢網
公眾號
事業單位
當前位置：
公考類
招聘類
各類考試