资源描述
南京理工大学课程考试试卷学生考试用）第1页共3页课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院级学生学号：学生姓名：、选择题（分）若以，作为叶子结点的权值构造哈夫曼树，则带权路径长度是无向图（，）,其中：对该图进行广度优先遍历，得到的顶点序列正确的是对关键字码集合，从空二叉树出发建立与集合对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列。已知一组数，的排序过程为:问它是下面那一种排序：快速排序直接插入排序起泡排序选择排序.计算机算法必须具备输入、输出和等五个特征。可行性、可移植性和可扩充性可行性、确定性和有穷性确定性、有穷性和稳定性易读性、稳定性和安全性.设哈希表长为，哈希函数是表中已有数据的关键字为共四个,现要将关键字为的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是_.在一个单链表中，若要删除所指结点的后继结点，则执行。语言格式或语言格式数组的每个元素需要个字节存放，数组有行歹0若数组以行为主顺序存放在内存开始的存储区中，则中行列的元素的位置是.在一棵阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是。数已知四个元素依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的.，队列操作的原则是。先进先出后进先出只能进行插入只能进行删除，在有个结点的二叉链表中值为空链域的个数为4具有个结点的完全二叉树的深度为5若已知一个栈的入栈序列是元素123,其输出序列为P,P,P,P，若P是，则P是不确定6对于一个具有个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是对线性表进行二分查找时，要求线性表必须以顺序方式存储以顺序方式存储，且数据有序8若用起泡排序对序列，以链接方式存储以链接方式存储，且数据有序,从小到大排序，需要次比较有一个有序表为，39,的数据时要次比较成功。当二分查找值则应执行下列操作PPPPPPPPPPPPPPPPPPPP、填空题（分，其余每空分）0设双向循环链表中结点的结构为（,卩），若在指针P所指结点之后插入结点PPPP已知是无表头结点的单链表，且P结点既不是首元结点，亦不是尾元结点，试从下列提供答案中选择合适的语句序列给出序号：在P结点后插入结点的语句序列是；在P结点前插入结点的语句序列是:在表首插入结点的语句序列是在表尾插入结点的语句序列是PPPPPPPPPPPP图的遍历分为和。假设一棵二叉树的中序序列为和后序序列为，则先序序列为:.深度为的完全二叉树至少有个结点；至多有结点。.在一棵二叉树中，度为的结点有个，总的结点数为9则二叉树中叶子结点数共有6在一棵阶树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有个关键字；右边结点的关键字数是。求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。8一个深度为的，具有最少结点数的完全二叉树按层次，同层次从左向右用自然数依此对结点编号，则编号最小的叶子的序号是）编号是的结点所在的层次号是（根所在的层次号规定为层）。三、简答题（分）g12g158g、gg13ggggggggg6g25gg5ggg5g20gg2g7g丿（分）画出该有向图。分按算法给出从顶点顶点标号从计到其余顶点的最短路径长度以及经过的中间点。）（分）画出该图邻接表存储结构示意图。）（分）画出对应无向图的最小生成树，给出生成树边权之和。如果去掉方向后一对顶点之间有两条以上的边只保留权值最小的边.已知关键字的集合，（）（分）试按给出的序列构造一棵平衡二叉树。（）（分）试构造阶树。（）（分）写出依次删除关键字后的树。（）（分）按以上数据用链地址法处理冲突函数（）3画出示意图不要写算法（分）已知三棵树的森林如下，试把它转化为二叉树4（分）按大顶堆将序列，调整为堆，写出最后的数据序列，（分）给出拓扑排序算法描述（不用写算法）四、算法设计（用类类描述）（分）1分完成一个二叉树左右子树交换的递归算法。，分设在一个带头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法,删除表中所有大于，小于的元素（若存在）。双链表的定义如下：南京理工大学课程考试试卷学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院级学生学号：学生姓名：第5页共3页一、单项选择题分=1对于序列(，),用筛选法建堆，必须从值为的数据开始建初始堆。A) )B)C)D、若一棵二叉树具有个度为的结点，则该二叉树的度为的结点个数是A)B)C)D不确定3对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为A)DBFEACB)DFEBCAC)BDFECAD)BDEFAC4阶B树中，每个结点最多有个关键字。A)BCD、设有一个二维数组a,假设a存放位置在，a存放位置在，每个元素占一个空间，则a在位置数组元素以行为主存储A)B)C)D)6一棵完全二叉树按顺序方式存储在一维数组chars=A,B,C,D,E,F,G,H,I,J中，则结点E在二叉树的第层。注：根所在的层为层A)BCD、下面说法不正确的是A) 循环链表从任何一个结点出发，都能访问到所有结点B) 般树和二叉树的结点的孩子数都可以为C) 在拓扑排序序列中，若在之前，则必定存在从到的路径D) 图(网)的最小代价生成树不是唯一的、下面说法不正确的说法有个)队列逻辑上是一个表头和表尾都能插入又能删除的线性表有个顶点的无向图G的最小生成树就是由G中具有最小权值条边所构造出来的G的子图。)在万个随机排列的数据中，要选出个最小的数，采用快速排序比采用h排序、堆排序及直接排序法都快。哈希表查找无需进行关键字的比较。ABCD9一个堆通常采用存储结构来存储A)顺序B)链接C)索引D)哈希(散列)10、长度为n的线性表中，都有一个直接前驱元素。A)任意元素B)除第n/2个元素C)除第一个元素D)除最后一个元素11、在由head所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q=p-next;deleteq;A.)p-next=qB)q-next=pC)q-next=p-nextD)p-next=q-next12、稀疏矩阵采用三元组方法进行压缩存储的原因是A)0元素分布有规律B)非0元素分布有规律C)0元素多D)非0元素多13、已知一个有向图的弧集合为va,b,va,c,va,d,vb,d,vb,e,vd,e,则由该图产生的一种可能的拓扑序列为A)a,c,)B,c,)a，c,)D,c,，对于一个数据序列，按照给定的次序建立一个二叉排序树，该二叉排序树的形状取决于A)该序列的存储结构B)序列中的数据元素的取值范围C)数据元素的输入次序D)使用的计算机的软、硬件条件、一组数据为(25,48,16,35,79,8223,40,36,72),现在用某种排序算法进行一趟后的结果如下：16482535798223403672,则采用的是排序A)选择B)快速C)h希尔D直接插入16、链表不具有的特点是.A)可随机访问任一元素B)插入删除不需要移动元素C)不必事先估计存储空间D)所需空间与线性表长度成正比17、在有n个叶子的哈夫曼树中，其结点总数为。A）不确定B）2nC）2n+1D）2n-118、任何一个无向带权连通图的最小生成树。A只有一棵B）有一棵或多棵C）一定有多棵D）可能不存在19、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为。A）98B）99C）50D）4820、下面说法正确的是）二叉树的前序遍历序列中，任意一个结点均处于其子孙结点的前面一棵树的先序遍历序列同它对应的转换后的二叉树的中序遍历序列相同二叉线索树中每个结点都有指向前驱和后继的指针）一）和二、填空题（分）i已知一有个链表表示的栈，栈顶指针为退栈后，对的操作是（用语句描述，每个结点的两个域为值域和指针域）2若由368,构成一棵哈夫曼树，则该树的高度是,带权路径长度为；、求从指定源点到其余各顶点的最短路径长度的算法中，弧上权须为正的原因是（）；4图的遍历是一种递归的算法，图的遍历算法需要使用队列。5写出两个排序算法的名字其平均排序时间为06有个结点的二叉树至少高个结点；最大高度可达97在一棵二叉树中，度为的结点有个，总的结点数为，则二叉树中叶子结点数共有_在一棵阶树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有个关键字；右边结点的关键字数是0快速排序在情况下效率最坏；此时，时间复杂度达到（4.一个深度为的，具有最少结点数的完全二叉树按层次，同层次从左向右用自然数依此对结点编号，则编号最小的叶子的序号是（编号是的结点所在的层次号是（根所在的层次号规定为层）。三、简答题（分）.已知有向图有个顶点（顶点号从计），弧集如下：其中弧后面冒号后数表示弧上的权:,完成问题）至）（分）画出该有向图。分按算法给出从顶点顶点标号从计到其余顶点的最短路径长度以及经过的中间点。）（分）画出该图邻接表存储结构示意图。）（分）上图去除弧上方向（去方向后，若两个顶点有两条边，去权值大的边），画出对应无向图的最小生成树，给出生成树边权之和。.已知关键字的集合，（）（分）试按给出的序列构造一棵平衡二叉树。（）（分）试构造阶树。（）（分）写出依次删除关键字后的树。（）（分）按以上数据用链地址法处理冲突函数（）3画出示意图不要写算法第7页共3页.（分）已知三棵树的森林如下，试把它转化为二叉树（分）按大顶堆将序列，数据序列，（分）给出求最小生成树的算法描述（不用写四、算法设计（用类类描述）（分）i分完成一个求二叉树叶子的递归算法。，分有个顶点的有向图用邻接表表示写算法算法）调整为堆，写出最后的放在数组中WW。（表示顶点为二叉树根）求出所有顶点的出度结果的出度图的顶点号从计）第8页共3页南京理工大学课程考试试卷学生考试用）第9页共3页课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：年月曰组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院级、选择题（分）不是算法的基本特征可行性长度有限在有限时间内完成某算法的时间复杂度为表明该算法的问题规模是执行时间等于设个元素进栈序列是可能是一定是链表不具备的特点是可随机访问任一结点不必事先估计存储空间.最不合适用作链队的链表是）只带队首指针的非循环单链表）只带队尾指针的循环双链表.设二维数组的存储地址为执行时间与p其输出序列是不可能是一定是确定性成正比问题规模与成正比若贝,的值为_插入、删除不需要移动元素所需空间与其长度成正比只带队首指针的循环双链表只带队尾指针的循环单链表,每个数组元素占用个字节，若按行优先顺序存放时，数组元素0则的存储地址是.以下不是堆的序列是一棵完全二叉树上有个结点，其中叶子结点的个数是.无向图的邻接矩阵是一个矩阵。对称零上三角对角0对于含有个结点的带权连通图，它的最小生成树是指图中任意一个有条权值最小的边构成的子图有条权值之和最小的边构成的子图有条权值最小的边构成的连通子图有个顶点构成的边的权值之和最小的连通子图.有个结点的线索二叉树上含有的线索数为2若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图是个有根有向图是个强连通图3关键路径是指含有多个入度为的顶点）含有顶点数目大于的强连通分量网络中从源点到汇点的最长路径最长的回路4对有个元素的有序表至从源点到汇点的最短路径最短的回路1则二分查找的比较序列的下标为.5有个相同的数据，若用线性探测法把这个数据存入哈希表，至少要进行次探查6在一棵二叉排序树上查找值为的数据，以下比较的数据序列正确的为）、）、）、）、7快速排序在情况下最不利于发挥其长处要排序的数据量太大要排序的数据中含有多个相同的值要排序的数据已基本有序要排序的数据个数是奇数稀疏矩阵采用压缩存储的目的主要是为了。表达变得简单对矩阵元素的存取变得简单去掉矩阵中的多余元素减少不必要的存储空间的开销.哈希函数构造的原则是：它的函数值概率的取其值域的每一个值。最大最小同等平均树的遍历策略可分为先序遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有三种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论：“树的序遍历序列与其对应的二叉树的序遍历序列相同”是正确的先先后（中）后先中先后、填空题（分其余每空分）下面是对无向图的一种操作，其中是无向图的邻接矩阵，是图的顶点数，顶点标号为到，是一个全程变量的一维数组，初值为全，下面的类算法对图做什么操作（）Q是图的顶点号，值范围为至【J之间的整数是一个函数，完成对给定图顶点的访问求最短路径的算法若用邻接矩阵表示图，在有个顶点时如果时间是则在个顶点时，时间大约是（）。已知一棵完全二叉树吉点，则该二叉树的高度是（），叶子数是（），度为的结点数是（）,最后一个非叶结点的序号是（）（注：二叉树结点按自然数顺序从开始从上到下，同一层从左到右编号）原始数据为（、，）按快速排序算法一趟划分后，数据的排列是（）Q求最小生成树有（）和（）两个算法。.在一棵阶树中，高度是（叶子层不算），则这棵树至少有个结点三、简答题（分）（分）按、的次序，画出建立平衡二叉树的过程并注明平衡类型（分）画出建立阶树（又称树）的过程（分）.（分）有一个网如下:画出该网的邻接表示意图（分）求出所有事件的最早发生时间与最迟发生时间（分）列出所有关键活动（分）把上图看成无向图（忽略弧的方向），求出一棵最小生成树，生成树边权之和为多少？（生成树不需要画出，分）（分）有数据3、，试建立一棵树并计算。（分）（分）简述分块查找的数据组织方式，查找过程。（分）四、算法设计（用类类描述）（分）1 分完成一个二叉树拷贝的递归算法。其中是源二叉树，是目的二叉树。2 分设在个数据存在一维数组中，试写一个算法将数据按原始顺序构造一个带有头结点的双向循环链表。函数名为，其中为存有个数据的一维数组，为链表头指针。双向链表的三个域为：数据域前向指针后向指针，数组下标从计。第11页共3页南京理工大学课程考试试卷学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：年月曰组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院级三、选择题（分）对于链队，在进行删除操作时，仅修改头指针仅修改尾指针头、尾指针都修改头、尾指针都可能修改二维数组中，每个元素的长度为个字节，行下标从到9列下标从到1则连续存放该数组至少需要字节）一棵有个叶子的完全二叉树，最多有个结点利用这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权利路径长度为.一个堆是一棵二叉树）普通排序）满）完全.在一个有向图的邻接表中，每个顶点链表中结点的个数等于该定点的入度出度度度数减.下面程序段的时间复杂度是。一棵深度为的完全二叉树上所含结点的个数不小于.在一个带头结点的循环双向链表中，若要在所指向的结点之前插入一个新结点，则需要相继修改个指针域0下面叙述中不正确的是。任何关键活动不按期完成就会影响整个工程完成时间任何一个关键活动提前完成，将使整个工程提前完成所有关键活动提前完成，将使整个工程提前完成所有关键活动按期完成，整个工程也按期完成.用二分查找表中查找一个数据的速度比用顺序查找必然块必然慢相等不能确定.对图进行广度优先遍历时，通常采用来实现算法栈队树）图3具有个结点的二叉树的最小深（高）是.对有序表中，用二分查找数据需要比较次5在一个二叉树的中序遍历中，根结点的右边只有结点A）右子树上的所有B）右子树上的部分C）左子树上的所有D）左子树上的部分.在一棵平衡二叉树中每个结点的平衡因子数的取值范围是）至I）至I）至I）至I7将两个各有个元素的有序表归并为一个有序表，至少比较次数是。第12页共3页就排序算法所用的辅助空间多少而言，下面正确的是堆排序快速排序希尔（）排序堆排序希尔（）排序快速排序.哈希表范围是到哈希函数在表中，位置分别在堆排序希尔（）排序快速排序堆排序快速排序希尔（）排序。已有个数据581如果用二次探测再散列，数据的位置是0树的遍历策略可分为先序遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有三种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论：“树的序遍历序列与其对应的二叉树的序遍历序列相同”是正确的后（中）先后（中）中先中先后、填空题（分每空分）下面是对无向图的一种操作，其中是无向图的邻接表，是图的顶点数，顶点标号为到，是一个全程变量的一维数组，初值为全0下面的类算法，对图做什么操作（）堆是图的顶点号，值范围为至I之间的整数是一个函数，完成对给定图顶点的访问.假定对数据序列（）进行快速排序，则进行第一次划分后在的左边数据依次是,的右边数据依次是3.从邻接矩阵010101可以看出，该图有（）个顶点。如果是有向图,该图有010条弧，若是无向图，该图有（）条边。.有向图如图所示：写岀一个拓扑序列（）,添加孤（）后,则仅可能有唯一的拓扑序列。.由一棵二叉树的先序序列和（）可唯一的确定这棵二叉树。.已知完全二叉树的第层有个结点（根为第层），则叶子数为O算法可以求从指定源点到其它各顶点的（）路径，路径长度按（）序产生，若采用邻接矩阵存储有向图，对于有个顶点的图而言，算法的时间复杂度是（）。简答题（分）言,简单叙述哈希查找的思想，链地址法是如何解决冲突的？（分）图引入平衡二叉树的目的是什么？在图中的平衡二叉树中加入后需要做什么类型的平衡，画出平衡后的二叉树。（分）第13页共3页（）求出所有事件的最早发生时间与最迟发生时间（分）（）列出所有关键活动（分）（）画出该网的逆邻接表（分）四、算法设计（用类类描述）（分）1 分完成一个在根为的二叉排序树中插入数据的算法。二叉排序树结点的三个域为：左、右孩子与，数据域2 分有个结点的有向图（图的顶点号为至）用邻接表表示，试完成从图中删去弧的算法。注：（）为简便，假定弧是存在的（）为邻接表表头数组，数组下标从计（）结点的数据域名称可自己命名第14页共3页南京理工大学课程考试试卷学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院级四、选择题（分）、以下不属于算法特性的是可行性有输入确定性健壮性、下面关于算法的说法正确的是算法最终必须由计算机程序实现算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束算法的可行性是指指令不能有二义性以上几个都是错误的、线性表采用链表存储时，其地址必须是连续的一定是不连续的部分地址必须是连续的连续与否均可以、一个栈的进栈序列是则栈的不可能输出序列是、对于链队，在进行删除操作时，。）仅修改头指针仅修改尾指针）头、尾指针都要修改头、尾指针可能都要修改、设二维数组，每个数组元素占用个字节，第一个数组元素的存储地址是求按行优先顺序存放的数组元素WWW0的存储地址为、如果二叉树是由树转换而来的二叉树，那么中结点的先序就是中结点的先序中序后序无对应关系、一个具有个结点的二叉树的高为10至I、一棵二叉树的后序遍历序列为I中序遍历序列为G则该二叉树根结点的右孩子为有、个结点的线索二叉树上含有的线索数为。、堆是完全二叉树线性表二叉排序树平衡二叉树、假定在一棵二叉树中，度为的结点数为，度为的结点数为，则叶子结点数为。）3由带权为9、5的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为4下面的叙述中，不正确的是关键活动不按期完成就会影响整个工程完成时间任何一个关键活动提前完成，将使整个工程提前完成所有关键活动提前完成，则整个工程提前完成某些关键活动若提前完成，将可能使整个工程提前完成、设哈希表长为，哈希函数为=表中现有数据、和，其余位置为空，如果用二次探测再散列处理冲突，则的位置是6在一棵二叉排序树上查找值为的数据，以下比较的数据序列正确的为）、）、）、）、7下面排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多堆排序冒泡排序快速排序希尔（）排序、任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序。不发生改变发生改变不能确定以上都不对9如果从无向图的任一顶点出发进行一次图遍历即可访问所有顶点，则该图一定是。完全图连通图有回路一棵树0对有个元素的有序表进行二分查找，则查找的比较序列下标为、五、填空题（分每空分）下面程序段的时间复杂度为（）。2、已知完全二叉树T的第5层只有7个结点，则该树共有（2）个叶子结点3、始数据为（、，）按快速排序算法一趟划分后，数据的排列是D。4个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）非零元素。5评价哈希函数好坏的标准是（）。、对于关键字序列：用筛选法建堆，必须从值为（）的关键字开始。7最短路径算法按（）依次产生路径，在边（弧）上权有（）值时不能正确工作。三、简答题（分）,（分）有试用W把它们从左向右连接起来。2（分）已知3阶B_树如图所示。（1）画出将关键字88插入之后的B-树；（2）画出将关键字47和66依次插入之后的B-树。、（分）简述哈希查找中链地址法解决冲突的方法。、（分）有一个网如下:求出所有事件的最早发生时间与最迟发生时间（分）列出所有关键活动（分）四、算法设计（用类类描述）（分）1 分写一个递归的二分查找算法d其中：为一维数组，为待查数据，、为查找的范围（给出的是下标范围，下标从计算）2 分在邻接表表示的无向图中加入一条边（），完成算法：其中：为邻接表表头数组，、是顶点号，为方便，、假定是合法的，且邻接表中没有边（顶点号从计，数组下标从计，图的顶点数为）第18页共3页南京理工大学课程考试试卷学生考试用）07年六、选择题（分）、一个算法必须保证执行有限步之后结束，这是算法的性有穷确定可行输出、算法的时间复杂度为（3算法的时间复杂度为（）则说明对于任何数据量，算法的时间开销都比算法小随着问题规模的增大，A算法比B算法有效随着问题规模的增大，B算法比A算法有效对于任何数据量，B算法的时间开销都比算法小、对线性表，在情况下应当采用链表表示经常需要随机地存取元素经常需要进行插入和删除运算表中元素需要占据一片连续的存储空间表中元素的个数不变、对线性表进行二分查找，其前提条件是顺序表有序的顺序表链表有序的链表、对于链队，在进行删除操作时，。）仅修改头指针仅修改尾指针）头、尾指针都要修改头、尾指针可能都要修改、设二维数组，每个数组元素占用个字节，第一个数组元素的存储地址是求按行优先顺序存放的数组元素WWWW的存储地址为、如果二叉树是由树转换而来的二叉树，那么中结点的先序就是中结点的先序中序后序无对应关系、一个具有个结点的二叉树的高为10至I、一棵二叉树的后序遍历序列为I中序遍历序列为G则该二叉树根结点的右孩子为输0个结点的线索二叉树上含有的线索数为。0堆是完全二叉树线性表二叉排序树平衡二叉树、假定在一棵二叉树中，度为的结点数为，度为的结点数为，则叶子结点数为。）、由带权为9、5的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为4下面的叙述中，不正确的是关键活动不按期完成就会影响整个工程完成时间任何一个关键活动提前完成，将使整个工程提前完成所有关键活动提前完成，则整个工程提前完成某些关键活动若提前完成，将可能使整个工程提前完成、设哈希表长为，哈希函数为=表中现有数据、和，其余位置为空，如果用二次探测再散列处理冲突，则的位置是、在一棵二叉排序树上查找值为的数据，以下比较的数据序列正确的为.）、）、）、）、7下面排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多堆排序冒泡排序快速排序希尔（）排序8任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序。不发生改变发生改变不能确定以上都不对、如果从无向图的任一顶点出发进行一次图遍历即可访问所有顶点，则该图一定是。完全图连通图有回路一棵树0对有个元素的有序表进行二分查找，则查找的比较序列下标为七、填空题（分每空分）下面程序段的时间复杂度为（）4、已知完全二叉树T的第5层只有7个结点，则该树共有（2）个叶子结点5、始数据为（、，6按快速排序算法一趟划分后，数据的排列是D。4个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）非零元素。5评价哈希函数好坏的标准是（）。6对于关键字序列：用筛选法建堆，必须从值为（）的关键字开始。，最短路径算法按（）依次产生路径，在边（弧）上权有（）_值时不能正确工作。三、简答题（分）1 （分）有试用W把它们从左向右连接起来。2 （分）已知3阶B_树如图所示。（1）画出将关键字88插入之后的B-树；（2）画出将关键字47和66依次插入之后的B-树。、（分）简述哈希查找中链地址法解决冲突的方法。、（分）有一个网如下:求出所有事件的最早发生时间与最迟发生时间（分）列出所有关键活动（分）四、算法设计（用类类描述）（分）1分写一个递归的二分查找算法d其中：为一维数组，为待查数据，、为查找的范围（给出的是下标范围，下标从计算）分在邻接表表示的无向图中加入一条边（）,完成算法：其中：为邻接表表头数组，、是顶点号，为方便，、假定是合法的，且邻接表中没有边（顶点号从计，数组下标从计，图的顶点数为）。南京理工大学课程考试-答-案-及评分标准课程名称：数据结构A学分：3大纲编号试卷编号：考试方式：笔试满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅注意：请将答案按题号和序号写在答题纸上八、选择题（分）、填空题（分每空分其余每空分）答案不唯一也可以注意广度优先遍历或深度优先遍历深度优先遍历或广度优先遍历答案可以有几种写法克鲁斯卡尔向上取整三、简答题1.1）（3分）2）（3分）用Dijkstra算法求从顶点1开始的到其余顶点的最短路径（给出路径长度和中间点）1-5:81-2:121-（5）-4:131-（5-,4）6:181-（5,4,6）-3:203）（3分）画出邻接表第22页共3页A41558A653212466552815568225080406490104）（3分）权之和302(1)(3分)123A456212313A164532325620A57A第23页共3页第24页共3页A802A56AAGBCDHNOEIFKPRLSMT4）（3分）3、（3分）AAAAA、A40A1585622A10A50A90A60第25页共3页4、(4分)9080286040221550568105、拓扑排序算法(4分)设置一个栈(设图的顶点数为n)(1) 把邻接表中入度为0的顶点依此进栈(2) 若栈不空，则a) 栈顶元素v.退栈并输出；b) 在邻接表中查找v.的直接后继vk，把vk的入度减1；若vk的入度为0则进栈若栈空时输出的顶点个数不是n,则有向图有环；否则，拓扑排序完毕。四、算法设计1) (分)VOidBitree_Revolute(BitreeT)if(T)T-lchildv-T-rchild;Bitree_Revolute(BitreeT-lchild);Bitree_Revolute(BitreeT-rchild);/Revolute(BitreeT)2) (8分)Statusdelnode(DuLinklist&la,intmink,intmaxk)有头结点if(la-next=NULL)returnERROR;if(minkmaxk)returnERROR;q=la;p=la-next;while(p&p-datanext;while(p&p-datanext;free(s);q_next=p;p_pre=q;returnok;/delnode第26页共3页南京理工大学课程考试-答-案-及评分标准课程名称：数据结构b学分：3大纲编号试卷编号：考试方式：笔试满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅注意：请将答案按题号和序号写在答题纸上九、选择题（分）二、填空题（分每空分）1p为负则不能满足按路径递增产生路径4深度优先（）广度优先快速排序堆排序归并排序数据已有序O1三、简答题（39分）1.1）（3分）2）（3分）用Dijkstra算法求从顶点1开始的到其余顶点的最短路径（给出路径长度和中间点）1-5:81-2:121-（5）-4:131-（5-,4）6:181-（5,4,6）-3:203）（3分）画出邻接表第27页共3页A41558A653212466552815568225080406490104）（3分）权之和302(1)(4分)123A456212313A164532325620A57A第28页共3页281520609028152040609028501540602081050805680810810（4分）(3)(4分)删除56删除90第29页共3页A802A56AAGBCDHNOEIFKPRLSMT(4)(4分)3、（4分）AAAAA、A40A1585622A10A50A90A60第30页共3页4、（4分）9080286040221550568105、拓扑排序算法（4分）设置一个边集合E,开始为空。重复以下工作n-1次（n为图顶点数）（1）在图G中选最小的边删除（2）该边加到集合E中，若加入后在E中形成回路，则丢弃四、算法设计（14分）1）（分）if（P）m=treeleaf（p-lchild）;n=treeleaf（p-rchild）;if（m+n=0）return1;elsereturnm+n;elsereturn0;2）（7分）for（i=0;ivn;i+）outdegreei=0;p=adji.firstarc;while（p）outdegreei+;p=p-next;/whlie/for/finddegree第31页共3页南京理工大学课程考试-答-案-及评分标准课程名称：数据结构A学分：3大纲编号试卷编号：考试方式：笔试满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅十、选择题（分此部分大为基础试题，需要综合分析）二、填空题（分，023为综合题目）（）深度优先搜索（只答遍历扣分）6（理解为数据个数，答案为的给分）四、简答题2(1)(3分)第33页共3页（4分）vevl0001362443515477591961521711118212192222102828（3分）关键活动：气叫卫8，气2已3卫4第34页共3页21790127537437371324要点：数据划分法，索引3（2+2分）WPL=455（计算错扣1分）4（3分）分块查找时，数据分成若干块，每块中数据是无序的，但块与块之间是有序的，将每块中最大（或最小）的关键字组成索引表。查找时先查索引表确定要查找数据所在的块，然后在块内顺序查找，直到找到或块中数据查完后没有。（查找不成功）。四、（7+7分）（因为程序编制方法较多，答案供参考，题目有一定综合性）（1）voidtreecopy（d,s）if（s!=NULL）d=newTreeNode;d-date=s-date;treecopy（d-lchild,s-lchild）;treecopy（d-rchild,s-rchild）;elsed=NULL;（没有空间分配扣一分，无递归扣2分）（没有循环扣一分）南京理工大学课程考试-答-案-及评分标准课程名称：数据结构B学分：3大纲编号试卷编号：考试方式：笔试满分分值：100考试时间：120分钟组卷日期：年月日组卷教师（签字）张宏审定人（签字）王树梅卜一、选择题（分、基本题）二、填空题（分）1（）深度优先搜索（只答遍历扣分、综合题目，依据程序判定功能）3（）9、8（次序错误给一半分）.）4 ,2（,）（）5 中序（）最短（）递增（）（）五、简答题1、要点（1、2分）通过计算得到数据元素存储位置的信息（2、3分）具有相同HASH值的数据元素在同一个链中，并构成一个数组（此题允许学生以画图以案例的形式解答）2、（2+2+2分）避免形成向单枝二叉排序树的形式，目的是提高查找效率；需要LR平衡；3（综合题）（1）（3分）(2)(3分),v2,4,v4,6vevl100222325466557688(3)(3分)(没有写出权的扣一分，分开的扣一分)四、(7+7分)(因为程序编制方法较多，答案供参考，题目有综合性)(1)voidif(tree!=NULL)if(xvtree-data)(tree-lchild,x)else(tree-rchild,x);elsetree=newTreeNode;tree-lchild=tree-rchild=NULL;tree-data=x;(综合题，没有空间分配扣一分，无递归扣1分，左右指针没置空扣1分)(提咼题)空间没释放扣1分，没考虑第一个删除点扣1分。第37页共3页
展开阅读全文