2022年呼和浩特民族學(xué)院專升本計算機科學(xué)與技術(shù)專業(yè)課考試說明

　　一、考試科目：

　　《數(shù)據(jù)結(jié)構(gòu)》占比 40%、《程序設(shè)計基礎(chǔ)》占比 60%，兩門課程一張卷。

　　二、考試形式

　　考試采用閉卷、筆試形式

　　三、考試滿分及考試時間

　　兩門課程試卷滿分 100 分，其中數(shù)據(jù)結(jié)構(gòu)占 40%，程序設(shè)計基礎(chǔ)占 60%;考試時間為 150 分鐘。

　　四、 考試題型

　　考試題型從以下類行中選擇：單項選擇題判斷題、填空題、應(yīng)用題、簡答題、寫出程序運行結(jié)果、編寫程序、補全代碼等。

　　五、參考書目：

　　1.《實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》，(第四版)，中國鐵道出版社，陳元春、王中華、張亮、王勇等編著,2015 年;

　　2.《C++程序設(shè)計》(第三版)，清華大學(xué)出版社，譚浩強，2015 年 ;

　　六、考試大綱：

　　(一)《數(shù)據(jù)結(jié)構(gòu)》考試大綱

　　《數(shù)據(jù)結(jié)構(gòu)》作為一門基礎(chǔ)理論性考試科目，考試目的是：考試應(yīng)試人員在基礎(chǔ)方面應(yīng)具備常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實現(xiàn)方法;在技能方面應(yīng)具備在不同存儲結(jié)構(gòu)上實現(xiàn)不同的運算，并了解對算法設(shè)計的方式和技巧。其內(nèi)容包括：緒論、線性表、棧、隊列、串、數(shù)組與廣義表、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)、查找、排序等。具體內(nèi)容與要求如下：

　　1.緒論

　　1.1 數(shù)據(jù)結(jié)構(gòu)的概念

　　1.1.1 掌握數(shù)據(jù)結(jié)構(gòu)的概念

　　1.1.2 掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語、 抽象數(shù)據(jù)類型的表示

　　和實現(xiàn)

　　1.2 算法和算法分析

　　1.2.1 掌握算法的含義

　　1.2.2 了解算法分析的方法

　　2. 線性表

　　2.1 掌握線性表的類型定義

　　2.2 掌握線性表的順序表示和實現(xiàn)

　　2.3 掌握線性表的鏈式表示和實現(xiàn)

　　3.棧和隊列

　　3.1 棧

　　3.1.1 掌握棧的定義及基本運算

　　3.1.2 掌握棧的存儲實現(xiàn)和運算

　　-2-3.1.3 了解棧的應(yīng)用舉例

　　3.2 隊列

　　3.2.1 掌握隊列的定義及基本運算

　　3.2.2 掌握隊列的存儲實現(xiàn)和運算

　　3.2.3 了解隊列的應(yīng)用舉例

　　4.串

　　4.1 串的定義及基本概念

　　4.1.1 了解串的定義

　　4.1.2 熟悉串的基本概念

　　4.2 串的表示和實現(xiàn)

　　4.2.1 熟悉串的定長順序存儲及運算

　　4.2.2 掌握串的堆存儲及運算

　　4.3 串的模式匹配算法

　　4.3.1 了解串的模式匹配算法的思想

　　5.數(shù)組與廣義表

　　5.1 數(shù)組與多維數(shù)組

　　5.1.1 掌握數(shù)組的定義

　　5.1.2 熟悉數(shù)組的順序表示和實現(xiàn)

　　5.1.3 掌矩陣的壓縮存儲

　　5.2 廣義表

　　5.2.1 掌握廣義表的定義

　　5.2.2 了解廣義表的存儲結(jié)構(gòu)

　　-3-6.樹和二叉樹

　　6.1 掌握樹的定義和基本術(shù)語

　　6.2 掌握二叉樹及它的性質(zhì)

　　6.3 掌握遍歷二叉樹

　　6.4 掌握樹和森林、二叉樹之間的轉(zhuǎn)換

　　6.5 掌握哈夫曼樹及其應(yīng)用

　　7.圖

　　7.1 掌握圖的定義和術(shù)語

　　7.2 掌握圖的存儲結(jié)構(gòu)

　　7.3 掌握圖的遍歷方法

　　7.4 掌握圖的連通性問題及其應(yīng)用

　　7.5 掌握最短路徑

　　8.查找

　　8.1 靜態(tài)查找

　　8.1.1 掌握順序查找方法的算法思想及效率

　　8.1.2 掌握二分查找方法的算法思想及效率

　　8.1.3 掌握分塊查找方法的算法思想及效率

　　8.2 動態(tài)查找

　　8.2.1 掌握構(gòu)造二叉排序樹的方法

　　8.2.2 掌握平衡二叉樹的判斷方法

　　8.3 散列查找

　　8.3.1 掌握散列函數(shù)的構(gòu)造方法

　　8.3.2 掌握散列表的沖突處理方法

　　8.3.3 掌握散列表(哈希表)的構(gòu)造

