2022年马鞍山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年马鞍山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表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））））2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、以下与数据的存储结构无关的术语是（）。A.循环队列B.链表C.哈希表D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、已知关键字序列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。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、有关二叉树下列说法正确的是（）。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空题11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。12、在有n个顶点的有向图中，每个顶点的度最大可达______。13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。14、文件由______组成；记录由______组成。15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。16、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。17、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。三、判断题19、倒排序文件的优点是维护简单。（）20、对磁带机而言，ISAM是一种方便的文件组织方法（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）22、一个广义表可以为其他广义表所共享。（）23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）25、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）27、B-树中所有结点的平衡因子都为零。（）28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）四、简答题29、调用下列C函数f（n），回答下列问题：（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。C函数：30、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序?对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。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、设有一个数组中存放了一个无序的关键序列K1，K2，…，Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n（注：用程序实现）。33、一个有向图G=(V，E)的平方图G2=(V，E2)满足下述性质：(U，w)∈E2当且仅当存在某个顶点v∈V，使得(u，v)∈E且(v，w)∈E。写一个算法从给定的G求出G2，G和G2可分别用两个邻接表表示。34、按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)35、编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】D4、【答案】C5、【答案】A6、【答案】A7、【答案】D8、【答案】D9、【答案】B10、【答案】C二、填空题11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】2(n-1)13、【答案】2；4；3【解析】二分法查找元素次数列表查找100是找到115就停止了。14、【答案】记录；数据项15、【答案】分配和释放存储空间；重组；对插入的记录@16、【答案】（rear+1）%（n-m+1）==front17、【答案】【解析】最大的分支结点是最后一个叶子结点的父结点。18、【答案】23；100CH三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（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，执行过程中，输出结果为：30、答：n个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j趟起泡排序要进行n-j次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记flag的使用。31、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再将数组R中的前n－P个数和后P个数分别原地逆置，最终