2022年江西理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（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>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<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是其双亲的右孩子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树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 域作为后链域，指向结点的直接后继。

算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。

试填充算法中的空格，使算法完整。

14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。

15、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。

16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。

17、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。

18、阅读下列程序说明和程序，填充程序中的______。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。

交换的结果如下所示（编者略）。

本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。

交换左、右子树的算法为：（1）把根结点放入堆栈。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

（3）重复（2）直到堆栈为空时为止。

三、判断题19、倒排文件的目的是为了多关键字查找。

（）20、倒排文件是对次关键字建立索引。

（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。

（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。

（）23、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

（）24、二叉树是一般树的特殊情形。

（）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。

（）26、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。

（）28、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。

（）四、简答题29、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。

(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。

其中：l i表示第i个叶结点所在的层号（设根结点所在层号为1）。

30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。

请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。

31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)（1）画出这六大城市的交通网络图。

（2）画出该图的邻接表表示法。

（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。

五、算法设计题32、图G有n个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G的最小生成树的算法。

33、设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于l～100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=11时，则要求将A[1]的内容调整到A[11]中去。

规定可使用的附加空间为O（1）。

34、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。

35、以三元组表存储的稀疏矩阵A，B非零元个数分别为m和n。

试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。

A的空间足够大，不另加辅助空间。

要求描述所用结构。

参考答案一、选择题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、【答案】【解析】m阶B-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少15、【答案】（Q，A，C，S，Q，D，F，X，R，H，M ,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）16、【答案】模式匹配；模式串17、【答案】（）；（（））；2；218、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。

首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。

并将左右指针分别进栈，重复这一操作。

完成二叉树左右孩子的交换。

三、判断题19、【答案】√20、【答案】√21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、简答题29、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。

（2）证明：当i=1时，2-（1-1）=20=1，公式成立。

设当i=n-1时公式成立，证明当i=n时公式仍成立。

设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。

证毕。

30、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。

设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。

用C语言写的入栈操作push（i，x）如下：31、答：(1)这六大城市的交通网络图如图所示：(2)该图的邻接表表示法如图所示：(3)最小生成树有6个顶点与条边：V(G)={Pe，N，Pa，L，T，M}E(G)=｛(L，Pa，3)，(Pe，T，21)，(M，N，32)，(L，N，55)，(L， Pe，81)}五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：算法如下：。