2022年南京师范大学计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年南京师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表双B.链表带头结C.点的双循环链表D.单循环链表4、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12115、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只有BⅡ．ⅠC和Ⅱ．ⅠD和Ⅲ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180．500B，450，200，180C．180，500，200，450．180D，200，500，4508、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、一个具有1025个结点的二叉树的高h为（）。A.11B.10至1025之间C.11至1024之间D.1010、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序起泡排序B.简单选择C.排序快速排序D.二、填空题11、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：12、在哈希函数H（key）=key%p中，p值最好取______。13、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。14、建立索引文件的目的是______。15、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，rflag=1，right指向其后继。16、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。17、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。三、判断题19、对磁带机而言，ISAM是一种方便的文件组织方法（）20、倒排文件是对次关键字建立索引。（）21、循环队列也存在空间溢出问题。（）22、在链队列中，即使不设置尾指针也能进行入队操作。（）23、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（）24、二叉树是一般树的特殊情形。（）25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）26、归并排序辅助存储为O（1）。（）27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、已知n阶下三角矩阵A（即当i＜j时，有a=0），按照存的思想，可以将其ij压缩储主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序主序分配方式在B中确定元素a的存放位置的公式。为时ij30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。要求：（1）给出算法的基本设计思想。（2）使用C或C++