2020年广东专版考试时间已经确定，准备参加考试的考生必须在考试前做好准备。乐贞老师和李老师整理了广东寒山师范学院2020年数据结构考试大纲，希望对考生有所帮助。

本科分班考试是由大学毕业生参加的选择性考试。《数据结构》是计算机科学与技术专业(本科)的专业基础课。考试主要考查考生对存储组织、维护操作、基本应用、常用基本数据结构(顺序表、链表、栈、队列、树、二叉树、图等)的搜索排序等基本算法的掌握情况。)，从而保证后续课程的学习。

二、考试内容

一、考试的基本要求

1.基础理论知识

(l)数据结构的基本概念和术语，算法的描述方法，算法分析的基本概念。

(2)线性表的基本概念，线性表的基本操作，以及这些操作分别在顺序存储和链式存储结构下的实现和复杂度分析。

(3)栈和队列的定义、存储结构、实现和典型应用。

(4)字符串的定义及其基本操作。

(5)数组的定义、操作和存储。

(6)树的定义、基本术语和存储结构，二叉树的定义和性质，二叉树的存储结构和各种运算，哈夫曼树的概念和应用。

(7)图形的定义和术语，图形的存储结构及其基本操作。

(8)各种搜索方法的算法、适用范围和时间复杂度分析。

(9)、各种内部行算法的基本思想和时间复杂度分析，以及不同排序方法的比较。

2.基本功

(1)、可以用基本数据结构及其算法来描述和解决实际的简单问题。

(2)能看懂“C类”语言写的算法，能根据需要写“C类”语言的算法。

(3)可以分析算法的功能、运行结果和时间复杂度。

二、考核知识点和考核要求

靠前章导言

首先，评估知识点

1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、节点等基本概念。抽象数据类型的定义、表示和实现。

2.算法，它的特点，以及如何用类C语言描述算法。

3.算法设计的基本要求以及计算语句频率和估计算法时间复杂度的方法。

二、考核要求

1.记忆:数据结构的基本概念和四种基本数据结构的特征。

2.理解:四种基本数据结构的基本运算，算法复杂度度量的基本概念。

3.应用:用类C语言描述算法

第二章线性表

首先，评估知识点

1.线性表的定义和基本操作。

2.线性表顺序存储结构的表示和基本操作。

3.线性表链存储，有附加头节点和单链表，循环链表和双链表没有附加头节点，搜索、插入、删除等基本操作。

二、考核要求

1.记忆:线性表的基本概念和运算，各种链表的表示。

2.理解:顺序存储和链式存储的比较，以及各种链表的基本运算算法

第三章堆栈和队列

首先，评估知识点

1.栈的定义和操作特征，包括顺序存储、链式存储，以及栈、栈、判断空 (full)、取栈顶元素等基本操作。

2.队列的定义和操作特点，如存储、入队、出队、判断空(满)、取队列靠前个元素等。

3.栈应用的例子，比如数字转换，表达式求值等。

二、考核要求

1.记忆:栈和队列的概念、功能、操作特点和主要操作。

2.理解:栈和队列相对于一般线性表的特殊性，栈和队列的顺序存储和链式存储，循环队列。

3.应用:栈和队列的常用场合。

第四章弦

首先，评估知识点

1.字符串的定义和空字符串的概念。

2.字符串的基本操作。

3.字符串的顺序存储结构及其下基本操作的实现。

4.字符串的基本模式匹配算法。

二、考核要求

1.记忆:字符串的相关概念。

2.理解:字符串的基本运算，字符串的顺序存储结构及其基本运算。

3.应用:使用字符串的基本运算功能。

第五章数组和广义表

首先，评估知识点

1.数组的顺序存储结构。

2.二维数组按行和列存储，计算数组元素的地址计算公式。

3.三重表的概念和基本操作。

4.广义表的定义。

二、考核要求

1.记忆:数组的顺序存储结构和广义表的定义。

2.理解:二维数组的地址计算和三重表的表示。

3.应用:利用三重表解决稀疏矩阵的存储问题。

第六章树和二叉树

首先，评估知识点

1.树的定义和术语。

2.二叉树(完全二叉树和全二叉树)的定义和性质，二叉树的存储结构(顺序表示和二进制链表表示)。

3.二叉树遍历算法(一阶、中阶、末阶、层次)。

4.将树和森林转换为二叉树的方法(孩子和兄弟表示)。

5.树的路径长度，树的加权路径长度，哈夫曼树的构造方法。

二、考核要求

1.记忆:树木的基本概念

2.了解:二叉树的存储结构，遍历算法，子兄弟表示，树的路径长度，以及霍夫曼树的构造方法

3.应用:使用霍夫曼树解决一些优化问题

第七章图

首先，评估知识点

1.图的定义。

2.图形的基本术语。

(1)图与无向图、有向图、网、子图、连通图、强连通图。

(2)度、度、顶点度。

(3)顶点之间的路径、路径长度和循环。

3.图的存储结构

(1)邻接矩阵(2)邻接表(包括逆邻接表)

4.遍历图

