2023年长安大学信息管理与信息系统专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年长安大学信息管理与信息系统专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（　　）。 A.N B.2N-1 C.2N D.N-1 2、下述文件中适合于磁带存储的是（　　）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 3、算法的计算量的大小称为计算的（　　）。 A.效率 B.复杂性 C.现实性 D.难度 4、在下列表述中，正确的是（　　） A.含有一个或多个空格字符的串称为空格串 B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 5、已知串S=aaab，其next数组值为（　　）。 A.0123 B.1123 C.1231 D.1211 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。 8、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 9、一个具有1025个结点的二叉树的高h为（　　）。 A.11 B.10 C.11至1025之间 D.10至1024之间 10、下列二叉排序树中查找效率最高的是（　　）。 A.平衡二叉树 B.二叉查找树 C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 二、填空题 11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、无用单元是指______，例______ 13、外排序的基本操作过程是______和______。 14、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。 15、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。 16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 18、模式串P=‘abaabcac’的next函数值序列为______。 三、判断题 19、文件系统采用索引结构是为了节省存储空间。（　　） 20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（　　） 21、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：aiai+1…an。（　　） 23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　） 24、树形结构中元素之间存在一对多的关系。（　　） 25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（　　） 26、顺序存储结构的主要缺点是不利于插入或删除操作。（　　） 27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（　　） 28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（　　） 四、简答题 29、已知n阶下三角矩阵A（即当i＜j时，有aij=0），按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素aij的存放位置的公式。 30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。 31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为： 其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。要求： （1）给出算法的基本设计思想。 （2）使用C或C++语言，给出二叉树结点的数据类型定义。 （3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 五、算法设计题 32、有二叉排序树采用二叉链表方式存放，树中结点值