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

2023年河北民族师范学院计算机应用技术专业《数据结构与算法》科目期末试卷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 B.a，c，f,e，b，d C.a，e，b，c，f, d D.a，e，d，f，c，b 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 3、算法的计算量的大小称为计算的（　　）。 A.效率 B.复杂性 C.现实性 D.难度 4、下面关于串的叙述中，不正确的是（　　）。 A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（　　）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 9、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（　　）。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 12、阅读下列程序，指出其功能，并写出空格处应填上的语句。 13、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。 14、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：(1)图的顶点号从0开始计。 (2)indegree是有n个分量的一维数组，放顶点的入度， (3)函数crein用于计算顶点入度。 (4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。 15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。 16、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B 中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始） 17、模式串P=‘abaabcac’的next函数值序列为______。 18、阅读下列程序说明和程序，填充程序中的______。 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树