(1)深度优先搜索遍历图算法及其时间复杂度。

(2)广度优先搜索遍历图的思想及其时间复杂度。

5.生成树和最小生成树的概念。

6.拓扑排序法

7.最短路径算法。

二、考核要求

1.记忆:图的基本概念和术语，最小生成树、拓扑排序和最短路径的概念和算法思想。

2.理解:图形的存储方式以及基于这种存储方式的基本操作(求进度、出度、下一条边等)。)

3.应用:拓扑序列的应用，最短路径的应用。

第8章动态存储管理(不需要)

第九章搜索

首先，评估知识点

1.搜索、关键词、平均搜索长度的概念。

2.静态查找表查找算法及其效率(最差和平均查找长度)。

(1)顺序搜索(2)二分搜索法(3)块搜索

3.动态查找表

二叉排序树的定义、构造过程、搜索算法和效率。

4.哈希表

哈希表的特点。(2)构造哈希函数的方法(除了留余数等。).(3)处理冲突的方法。

二、考核要求

1.记忆:搜索的基本概念，静态查找表和动态查找表的概念，以及哈希表的概念

2.了解:各种静态搜索算法的比较次数分析；二叉排序树的生成过程和搜索算法；哈希函数的选择，冲突处理的方法，哈希搜索的过程。

3.应用:分析各种搜索算法的比较次数。

第十章内部排序

首先，评估知识点

1.排序的目的、分类和排序方法稳定性的定义。

2.直接插入排序的想法

3.快速分类

(1)冒泡排序算法。(2)快速排序的思想。

4.选择排序

(1)简单的选择和排序算法。

(2)堆的定义和堆排序的思想。

5.双向合并排序的思路。

二、考核要求

1.记忆:直接插入排序、冒泡排序和简单选择排序的想法

2.了解:快速排序、堆排序、双向合并排序的思路，以及各种排序方法的稳定性、平均比较次数、平均移动次数的分析。

3.应用:使用类C语言或类C语言编译直接插入排序、冒泡排序、简单选择排序等排序算法。

第11章外部排序(不需要)

第十二章文件(不要求)

三、考试形式和试卷结构

1.考试形式:采用闭卷笔试形式。考试时间120分钟，全卷100分钟。

2.试卷中各章节的比例:靠前章约占8%，第二、三、四、五章约占40%，第六章约占20%，第七章约占15%，第九章约占12%，第十章约占5%。

3.不同能力水平的试题要求的分数，记忆约为30%，理解约为40%，应用约为30%。

4.试题难度比例:易30%左右，中50%左右，难20%左右。

5.试卷结构:试题分为客观题和主观题。客观题一般包括填充空题、选择题、名词解释、程序填充空题等。主观题一般包括简答题和算法设计题。

四.参考书目

主要参考书:《数据结构》(C语言版)严为民吴伟民主编，清华大学出版社。

v题举例

一、填写空

1.深度为8(根的层数为1)的全二叉树有_ _ _ _ _ _ _ _ _ _ _ _ _ _个叶节点。

2.字符串的长度是指_ _ _ _ _ _ _ _。

二、选择题

1.如果堆栈的堆叠顺序是a、b、c、d、e，那么堆栈的不可能输出顺序是_ _ _ _ _ _ _ _。

答。e d c b a B. d e c b a C. d c e a b D. a b c d e

2.栈操作数据的原理是_ _ _ _ _ _。

A.先进先出b .后进先出c .后进后出d .没有顺序

第三，名词解释

1.连通图

2.完全二叉树

四.在程序中填写空问题

下面的过程是在二进制排序树中查找给定的关键字，如果找到就返回1，如果没有找到就返回0。请完成该程序。

{ Tree * p = boot

while(_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _){

if(item . key , lt；boot->；data.key)

____________________________

else if(item . key , gt；p-,gt。data.key)

___________________________

其他

___________________________

}

return(0)；

}

动词 （verb的缩写）简答题

1、尝试比较链式存储和顺序存储的优缺点。

2.已知二叉树的中间序列和后面序列分别是BDCEAFHG和DECBHGFA，所以尽量写出前面的序列。

六、算法设计题

设计了一种算法来合并递减数组A [0...n-1]和前导节点的递增单链表B组成前导节点的递增链表C。单一链表的已知数据结构定义为:

struct SingleLink{

ElemType数据；

SingleLink * next

};

使用功能原型:

single link * link aandb(elem type A[]，int n，single link * B)；

数组a和链表b是通过函数参数传递的，n是数组的大小。该函数的返回值是生成的链表。

2020年广东专版考试时间是3月7-8日。对于准备参加考试的考生，我们和乐贞老师一起来看看广东寒山师范学院2020年专版数据结构考试大纲。了解考试大纲后，考生备考会更加得心应手。

部分内容来源于网络转载、学生投稿，如有侵权或对本站有任何意见、建议或者投诉，请联系邮箱（1296178999@qq.com）反馈。 未经本站授权，不得转载、摘编、复制或者建立镜像， 如有违反，本站将追究法律责任！