数据结构课程考核说明

1、数据结构课程考核说明第一部分 考核说明数据结构 是全国电大计算机应用专业的一门核心课程， 起到承上启下的作用和地位， 主要任务是讨论数据的各种逻 辑结构、存储结构以及相应运算的算法。考核对象： 全国电大系统计算机应用专业“开放教育试点”的学生。教学媒体：主教材数据结构 许卓群主编 中央广播电视大学出版社出版。实验教材数据结构实验 徐孝凯编 中央广播电视大学出版社出版。录像教材数据结构 20 讲 刘杰主讲 中央电大音像出版社出版。辅助教材数据结构习题解析徐孝凯编 中央电大教育杂志社出版，通过各地电大教材发行部门统一征订发行。命题依据： 本考核说明严格按照中央电大计算机应用专业数据结构课程教学大纲

2、编写。考核要求： 考核学生掌握和运用数据结构基本概念和知识分析和编写数据处理算法的能力。具体考核要求分为以下 3 个层次：了解：了解数据结构的一些基本概念。包括线性表、栈、队列、链表、树、二叉树、二叉搜索树、堆、哈夫曼树、图、 网、二分查找、索引查找、分块查找、散列查找、堆排序、快速排序、归并排序等概念。掌握：能够分析现成程序和算法， 即指出功能或写出运行结果； 能够写出对已知数据进行相应运算的数据变化过程和最 终结果。应用：能够根据解决问题的需要选择数据结构和编写算法。命题原则：1. 严格按照该课程教学大纲和考核说明的要求命题。2. 试题的覆盖面较广，并适当突出重点。3试题的难易程度和题量适

3、当，按难易程度分为三个层次：容易占40%，一般占 40%，较难占 20%。4题型有六种：单选题、填空题、运算题、阅读算法并回答问题、算法填空、编写算法。考核形式：采用期末 卷面考核 与形成性考核 相结合的方式。形成性考核占 20 分，视平时上机和作业完成情况而定，由所在班级的 任课教师给定，由省（市、自治区）级电大认定；期末卷面考核占 80 分，由中央电大统一命题并采用 闭卷 方式，答题时限 为 120 分钟。两方面成绩累计达到 60 分者为及格。第二部分 考核内容及要求第一章 绪论重点掌握的内容：1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。2. 集合结构、线性结构、树

4、结构和图结构的特点。3. 抽象数据类型的定义和表示方法。4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空 间大小和数组占用存储空间大小的计算。5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。 对于本章的其余内容均作一般掌握。第二章 线性表重点掌握的内容：1. 线性表的定义和抽象数据类型的描述，线性表中插入、删除等操作的功能，对应的函数名、返回值类型和参数表中 每个参数的

5、作用。2. 线性表的顺序存储结构的类型定义，即 List 类型的定义和每个域的定义及作用。3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4. 单链表中结点的结构，每个域的定义及作用，即 LNode 类型的定义及结构。5. 带表头附加结点的链表、循环链表、双向链表的结构特点。6. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。7. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。对于本章的其余内容均作一般掌握。第三章 稀疏矩阵和广义表重点掌握的内容：1. 稀疏矩阵的定义和三元组线性表表示。2. 稀疏矩阵的顺序存储、带行指针向量的链接存储，它们中

6、非零元素结点的结构。3. 稀疏矩阵的转置运算和算法描述。4. 广义表的定义和表示，广义表长度和深度的计算。5. 广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法。对于本章的其余内容均作一般了解。第四章 栈和队列重点掌握的内容：1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用2. 栈的顺序存储结构的类型定义，即 Stack 类型的定义和每个域的定义及作用。3栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。5. 算术表达式的中缀表示和后缀表

7、示，以及相互转换的规则。6. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的 作用。7. 队列的顺序存储结构的类型定义，即 Queue 类型的定义和每个域的定义及作用。8. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。9. 利用栈和队列解决简单问题的算法分析和设计。一般掌握的内容：1. 求解阶乘问题方法和算法。2. 后缀表达式求值的方法和算法，3. 把中缀表达式转换为后缀表达式的方法和算法。4. 队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。一般了解的内容：求解迷宫问题的方法和算法。第五章 树和二叉树

8、重点掌握的内容：1. 树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。2. 树和二叉树的概念。3. 树和二叉树的性质。4. 二叉树中结点的编号规则和对应的顺序存储结构。5. 二叉树的链接存储结构及存储结点的类型定义，即 BTreeNode 类型的定义和每个域的定义及作用。6. 二叉树的先序、中序、后序遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法。7. 在链接存储的二叉树上实现指定功能的算法分析和设计。一般掌握的内容1. 普通树的链接存储结构， GTreeNode 类型的定义和每个域的定义及作用。2普通树的先根、后根和按层遍历的过程及算法。第六章 二叉树

9、的应用重点掌握的内容：1. 二叉搜索树的定义和性质。2. 二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点 的路径上的结点数。3. 二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度。4根据一组数据采用顺序插入生成一棵二叉搜索树的过程。5. 堆的定义和顺序存储结构，小根堆和大根堆的异同。6. 向堆中插入元素的过程、算法描述及时间复杂度7. 从堆中删除元素的过程、算法描述及时间复杂度。一般掌握的内容：哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。 对本章的其余内容均作一般了解。第七章 图重点掌握的内容：1

