20春学期《数据结构Ⅱ》在线平时作业1

20春学期数据结构在线平时作业1试卷总分:100 得分:100一、单选题 (共 20 道试题,共 100 分)1.适宜进行批量处理的文件类型是A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件答案:A2.用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为A.9B.8C.6D.5答案:D3.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.4答案:B4.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BTm中，其中根结点存放在BT0，若BTi中的结点有左孩子，则左孩子存放在A.BTi/2B.BT2*iC.BT2*i-1D.BT2*i+1答案:D5.下列陈述中正确的是A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点答案:C6.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是A.6B.5C.3D.2答案:C7.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A.n-1B.nC.2n-1D.2n答案:B8.栈和队列都是A.顺序存储的线性结构B.限制存取位置的非线性结构C.限制存取位置的线性结构D.链式存储的线性结构答案:C9.带行表的三元组表是稀疏矩阵的一种A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构答案:A10.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A.O(n2)B.O(n)C.O(1)D.O(0)答案:B11.下面说法错误的是 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低A.(1),(4)B.(1),(2)C.(3)D.(1)答案:A12.以下属于逻辑结构的是A.顺序表B.有序表C.哈希表D.单链表答案:B13.ALV树是一种平衡的二叉排序树，树中任一结点的A.左子树的高度均小于右子树的高度B.左子树的高度均大于右子树的高度C.左、右子树高度差的绝对值不超过1D.左、右子树的高度均相同答案:C14.栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构答案:A15.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为A.O(n+e)B.O(n3)C.O(n2)D.O(n)答案:A16.当采用分快查找时，数据的组织方式为A.数据分成若干块，每块（除最后一块外）中数据个数需相同B.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序D.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块答案:D17.倒排文件的主要优点是A.节省存储空间B.便于进行文件的恢复C.便于进行插入和删除运算D.便于进行多关键字查询答案:D18.引起循环队列队头位置发生变化的操作是A.取队尾元素B.取队头元素C.出队D.入队答案:C19.下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，便于插入和删除操作。D.线性表采用链接存储，不必占用一片连续的存储单元。答案:B20.在目标串T0.n-1=″xwxxyxy″中，对模式串P0.m-1=″xy″进行子串定位操作的结果是A.5B.3C.2D.1答案:B