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