2022年内蒙古大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年内蒙古大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、将两个各有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、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、已知关键字序列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、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A．只有eB．有e、bC．有e、cD．无法确定8、一个具有1025个结点的二叉树的高h为（）。A.11B.10C.11至1025之间D.10至1024之间9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。13、在单链表L中，指针P所指结点有后继结点的条件是______。14、建立索引文件的目的是______。15、索引顺序文件既可以顺序存取，也可以______存取。16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。17、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、倒排文件是对次关键字建立索引。（）21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）25、算法的优劣与算法描述语言无关，但与所用计算机有关。（）26、归并排序辅助存储为O（1）。（）27、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）28、B-树中所有结点的平衡因子都为零。（）四、简答题29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’（1）计算模式p的nextval函数值。（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。30、调用下列C函数f（n），回答下列问题：（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。C函数：31、二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。要求：（1）给出算法的基本设计思想。（2）使用C或C++语言，给出二叉树结点的数据类型定义。（3）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。五、算法设计题32、对给定关键字序号j（1<j<n），要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找（要求用最少的时间和最少的空间）。例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。33、线性表中元素存放在向量A（1，…，l）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。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、编写算法，将自然数l～n2按“蛇形”填n×n矩阵中。例（1～42）如图所示（用程序实现）。

参考答案一、选择题1、【答案】A2、【答案】A3、【答案】D4、【答案】A5、【答案】B6、【答案】A7、【答案】A8、【答案】C9、【答案】C10、【答案】C二、填空题11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】（n+1）/213、【答案】P->next!=NULL14、【答案】提高查找速度15、【答案】随机16、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。17、【答案】【解析】最大的分支结点是最后一个叶子结点的父结点。18、【答案】模式匹配；模式串三、判断题19、【答案】√20、【答案】√21、【答案】√22、【答案】×23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）p的nextval函数值为0110132（p的next函数值为0111232）。（2）利用KMP（改进的nextval）算法，每趟匹配过程如下：30、答：（1）第一层for循环判断n+1次，往下执行n次，第二层for执行次数为（n+（n-1）+（n-2）+…+1），第三层循环体受第一层循环和第二层循环的控制，其执行次数如表1-1所示。执行次数为f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5对，f（5）=55，执行过程中，输出结果为：31、答