2023年信阳师范学院软件工程专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年信阳师范学院软件工程专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、下列排序算法中，占用辅助空间最多的是（　　）。 A.归并排序 B.快速排序 C.希尔排序D.堆排序 2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（　　）排序法。 A.插入 B.选择 C.希尔 D.二路归并 3、算法的计算量的大小称为计算的（　　）。 A.效率 B.复杂性 C.现实性 D.难度 4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 5、在下列表述中，正确的是（　　） A.含有一个或多个空格字符的串称为空格串 B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。 A．只有e B．有e、b C．有e、c D．无法确定 7、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（　　）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（　　）的两趟排序后的结果。 A.选择排序 B.起泡排序 C.插入排序 D.堆排序 二、填空题 11、无用单元是指______，例______ 12、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 13、数据结构中评价算法的两个重要指标是______。 14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 15、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。 16、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。 17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 18、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （1） 存放该数组至少需要的单元数是______。 （2） 存放数组的第8列的所有元素至少需要的单元数______。 （3） 数组按列存储时，元素A[5，8]的起始地址是______。 三、判断题 19、倒排文件的目的是为了多关键字查找。（　　） 20、文件系统采用索引结构是为了节省存储空间。（　　） 21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：aiai+1…an。（　　） 22、循环队列也存在空间溢出问题。（　　） 23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（　　） 24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（　　） 25、抽象数据类型与计算机内部表示和实现无关。（　　） 26、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （　　） 27、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（　　） 28、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 （　　） 四、简答题 29、已知n阶下三角矩阵A（即当i＜j时，有aij=0）