2022年呼和浩特民族学院专升本计算机科学与技术专业课考试说明
一、考试科目：
《数据结构》占比 40%、《程序设计基础》占比 60%，两门课程一张卷。
二、考试形式
考试采用闭卷、笔试形式
三、考试满分及考试时间
两门课程试卷满分 100 分，其中数据结构占 40%，程序设计基础占 60%;考试时间为 150 分钟。
四、 考试题型
考试题型从以下类行中选择：单项选择题判断题、填空题、应用题、简答题、写出程序运行结果、编写程序、补全代码等。
五、参考书目：
1.《实用数据结构基础》，(第四版)，中国铁道出版社，陈元春、王中华、张亮、王勇等编著,2015 年;
2.《C++程序设计》(第三版)，清华大学出版社，谭浩强，2015 年 ;
六、考试大纲：
(一)《数据结构》考试大纲
《数据结构》作为一门基础理论性考试科目，考试目的是：考试应试人员在基础方面应具备常用数据结构的基本概念及其不同的实现方法;在技能方面应具备在不同存储结构上实现不同的运算，并了解对算法设计的方式和技巧。其内容包括：绪论、线性表、栈、队列、串、数组与广义表、树形结构、图形结构、查找、排序等。具体内容与要求如下：
1.绪论
1.1 数据结构的概念
1.1.1 掌握数据结构的概念
1.1.2 掌握数据结构的相关术语、 抽象数据类型的表示
和实现
1.2 算法和算法分析
1.2.1 掌握算法的含义
1.2.2 了解算法分析的方法
2. 线性表
2.1 掌握线性表的类型定义
2.2 掌握线性表的顺序表示和实现
2.3 掌握线性表的链式表示和实现
3.栈和队列
3.1 栈
3.1.1 掌握栈的定义及基本运算
3.1.2 掌握栈的存储实现和运算
-2-3.1.3 了解栈的应用举例
3.2 队列
3.2.1 掌握队列的定义及基本运算
3.2.2 掌握队列的存储实现和运算
3.2.3 了解队列的应用举例
4.串
4.1 串的定义及基本概念
4.1.1 了解串的定义
4.1.2 熟悉串的基本概念
4.2 串的表示和实现
4.2.1 熟悉串的定长顺序存储及运算
4.2.2 掌握串的堆存储及运算
4.3 串的模式匹配算法
4.3.1 了解串的模式匹配算法的思想
5.数组与广义表
5.1 数组与多维数组
5.1.1 掌握数组的定义
5.1.2 熟悉数组的顺序表示和实现
5.1.3 掌矩阵的压缩存储
5.2 广义表
5.2.1 掌握广义表的定义
5.2.2 了解广义表的存储结构
-3-6.树和二叉树
6.1 掌握树的定义和基本术语
6.2 掌握二叉树及它的性质
6.3 掌握遍历二叉树
6.4 掌握树和森林、二叉树之间的转换
6.5 掌握哈夫曼树及其应用
7.图
7.1 掌握图的定义和术语
7.2 掌握图的存储结构
7.3 掌握图的遍历方法
7.4 掌握图的连通性问题及其应用
7.5 掌握最短路径
8.查找
8.1 静态查找
8.1.1 掌握顺序查找方法的算法思想及效率
8.1.2 掌握二分查找方法的算法思想及效率
8.1.3 掌握分块查找方法的算法思想及效率
8.2 动态查找
8.2.1 掌握构造二叉排序树的方法
8.2.2 掌握平衡二叉树的判断方法
8.3 散列查找
8.3.1 掌握散列函数的构造方法
8.3.2 掌握散列表的冲突处理方法
8.3.3 掌握散列表(哈希表)的构造
9.排序
9.1 掌握排序的基本思想和基本概念
9.2 理解并掌握直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析
注：本考试大纲分别用掌握、熟悉和了解来界定各条目的考试要求。“掌握”是指必须具备的重要知识，“熟悉”是指应当具备的较重要的知识，“了解”是指一般知识。
(二)《程序设计基础》考试大纲
《程序设计基础》作为计算机专业编程语言入门考试科目，内容是关于初步认识 C++，数据类型、运算符、表达式和语句，程序控制结构，函数，数组，指针与引用，自定义数据类型，类和对象，静态成员与友元，类的继承，多态性的知识。本课程考试目的是：考试应试人员所具备的程序设计语言知识的状况，包括对结构化程序设计基础和面向对象程序设计的基本概念与方法的具备程度，对计算机程序设计语言有关的专业理论的具备程度。具体内容与要求如下：
1.C++的初步知识
1.1 C++程序的构成和书写形式
1.1.1 掌握 C++程序的书写形式
1.2 C++程序的编写和实现
1.2.1 了解 C++语言的特点及 C++简单程序的构成
1.2.2 掌握 C++程序的编辑、编译、链接和运行的过程
2.数据的存储、表示形式和基本运算
2.1 了解整型、字符型、实型等基本数据类型的概念
2.2 了解数据类型与变量、常量的关系
2.3 了解表达式和运算符的概念
2.4 掌握各种常量的性质和定义，表达式中各种运算符的功能和特点
3.程序设计初步
3.1 基于过程的程序设计和算法
3.1.1 了解基于过程的程序设计的特点
3.1.2 掌握算法的概念
3.2 C++的程序结构和语句
3.2.1 掌握 C++语句书写格式
3.3 C++的输入与输出
3.3.1 掌握 C++输入与输出的基本操作
3.4 关系运算与逻辑运算
3.4.1 掌握关系运算与逻辑运算符的功能和特点
3.5 选择结构和 if 语句
3.5.1 掌握 if 语句和 switch 语句的使用，会在程序中
利用它们实现单分支或多分支控制
3.6 循环结构和循环语句
3.6.1 掌握 while，do...while 和 for 这三种循环语句的结构和执行过程
3.6.2 掌握 continue 语句和 break 语句的作用
4. 函数
4.1 函数的概念及定义形式
4.1.1 了解函数的概念
4.1.2 掌握函数的定义格式及相关概念
4.2 函数的调用
4.2.1 掌握函数调用的方式
4.3 函数的嵌套调用及递归调用
4.3.1 了解嵌套调用及递归调用的概念
4.3.2 掌握函数的嵌套调用及递归调用方式
4.4 函数的重载
4.4.1 掌握函数重载的概念
4.4.2 掌握定义重载函数的格式
4.5 有默认参数的函数
4.5.1 掌握有默认参数的函数的定义及调用格式
4.6 局部变量和全局变量
4.6.1 掌握变量及其作用域
5. 数组
5.1 为什么需要用数组
5.1.1 了解数组的基本概念，数组下标
5.2 定义和引用一维数组
5.2.1 掌握一维数组的定义格式及初始化方法
5.2.2 掌握一维数组元素的引用形式
5.3 定义和引用二维数组
5.3.1 掌握二维数组的定义格式及初始化方法
5.3.2 掌握二维数组元素的引用形式
5.4 用数组作函数参数
5.4.1 掌握数组元素及数组名作为函数参数格式
5.5 字符数组
5.5.1 掌握字符数组的定义及初始化格式
5.5.2 掌握字符数组的赋值与引用
5.5.3 熟悉字符串和字符串结束标志
5.5.4 掌握字符数组的输入与输出格式
5.5.5 了解字符数组与字符串的关系
5.5.6 掌握使用字符串处理函数对字符串进行操作
6.指针与引用
6.1 指针与变量
6.1.1 熟悉指针及指针相关的基本概念
6.1.2 了解指针与变量的关系
6.1.3 掌握指针变量定义格式、使用方式和指针运算
6.1.4 了解指针作函数参数的本质
6.1.5 掌握指针作函数参数传递方式
6.2 数组与指针
6.2.1 掌握如何使指针指向数组元素
6.2.2 掌握用指针变量作函数形参接收数组地址
6.3 字符串与指针
6.3.1 掌握如何使用字符指针指向一个字符串
6.4 函数与指针
6.4.1 掌握指向函数的指针变量的定义形式并正确使用
6.4.2 熟悉指针函数的概念
6.4.3 掌握定义指针函数的形式
6.5 指针数组和指向指针的指针
6.5.1 熟悉指针数组的概念
6.5.2 掌握一维指针数组的定义形式及使用
6.6 引用
6.6.1 熟悉引用的概念
6.6.2 掌握引用变量的使用方式
6.6.3 掌握引用作为函数参数怎样传递
7. 自定义数据类型
7.1 结构体类型及结构体变量
7.1.1 熟悉结构体的概念
7.1.2 掌握结构体类型的定义格式
7.1.3 掌握结构体变量的定义方式、初始化及引用
7.1.4 掌握结构体数组的定义方式
7.1.5 了解指向结构体变量的指针的概念
7.1.6 掌握如何使用指针变量指向数组中的元素
7.2 枚举类型
7.2.1 了解枚举的概念
7.2.2 掌握枚举类型定义格式及使用
8.类和对象
8.1 类的声明和对象的定义
8.1.1 了解类和对象的关系
8.1.2 掌握类类型的声明格式及对象的定义方式
8.2 成员函数
8.2.1 了解成员函数的概念
8.2.2 掌握成员函数的定义方式
8.2.3 掌握对象成员的引用方式
9.怎样使用类和对象
9.1 构造函数和析构函数
9.1.1 掌握定义构造函数和析构函数的意义
9.1.2 掌握构造函数和析构函数的调用顺序
9.2 对象数组及对象指针
9.2.1 掌握对象数组的定义格式及使用
9.2.2 掌握对象指针的定义格式及使用
9.3 对象的赋值和复制
9.3.1 掌握对象的赋值和复制格式
9.4 静态成员
9.4.1 掌握怎样声明一个静态数据成员
9.4.2 掌握怎样使用静态成员函数以及静态成员函数
为什么与特定对象无关
9.5 友元
9.5.1 了解友元的概念
9.5.2 掌握友元的定义格式及使用
10 继承与派生
10.1 了解继承与派生的概念
10.2 掌握单一及多重派生类的声明方式
10.3 熟悉派生类的构成
10.4 掌握三种不同继承方式对基类成员、派生类成员访问权限的影响
10.5 掌握派生类的构造函数及析构函数的定义格式及调用顺序
11 多态性与虚函数
11.1 熟悉多态性的概念
11.2 掌握利用虚函数实现动态多态性
11.3 掌握纯虚函数和抽象类的概念、声明格式及使用
注：本考试大纲分别用掌握、熟悉和了解来界定各条目-的考试要求。“掌握”是指必须掌握的重要知识，“熟悉”是指应当掌握的比较重要的知识，“了解”是指应该掌握的基础性知识。