2022年呼和浩特民族學(xué)院專升本計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)課考試說明
一、考試科目：
《數(shù)據(jù)結(jié)構(gòu)》占比 40%、《程序設(shè)計(jì)基礎(chǔ)》占比 60%，兩門課程一張卷。
二、考試形式
考試采用閉卷、筆試形式
三、考試滿分及考試時(shí)間
兩門課程試卷滿分 100 分，其中數(shù)據(jù)結(jié)構(gòu)占 40%，程序設(shè)計(jì)基礎(chǔ)占 60%;考試時(shí)間為 150 分鐘。
四、 考試題型
考試題型從以下類行中選擇：?jiǎn)雾?xiàng)選擇題判斷題、填空題、應(yīng)用題、簡(jiǎn)答題、寫出程序運(yùn)行結(jié)果、編寫程序、補(bǔ)全代碼等。
五、參考書目：
1.《實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》，(第四版)，中國鐵道出版社，陳元春、王中華、張亮、王勇等編著,2015 年;
2.《C++程序設(shè)計(jì)》(第三版)，清華大學(xué)出版社，譚浩強(qiáng)，2015 年 ;
六、考試大綱：
(一)《數(shù)據(jù)結(jié)構(gòu)》考試大綱
《數(shù)據(jù)結(jié)構(gòu)》作為一門基礎(chǔ)理論性考試科目，考試目的是：考試應(yīng)試人員在基礎(chǔ)方面應(yīng)具備常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法;在技能方面應(yīng)具備在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并了解對(duì)算法設(shè)計(jì)的方式和技巧。其內(nèi)容包括：緒論、線性表、棧、隊(duì)列、串、數(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ù)類型的表示
和實(shí)現(xiàn)
1.2 算法和算法分析
1.2.1 掌握算法的含義
1.2.2 了解算法分析的方法
2. 線性表
2.1 掌握線性表的類型定義
2.2 掌握線性表的順序表示和實(shí)現(xiàn)
2.3 掌握線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
3.棧和隊(duì)列
3.1 棧
3.1.1 掌握棧的定義及基本運(yùn)算
3.1.2 掌握棧的存儲(chǔ)實(shí)現(xiàn)和運(yùn)算
-2-3.1.3 了解棧的應(yīng)用舉例
3.2 隊(duì)列
3.2.1 掌握隊(duì)列的定義及基本運(yùn)算
3.2.2 掌握隊(duì)列的存儲(chǔ)實(shí)現(xiàn)和運(yùn)算
3.2.3 了解隊(duì)列的應(yīng)用舉例
4.串
4.1 串的定義及基本概念
4.1.1 了解串的定義
4.1.2 熟悉串的基本概念
4.2 串的表示和實(shí)現(xiàn)
4.2.1 熟悉串的定長(zhǎng)順序存儲(chǔ)及運(yùn)算
4.2.2 掌握串的堆存儲(chǔ)及運(yùn)算
4.3 串的模式匹配算法
4.3.1 了解串的模式匹配算法的思想
5.數(shù)組與廣義表
5.1 數(shù)組與多維數(shù)組
5.1.1 掌握數(shù)組的定義
5.1.2 熟悉數(shù)組的順序表示和實(shí)現(xiàn)
5.1.3 掌矩陣的壓縮存儲(chǔ)
5.2 廣義表
5.2.1 掌握廣義表的定義
5.2.2 了解廣義表的存儲(chǔ)結(jié)構(gòu)
-3-6.樹和二叉樹
6.1 掌握樹的定義和基本術(shù)語
6.2 掌握二叉樹及它的性質(zhì)
6.3 掌握遍歷二叉樹
6.4 掌握樹和森林、二叉樹之間的轉(zhuǎn)換
6.5 掌握哈夫曼樹及其應(yīng)用
7.圖
7.1 掌握?qǐng)D的定義和術(shù)語
7.2 掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)
7.3 掌握?qǐng)D的遍歷方法
7.4 掌握?qǐng)D的連通性問題及其應(yīng)用
7.5 掌握最短路徑
8.查找
8.1 靜態(tài)查找
8.1.1 掌握順序查找方法的算法思想及效率
8.1.2 掌握二分查找方法的算法思想及效率
8.1.3 掌握分塊查找方法的算法思想及效率
8.2 動(dòng)態(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ù)排序的基本思想、步驟、算法及時(shí)空效率分析
注：本考試大綱分別用掌握、熟悉和了解來界定各條目的考試要求?！罢莆铡笔侵副仨毦邆涞闹匾R(shí)，“熟悉”是指應(yīng)當(dāng)具備的較重要的知識(shí)，“了解”是指一般知識(shí)。
(二)《程序設(shè)計(jì)基礎(chǔ)》考試大綱
《程序設(shè)計(jì)基礎(chǔ)》作為計(jì)算機(jī)專業(yè)編程語言入門考試科目，內(nèi)容是關(guān)于初步認(rèn)識(shí) C++，數(shù)據(jù)類型、運(yùn)算符、表達(dá)式和語句，程序控制結(jié)構(gòu)，函數(shù)，數(shù)組，指針與引用，自定義數(shù)據(jù)類型，類和對(duì)象，靜態(tài)成員與友元，類的繼承，多態(tài)性的知識(shí)。本課程考試目的是：考試應(yīng)試人員所具備的程序設(shè)計(jì)語言知識(shí)的狀況，包括對(duì)結(jié)構(gòu)化程序設(shè)計(jì)基礎(chǔ)和面向?qū)ο蟪绦蛟O(shè)計(jì)的基本概念與方法的具備程度，對(duì)計(jì)算機(jī)程序設(shè)計(jì)語言有關(guān)的專業(yè)理論的具備程度。具體內(nèi)容與要求如下：
1.C++的初步知識(shí)
1.1 C++程序的構(gòu)成和書寫形式
1.1.1 掌握 C++程序的書寫形式
1.2 C++程序的編寫和實(shí)現(xiàn)
1.2.1 了解 C++語言的特點(diǎn)及 C++簡(jiǎn)單程序的構(gòu)成
1.2.2 掌握 C++程序的編輯、編譯、鏈接和運(yùn)行的過程
2.數(shù)據(jù)的存儲(chǔ)、表示形式和基本運(yùn)算
2.1 了解整型、字符型、實(shí)型等基本數(shù)據(jù)類型的概念
2.2 了解數(shù)據(jù)類型與變量、常量的關(guān)系
2.3 了解表達(dá)式和運(yùn)算符的概念
2.4 掌握各種常量的性質(zhì)和定義，表達(dá)式中各種運(yùn)算符的功能和特點(diǎn)
3.程序設(shè)計(jì)初步
3.1 基于過程的程序設(shè)計(jì)和算法
3.1.1 了解基于過程的程序設(shè)計(jì)的特點(diǎn)
3.1.2 掌握算法的概念
3.2 C++的程序結(jié)構(gòu)和語句
3.2.1 掌握 C++語句書寫格式
3.3 C++的輸入與輸出
3.3.1 掌握 C++輸入與輸出的基本操作
3.4 關(guān)系運(yùn)算與邏輯運(yùn)算
3.4.1 掌握關(guān)系運(yùn)算與邏輯運(yùn)算符的功能和特點(diǎn)
3.5 選擇結(jié)構(gòu)和 if 語句
3.5.1 掌握 if 語句和 switch 語句的使用，會(huì)在程序中
利用它們實(shí)現(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 有默認(rèn)參數(shù)的函數(shù)
4.5.1 掌握有默認(rèn)參數(shù)的函數(shù)的定義及調(diào)用格式
4.6 局部變量和全局變量
4.6.1 掌握變量及其作用域
5. 數(shù)組
5.1 為什么需要用數(shù)組
5.1.1 了解數(shù)組的基本概念，數(shù)組下標(biāo)
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é)束標(biāo)志
5.5.4 掌握字符數(shù)組的輸入與輸出格式
5.5.5 了解字符數(shù)組與字符串的關(guān)系
5.5.6 掌握使用字符串處理函數(shù)對(duì)字符串進(jìn)行操作
6.指針與引用
6.1 指針與變量
6.1.1 熟悉指針及指針相關(guān)的基本概念
6.1.2 了解指針與變量的關(guān)系
6.1.3 掌握指針變量定義格式、使用方式和指針運(yùn)算
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 掌握如何使用字符指針指向一個(gè)字符串
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.類和對(duì)象
8.1 類的聲明和對(duì)象的定義
8.1.1 了解類和對(duì)象的關(guān)系
8.1.2 掌握類類型的聲明格式及對(duì)象的定義方式
8.2 成員函數(shù)
8.2.1 了解成員函數(shù)的概念
8.2.2 掌握成員函數(shù)的定義方式
8.2.3 掌握對(duì)象成員的引用方式
9.怎樣使用類和對(duì)象
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 對(duì)象數(shù)組及對(duì)象指針
9.2.1 掌握對(duì)象數(shù)組的定義格式及使用
9.2.2 掌握對(duì)象指針的定義格式及使用
9.3 對(duì)象的賦值和復(fù)制
9.3.1 掌握對(duì)象的賦值和復(fù)制格式
9.4 靜態(tài)成員
9.4.1 掌握怎樣聲明一個(gè)靜態(tài)數(shù)據(jù)成員
9.4.2 掌握怎樣使用靜態(tài)成員函數(shù)以及靜態(tài)成員函數(shù)
為什么與特定對(duì)象無關(guān)
9.5 友元
9.5.1 了解友元的概念
9.5.2 掌握友元的定義格式及使用
10 繼承與派生
10.1 了解繼承與派生的概念
10.2 掌握單一及多重派生類的聲明方式
10.3 熟悉派生類的構(gòu)成
10.4 掌握三種不同繼承方式對(duì)基類成員、派生類成員訪問權(quán)限的影響
10.5 掌握派生類的構(gòu)造函數(shù)及析構(gòu)函數(shù)的定義格式及調(diào)用順序
11 多態(tài)性與虛函數(shù)
11.1 熟悉多態(tài)性的概念
11.2 掌握利用虛函數(shù)實(shí)現(xiàn)動(dòng)態(tài)多態(tài)性
11.3 掌握純虛函數(shù)和抽象類的概念、聲明格式及使用
注：本考試大綱分別用掌握、熟悉和了解來界定各條目-的考試要求?！罢莆铡笔侵副仨氄莆盏闹匾R(shí)，“熟悉”是指應(yīng)當(dāng)掌握的比較重要的知識(shí)，“了解”是指應(yīng)該掌握的基礎(chǔ)性知識(shí)。