2020广东技术师范大学天河学院专插本专业课《数据结构与算法》考试大纲

2020年广东技术师范大学天河学院专插本专业课《数据结构与算法》考试大纲是什么？即将参加2020年广东专插本考试且将广东技术师范大学天河学院作为目标院校的考生注意啦，此次易学仕小编为大家整理了《数据结构与算法》的考试大纲，详情如下：

广东技术师范大学天河学院 2020 年本科插班生招生考试 《数据结构与算法》考试大纲

一、考试要求

本大纲为计算机科学与技术专业本科插班生专门编写，作为考试命题的依据。《数据结构与算法》是计算机科学与技术专业的一门学科核心课程，它是培养程序设计所用到的基本数据类型和数据结构的基本操作和解决实际软件工程问题的相关算法的重要课程。

《数据结构与算法》课程考试旨在考察学生对本课程涉及的基本数据类型、基本数据结构的基本操作及基本算法应用掌握的深度和广度，具备进一步学习计算机科学与技术专业后续课程的能力和基础。

二、教材及主要参考书目

教材：《数据结构 c 语言版（第二版）》 严蔚敏、李冬梅、吴伟民著 中国工信出版集团 人民邮电出版社

三、考试内容

第 1 章 绪论

1、数据结构的基本概念：数据结构是相互之间存在一种或多种特定

关系的数据元素的集合。

2、数据结构的三要素：

1）逻辑结构：集合结构； 线性结构：一对一关系；树结构：一对多关系；图结构：多对多关系。例如：线性表、栈、队列、串、数组等是逻辑结构；

2）存储结构：顺序存储结构和 链式存储结构

例如：顺序表、链表、链队列等是存储结构；

3）数据的操作：有插入、删除、查找、排序等。

此处尤其要注意逻辑结构与存储结构的区分，多有考选择题如：以下哪个是存储结构的术语或以下哪个不是存储结构的术语。

3、算法：（算法的概念、特性；算法优劣的评价标准；算法分析的目的；熟记）；算法的时间复杂度的分析(能分析出一段程序的时间复杂度；掌握分析的方法)

第 2 章 线性表

1、顺序表：存储和操作；

如：两个有序的顺序表要合并成一个顺序，要进行的最少的比较次数。顺序表中删除或插入一个元素时进行的移动操作。

2、线性表:

1）单链表：

如：单链表中数据的插入、删除和比较操作；例：以带头结点的单链表表示有序表，编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。 带头结点的单链表中，删除数据域的值为 n 的结点，或者删除所有数据域的值为 n 的结点（意思是单链表中有多个数据域的值为 n）。

2）循环链表：

第 3 章 栈和队列

1、栈：栈的应用：如：栈在递归函数中的应用，已知栈的入栈顺序，求栈的出栈顺序。

2、队列：

已知循环链表的头指针、尾指针，求长度；

已知循环链表的头指针、长度，求尾指针；

已知循环链表的尾指针、长度，求头指针；

第 4 章 串、数组和广义表

1、串类型的定义

字符串的实现

字符串模式匹配算法

如：串匹配算法的实现：求子串在主串中首次出现位置的算法

2、数组:

数组的基本概念

数组的顺序存储方式

如：求二维数组某元素的存储地址：按行优先和按列优先；

例：已知二维数组的首地址和每个元素的存储长度，求 A[i][j]存储地址。

矩阵

矩阵的定义和操作

特殊矩阵

稀疏矩阵

求特殊矩阵的压缩存储：

如：某矩阵压缩存储一维数组 S[k]中，二维数组元素 a[i][j]存储在一维数组 S[k]中时元素下标 k 与二维数组元素下标 i，j 的关系。

3、广义表

基本概念

如：广义表的深度、长度的计算；Head(L)求表头函数和 Tail(L)求表

尾函数的应用。

广义表 L=((a,b),((c,d),(e,f)))

广义表的深度=?

广义表的长度=?

head(tail(head(tail(L))))=?

第 5 章 树和二叉树

1、树的基本概念

树的定义

基本术语

2、二叉树

二叉树的定义

二叉树的性质

如：已知完全二叉树的结点总数，求该二叉树的叶子结点数。