　　9.排序

　　9.1 掌握排序的基本思想和基本概念

　　9.2 理解并掌握直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟、算法及時空效率分析

　　注：本考試大綱分別用掌握、熟悉和了解來界定各條目的考試要求?！罢莆铡笔侵副仨毦邆涞闹匾R，“熟悉”是指應(yīng)當具備的較重要的知識，“了解”是指一般知識。

　　(二)《程序設(shè)計基礎(chǔ)》考試大綱

　　《程序設(shè)計基礎(chǔ)》作為計算機專業(yè)編程語言入門考試科目，內(nèi)容是關(guān)于初步認識 C++，數(shù)據(jù)類型、運算符、表達式和語句，程序控制結(jié)構(gòu)，函數(shù)，數(shù)組，指針與引用，自定義數(shù)據(jù)類型，類和對象，靜態(tài)成員與友元，類的繼承，多態(tài)性的知識。本課程考試目的是：考試應(yīng)試人員所具備的程序設(shè)計語言知識的狀況，包括對結(jié)構(gòu)化程序設(shè)計基礎(chǔ)和面向?qū)ο蟪绦蛟O(shè)計的基本概念與方法的具備程度，對計算機程序設(shè)計語言有關(guān)的專業(yè)理論的具備程度。具體內(nèi)容與要求如下：

　　1.C++的初步知識

　　1.1 C++程序的構(gòu)成和書寫形式

　　1.1.1 掌握 C++程序的書寫形式

　　1.2 C++程序的編寫和實現(xiàn)

　　1.2.1 了解 C++語言的特點及 C++簡單程序的構(gòu)成

　　1.2.2 掌握 C++程序的編輯、編譯、鏈接和運行的過程

　　2.數(shù)據(jù)的存儲、表示形式和基本運算

　　2.1 了解整型、字符型、實型等基本數(shù)據(jù)類型的概念

　　2.2 了解數(shù)據(jù)類型與變量、常量的關(guān)系

　　2.3 了解表達式和運算符的概念

　　2.4 掌握各種常量的性質(zhì)和定義，表達式中各種運算符的功能和特點

　　3.程序設(shè)計初步

　　3.1 基于過程的程序設(shè)計和算法

　　3.1.1 了解基于過程的程序設(shè)計的特點

　　3.1.2 掌握算法的概念

　　3.2 C++的程序結(jié)構(gòu)和語句

　　3.2.1 掌握 C++語句書寫格式

　　3.3 C++的輸入與輸出

　　3.3.1 掌握 C++輸入與輸出的基本操作

　　3.4 關(guān)系運算與邏輯運算

　　3.4.1 掌握關(guān)系運算與邏輯運算符的功能和特點

　　3.5 選擇結(jié)構(gòu)和 if 語句

　　3.5.1 掌握 if 語句和 switch 語句的使用，會在程序中

　　利用它們實現(xiàn)單分支或多分支控制

　　3.6 循環(huán)結(jié)構(gòu)和循環(huán)語句

　　3.6.1 掌握 while，do...while 和 for 這三種循環(huán)語句的結(jié)構(gòu)和執(zhí)行過程

　　3.6.2 掌握 continue 語句和 break 語句的作用

　　4. 函數(shù)

　　4.1 函數(shù)的概念及定義形式

　　4.1.1 了解函數(shù)的概念

　　4.1.2 掌握函數(shù)的定義格式及相關(guān)概念

　　4.2 函數(shù)的調(diào)用

　　4.2.1 掌握函數(shù)調(diào)用的方式

　　4.3 函數(shù)的嵌套調(diào)用及遞歸調(diào)用

　　4.3.1 了解嵌套調(diào)用及遞歸調(diào)用的概念

　　4.3.2 掌握函數(shù)的嵌套調(diào)用及遞歸調(diào)用方式

　　4.4 函數(shù)的重載

　　4.4.1 掌握函數(shù)重載的概念

　　4.4.2 掌握定義重載函數(shù)的格式

　　4.5 有默認參數(shù)的函數(shù)

　　4.5.1 掌握有默認參數(shù)的函數(shù)的定義及調(diào)用格式

　　4.6 局部變量和全局變量

　　4.6.1 掌握變量及其作用域

　　5. 數(shù)組

　　5.1 為什么需要用數(shù)組

　　5.1.1 了解數(shù)組的基本概念，數(shù)組下標

　　5.2 定義和引用一維數(shù)組

　　5.2.1 掌握一維數(shù)組的定義格式及初始化方法

　　5.2.2 掌握一維數(shù)組元素的引用形式

　　5.3 定義和引用二維數(shù)組

　　5.3.1 掌握二維數(shù)組的定義格式及初始化方法

　　5.3.2 掌握二維數(shù)組元素的引用形式

　　5.4 用數(shù)組作函數(shù)參數(shù)

　　5.4.1 掌握數(shù)組元素及數(shù)組名作為函數(shù)參數(shù)格式

　　5.5 字符數(shù)組

　　5.5.1 掌握字符數(shù)組的定義及初始化格式

