2023年江西理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(含答案)

2023期末试卷A〔有答案〕一、选择题1、广义LS=〔〔a，b，c〕，〔d，e，f〕〕，headtailLS中原子e的运算是〔 〕。A.head〔tail〔LS〕〕B.tail 〔head〔LS〕〕〔tail〔tail〔head〔LS〕〕〕〕2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是〔 〕。A.NB.2N-1C.2ND.N-13、链表不具有的特点是〔 〕。A.插入、删除不需要移动元素B. 可随机访问任一元素C.不必事先估量存储空间D. 所需空间与线性长度成正比4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是〔 〕。A.〔rear-front+m〕%mB.rear-front+1C.rear-front-1D.rear-front5、有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V6，V7>｝，G的拓扑序列是〔 〕。A.V1，V3，V4，V6，V2，V5，V7B.V1 ，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1 ，V2，V5，V3，V4，V6，V76、以下表达中，不符合m阶B树定义要求的是〔 〕。A．根结点最多有m棵子树B ．全部叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接7、关键5，8，12，19，28，20，15，22是小根堆〔最小堆〕，插入关键字3，调整后的小根堆是〔〕。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树肯定满足〔〕。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度2的结点最多为一个9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，以下结论正确的选项是〔 〕。在树T中，X是其双亲的第一个孩子在树T中，X肯定无右兄弟在T中，X肯定是叶结点在T中，X肯定有左兄弟10、下面关于B和B+树的表达中，不正确的选项是〔 〕A.B树和B+树都是平衡的多叉树B.B 树和B+树都可用于文件的索引构造C.B树和B+树都能有效地支持挨次检索D.B 树和B+树都能有效地支持随机检索二、填空题11、属于不稳定排序的有 。12、在哈希函数H〔key〕=key%p中，p值最好取 。13、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的挨次链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使top，p，t为关心指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。棵m阶B-树中，假设在某结点中插入一个关键字而引起该结点分裂，则此结点中原有的关键字的个数是 ；假设在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是 。15、关键码序列〔Q，H，C，Y，Q，A，M，S，R，D，F，X〕，要依据关键码值递增的次序进展排序，假设承受初始步4的希尔排序法，则一趟扫描的结果是；假设承受以第一个元素为分界元素的快速排序法，则扫描一趟的结果是。16、TP是两个给定的串，在T中查找等于P的子串的过程称为P为 。义表L=〔〔〕，〔〕〕，则head〔L〕是 ；tail〔L〕是 ；L的长度是 ；深度是 。18、阅读以下程序说明和程序，填充程序中的 。说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示〔编者略〕。本程序承受非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针tp。交换左、右子树的算法为：把根结点放入堆栈。当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。重复〔2〕直到堆栈为空时为止。三、推断题键字查找。〔 〕20、倒排文件是对次关键字建立索引。〔 〕21、队列和栈都是运算受限的线性表，只允许在表的两端进展运算。〔 〕必会失去随机存取功能。〔 〕23、一棵树中的叶子数肯定等于与其对应的二叉树的叶子数。〔 〕24、二叉树是一般树的特别情形。〔 〕25、数据的规律构造是指数据的各数据项之间的规律关系。〔 〕〔 〕27、连通图上各边权值均不一样，则该图的最小生成树是唯一的。〔 〕28、平衡二叉树中，假设某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子肯定是零。〔 〕四、简答题i29、对于具有n个叶结点且全部非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?i试证明〕。

2〔li-〕=1。其中：l表示第i结层号设结层号为30、用一个数组S〔设大小为MAX〕作为两个堆栈的共享空间。请说明共享方法，栈满栈空的推断条件，并用C语言或PASCAL语言栈操作pusi，x〕，i01，用于表示栈号，x为入栈值。31、世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)画出这六大城市的交通网络图。画出该图的邻接表表示法。画出该图按权值递增的挨次来构造的最小〔代价〕生成树。五、算法设计题32、图G有n个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G的最小生成树的算法。33、设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于l～100之间，现要求按B[1..100]的内容调整A中记录的次序，比方当B[1]=11时，则要求将A[1]整到A[11规间为〔〕。34、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。35、以三元组表存储的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言写简单为〔m+〕阵B阵AA足够大，不另加关心空间。要求描述所用构造。参考答案一、选择题1、【答案】C2、【答案】A3、【答案】B4、【答案】A5、【答案】A6、【答案】D7、【答案】A8、【答案】C9、【答案】D10、【答案】C二、填空题11、【答案】希尔排序、简洁选择排序、快速排序、堆排序等12、【答案】小于等于表长20的质因子的合数13、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p14、【答案】【解析】mB-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少15、【答案】〔Q，A，C，S，Q，D，F，X，R，H，M,Y〕；〔F，H，C，D，a【解析】mB-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少16、【答案】模式匹配；模式串17、【答案】〔〕；〔〔〕〕；2；218、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】此题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，假设不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。三、推断题19、【答案】√20、【答案】√21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、简答题9〔1〕树中度为2的结结点个数减1，故具有n个叶结点且非叶子结点均有左子树的二叉树的结2n-1。2〕证明：当i=1时21-〕=20=1设当i=n-1时证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是削减了一结2〔t1=2-t+1-1〕+2-t+1-1〕变，这证明当i=n。30、答：两栈共享一向量空间〔一维数组〕，栈底设在数组的两端，两栈顶相邻时为栈