奥鹏[东北大学]20春学期《数据结构Ⅱ》在线平时作业1答卷

20春学期《数据结构Ⅱ》在线平时作业1
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 100 分)
1.适宜进行批量处理的文件类型是
A.顺序文件
B.索引顺序文件
C.散列文件
D.多关键字文件
答案:A

2.用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A.9
B.8
C.6
D.5
答案:D

3.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A.9
B.8
C.5
D.4
答案:B

4.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在
A.BT[i/2]
B.BT[2*i]
C.BT[2*i-1]
D.BT[2*i+1]
答案:D

5.下列陈述中正确的是
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中最多只有两棵子树，并且有左右之分
D.二叉树中必有度为2的结点
答案:C

6.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A.6
B.5
C.3
D.2
答案:C

7.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
A.n-1
B.n
C.2n-1
D.2n
答案:B

8.栈和队列都是
A.顺序存储的线性结构
B.限制存取位置的非线性结构
C.限制存取位置的线性结构
D.链式存储的线性结构
答案:C

9.带行表的三元组表是稀疏矩阵的一种
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
答案:A

10.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O(n2)
B.O(n)
C.O(1)
D.O(0)
答案:B

11.下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.(1),(4)
B.(1),(2)
C.(3)
D.(1)
答案:A

12.以下属于逻辑结构的是
A.顺序表
B.有序表
C.哈希表
D.单链表
答案:B

13.ALV树是一种平衡的二叉排序树，树中任一结点的
A.左子树的高度均小于右子树的高度
B.左子树的高度均大于右子树的高度
C.左、右子树高度差的绝对值不超过1
D.左、右子树的高度均相同
答案:C

14.栈的两种常用存储结构分别为
A.顺序存储结构和链式存储结构
B.顺序存储结构和散列存储结构
C.链式存储结构和索引存储结构
D.链式存储结构和散列存储结构
答案:A

15.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
A.O(n+e)
B.O(n3)
C.O(n2)
D.O(n)
答案:A

16.当采用分快查找时，数据的组织方式为
A.数据分成若干块，每块（除最后一块外）中数据个数需相同
B.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
C.数据分成若干块，每块内数据有序
D.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
答案:D

17.倒排文件的主要优点是
A.节省存储空间
B.便于进行文件的恢复
C.便于进行插入和删除运算
D.便于进行多关键字查询
答案:D

18.引起循环队列队头位置发生变化的操作是
A.取队尾元素
B.取队头元素
C.出队
D.入队
答案:C

19.下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，便于插入和删除操作。
D.线性表采用链接存储，不必占用一片连续的存储单元。
答案:B

20.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A.5
B.3
C.2
D.1
答案:B

 

AI创作