精品大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有精品.pdf

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，V7，V3B.V1，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7，V2，V5，D.V1V3，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，，cd，e，a，则根结点的孩子结点（）。A．只有e．有Be、b．有Ce、c．无法确定D8、一个具有1025个结点的二叉树的高h为（）。A.11B.10至1025之间C.11至1024之间D.109、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。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）是二叉树中所有叶结点