2023年甘肃农业大学数据科学与大数据技术专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年甘肃农业大学数据科学与大数据技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、下列排序算法中，占用辅助空间最多的是（　　）。 A.归并排序 B.快速排序 C.希尔排序D.堆排序 3、计算机算法指的是解决问题的步骤序列，它必须具备（　　）三个特性。 A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（　　）。 A.（rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（　　）。 A.543612 B.453126 C.346521 D.234156 6、下列叙述中，不符合m阶B树定义要求的是（　　）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 7、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8、一个具有1025个结点的二叉树的高h为（　　）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（　　）个不同的码字。 A.107 B.108 C.214 D.215 10、就平均性能而言，目前最好的内排序方法是（　　）排序法。 A.起泡 B.希尔插入 C.交换 D.快速 二、填空题 11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m， n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2， 3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整。 ②执行程序，f（6，4）=______。 12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。 13、索引顺序文件既可以顺序存取，也可以______存取。 14、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。 15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 16、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。 17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B 中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始） 18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 三、判断题 19、倒排文件的目的是为了多关键字查找。（　　） 20、文件系统采用索引结构是为了节省存储空间。（　　） 21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（　　） 22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 23、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（　　） 24、深度为k的二叉树中结点总数小于等于2k-1。（　　） 25、算法的优劣与算法描述语言无关，但与所用计算机有关。（　　） 26、排序算法中的比较次数与初始元素序列的排列无关。（　　） 27、无环有向图才能进行拓扑排序。（　　） 28、B-树中所有结点的平衡因子都为零。（　　） 四、简答题 29、调用下列C函数f（n），回答下列问题： （1）试指出f（n）值的大小，并写出，f（n）值的推导过程。 （2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。 C函数： 30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。 31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、