数据结构课程考核说明cum.docx

数据结构课课程考核核说明第一部分 考核说说明数据据结构是是全国电电大计算算机应用用专业的的一门核核心课程程，起到到承上启启下的作作用和地地位，主主要任务务是讨论论数据的的各种逻逻辑结构构、存储储结构以以及相应应运算的的算法。考核对对象：全全国电大大系统计计算机应应用专业业“开放教教育试点点”的学生生。教学媒体：主教材材数据据结构 许卓群群主编 中央广广播电视视大学出出版社出出版。实验教教材数数据结构构实验 徐孝凯凯编 中中央广播播电视大大学出版版社出版版。录像教教材数数据结构构200讲 刘刘杰主讲讲 中央央电大音音像出版版社出版版。辅助教教材数数据结构构习题解解析徐徐孝凯编编 中央央电大教教育杂志志社出版版，通过过各地电电大教材材发行部部门统一一征订发发行。命题依据：本考核核说明严严格按照照中央电电大计算算机应用用专业数数据结构构课程程教学大大纲编写写。考核要求：考核学学生掌握握和运用用数据结结构基本本概念和和知识分分析和编编写数据据处理算算法的能能力。具具体考核核要求分分为以下下3个层层次：了解：了解数数据结构构的一些些基本概概念。包包括线性性表、栈栈、队列列、链表表、树、二二叉树、二二叉搜索索树、堆堆、哈夫夫曼树、图图、网、二二分查找找、索引引查找、分分块查找找、散列列查找、堆堆排序、快快速排序序、归并并排序等等概念。掌握：能够分分析现成成程序和和算法，即即指出功功能或写写出运行行结果；能够写写出对已已知数据据进行相相应运算算的数据据变化过过程和最最终结果果。应用：能够根根据解决决问题的的需要选选择数据据结构和和编写算算法。命题原则：1. 严格按按照该课课程教学学大纲和和考核说说明的要要求命题题。2. 试题的的覆盖面面较广，并并适当突突出重点点。3试试题的难难易程度度和题量量适当，按按难易程程度分为为三个层层次：容容易占440%，一一般占440%，较较难占220%。4题型有有六种：单选题题、填空空题、运运算题、阅阅读算法法并回答答问题、算算法填空空、编写写算法。考核形式：采用期期末卷面面考核与与形成性性考核相相结合的的方式。形形成性考考核占220分，视视平时上上机和作作业完成成情况而而定，由由所在班班级的任任课教师师给定，由由省（市市、自治治区）级级电大认认定；期期末卷面面考核占占80分分，由中中央电大大统一命命题并采采用闭卷卷方式，答答题时限限为1220分钟钟。两方方面成绩绩累计达达到600分者为为及格。第二部分 考核内内容及要要求第一章章 绪论论重点掌掌握的内内容：1. 数据结结构的二二元组表表示，对对应的图图形表示示，序偶偶和边之之间的对对应关系系。2. 集合结结构、线线性结构构、树结结构和图图结构的的特点。3. 抽象数数据类型型的定义义和表示示方法。4. 一维和和二维数数组中元元素的按按下标和和按地址址的访问问方式以以及相互互转换，元元素地址址和数组组地址的的计算，元元素占用用存储空空间大小小和数组组占用存存储空间间大小的的计算。5. 普通函函数重载载和操作作符函数数重载的的含义，定定义格式式和调用用格式。6. 函数定定义中值值参数和和引用参参数的说说明格式式及作用用，函数数被调用用执行时时对传送送来的实实际参数数的影响响。7. 算法的的时间复复杂度和和空间复复杂度的的概念，计计算方法法，数量量级表示示。对于本章的的其余内内容均作作一般掌掌握。第二章章 线性性表重点掌掌握的内内容：1. 线性表表的定义义和抽象象数据类类型的描描述，线线性表中中插入、删删除等操操作的功功能，对对应的函函数名、返返回值类类型和参参数表中中每个参参数的作作用。2. 线性表表的顺序序存储结结构的类类型定义义，即LListt类型的的定义和和每个域域的定义义及作用用。3. 线性表表的每一一种运算算在顺序序存储结结构上实实现的算算法，及及相应的的时间复复杂度。4. 单链表表中结点点的结构构，每个个域的定定义及作作用，即即LNoode类类型的定定义及结结构。5. 带表头头附加结结点的链链表、循循环链表表、双向向链表的的结构特特点。6. 线性表表的每一一种运算算在单链链表上实实现的算算法及相相应的时时间复杂杂度。7. 在顺序序存储或或链接存存储的线线性表上上实现指指定功能能的算法法的分析析和设计计。对于本本章的其其余内容容均作一一般掌握握。第三章章 稀疏疏矩阵和和广义表表重点掌掌握的内内容：1. 稀疏矩矩阵的定定义和三三元组线线性表表表示。2. 稀疏矩矩阵的顺顺序存储储、带行行指针向向量的链链接存储储，它们们中非零零元素结结点的结结构。3. 稀疏矩矩阵的转转置运算算和算法法描述。4. 广义表表的定义义和表示示，广义义表长度度和深度度的计算算。5. 广义表表的链接接存储结结构中结结点类型型的定义义，分别别求广义义表长度度和深度度的递归归算法。对于本本章的其其余内容容均作一一般了解解。第四章章 栈和和队列重点掌掌握的内内容：1. 栈的定定义和抽抽象数据据类型的的描述，栈栈中每一一种操作作的功能能，对应应的函数数名、返返回值类类型和参参数表中中每个参参数的作作用。2. 栈的顺顺序存储储结构的的类型定定义，即即Staack类类型的定定义和每每个域的的定义及及作用。3栈栈的每一一种运算算在顺序序存储结结构上实实现的算算法，及及相应的的时间复复杂度。4. 栈的每每一种运运算在链链接存储储结构上上实现的的算法及及相应的的时间复复杂度。5. 算术表表达式的的中缀表表示和后后缀表示示，以及及相互转转换的规规则。6. 队列的的定义和和抽象数数据类型型的描述述，队列列中每一一种操作作的功能能，对应应的函数数名、返返回值类类型和参参数表中中每个参参数的作作用。7. 队列的的顺序存存储结构构的类型型定义，即即Queeue类类型的定定义和每每个域的的定义及及作用。8. 队列的的每一种种运算在在顺序存存储结构构上实现现的算法法及相应应的时间间复杂度度。9. 利用栈栈和队列列解决简简单问题题的算法法分析和和设计。一般掌掌握的内内容：1. 求解阶阶乘问题题方法和和算法。2. 后缀表表达式求求值的方方法和算算法，3. 把中缀缀表达式式转换为为后缀表表达式的的方法和和算法。4. 队列的的链接存存储结构构，以及及实现每每一种队队列运算算的算法法和相应应的时间间复杂度度。一般了了解的内内容：求解迷迷宫问题题的方法法和算法法。第五章章 树和和二叉树树重点掌掌握的内内容：1. 树和二二叉树的的定义，对对于一棵棵具体树树和二叉叉树的二二元组表表示及广广义表表表示。2. 树和二二叉树的的概念。3. 树和二二叉树的的性质。4. 二叉树树中结点点的编号号规则和和对应的的顺序存存储结构构。5. 二叉树树的链接接存储结结构及存存储结点点的类型型定义，即即BTrreeNNodee类型的的定义和和每个域域的定义义及作用用。6. 二叉树树的先序序、中序序、后序序遍历的的递归过过程和递递归算法法，中序序遍历的的非递归归算法，按按层遍历历的过程程和算法法。7. 在链接接存储的的二叉树树上实现现指定功功能的算算法分析析和设计计。一般掌掌握的内内容1. 普通树树的链接接存储结结构，GGTreeeNoode类类型的定定义和每每个域的的定义及及作用。2普普通树的的先根、后后根和按按层遍历历的过程程及算法法。第六章章 二叉叉树的应应用重点掌掌握的内内容：1. 二叉搜搜索树的的定义和和性质。2. 二叉搜搜索树查查找的递递归算法法和非递递归算法法，相应应的时间间复杂度度，查找找一个元元素的查查找长度度，即从从树根结结点到该该结点的的路径上上的结点点数。3. 二叉搜搜索树插插入的递递归算法法和非递递归算法法，相应应的时间间复杂度度。4根根据一组组数据采采用顺序序插入生生成一棵棵二叉搜搜索树的的过程。 5. 堆的定定义和顺顺序存储储结构，小小根堆和和大根堆堆的异同同。6. 向堆中中插入元元素的过过程、算算法描述述及时间间复杂度度。7. 从堆中中删除元元素的过过程、算算法描述述及时间间复杂度度。一般掌掌握的内内容：哈夫曼曼树的定定义，树树的带权权路径长长度的计计算，根根据若干干个叶子子结点的的权构造造哈夫曼曼树的过过程。对本章章的其余余内容均均作一般般了解。第七章章 图重点掌掌握的内内容：1. 图的定定义，它它的顶点点集和边边集表示示。2. 图的基基本概念念。3. 图的邻邻接矩阵阵、邻接接表和边边集数组组三种存存储结构构及相应应的空间间复杂度度。4. 存储图图使用的的vexxlisst, adjjmattrixx, aadjllistt, eedgeenodde, edggeseet, edgge等类类型的定定义及用用途。5. 图的深深度优先先和广度度优先搜搜索遍历历的过程程。6. 对分别别用邻接接矩阵和和用邻接接表表示示的图进进行深度度优先搜搜索遍历历的过程程、算法法描述以以及相应应的时间间复杂度度。7. 对分别别用邻接接矩阵和和用邻接接表表示示的图进进行广度度优先搜搜索遍历历的过程程、算法法描述以以及相应应的时间间复杂度度。8. 图的生生成树、生生成树的的权、最最小生成成树等的的定义。9. 根据普普里姆算算法求图图的最小小生成树树的过程程。10根据克克鲁斯卡卡尔算法法求图的的最小生生成树的的过程。11. 图的的拓扑序序列和拓拓扑排序序的概念念，求图图的拓扑扑序列的的方法，对对用邻接接表表示示的图进进行拓扑扑排序的的过程。对本章章的其余余内容均均作一般般掌握。第八章章 查找找重点掌掌握的内内容：1. 在顺序序表上进进行顺序序查找的的过程、算算法、平平均查找找长度和和时间复复杂度。2. 在顺序序存储的的有序表表上进行行二分查查找的过过程、递递归和非非递归算算法、平平均查找找长度和和时间复复杂度，二二分查找找一个给给定值元元素的查查找长度度（即查查找路径径上的元元素数），二二分查找找对应的的判定树树的性质质。3. 索引存存储的概概念，索索引表的的存储结结构和索索引项的的存储结结构，索索引查找找一个元元素的过过程、平平均查找找长度和和时间复复杂度。4. 散列存存储的概概念，散散列函数数、散列列表、冲冲突、同同义词、装装填因子子等术语语的含义义。5. 利用除除留余数数法建立立散列函函数求元元素散列列地址的的方法。6. 利用开开放定址址法中的的线性探探查法处处理冲突突进行散散列存储储和查找找的过程程，利用用链接法法处理冲冲突进行行散列存存储和查查找的过过程。7. 根据除除留余数数法构造造散列函函数，采采用线性性探查法法或链接接法处理理冲突，把把一组数数据散列列存储到到散列表表中，计计算出一一个给定定值元素素的查找找长度和和查找所所有元素素的平均均查找长长度。8. B_树树中每个个结点的的结构，树树根结点点或非树树根结点点中关键键字的个个数范围围和子树树的个数数范围，BB_的结结构特性性，从BB_树上上查找一一个给定定值元素素的过程程。一般掌掌握的内内容：1. 索引查查找和分分块查找找算法。2. B_树树查找算算法。3. 向B_树中插插入元素素的过程程。对本章章的其余余内容均均作一般般了解。第九章章 排序序重点掌掌握的内内容：1. 在堆排排序中建建立初始始堆的过过程和利利用堆排排序的过过程，对对一个分分支结点点进行筛筛运算的的过程、算算法及时时间复杂杂度，整整个堆排排序的算算法描述述及时间间复杂度度。2. 快速排排序的方方法，对对一组数数据的排排序过程程，对应应的二叉叉搜索树树，快速速排序过过程中划划分的层层数和递递归排序序区间的的个数。3. 快速排排序的递递归算法法，它在在平均情情况下的的时间和和空间复复杂度，在在最坏情情况下的的时间和和空间复复杂度。4. 二路归归并排序序的方法法和对数数据的排排序过程程，每趟趟排序前前、后的的有序表表长度，二二路归并并排序的的趟数、时时间复杂杂度和空空间复杂杂度。一般掌掌握的内内容：1. 直接插插入、直直接选择择和冒泡泡排序的的方法，排排序过程程及时间间复杂度度。2. 每一种种排序方方法的稳稳定性。3. 直接插插入排序序和直接接选择排排序的算算法。一般了了解的内内容：1. 二路归归并排序序过程中中涉及的的每个算算法。2. 冒泡排排序算法法。第三部分 模拟考考核试题题及解答答一、单单选题（每每小题22分，共共8分）1. 在一个个单链表表HL中中，若要要向表头头插入一一个由指指针p指指向的结结点，则则执行_。AA HLL=p; p->neext=HL; B p->>nexxt=HHL; HL=p;CC p->neext=HL; p=HL; D p->>nexxt=HHL->>nexxt; HL->neext=p; 2. 在一个个顺序队队列中，队队首指针针指向队队首元素素的_位置。AA 前一一个 BB 后一一个 CC 当前前 3. 从二叉叉搜索树树中查找找一个元元素时，其其时间复复杂度大大致为_。AA O(n) B OO(1) C O(llog22n) D OO(n22)4. 由权值值分别为为3,88,6,2,55的叶子子结点生生成一棵棵哈夫曼曼树，它它的带权权路径长长度为_。A 224 BB 488 C 72 D 553二、填填空题（每每空1分分，共332分）1. 一个算算法的时时间复杂杂度为(3n2+2nlogg2n+4n-7)/(55n)，其其数量级级表示为为_。2. 在以HHL为表表头指针针的带表表头附加加结点的的单链表表和循环环单链表表中，链链表为空空的条件件分别为为_和和_。3一一个广义义表中的的元素分分为_元素和和_元元素两类类。4从从一个链链栈中删删除一个个结点时时，需要要把栈顶顶结点的的_域的值值赋给_。5在在进行函函数调用用时，需需要把每每个实参参的值和和调用后后的_传送给给被调用用的函数数中。6对对于一棵棵具有nn个结点点的二叉叉树，若若一个结结点的编编号为ii(1in)，则则它的左左孩子结结点的编编号为_，右右孩子结结点的编编号为_，双双亲结点点的编号号为_。7在在一棵高高度为55的理想想平衡树树中，最最少含有有_个个结点，最最多含有有_个个结点。8在在一个堆堆的顺序序存储中中，若一一个元素素的下标标为i(0in-11)，则则它的左左孩子元元素的下下标为_，右右孩子元元素的下下标为_。9在在一个具具有n个个顶点的的无向完完全图中中，包含含有_条边，在在一个具具有n个个顶点的的有向完完全图中中，包含含有_条边。10对于一一个具有有n个顶顶点和ee条边的的有向图图和无向向图，若若采用边边集数组组表示，则则存于数数组中的的边数分分别为_和_条。11以二二分查找找方法从从长度为为20的的有序表表中查找找一个元元素时，平平均查找找长度为为_。12假定一一个线性性表为(12,23,74,55,63,40,82,36)，若按按Keyy % 3条件件进行划划分，使使得同一一余数的的元素成成为一个个子表，则则得到的的三个子子表分别别为_、_和_。13在线性性表的散散列存储储中，装装填因子子a又称称为装填填系数，若若用m表表示散列列表的长长度，nn表示待待散列存存储的元元素的个个数，则则a等于于_。14在一棵棵m阶BB_树上上，每个个非树根根结点的的关键字字数目最最少为_个，最最多为_个，其其子树数数目最少少为_，最多多为_。15在堆排排序的过过程中，对对任一分分支结点点进行筛筛运算的的时间复复杂度为为_，整整个堆排排序过程程的时间间复杂度度为_。16. 快速速排序在在平均情情况下的的时间复复杂度为为_，在在最坏情情况下的的时间复复杂度为为_。三、运运算题（每每小题66分，共共24分分）1. 假定一一棵二叉叉树广义义表表示示为a(b(cc),dd(e,f)，分别别写出对对它进行行先序、中中序、后后序、按按层遍历历的结果果。先先序：中中序：后后序：按按层：2已已知一个个图的顶顶点集VV和边集集G分别别为：VV=00,1,2,33,4,5,66,7;EE=(0,11)8,(0,2)55,(00,3)2,(1,55)6,(2,3)225,(2,44)133,(33,5)9,(3,66)100, (4,6)44,(55,7)20,(6,7)330;按照普普里姆算算法从顶顶点0出出发得到到最小生生成树，试试写出在在生成最最小生成成树的过过程中依依次得到到的各条条边。_, _, _, _, _, _, _。3. 已知知一个图图的顶点点集V和和边集GG分别为为：VV=00,1,2,33,4,5,66,7,8;EE=<<0,22>,<<1,33>,<<1,44>,<<2,44>,<<2,55>,<<3,66>,<<3,77>,<<4,77>,<<4,88>,<5,7>,<6,7>,<7,8>若存储储它采用用邻接表表，并且且每个顶顶点邻接接表中的的边结点点都是按按照终点点序号从从小到大大的次序序链接的的，则按按主教材材中介绍绍的进行行拓扑排排序的算算法，写写出得到到的拓扑扑序列（提提示：先先画出对对应的图图形，然然后再运运算）。拓扑序序列：4. 假定一一组记录录的排序序码为(46,79,56,38,40,80,25,34)，则对对其进行行快速排排序的第第一次划划分后的的结果为为_。四、阅阅读算法法，回答答问题（每每小题88分，共共16分分）该算法法被调用用后得到到的输出出结果为为：该算法法的功能能为：_。五、算算法填空空，在画画有横线线的地方方填写合合适的内内容(110分)。六、编编写算法法(100分)编写向向类型为为Lisst的线线性表LL中第ii个元素素位置插插入一个个元素的的算法，假假定不需需要对ii的值进进行有效效性检查查，同时时不需要要检查存存储空间间是否用用完。voiid IInseert(Lisst& L, intt i, EllemTTypee x)参考解答一、单单选题（每每小题22分，共共8分）1. B 22. AA 3. C 4. D二、填填空题（每每空1分分，共332分）1. O(nn)2. HL->neext=NUULL HL->neext=HLL3. 单 表表4. 指针 栈顶指指针5. 返回地地址6. 2i 2i+1 ii/2（或或ëi/22û）7. 16 318. 2i+1 22i+229. n(nn-1)/2 n(nn-1)10. e e11. 377/10012. （112,663,336） (555,400,822) (23,74)13. n/m14. ém/22ù-1 m-11 ém/22ù m15. O(logg2n) O(nnlogg2n)16. O(nloog2n) O(nn2)三、运运算题（每每小题66分，共共24分分）1. 先序： a,b,cc,d,e,ff中中序： c,bb,a,e,dd,f 后后序： c,bb,e,f,dd,a 按按层： a,bb,d,c,ee,f 2. (0,3)22, (0,22)5, (00,1)8, (1,5)66, (3,66)100, (6,44)4, (55,7)203. 拓扑序序列：11,3,6,00,2,5,44,7,8 4. 400 344 255 388 446 80 56 79 四、阅阅读算法法，回答答问题（每每小题88分，共共16分分）1. 15 12 8 55 1330 3302. 从初始始点vii出发广广度优先先搜索由由邻接表表GL所所表示的的图。五、算算法填空空，在画画有横线线的地方方填写合合适的内内容(110分)。BSTT->lleftt=BSST->>rigght=NULLLInssertt(BSST->>lefft, iteem)Inssertt(BSST->>rigght, ittem)六、编编写算法法(100分)