2022年云南大学滇池学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、算法的计算量的大小称为计算的（）。

A.效率B.复杂性C.现实性D.难度4、已知有向图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，V75、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。

A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、属于不稳定排序的有______。

12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。

13、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。

14、文件由______组成；记录由______组成。

15、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。

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

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

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

17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

18、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。

三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。

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

（）21、一个广义表可以为其他广义表所共享。

（）22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

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

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

（）25、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。

（）26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。

（）27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。

（）28、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。

（）四、简答题29、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。

30、已知n阶下三角矩阵A（即当i＜j时，有a ij=0），按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素a ij的存放位置的公式。

31、已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。

在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。

若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。

要求：（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤。

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。

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

33、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。

请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

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

35、设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

参考答案一、选择题1、【答案】D2、【答案】A3、【答案】B4、【答案】A5、【答案】B6、【答案】A7、【答案】D8、【答案】B9、【答案】D10、【答案】C二、填空题11、【答案】希尔排序、简单选择排序、快速排序、堆排序等12、【答案】起泡；快速13、【答案】1514、【答案】记录；数据项15、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p16、【答案】模式匹配；模式串17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

18、【答案】9174；8788三、判断题19、【答案】×20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】√26、【答案】×27、【答案】√28、【答案】×四、简答题29、答：数组占的存储字节数=10*9*7*4=2520；A[5，0，7]的存储地址=100+[4*9*7+2*7+5]*4=1184。

30、答：2阶下三角矩阵元素A[i][j]（1≤i，j≤n，i≥j）。

第1列有n个元素，第j 列有n-j+1个元素，第1列到第j-1列是梯形，元素数为（n+（n-j+2）（j-1）/2，而a ij在第j列上的位置是为i-j+1。

所以n阶下三角矩阵A按列存储，其元素a ij在一维数组B中的存储位置k与i和j的关系为：31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。

p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。

以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤① count＝0，p和q指向链表表头结点的下一个结点。

②若p为空，转⑤。

③若count等于k，则q指向下一个结点；否则，count＝count＋1。

④ p指向下一个结点，转步骤②。

⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0。

⑥算法结束。

（3）算法实现五、算法设计题32、答：算法如下：33、答：算法如下：34、答：算法如下：35、答：（1）递归算法如下：（2）非递归算法如下：。