　　5.5.2 掌握字符數(shù)組的賦值與引用

　　5.5.3 熟悉字符串和字符串結(jié)束標志

　　5.5.4 掌握字符數(shù)組的輸入與輸出格式

　　5.5.5 了解字符數(shù)組與字符串的關(guān)系

　　5.5.6 掌握使用字符串處理函數(shù)對字符串進行操作

　　6.指針與引用

　　6.1 指針與變量

　　6.1.1 熟悉指針及指針相關(guān)的基本概念

　　6.1.2 了解指針與變量的關(guān)系

　　6.1.3 掌握指針變量定義格式、使用方式和指針運算

　　6.1.4 了解指針作函數(shù)參數(shù)的本質(zhì)

　　6.1.5 掌握指針作函數(shù)參數(shù)傳遞方式

　　6.2 數(shù)組與指針

　　6.2.1 掌握如何使指針指向數(shù)組元素

　　6.2.2 掌握用指針變量作函數(shù)形參接收數(shù)組地址

　　6.3 字符串與指針

　　6.3.1 掌握如何使用字符指針指向一個字符串

　　6.4 函數(shù)與指針

　　6.4.1 掌握指向函數(shù)的指針變量的定義形式并正確使用

　　6.4.2 熟悉指針函數(shù)的概念

　　6.4.3 掌握定義指針函數(shù)的形式

　　6.5 指針數(shù)組和指向指針的指針

　　6.5.1 熟悉指針數(shù)組的概念

　　6.5.2 掌握一維指針數(shù)組的定義形式及使用

　　6.6 引用

　　6.6.1 熟悉引用的概念

　　6.6.2 掌握引用變量的使用方式

　　6.6.3 掌握引用作為函數(shù)參數(shù)怎樣傳遞

　　7. 自定義數(shù)據(jù)類型

　　7.1 結(jié)構(gòu)體類型及結(jié)構(gòu)體變量

　　7.1.1 熟悉結(jié)構(gòu)體的概念

　　7.1.2 掌握結(jié)構(gòu)體類型的定義格式

　　7.1.3 掌握結(jié)構(gòu)體變量的定義方式、初始化及引用

　　7.1.4 掌握結(jié)構(gòu)體數(shù)組的定義方式

　　7.1.5 了解指向結(jié)構(gòu)體變量的指針的概念

　　7.1.6 掌握如何使用指針變量指向數(shù)組中的元素

　　7.2 枚舉類型

　　7.2.1 了解枚舉的概念

　　7.2.2 掌握枚舉類型定義格式及使用

　　8.類和對象

　　8.1 類的聲明和對象的定義

　　8.1.1 了解類和對象的關(guān)系

　　8.1.2 掌握類類型的聲明格式及對象的定義方式

　　8.2 成員函數(shù)

　　8.2.1 了解成員函數(shù)的概念

　　8.2.2 掌握成員函數(shù)的定義方式

　　8.2.3 掌握對象成員的引用方式

　　9.怎樣使用類和對象

　　9.1 構(gòu)造函數(shù)和析構(gòu)函數(shù)

　　9.1.1 掌握定義構(gòu)造函數(shù)和析構(gòu)函數(shù)的意義

　　9.1.2 掌握構(gòu)造函數(shù)和析構(gòu)函數(shù)的調(diào)用順序

　　9.2 對象數(shù)組及對象指針

　　9.2.1 掌握對象數(shù)組的定義格式及使用

　　9.2.2 掌握對象指針的定義格式及使用

　　9.3 對象的賦值和復(fù)制

　　9.3.1 掌握對象的賦值和復(fù)制格式

　　9.4 靜態(tài)成員

　　9.4.1 掌握怎樣聲明一個靜態(tài)數(shù)據(jù)成員

　　9.4.2 掌握怎樣使用靜態(tài)成員函數(shù)以及靜態(tài)成員函數(shù)

　　為什么與特定對象無關(guān)

　　9.5 友元

　　9.5.1 了解友元的概念

　　9.5.2 掌握友元的定義格式及使用

　　10 繼承與派生

　　10.1 了解繼承與派生的概念

　　10.2 掌握單一及多重派生類的聲明方式

　　10.3 熟悉派生類的構(gòu)成

　　10.4 掌握三種不同繼承方式對基類成員、派生類成員訪問權(quán)限的影響

　　10.5 掌握派生類的構(gòu)造函數(shù)及析構(gòu)函數(shù)的定義格式及調(diào)用順序

　　11 多態(tài)性與虛函數(shù)

　　11.1 熟悉多態(tài)性的概念

　　11.2 掌握利用虛函數(shù)實現(xiàn)動態(tài)多態(tài)性

　　11.3 掌握純虛函數(shù)和抽象類的概念、聲明格式及使用

　　注：本考試大綱分別用掌握、熟悉和了解來界定各條目-的考試要求。“掌握”是指必須掌握的重要知識，“熟悉”是指應(yīng)當掌握的比較重要的知識，“了解”是指應(yīng)該掌握的基礎(chǔ)性知識。