2022年哈尔滨金融学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年哈尔滨金融学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f,dD.a，e，d，f，c，b3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。A.单链表B.双向链表C.单循环链表D.顺序表4、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341566、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modMB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modMD．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）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、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、有关二叉树下列说法正确的是（）。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。A.1B.4C.3D.2二、填空题11、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元组表示弧<a，b>及弧上的权d。E(G)为E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。12、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。14、在单链表L中，指针P所指结点有后继结点的条件是______。15、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。18、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排序文件的优点是维护简单。（）21、广义表（（（a，b，c），d，e，f））的长度是4。（）22、在链队列中，即使不设置尾指针也能进行入队操作。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（）25、在待排数据基本有序的情况下，快速排序效果最好。（）26、为了很方便地插入和删除数据，可以使用双向链表存放数据。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54，需依次与哪些元素比较?（3）若查找元素90，需依次与哪些元素比较?（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。31、设将n（n＞1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循左移P（0＜P＜n）个位置，即将R中的数据由（X0，X1，…，Xn－1）变换为（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 给出算法的基本设计思想。（2） 根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。五、算法设计题32、请编写完整的程序。如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。33、已知指针p指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG，LLINK，INFO，RLlNK，RTAG），且规定线索树的最左下结点的LLINK域和最右下结点的RLINKt域指向表头。34、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。35、编写算法，求二叉树的宽度。

参考答案一、选择题1、【答案】D2、【答案】D3、【答案】D4、【答案】B5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】B10、【答案】B二、填空题11、【答案】50；412、【答案】n（n-1）/213、【答案】分配和释放存储空间；重组；对插入的记录@14、【答案】P->next!=NULL15、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。16、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。18、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】√27、【答案】√28、【答案】√四、简答题29、答：森林转换为二叉树分以下三步：连线（将兄弟结点相连，各树的根看作兄弟）。切线（保留最左边子女为独生子女，将其他子女分支切掉）。旋转（以最左边树的根为轴，顺时针向下旋转45度）。所以由上面三棵树转换得到的二叉树如图所示：30、答：（1）判定树如图所示：（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。（4）31、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再将数组R中