2024年湖南工学院专升本考试大纲《程序设计综合》

　　2024年湖南工学院专升本考试大纲《程序设计综合》，考试内容与要求：本科目考试内容涵盖C语言程序设计、基础算法、数据结构等方面，主要考查考生对C语言基础语法与数据类型、程序控制结构、函数、指针、结构体、线性表、树、图、排序、查找，以及枚举、递归、分治等基础算法，突出考查考生的抽象思维能力、综合运用所学的知识分析问题和解决问题的能力，以及程序设计能力。

　　一、 C 语言数据类型和表达式

　　1. 熟悉 C 语言的数据类型，掌握常量和变量的表示方法。

　　2. 掌握变量的赋值方法。

　　3. 熟悉 C 语言的各种运算符。

　　4. 掌握 C 语言的算数表达式、赋值表达式、关系表达式、逻辑表达式。

　　5. 掌握混合运算的优先级和结合性，能正确计算混合表达式的结果。

　　6. 能根据要求将数学表达式、自然语言描述的功能翻译成 C 语言的表达式。

　　7. 熟悉 C 语句的特点，C 语言程序基本结构、基本语法单位等。

　　8. 掌握格式输入函数 scanf 与格式输出 printf 函数的使用方法。

　　9. 掌握字符输入函数 getchar 与格式输出 putchar 函数的使用方法。

　　二、 程序的控制结构

　　1. 掌握 顺序、分支、循环三种控制结构及其表达形式。

　　2. 掌握 分支结构的if和switch语句的应用。

　　3. 掌握 while、do-while、for 语句的使用方法。

　　4. 掌握应用顺序、分支、循环结构解决相应问题。

　　三、 数组

　　1. 掌握一维、二维数组的定义、初始化和引用方法。

　　2. 掌握字符数组的定义、初始化和引用方法。

　　3. 能阅读与数组类型数据相关的 C 程序并分析其功能，会使用数组编程解决相应问题。

　　四、 函数

　　1. 熟悉函数定义的一般形式，熟悉函数的参数和函数的值类型。

　　2. 熟悉函数的形式参数和实际参数的用法。

　　3. 理解函数的各种调用方法，能跟踪函数参数的传递过程。

　　4. 能根据需求用C语言编写相应的函数。

　　五、 指针

　　1. 熟悉指针的基本概念，掌握指针变量的定义、引用方法。

　　2. 能熟练应用指针、掌握指针与数组、函数、结构体等方面的应用。

　　六、 结构体

　　1. 熟悉结构体的定义形式，掌握结构成员变量的表示方法。

　　2. 掌握结构变量、结构数组的赋值和初始化方法。

　　3. 能应用结构类型开展程序设计解决相应问题。

　　七、 数据结构绪论

　　1.了解非数值问题的数学模型不是数学方程，而是表、树和图之类的数据结构。

　　2.理解数据、数据元素、数据对象、数据结构和数据类型等的定义。

　　3.掌握数据的逻辑结构和存储结构及其种类;算法的重要特征等。

　　4.会根据语句的最大频度计算算法的时间复杂度的方法。

　　八、 线性表

　　1.了解线性表的定义和线性结构的特点。

　　2.理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点。

　　3.掌握线性顺序表中数据元素的存储位置的计算，顺序表、单向链表、循环链表和双向链表的插入、删除等有关操作。

　　4.会用单链表编写插入、删除等有关算法。

　　5.能够从时间和空间复杂度的角度综合比较两存储结构的特点及适用场合。

　　九、 栈和队列

　　1.了解栈和队列的定义。

　　2.理解线性表、栈和队列特点及区别，栈对实现递归过程的作用。

　　3.掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。

　　4.会编写入栈和出栈，入队和出队的有关算法，会应用栈与队列。

　　十、 串、数组和广义表

　　1.理解串的有关定义、串的逻辑结构和物理存储结构。

　　2.掌握串的模式匹配传统方法、串的模式匹配KMP算法。

　　3.了解数组、特殊矩阵和稀疏矩阵的定义，广义表的概念和链表表示。

　　4、掌握矩阵的压缩存储的有关计算方法。

　　十一、 树和二叉树

　　1.了解树的定义和二叉树的定义。

　　2.理解二叉树的性质、二叉树的存储结构。

　　3.掌握遍历二叉树的方法、线索二叉树的构造，森林与二叉树的转换，最优二叉树和哈夫曼编码。

　　4.会利用二叉树的先根、中根和后根遍历解决有关二叉树的应用问题，会编写与二叉树有关的算法。

　　十二、 图

　　1.了解图的定义和术语，生成树和最小生成树的概念。

　　2.理解邻接矩阵中元素的含义和邻接表中结点的含义。

　　3.掌握深度优先搜索、广度优先搜索、并查集等算法。

　　4.会用Prim算法和Kruskal算法构造最小生成树，会找出图中顶点的拓扑序列等。

　　5.会计算AOE网中的关键路径及活动最早、最晚开始时间等。

　　十三、 查找

　　1.了解顺序查找、二分查找和分块查找的概念，二叉排序树和平衡二叉树、哈希查找等的概念。

　　2.理解顺序查找、二分查找和分块查找算法，二叉排序树的性质。

　　3.掌握哈希函数的构造方法和处理冲突的方法，平衡二叉树的查找、插入和删除操作算法，相关查找方法的ASL。

　　4.会用哈希函数、开放地址法或拉链法建立散列表。

　　十四、 内部排序

　　1.了解排序算法的稳定性问题。

　　2.理解直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和基数排序的基本思想。

　　3.掌握直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序的算法和时间分析。

　　4.会用希尔排序、快速排序、堆排序、二路归并排序方法写出每趟排序的结果，会编写与直接插入排序和简单选择排序有关的算法。

　　十五、基础算法

　　1.掌握枚举、分治、递归、贪心算法的概念与基本原理。

　　2.会用枚举、分治、递归、贪心算法等基础算法解决相应问题。

　　Ⅱ.考试形式与试卷结构

　　一、考试形式

　　考试采用闭卷、笔试形式。试卷满分 200 分，考试时间 150 分钟。

　　二、试卷结构

　　试卷包括选择题、填空题、函数题、应用题、程序设计题。

　　三、使用教材

　　1.C程序设计，清华大学出版社，谭浩强主编，ISBN: 9787302481447.

　　2.数据结构教程，清华大学出版社，李春葆主编，ISBN: 9787302595397.