826-计算机软件技术基础.doc

2023 年全国硕士研究生招生考试 湖北师范大学自命题考试科目考试大纲 （科目名称：计算机软件技术基础 科目代码:826） 一、考查目标 计算机软件技术基础科目考试内容包括 C 语言程序设计和数据结构两个部 分，它们是计算机各个专业的基础。其中，C 语言程序设计要求考生系统掌握程 序设计的基本数据类型、程序的基本结构、函数、数组、指针和结构体的基本概 念和使用方法；数据结构部分要求考生掌握各种基本类型的概念、特征、操作、 存储表示和基本应用，各种基本查找表的概念、特征以及查找方法，基本的排序 方法；注重考查考生运用相关理论和方法分析、解决实际问题的能力。 二、考试形式与试卷结构 （一）试卷成绩及考试时间 本试卷满分为 150 分，考试时间 180 分钟。 （二）答题方式 答题方式为闭卷、笔试。 （三）试卷题型结构 选择题：10 小题，每小题 5 分，共 50 分 填空题：10 小题，每小题 3 分，共 30 分 阅读程序题：4 小题，每小题 5 分，共 20 分 操作题：2 小题，每小题 10 分，共 20 分 算法设计题：2 小题，每小题 15 分，共 30 分 （四）主要参考书目 1. 《C 程序设计》（第五版），谭浩强著，清华大学出版社，2017 2.《数据结构(C 语言版)》，严蔚敏吴伟民编著，清华大学出版社，2020 三、考查范围 （一）考查目标 C 语言程序设计： 1、C 语言程序科目要求考生比较系统地掌握 C 语言的基础理论和基本知识。 2、熟练掌握 C 语言的基本语法，熟悉结构化程序设计的编程思想，能运用 C 语言设计应用程序以解决实际问题。 数据结构： 1、理解数据的基本概念；掌握数据的逻辑结构、存储及其差异，以及各种 基本操作的实现。 2、掌握基本的数据处理原来和方法的基础上，能够简单设计算法，并对其 进行基本的时间复杂度与空间复杂度的分析。 3、能够选择合适的数据结构和算法进行问题求解，具备采用 C 语言设计与 实现算法的能力。 （二）考试内容 C 语言程序设计： 1、程序设计概述：了解程序和程序设计语言的基本概念，掌握 C 语言程序 的基本结构。 2、数据类型、运算符与表达式：掌握 C 语言中各种基本数据类型；理解常 量、变量的概念；掌握标识符的命名规则；掌握符号常量的定义；掌握变量定义 和初始化；掌握算术运算符，关系运算符、逻辑运算符、赋值运算符和逗号运算 符的含义及优先级与结合性；掌握各种表达式的求值；掌握不同类型数据间的转 换与运算；掌握关系表达式和逻辑表达式及各种混合表达式的求值。 3、顺序程序设计：掌握 C 语言语句的种类；掌握赋值语句的功能和表达方 法；掌握数据输入、输出的格式控制；掌握字符的输入输出函数。 4、程序的控制结构：理解结构化程序设计的基本思想，掌握程序的三种基 本结构；掌握 if 语句的三种基本形式和嵌套使用；理解条件运算符的功能和作 用；掌握用 switch 语句实现多分支选择结构；掌握 for 、while 、do-while 语 句格式，并能用它们实现循环及循环嵌套，掌握三种循环的区别和联系；掌握 break 与 continue 语句的使用。 5、函数：理解函数的概念；掌握函数的定义和调用；理解函数的类型和返 回值；熟练使用函数编程；掌握函数的形式参数与实际参数的区别；理解函数的 参数传递；掌握函数的嵌套调用和函数递归调用；理解局部变量和全局变量及变 量的存储类别、变量的作用域和生存期；理解内部函数、外部函数的概念。 6、数组：掌握数组的定义和引用并能够灵活运用；掌握数组作为函数参数 的函数的定义和调用；掌握字符数组的定义和使用；掌握使用字符数组来处理字 符串；掌握字符串处理函数的使用。 7、指针：理解指针的概念；掌握指针变量的定义和使用；掌握指向简单变 量的指针和指向数组的指针使用；掌握指针变量和简单变量作为函数参数的区别； 掌握指针数组；掌握指向字符串的指针变量的定义和使用。了解指向函数的指针。 8、结构体与共用体：掌握结构体类型的定义、结构体类型变量的定义、初 始化及引用方法；掌握结构体数组的定义和使用；掌握结构体变量、结构体数组 和结构体指针作为函数参数；掌握关键字 typedef 的使用；了解结构体类型和共 用体类型的变量占用内存情况；了解链表的意义和实现。 9、文件：了解文件的概念；掌握文件类型指针、掌握文件的打开与关闭； 理解文件的读写。 数据结构： 1、绪论：掌握数据、数据元素、数据对象、数据结构、存储结构和数据类 型的概念和术语的含义；理解算法五要素的确切含义；掌握算法设计的基本要求 以及计算语句频度和估算算法时间复杂度的方法。 2、线性表：掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系； 熟练掌握线性表的顺序存储结构和链式存储结构的描述方法，头结点，头指针和 首元结点的区别及循环链表，双向链表的特点；熟练掌握线性表在顺序存储结构 和各种链表结构上的查找、插入和删除的算法；能够从时间和空间复杂度的角度 综合比较两种存储结构的不同特点及其适用的场合。 3、栈和队列：熟练掌握栈和队列的结构特性；熟练掌握栈类型在两种存储 结构表示时的基本操作实现方法；熟练掌握循环队列和链式队列的基本操作实现 算法；熟练掌握栈和队列的满和空的条件和它们的描述方法；熟悉栈和队列的典 型应用。 4、串：掌握串的结构特性----数据元素为字符的线性表；熟悉串的基本操 作；掌握串匹配的 KMP 算法，熟悉 next 函数的定义，学会手工计算 next 函数值。 5、数组：掌握数组存储表示方法存储结构中的地址计算；掌握对特殊矩阵 进行压缩存储时的下标变换公式；了解稀疏矩阵的三元组压缩存储表示方法及适 用范围。 6、树和二叉树：熟悉树的基本定义及其相关的术语的含义；熟练掌握二叉 树的结构特性，了解相应的证明方法，理解常见的二叉树有关理论结论；熟悉二 叉树的二叉链和线索二叉树存储结构特点及适用范围；熟悉三种遍历二叉树的递 归算法；掌握二叉树线索化的实质及线索化的过程；掌握树和森林与二叉树的转 换，及其各自遍历的对应关系；了解实现树的各种操作的算法；掌握最优树的特 性，掌握 Huffman 树及其应用。 7、图：掌握图的定义和术语；掌握图的两种存储结构：数组表示法、邻接 表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；掌握图的 两种遍历策略；图的遍历和树的遍历之间的类似与差异；熟悉图的最小生成树的 生成方法；AOE 有向无环网的关键路径，关键活动的计算思路；掌握网络顶点之 间的最短距离的计算思想。 8、查找：熟练掌握顺序表和有序表的查找方法；掌握查找效率的计算方 法；. 熟练掌握二叉排序树的构造和查找方法；掌握平衡二叉树的维护平衡的方 法。 9、内部排序：掌握排序的定义和各种排序方法的基本思想及其特点；了解 各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的 方法；熟练掌握快速排序和堆排序等方法的实例排序过程；能够进行各种排序方 法的时间复杂性(平均情况与最坏情况)估计或分析；一般了解排序方法“稳定” 的含义。