2022年中国矿业大学(北京)计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-12、已知广义表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））））3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。
A.543612B.453126C.346521D.2341565、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。
A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、已知关键字序列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，197、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。
n个结点的正则二叉树中有（）个叶子。
A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、有关二叉树下列说法正确的是（）。
A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、就平均性能而言，目前最好的内排序方法是（）排序法。
A.起泡B.希尔插入C.交换D.快速二、填空题11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。
12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。
如123存放成321。
请填空：13、外排序的基本操作过程是______和______。
14、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。
15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。
16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
17、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。
18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）20、倒排文件的目的是为了多关键字查找。
（）21、数组不适合作为任何二叉树的存储结构。
（）22、在链队列中，即使不设置尾指针也能进行入队操作。
（）23、深度为k的二叉树中结点总数小于等于2k-1。
（）24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。
（）25、数据元素是数据的最小单位。
（）26、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（）27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。
（）28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。
（）四、简答题29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’（1）计算模式p的nextval函数值。
（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
30、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序，每归并一次书写一个次序。
（2）快速排序，每划分一次书写一个次序。
（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：其中叶节点的weight域保存该结点的非负权值。
设root为指向T的根节点的指针，设计求T的WPL的算法。
要求：（1）给出算法的基本设计思想。
（2）使用C或C++语言，给出二叉树结点的数据类型定义。
（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
五、算法设计题32、设A[1..100]是一个记录构成的数组，B[1..100]是一个整数数组，其值介于l～100之间，现要求按B[1..100]的内容调整A中记录的次序，比如当B[1]=11时，则要求将A[1]的内容调整到A[11]中去。
规定可使用的附加空间为O（1）。
33、给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中i，j为顶点号，v 为权值。
34、假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二叉树的存储结构。
L[i]和R[i]分别指示结点i的左儿子和右儿子， L[i]=0（R[i]=0）表示i的左（右）儿子为空。
试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点u 是否为结点V的后代的算法。
35、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。
线索树中结点结构为：（ltag，lc，data，rc，rtag）。
其中，data存放结点的值；lc、rc为指向左、右孩子或该结点前驱、后继的指针，ltag、rtag为标志域，若值为0，则lc、rc为指向左、右孩子的指针；若值为1，则lc、rc为指向其前驱、后继结点的指针。
参考答案一、选择题1、【答案】A2、【答案】C3、【答案】A4、【答案】C5、【答案】D6、【答案】A7、【答案】D8、【答案】D9、【答案】B10、【答案】D二、填空题11、【答案】n(n-1)/212、【答案】a+1；n%10【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
13、【答案】生成有序归并段（顺串）；归并14、【答案】分配和释放存储空间；重组；对插入的记录@15、【答案】O（1）；O（n）16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
17、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
18、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
三、判断题19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、简答题29、答：（1）p的nextval函数值为0110132（p的next函数值为0111232）。
（2）利用KMP（改进的nextval）算法，每趟匹配过程如下：30、答：（1）2一路归并第一趟：18，29，25，47，12，58，10，51。
第二趟：18，25，29，47，10，12，51，58。
第三趟：10，12，18，25，29，47，51，58。
（2）快速排序第一趟：10，18，25，12，29，58，51，47。
第二趟：10，18，25，12，29，47，51，88。
第三趟：10，12，18，25，29，47，51，88。
（3）堆排序建大堆：58，47，51，29，18，12，25，10。
①51，47，25，29，18，12，10，58。
②47，29，25，10，18，12，51，58。
③29，18，25，10，12，47，51，58。
④25，18，12，10，29，47，51，58。
⑤18，10，12，25，29，47，51，58。
⑥12，10，18，25，29，47，51，58。
⑦10，12，18，25，29，47，51，58。
31、答：（1）算法的基本思路是利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：算法如下：。