10、. 图的定义，它的顶点集和边集表示。2. 图的基本概念。3. 图的邻接矩阵、邻接表和边集数组三种存储结构及相应的空间复杂度。4. 存储图使用的 vexlist, adjmatrix, adjlist, edgenode, edgeset, edge 等类型的定义及用途。5. 图的深度优先和广度优先搜索遍历的过程。6. 对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。8. 图的生成树、生成树的权、最小生成树等的定义。9. 根据普里姆算法求图的最小生成树的过

11、程。10根据克鲁斯卡尔算法求图的最小生成树的过程。11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程。 对本章的其余内容均作一般掌握。第八章 查找重点掌握的内容：1. 在顺序表上进行顺序查找的过程、算法、平均查找长度和时间复杂度。2. 在顺序存储的有序表上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定 值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。3. 索引存储的概念，索引表的存储结构和索引项的存储结构，索引查找一个元素的过程、平均查找长度和时间复杂度。4. 散列存储的概念，散列函数、散列表

12、、冲突、同义词、装填因子等术语的含义。5. 利用除留余数法建立散列函数求元素散列地址的方法。6. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的 过程。7. 根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个 给定值元素的查找长度和查找所有元素的平均查找长度。B_树上8. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_ 的结构特性，从查找一个给定值元素的过程。一般掌握的内容：1. 索引查找和分块查找算法。2. B_树查找算法。3. 向 B_ 树中插入元素

13、的过程。对本章的其余内容均作一般了解。第九章 排序重点掌握的内容：1. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度，整个 堆排序的算法描述及时间复杂度。2. 快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数3. 快速排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。4. 二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空 间复杂度。一般掌握的内容：1. 直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。

14、2. 每一种排序方法的稳定性。3. 直接插入排序和直接选择排序的算法。一般了解的内容：1. 二路归并排序过程中涉及的每个算法。2. 冒泡排序算法。第三部分 模拟考核试题及解答一、单选题(每小题 2 分，共 8 分)1. 在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行 。A HL=p; p->next=HL; B p->next=HL; HL=p;C p->next=HL; p=HL; D p->next=HL->next; HL->next=p;2. 在一个顺序队列中，队首指针指向队首元素的 位置。A 前一个 B 后一个 C 当前3

15、. 从二叉搜索树中查找一个元素时，其时间复杂度大致为 。2A O(n) B O(1) C O(log 2n) D O(n 2)4. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 。A 24 B 48 C 72 D 53二、填空题(每空 1 分，共 32 分)1. 一个算法的时间复杂度为 (3n2+2nlog2n+4n-7)/(5n) ，其数量级表示为 。2. 在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。3一个广义表中的元素分为 元素和 元素两类。4从一个链栈中删除一个结点时，需要把栈顶结点的 域的值赋给 。5在进

16、行函数调用时，需要把每个实参的值和调用后的 传送给被调用的函数中。6对于一棵具有 n 个结点的二叉树， 若一个结点的编号为 i(1in)，则它的左孩子结点的编号为 ，右孩子结点的编号为 ，双亲结点的编号为 。7在一棵高度为 5 的理想平衡树中，最少含有 个结点，最多含有 个结点。8在一个堆的顺序存储中，若一个元素的下标为i(0 in-1)，则它的左孩子元素的下标为 ，右孩子元素的下标为。9在一个具有 n 个顶点的无向完全图中， 包含有 条边，在一个具有 n 个顶点的有向完全图中， 包含有 条边。10对于一个具有 n 个顶点和 e 条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别

17、为 和条。11以二分查找方法从长度为 20 的有序表中查找一个元素时，平均查找长度为 。12假定一个线性表为 (12,23,74,55,63,40,82,36) ，若按 Key % 3 条件进行划分，使得同一余数的元素成为一个子表，则 得到的三个子表分别为 、和 。13在线性表的散列存储中， 装填因子 a 又称为装填系数， 若用 m 表示散列表的长度， n 表示待散列存储的元素的个数， 则 a 等于 。14在一棵 m阶B_树上，每个非树根结点的关键字数目最少为 个，最多为 个，其子树数目最少为，最多为 。15在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为 ，整个堆排序过程的时间复杂度

18、为。16. 快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 。三、运算题(每小题 6分，共 24 分)1. 假定一棵二叉树广义表表示为 a(b(c),d(e,f) ，分别写出对它进行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：2已知一个图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20,(6,7)30;按照普里姆算法从顶点 0 出发得到最小生成树，试写出在生成最小生成树的过程中依次得到的各条边

19、。3. 已知一个图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5,6,7,8;E=<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<4,8>,<5,7>,<6,7>,<7,8>若存储它采用邻接表， 并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的， 则按主教材中介绍的 进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。拓扑序列：4. 假定一组记录的

20、排序码为 （46,79,56,38,40,80,25,34） ，则对其进行快速排序的第一次划分后的结果为四、阅读算法，回答问题（每小题 8分，共 16 分）该算法被调用后得到的输出结果为：该算法的功能为：五、算法填空，在画有横线的地方填写合适的内容（10 分）。六、编写算法 （10 分）编写向类型为 List 的线性表 L 中第 i 个元素位置插入一个元素的算法，假定不需要对 i 的值进行有效性检查，同时不需 要检查存储空间是否用完。void Insert(List& L, int i, ElemType x)参考解答一、单选题(每小题 2 分，共 8 分)1. B 2. A 3. C 4. D二、填空题(每空 1 分，共 32 分)1