数据结构课程考核说明

数据结构课程查核说明第一部分查核说明《数据结构》是全国电大计算机应用专业的一门核心课程，起到承前启后的作用和地位，主要任务是议论数据的各样逻辑结构、储存结构以及相应运算的算法。考查对象：全国电大系统计算机应用专业“开放教育试点”的学生。教课媒体：主教材《数据结构》许卓群主编中央广播电视大学第一版社第一版。实验教材《数据结构实验》徐孝凯编中央广播电视大学第一版社第一版。录像教材《数据结构》20讲刘杰主讲中央电大音像第一版社第一版。协助教材《数据结构习题分析》徐孝凯编中央电大教育杂志社第一版，经过各地电大教材刊行部门一致征订刊行。命题依照：本查核说明严格依照中央电大计算机应用专业《数据结构》课程教课纲领编写。查核要求：查核学生掌握和运用数据结构基本观点和知识剖析和编写数据办理算法的能力。详细查核要求分为以下3个层次：认识：认识数据结构的一些基本观点。包含线性表、栈、行列、链表、树、二叉树、二叉搜寻树、堆、哈夫曼树、图、网、二分查找、索引查找、分块查找、散列查找、堆排序、迅速排序、合并排序等观点。掌握：可以剖析现成程序和算法，即指出功能或写出运转结果；可以写出对已知数据进行相应运算的数据变化过程和最后结果。应用：可以依据解决问题的需要选择数据结构和编写算法。命题原则：严格依照该课程教课纲领和查核说明的要求命题。试题的覆盖面较广，并适合突出要点。3．试题的难易程度和题量适合，按难易程度分为三个层次：简单占40%，一般占40%，较难占20%。4．题型有六种：单项选择题、填空题、运算题、阅读算法并回答下列问题、算法填空、编写算法。查核形式：采纳期末卷面查核与形成性查核相联合的方式。形成性查核占20分，视平常上机和作业达成状况而定，由所在班级的任课教师给定，由省（市、自治区）级电大认定；期末卷面查核占80分，由中央电大一致命题并采纳闭卷方式，答题时限为120分钟。双方面成绩累计达到60分者为及格。第二部分查核内容及要求第一章绪论要点掌握的内容：数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。会合结构、线性结构、树结构和图结构的特色。抽象数据种类的定义和表示方法。一维和二维数组中元素的按下标和按地点的接见方式以及互相变换，元素地点和数组地点的计算，元素占用储存空间大小和数组占用储存空间大小的计算。一般函数重载和操作符函数重载的含义，定义格式和调用格式。函数定义中值参数和引用参数的说明格式及作用，函数被调用履行时对传递来的实质参数的影响。算法的时间复杂度和空间复杂度的观点，计算方法，数目级表示。关于本章的其他内容均作一般掌握。第二章线性表要点掌握的内容：线性表的定义和抽象数据种类的描绘，线性表中插入、删除等操作的功能，对应的函数名、返回值种类和参数表中每个参数的作用。2.线性表的次序储存结构的种类定义，即List种类的定义和每个域的定义及作用。线性表的每一种运算在次序储存结构上实现的算法，及相应的时间复杂度。4.单链表中结点的结构，每个域的定义及作用，即LNode种类的定义及结构。带表头附带结点的链表、循环链表、双向链表的结构特色。线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。在次序储存或链接储存的线性表上实现指定功能的算法的剖析和设计。关于本章的其他内容均作一般掌握。第三章稀少矩阵和广义表要点掌握的内容：稀少矩阵的定义和三元组线性表表示。稀少矩阵的次序储存、带行指针向量的链接储存，它们中非零元素结点的结构。稀少矩阵的转置运算和算法描绘。广义表的定义和表示，广义表长度和深度的计算。广义表的链接储存结构中结点种类的定义，分别求广义表长度和深度的递归算法。关于本章的其他内容均作一般认识。第四章栈和行列要点掌握的内容：栈的定义和抽象数据种类的描绘，栈中每一种操作的功能，对应的函数名、返回值种类和参数表中每个参数的作用。栈的次序储存结构的种类定义，即Stack种类的定义和每个域的定义及作用。3．栈的每一种运算在次序储存结构上实现的算法，及相应的时间复杂度。栈的每一种运算在链接储存结构上实现的算法及相应的时间复杂度。算术表达式的中缀表示和后缀表示，以及互相变换的规则。行列的定义和抽象数据种类的描绘，行列中每一种操作的功能，对应的函数名、返回值种类和参数表中每个参数的作用。行列的次序储存结构的种类定义，即Queue种类的定义和每个域的定义及作用。行列的每一种运算在次序储存结构上实现的算法及相应的时间复杂度。利用栈和行列解决简单问题的算法剖析和设计。一般掌握的内容：求解阶乘问题方法和算法。后缀表达式求值的方法和算法，把中缀表达式变换为后缀表达式的方法和算法。行列的链接储存结构，以及实现每一种行列运算的算法和相应的时间复杂度。一般认识的内容：求解迷宫问题的方法和算法。第五章树和二叉树要点掌握的内容：树和二叉树的定义，关于一棵详细树和二叉树的二元组表示及广义表表示。树和二叉树的观点。树和二叉树的性质。二叉树中结点的编号规则和对应的次序储存结构。5.二叉树的链接储存结构及储存结点的种类定义，即BTreeNode种类的定义和每个域的定义及作用。二叉树的先序、中序、后序遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法。在链接储存的二叉树上实现指定功能的算法剖析和设计。一般掌握的内容一般树的链接储存结构，GTreeNode种类的定义和每个域的定义及作用。2．一般树的先根、后根和按层遍历的过程及算法。第六章二叉树的应用要点掌握的内容：二叉搜寻树的定义和性质。二叉搜寻树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。二叉搜寻树插入的递归算法和非递归算法，相应的时间复杂度。4．依据一组数据采纳次序插入生成一棵二叉搜寻树的过程。堆的定义温次序储存结构，小根堆和大根堆的异同。向堆中插入元素的过程、算法描绘实时间复杂度。从堆中删除元素的过程、算法描绘实时间复杂度。一般掌握的内容：哈夫曼树的定义，树的带权路径长度的计算，依据若干个叶子结点的权结构哈夫曼树的过程。对本章的其他内容均作一般认识。第七章图要点掌握的内容：图的定义，它的极点集和边集表示。图的基本观点。图的毗邻矩阵、毗邻表和边集数组三种储存结构及相应的空间复杂度。储存图使用的vexlist,adjmatrix,adjlist,edgenode,edgeset,edge等种类的定义及用途。图的深度优先和广度优先搜寻遍历的过程。对分别用毗邻矩阵和用毗邻表表示的图进行深度优先搜寻遍历的过程、算法描绘以及相应的时间复杂度。对分别用毗邻矩阵和用毗邻表表示的图进行广度优先搜寻遍历的过程、算法描绘以及相应的时间复杂度。图的生成树、生成树的权、最小生成树等的定义。依据普里姆算法求图的最小生成树的过程。10．依据克鲁斯卡尔算法求图的最小生成树的过程。图的拓扑序列和拓扑排序的观点，求图的拓扑序列的方法，对用毗邻表表示的图进行拓扑排序的过程。对本章的其他内容均作一般掌握。第八章查找要点掌握的内容：在次序表长进行次序查找的过程、算法、均匀查找长度和时间复杂度。在次序储存的有序表长进行二分查找的过程、递归和非递归算法、均匀查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判断树的性质。索引储存的观点，索引表的储存结构和索引项的储存结构，索引查找一个元素的过程、均匀查找长度和时间复杂度。散列储存的观点，散列函数、散列表、矛盾、同义词、装填因子等术语的含义。利用除留余数法成立散列函数求元素散列地点的方法。利用开放定址法中的线性探查法办理矛盾进行散列储存和查找的过程，利用链接法办理矛盾进行散列储存和查找的过程。依据除留余数法结构散列函数，采纳线性探查法或链接法办理矛盾，把一组数据散列储存到散列表中，计算出一个给定值元素的查找长度和查找全部元素的均匀查找长度。8.B_树中每个结点的结构，树根结点或非树根结点中要点字的个数范围和子树的个数范围，

