2022年湖北商贸学院计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年湖北商贸学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图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，f，c，f,eB.a，b，dC.a，e，b，c，f,d，e，d，fD.a，c，b2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序堆排序B.归并排序C.直接插入排序D.3、链表不具有的特点是（）。A.插入、删除不需要移动元素可随机访问任一元素B.C.不必事先估计存储空间所需空间与线性长D.度成正比4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只有BⅡ．ⅠC和Ⅱ．ⅠD和Ⅲ7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、就平均性能而言，目前最好的内排序方法是（）排序法。A.起泡希尔B.插入交换C.快速D.二、填空题11、属于不稳定排序的有______。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、在单链表L中，指针P所指结点有后继结点的条件是______。14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（）23、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）24、对于有n个结点的二叉树，其高度为log2n。（）25、在任何情况下，归并排序都比简单插入排序快。（）26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）27、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（）28、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）四、简答题29、阅读下面的算法，说明算法实现的功能。30、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。其中：l表示第i个叶点所在的号（根点所在号i结层设结层为1）。31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大