2023年上海電機(jī)學(xué)院專升本程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)考試大綱

一、課程的性質(zhì)與地位

《高級(jí)語言程序設(shè)計(jì)》和《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)類專業(yè)及相關(guān)專業(yè)的必修課程。通過這兩門課程的學(xué)習(xí)，使學(xué)生掌握C程序設(shè)計(jì)的基本概念和程序設(shè)計(jì)的思想和編程技巧；具備使用C語言開發(fā)小型軟件系統(tǒng)的能力；為后續(xù)學(xué)習(xí)計(jì)算機(jī)操作系統(tǒng)原理、編譯原理、數(shù)據(jù)庫原理等課程打下堅(jiān)實(shí)基礎(chǔ)。并培養(yǎng)學(xué)生計(jì)算思維能力，提高學(xué)生分析問題和解決問題的能力。

二、考試內(nèi)容

（一）C程序設(shè)計(jì)部分

1．C語言程序的結(jié)構(gòu)

（1）程序的構(gòu)成，main()函數(shù)和其他函數(shù)。

（2）頭文件、數(shù)據(jù)說明，函數(shù)的開始和結(jié)束標(biāo)志以及程序中的注釋。

2．?dāng)?shù)據(jù)類型及其運(yùn)算

（1）C的數(shù)據(jù)類型（基本類型、構(gòu)造類型、指針類型、無值類型）及其定義方法。

（2）C運(yùn)算符的種類、運(yùn)算優(yōu)先級(jí)和結(jié)合性。

（3）不同類型數(shù)據(jù)間的轉(zhuǎn)換與運(yùn)算。

（4）C表達(dá)式類型（賦值表達(dá)式、算術(shù)表達(dá)式、關(guān)系表達(dá)式、邏輯表達(dá)式、條件表達(dá)式、逗號(hào)表達(dá)式）和求值規(guī)則。

3．控制結(jié)構(gòu)

（1）順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)

（2）用if和switch語句實(shí)現(xiàn)選擇結(jié)構(gòu)程序設(shè)計(jì)。

（3）用for、while和do-while實(shí)現(xiàn)循環(huán)結(jié)構(gòu)程序設(shè)計(jì)。

（4）continue語句和break語句。

4．?dāng)?shù)組

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

（2）字符串與字符數(shù)組。

5．函數(shù)

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

（2）形式參數(shù)與實(shí)在參數(shù)，參數(shù)值傳遞。

（3）函數(shù)的調(diào)用、嵌套調(diào)用、遞歸調(diào)用。

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

6．指針

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

（2）一維、二維數(shù)組和字符串的地址以及指向變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針變量的定義。通過指針引用以上各類型數(shù)據(jù)。

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

（4）指針數(shù)組。

7．結(jié)構(gòu)體與共同體

（1）用typedef說明一個(gè)新類型。

（2）結(jié)構(gòu)體和共用體類型數(shù)據(jù)的定義和成員的引用。

（3）動(dòng)態(tài)內(nèi)存管理，單向鏈表的建立，結(jié)點(diǎn)數(shù)據(jù)的輸出、刪除與插入。

8．文件操作

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

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

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

（二）數(shù)據(jù)結(jié)構(gòu)部分

1．?dāng)?shù)據(jù)結(jié)構(gòu)的研究內(nèi)容

（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。

（2）算法和算法分析。

2．線性表

（1）線性表的定義與運(yùn)算。

（2）線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3．棧和隊(duì)列

（1）棧和隊(duì)列的定義與運(yùn)算。

（2）棧和隊(duì)列的存儲(chǔ)和實(shí)現(xiàn)。

4．串

（1）串的定義與存儲(chǔ)。

（2）串運(yùn)算的實(shí)現(xiàn)：求串長、串連接、求子串、串比較、插入子串、刪除子串、模式匹配。

5．多維數(shù)組和廣義表

（1）特殊矩陣的壓縮存儲(chǔ)：對(duì)稱矩陣、三角矩陣。

（2）稀疏矩陣的存儲(chǔ)

（3）廣義表的定義和運(yùn)算

6．樹和二叉樹

（1）樹的定義和術(shù)語。

（2）二叉樹的性質(zhì)、遍歷、轉(zhuǎn)換和應(yīng)用。

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

7．圖

（1）圖的定義和術(shù)語。

（2）圖的存儲(chǔ)：鄰接矩陣、鄰接表。

（3）圖的遍歷：深度優(yōu)先搜索、廣度優(yōu)先搜索。

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

（4）最短路徑、拓?fù)渑判?、關(guān)鍵路徑。

8．查找

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

（2）動(dòng)態(tài)查找表：二叉排序樹、平衡二叉樹。

（3）哈希表的構(gòu)造與處理沖突的方法。

9．排序

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

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

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

（4）歸并排序。

三、參考教材

1．C程序設(shè)計(jì)部分

《C程序設(shè)計(jì)教程與實(shí)驗(yàn)》（第3版） 清華大學(xué)出版社，吉順如主編

《C程序設(shè)計(jì)習(xí)題集與課程設(shè)計(jì)指導(dǎo)》（第2版）電子工業(yè)出版社，吉順如主編

2．?dāng)?shù)據(jù)結(jié)構(gòu)部分

《實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》中國鐵道出版社，陳元春等編著

四、考試題型

題型包含選擇題、程序填空題、改錯(cuò)題、應(yīng)用題、編程題等。