2022年江苏理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年江苏理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.332、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序3、链表不具有的特点是（）。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.46、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝28、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。12、无用单元是指______，例______13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）18、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、循环队列也存在空间溢出问题。（）22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）25、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（）26、归并排序辅助存储为O（1）。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）四、简答题29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’（1）计算模式p的nextval函数值。（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。30、阅读下面的算法，说明算法实现的功能。31、设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（1） 给出完整的合并过程，并求出最坏情况下比较的总次数。（2） 根据你的合并过程，描述n（n≥2）个不等长升序表的合并策略，并说明理由。五、算法设计题32、设二叉树用二指针结构存储（可以是动态存储结构），元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。33、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。34、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。35、在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。顺序存储结构的线性表描述为：

参考答案一、选择题1、【答案】B2、【答案】C3、【答案】B4、【答案】B5、【答案】C6、【答案】A7、【答案】C8、【答案】B9、【答案】C10、【答案】C二、填空题11、【答案】2(n-1)12、【答案】用户不再使用而系统没有回收的结构和变量；p=ma11oc（size）;…,p=nu1113、【答案】2；4；3【解析】二分法查找元素次数列表查找100是找到115就停止了。14、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null15、【答案】分配和释放存储空间；重组；对插入的记录@16、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。17、【答案】9318、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、简答题29、答：（1）p的nextval函数值为0110132（p的next函数值为0111232）。（2）利用KMP（改进的nextval）算法，每趟匹配过程如下：30、答：本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2，head2最后一个结点的链域指向head1，head1为结果循环链表的指针。31、答（1）6个表的合并顺序如下图所示。对应于合并过程的哈夫曼树根据上图中的哈夫曼树，6个序列的合并过程为：第1次合并：表A与表B合并，生成含45个元素的表AB。第2次合并：表AB与表C合并，生成含85个元素的表ABC。第3次合并：表D与表E合并，生成含110个元素的表DE。第4次合并：表ABC与表DE合并，生成含195个元素的表ABCDE。第5次合并：表ABCDE与表F合并，生成含395个元素的最终表。由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m＋n－1次，故最坏情况下比较的总次数计算如下：第1次合并：最多比较次数＝10＋35－1＝44。第2次合并：最多比较次数＝45＋40－1＝84。第3次合并：最多比较次数＝50＋60－1＝109。第4次合并：最多比较次数＝85＋110－1＝194。第5次合并：最多比较次数＝195＋200－1＝394；比较的总次数最多为：44＋84＋109＋1