二叉树的存储结构

3、二叉树的遍历

遍历的定义

遍历算法

如：已知二叉树的中序遍历序列和先序遍历序列，画出该二叉树和写出后序遍历序列；或者已知二叉树的中序遍历序列和后序遍历序列，画出该二叉树和写出先序遍历序列；或者已知二叉树的中序遍历序列和层序遍历序列，画出该二叉树和写出先序遍历序列；

4、树和森林

树的存储表示

森林的存储表示

如：一个森林有 m 棵树，顶点总数为 n，则森林中含有的总边数是

树和森林的遍历

树和森林与二叉树的转换

5、哈夫曼树与哈夫曼编码

哈夫曼树的基本概念

哈夫曼树构造算法

哈夫曼树编码

如：已知一串字母的权值，画出该哈夫曼树和写出各字母的哈夫曼编码；

第 6 章 图

1、图的定义和术语

2、图的存储表示

邻接矩阵

如：已知图的邻接矩阵 A，求各顶点的度

邻接表

如：已知有向图的邻接表，画出该有向图和该有向图的逆邻接表。

3、图的遍历

深度优先搜索

广度优先搜索

4、图的最小生成树

Prim 算法

Kruskal 算法

如：已知无向带权图 G，画出图 G 的邻接矩阵和图 G 的一棵最小生成树。

5、有向无环图的应用

拓扑排序

如：己知有向图 G，求 G 的拓扑序列

关键路径

6、最短路径问题

单源点最短路径

所有顶点之间的最短路径

第 7 章 查找

1、查找的基本概念

2、静态表的查找

顺序查找

有序表的查找

如：对表长为 n 的顺序表进行分块查找，假设每一块的长度均为 m，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为？

3、动态查找表

二叉排序树

如：在一棵深度为 h 的具有 n 个结点的二叉排序树中，查找任一结点的最多比较次数是。

4、散列表

4.1 散列表的概念

4.2 构造散列函数的方法

4.3 处理冲突的方法

如：设散列表长 m=8，散列函数 H(key)=key％7。表中已保存 4 个关键字：addr(17)=3，addr(32)=4，addr(54)=5，addr(20)=6，其余地址均为开放地址。存储关键字 47 时存在冲突，采用线性探测法来处理。则查找关键字 42 时的探查次数是？

第 8 章 排序

1、排序概述

排序算法的时间复杂度和稳定性；如：以下哪个排序算法的最好时间复杂度和最坏时间复杂度都是 O（nlogn）且是稳定的。或以下哪个排序算法是不稳定的或以下哪个排序算法是稳定的；

2、插入排序

直接插入排序

Shell 排序

3、交换排序

冒泡排序

快速排序

4、选择排序

普通选择排序

堆排序

5、归并排序

如：

1）排序算法的应用；求应用 XX 排序，对关键字序列（43，02，80，

48，26，57，15，73，21，24，66）进行一趟、二趟或三趟排序时，则得到的各趟结果为：

第一趟：

第二趟：

第三趟：

2）能应用某种排序算法编写程序，将某关键字序列进行升序或者降

序排列；

四、考试方式与试题类型

1、考试方式：闭卷、笔试，考试时间为 120 分钟，试卷满分为 100分。

2、试题类型

1）选择题(每题 1 分，共 20 分)

单项选择题，共 20 题，每题 1 分，共 20 分

2）填空题(每题 2 分，共 20 分)

共 10 题，每题 2 分，共 20 分

3）简答题(每题 5 分，共 20 分)

共 4 题，每题 5 分，共 20 分

4）程序填空题(每题 10 分，共 20 分)

共 2 题，每题 10 分，共 20 分

5）算法设计题(每题 20 分，共 20 分)

共 1 题，每题 20 分，共 20 分

总分共 100 分，考试时间 120 分钟；

以上就是“2020年广东技术师范大学天河学院专插本专业课《数据结构与算法》考试大纲”全部内容。考生在备考的过程中，如遇到问题或有疑难的话，请访问易学仕在线，会有专业老师为你解答! 小编在此预祝大家在2020年广东专插本考试中都能取得优异成绩。

推荐阅读：

2020年广东技术师范大学天河学院专插本招生计划