东大18秋学期《数据结构Ⅰ》在线作业2[答案]满分答案
18秋学期《数据结构Ⅰ》在线作业2-0001
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A.A，B，C，D
B.D，C，B，A
C.A，C，D，B
D.D，A，B，C
2. 算法的时间复杂度主要取决于
A.问题的规模
B.待处理数据的初态
C.难度
D.A和B
3. 文件中，主关键字能唯一标识
A.一个记录
B.一组记录
C.一个类型
D.一个文件
4. 下列程序段 for(i=1;i<=n;i++) A[i,j]=0; 的时间复杂度是
A.O(1)
B.O(0)
C.O(1+n)
D.O(n)
5. 二叉树中第5层上的结点个数最多为
A.8
B.15
C.16
D.32
6. 有关二叉树下列说法正确的是
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
7. 抽象数据类型的三个组成部分分别为
A.数据对象、数据关系和基本操作
B.数据元素、逻辑结构和存储结构
C.数据项、数据元素和数据类型
D.数据元素、数据结构和数据类型
8. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A.O(1)
B.O(logn)
C.O(n)
D.O(n logn)
9. 用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A.5
B.6
C.8
D.9
10. 十字链表的三元组表是稀疏矩阵的一种
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
11. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A.G中有弧<Vi，Vj>
B.G中有一条从Vi到Vj的路径
C.G中没有弧<Vi,Vj>
D.G中有一条从Vj到Vi的路径
12. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为
A.插入排序
B.归并排序
C.冒泡排序
D.堆排序
13. 在待排关键字序列基本有序的前提下，效率最高的排序方法是
A.直接插入排序
B.快速排序
C.直接选择排序
D.归并排序
14. 下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
15. 在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A.LL型
B.LR型
C.RL型
D.RR型
16. 下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.(1)
B.(1),(2)
C.(1),(4)
D.(3)
17. 判定“带头结点的链队列为空”的条件是
A.Q.front==NULL
B.Q.rear==NULL
C.Q.front==Q.rear
D.Q.front!=Q.rear
18. 按排序过程中依据的原则分类，快速排序属于
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.. 归并类的排序方法
19.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
A.4
B.5
C.6
D.7
20. ISAM文件的周期性整理是为了空出
A.磁道索引
B.柱面索引
C.柱面基本区
D.柱面溢出区
东大18秋学期《数据结构Ⅰ》在线作业2[答案]历年参考题目如下：