B_的结构特征，从

B_树上查找一个给定值元素的过程。一般掌握的内容：1.索引查找和分块查找算法。B_树查找算法。向B_树中插入元素的过程。对本章的其他内容均作一般认识。第九章排序要点掌握的内容：在堆排序中成立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法实时间复杂度，整个堆排序的算法描绘实时间复杂度。迅速排序的方法，对一组数据的排序过程，对应的二叉搜寻树，迅速排序过程中区分的层数和递归排序区间的个数。迅速排序的递归算法，它在均匀状况下的时间和空间复杂度，在最坏状况下的时间和空间复杂度。二路合并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路合并排序的趟数、时间复杂度和空间复杂度。一般掌握的内容：直接插入、直接选择和冒泡排序的方法，排序过程实时间复杂度。每一种排序方法的稳固性。直接插入排序和直接选择排序的算法。一般认识的内容：二路合并排序过程中波及的每个算法。冒泡排序算法。第三部分模拟查核试题及解答一、单项选择题（每题2分，共8分）1.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则履行________。AHL=p;p->next=HL;Bp->next=HL;HL=p;Cp->next=HL;p=HL;Dp->next=HL->next;HL->next=p;2.在一个次序行列中，队首指针指向队首元素的________地点。A前一个B后一个C目前3.从二叉搜寻树中查找一个元素时，其时间复杂度大概为________。AO(n)BO(1)CO(log2n)DO(n2)4.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。A24B48C72D53二、填空题（每空1分，共32分）1.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数目级表示为________。2.在以HL为表头指针的带表头附带结点的单链表和循环单链表中，链表为空的条件分别为________和________。3．一个广义表中的元素分为________元素和________元素两类。4．从一个链栈中删除一个结点时，需要把栈顶结点的_________域的值赋给________。5．在进行函数调用时，需要把每个实参的值和调用后的________传递给被调用的函数中。6．关于一棵拥有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。7．在一棵高度为5的理想均衡树中，最少含有________个结点，最多含有________个结点。8．在一个堆的次序储存中，若一个元素的下标为i(0≤i≤n-1)，则它的左孩子元素的下标为______，右孩子元素的下标为________。9．在一个拥有n个极点的无向完整图中，包含有________条边，在一个拥有n个极点的有向完整图中，包含有________条边。10．关于一个拥有n个极点和e条边的有向图和无向图，若采纳边集数组表示，则存于数组中的边数分别为________________条。11．以二分查找方法从长度为20的有序表中查找一个元素时，均匀查找长度为________。12．假设一个线性表为(12,23,74,55,63,40,82,36)，若按Key%3条件进行区分，使得同一余数的元素成为一个子表，则获得的三个子表分别为_____________、_____________和_____________。13．在线性表的散列储存中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待散列储存的元素的个数，则a等于________。14．在一棵m阶B_树上，每个非树根结点的要点字数目最少为________个，最多为________个，其子树数目最少为________，最多为________。15．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。迅速排序在均匀状况下的时间复杂度为________，在最坏状况下的时间复杂度为________。三、运算题（每题6分，共24分）假设一棵二叉树广义表表示为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出发获得最小生成树，试写出在生成最小生成树的过程中挨次获得的各条边。________,________,________,________,________,________,________。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>};若储存它采纳毗邻表，而且每个极点毗邻表中的边结点都是依照终点序号从小到大的序次链接的，则按主教材中介绍的进行拓扑排序的算法，写出获得的拓扑序列（提示：先画出对应的图形，而后再运算）。拓扑序列：假设一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行迅速排序的第一次区分后的结果为________________。四、阅读算法，回答下列问题（每题8分，共16分）该算法被调用后获得的输出结果为：该算法的功能为：______________________________________________________________。五、算法填空，在画有横线的地方填写适合的内容(10分)。六、编写算法(10分)编写向种类为List的