2020年成都信息工程大学专升本考试《计算机类综合》大纲

考试说明：计算机类综合考试总分 100 分，包括《C 语言程序设计》 和《数据结构》，每门课程各占 50 分。考试时间总计 120 分钟。

一、《C语言程序设计》考试大纲

考试内容:

（一）C语言程序的结构

1．C语言程序的结构特点；

2．头文件，数据声明，函数的开始和结束标志；

3. 算法的特性和表示方法。

（二）数据类型、运算符与表达式

1．C的数据类型（整型，实型，字符类型，指针类型）及各类 型常量表示方法和变量定义方法；

2．C运算符的种类、运算优先级和结合性；

3．不同类型数据间的转换与运算；

4．C表达式（赋值表达式、算术表达式、关系表达式、逻辑表 达式、条件表达式、逗号表达式）的求值规则；

5．基本输入和输出的实现，字符输入、输出函数和格式化输 入、输出函数的使用。

（三）程序的控制结构

1．选择结构程序设计

（1）用if语句实现选择结构；

（2）用switch语句实现多分支选择结构；

（3）选择结构的嵌套；

2．循环结构程序设计

（1）while和do while循环结构；

（2）for 循环结构；

（3）continue语句和break语句的使用；

（4）循环的嵌套；

（5）用循环实现的常用算法，如递推、迭代、枚举等。

（四）数组的定义和引用 1．一维数组、二维数组的定义、初始化和引用方法；

2．一维数组的应用（如排序），二维数组的应用（如矩阵运算）；

3．数组作函数参数；

4．字符数组的定义、初始化和输入输出方法； 5．字符串与字符串处理函数的使用。

（五）函数 1．函数的定义方法；

2．函数的调用、参数和返回值；

3．形式参数与实在参数的两种传递方式；

4．变量的作用域（局部变量和全局变量）；

5．变量的存储类别(自动、静态、外部)，变量的生存期。

（六）指针 1．指针与指针变量的概念，指针与地址运算符；

2．通过指针引用数组；

3．通过指针引用字符串；

4．指针数组和多重指针；

5．动态内存分配。

（七）结构体 1．结构体类型数据的定义和引用方法；

2．结构体嵌套和用指针引用结构体成员；

3．结构体数组的应用；

4．链表的基本操作（创建，插入，删除，输出）。

（九）文件操作 1．C语言中的文件类型；

2．文件的打开与关闭（fopen,fclose）； 3．文件的读写（fputc,fgetc, fread,fwrite函数）。

考试题型:

1．选择题 （15分）

2．判断题 （10分）

3．程序阅读 （10分）

4．程序设计 （15分）

参考书目：

1．《C程序设计》（第四版） 谭浩强著 清华大学出

版社 二、《数据结构》考试大纲

考试内容：

（一）绪论

1. 数据结构的基本概念和术语；

2. 抽象数据类型(ADT)的概念；

3. 算法的时间复杂性和空间复杂性分析方法。

（二）线性表

1. 线性表的逻辑结构特性和线性表的抽象数据类型(ADT)的设 计；

2. 线性表的顺序存储结构和链式存储结构实现方法；

(1) 顺序表的创建、查找、插入和删除等基本操作及相关算法； (2) 单链表的创建、查找、插入和删除等基本操作及相关算法； (3) 双向链表的插入和删除等基本操作及相关算法；

(4) 循环链表的特点及创建、查找、插入和删除等基本操作及 相关算法

3. 一元多项式的表示方法及相加算法。

（三）栈与队列

1. 栈与队列的定义、操作特点；

2. 栈、队列（包括循环队列）的表示和基本操作的实现。

3．栈和队列在表达式求值、括号匹配、数制转换、舞伴问题中

的应用。

（四）树和二叉树 1．二叉树的定义、结构特点和性质；

2. 二叉树的设计和实现：二叉树存储结构的特点，三种遍历方式 的递归算法，二叉树的线索化过程和算法；

3. 树的设计和实现、树的各种表示方法及基本术语，树和森林与 二叉树的转换方法；4. 哈夫曼树的构造算法、哈夫曼编码。

（五）图

1. 图的定义、术语和性质；

2．图的设计和实现：

(1) 图的邻接矩阵、邻接表的存储结构及其构造方法； (2) 图的两种遍历方法：深度优先遍历和广度优先遍历；

3．图的应用：

（1）最小生成树的算法；

（2）构造最短路径的 Dijkstra 算法和 Floyd 算法。

（六）查找 1．查找的基本概念

2. 线性表的查找

（1）顺序查找算法

（2）折半查找算法

（3）分块查找算法 3．树表的查找

（1）二叉排序树的定义和基本操作（创建、插入、删除、

查找）；

（2）平衡二叉树的定义、平衡调整方法 4．Hash 表的查找

（1）Hash 查找的基本概念；

（2）Hash 函数的构造方法、处理冲突的方法；

（3）Hash 表的查找算法

（七）排序 1．排序的基本概念

2. 插入排序

（1）直接插入排序算法

（2）折半插入排序算法

（3）希尔排序算法 3．交换排序

（1）冒泡排序

（2）快速排序 4．选择排序

（1）简单选择排序

（2）堆排序

考试题型：

1．选择 （10 分）

2．判断 （10 分）

3．应用题 （20 分）

4．算法设计 （10 分） 参考书目：

1．《数据结构》（C 语言版） 严蔚敏 吴伟民编 清华大学出版社

2.《数据结构》（C 语言版|第 2 版） 严蔚敏 李冬梅 吴伟民编 人 民邮电出版社