2023年上海電機學院專升本程序設計與數據結構考試大綱

一、課程的性質與地位

《高級語言程序設計》和《數據結構》課程是計算機類專業及相關專業的必修課程。通過這兩門課程的學習，使學生掌握C程序設計的基本概念和程序設計的思想和編程技巧；具備使用C語言開發小型軟件系統的能力；為后續學習計算機操作系統原理、編譯原理、數據庫原理等課程打下堅實基礎。并培養學生計算思維能力，提高學生分析問題和解決問題的能力。

二、考試內容

（一）C程序設計部分

1．C語言程序的結構

（1）程序的構成，main()函數和其他函數。

（2）頭文件、數據說明，函數的開始和結束標志以及程序中的注釋。

2．數據類型及其運算

（1）C的數據類型（基本類型、構造類型、指針類型、無值類型）及其定義方法。

（2）C運算符的種類、運算優先級和結合性。

（3）不同類型數據間的轉換與運算。

（4）C表達式類型（賦值表達式、算術表達式、關系表達式、邏輯表達式、條件表達式、逗號表達式）和求值規則。

3．控制結構

（1）順序結構、選擇結構、循環結構

（2）用if和switch語句實現選擇結構程序設計。

（3）用for、while和do-while實現循環結構程序設計。

（4）continue語句和break語句。

4．數組

（1）一維數組和二維數組的定義、初始化和數組元素的引用。

（2）字符串與字符數組。

5．函數

（1）函數的定義、類型和返回值。

（2）形式參數與實在參數，參數值傳遞。

（3）函數的調用、嵌套調用、遞歸調用。

（4）局部變量和全局變量，變量的存儲類別，變量的作用域和生存期。

6．指針

（1）地址與指針變量的概念，指針變量的引用。

（2）一維、二維數組和字符串的地址以及指向變量、數組、字符串、函數、結構體的指針變量的定義。通過指針引用以上各類型數據。

（3）指針作為函數參數、返回指針值的函數。

（4）指針數組。

7．結構體與共同體

（1）用typedef說明一個新類型。

（2）結構體和共用體類型數據的定義和成員的引用。

（3）動態內存管理，單向鏈表的建立，結點數據的輸出、刪除與插入。

8．文件操作

（1）文件類型指針（FILE類型指針）。

（2）文件的打開與關閉（fopen()，fclose()）。

（3）文件的讀寫（fputc()，fgetc()，fputs()，fgets()，fread()，fwrite()，fprintf()，fscanf()函數的應用），文件的定位（rewind()，fseek()函數的應用）。

（二）數據結構部分

1．數據結構的研究內容

（1）數據的邏輯結構與存儲結構。

（2）算法和算法分析。

2．線性表

（1）線性表的定義與運算。

（2）線性表的順序存儲與鏈式存儲結構。

3．棧和隊列

（1）棧和隊列的定義與運算。

（2）棧和隊列的存儲和實現。

4．串

（1）串的定義與存儲。

（2）串運算的實現：求串長、串連接、求子串、串比較、插入子串、刪除子串、模式匹配。

5．多維數組和廣義表

（1）特殊矩陣的壓縮存儲：對稱矩陣、三角矩陣。

（2）稀疏矩陣的存儲

（3）廣義表的定義和運算

6．樹和二叉樹

（1）樹的定義和術語。

（2）二叉樹的性質、遍歷、轉換和應用。

（3）哈夫曼樹及哈夫曼編碼。

7．圖

（1）圖的定義和術語。

（2）圖的存儲：鄰接矩陣、鄰接表。

（3）圖的遍歷：深度優先搜索、廣度優先搜索。

（3）圖的連通性：無向圖的連通分量和生成樹。

（4）最短路徑、拓撲排序、關鍵路徑。

8．查找

（1）順序查找、二分查找和分塊查找。

（2）動態查找表：二叉排序樹、平衡二叉樹。

（3）哈希表的構造與處理沖突的方法。

9．排序

（1）插入排序：直接插入排序、二分插入排序、希爾排序。

（2）交換排序：冒泡排序、快速排序。

（3）選擇排序：簡單選擇排序、堆排序。

（4）歸并排序。

三、參考教材

1．C程序設計部分

《C程序設計教程與實驗》（第3版） 清華大學出版社，吉順如主編

《C程序設計習題集與課程設計指導》（第2版）電子工業出版社，吉順如主編

2．數據結構部分

《實用數據結構基礎》中國鐵道出版社，陳元春等編著

四、考試題型

題型包含選擇題、程序填空題、改錯題、應用題、編程題等。