2022年江苏警官学院计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年江苏警官学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入选择B.希尔二路C.归并D.3、线性表的顺序存储结构是一种（）。A.随机存取的存储结构顺序存取的存储结B.构C.索引存取的存储结构存取的存储结D.Hash构4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180．500B，450，200，180C．180，500，200，450．180D，200，500，4507、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树．所有叶B结点都在同一层上C．各结点内关键字均升序或降序排列．叶D结点之间通过指针链接8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.21510、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.（38，40，46，56，79，84）（40，B.38，46，79，56，84）C.（40，38，46，56，79，84）（40，D.38，46，84，56，79）二、填空题11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、外排序的基本操作过程是______和______。14、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。15、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、倒排文件是对次关键字建立索引。（）21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）22、串是一种数据对象和操作都特殊的线性表。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）25、算法的优劣与算法描述语言无关，但与所用计算机有关。（）26、排序算法中的比较次数与初始元素序列的排列无关。（）27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）28、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）四、简答题29、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判