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 版) 严蔚敏 李冬梅 吴伟民编 人民邮电出版社