2023年河北机电职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年河北机电职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（　　）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（　　）排序法。 A.插入 B.选择 C.希尔 D.二路归并 3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（　　）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（　　）。 A.543612 B.453126 C.346521 D.234156 5、动态存储管理系统中，通常可有（　　）种不同的分配策略。 A.1 B.2 C.3 D.4 6、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、下列叙述中，不符合m阶B树定义要求的是（　　）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、有关二叉树下列说法正确的是（　　）。 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 9、在下述结论中，正确的有（　　）。 ①只有一个结点的二叉树的度为0。 ②二叉树的度为2。 ③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.⑦③④ C.②④ D.①④ 10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（　　）。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、在有n个顶点的有向图中，每个顶点的度最大可达______。 12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 13、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。 14、已知有序表为（12，18，24，35，47，50，62，83，90，115， 134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。 15、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。 16、阅读下列程序说明和程序，填充程序中的______。 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 17、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。 18、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 三、判断题 19、倒排文件的目的是为了多关键字查找。（　　） 20、倒排文件是对次关键字建立索引。（　　） 21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：aiai+1…an。（　　） 22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（　　） 23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（　　） 24、对于有n个结点的二叉树，其高度为log2n。（　　） 25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（　　） 26、为了很方便地插入和删除数据，可以使用双向链表存放数据。 （　　） 27、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且