东大19秋学期《数据结构Ⅱ》在线平时作业1[满分答案]满分答案
19秋学期《数据结构Ⅱ》在线平时作业1
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.高度为5的完全二叉树中含有的结点数至少为
A.32
B.31
C.17
D.16
2.通常将链串的结点大小设置为大于1是为了
A.提高存储密度
B.提高串匹配效率
C.便于插入操作
D.便于删除操作
3.在VSAM文件的控制区间中，记录的存储方式为
A.有序顺序
B.有序链接
C.无序顺序
D.无序链接
4.在一棵高度为k的满二叉树中，结点总数为
A.2k-1
B.2k-1
C.2k
D.ëlog2kû+1
5.已知广义表的表头为a，表尾为(b,c)，则此广义表为
A..(a,b,c)
B..(a,(b,c))
C..((a,b,c))
D..((a),b,c)
6.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
A.8
B.5
C.18
D.11
7.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为
A.插入排序
B.归并排序
C.堆排序
D.冒泡排序
8.栈是一种操作受限的线性结构，其操作的主要特征是
A.进优于出
B.后进先出
C.出优于进
D.先进先出
9.下面的叙述不正确的是
A.线性表在顺序存储时，查找第i个元素的时间同i的值无关
B.线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
C.线性表在链式存储时，查找第i个元素的时间同i的值无关
D.线性表在链式存储时，查找第i个元素的时间同i的值成正比
10.n个顶点的有向完全图中含有向边的数目最多为
A.n(n-1)/2
B.n(n-1)
C.n-1
D.n
11.采用ISAM或VSAM组织的文件是
A.顺序文件
B.索引顺序文件
C.索引非顺序文件
D.散列文件
12.除第一层外，满二叉树中每一层结点个数是上一层结点个数的
A.3倍
B.2倍
C.1倍
D.1/2倍
13.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
A.队列
B.树
C.栈
D.图
14.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A.én/(m-1)ù-1
B.ën/mû-1
C.é(n-1)/(m-1)ù
D.n-1
15.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是
A.tail(head(LS))
B.head(tail(tail(head(LS))))
C.head(tail(head(tail(LS))))
D.head(tail(LS))
16.算法的时间复杂度主要取决于
A.难度
B.问题的规模
C.待处理数据的初态
D.A和B
17.已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有
A.以上答案都不对
B.dacb
C.cadb
D.bdac
18.设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A.D，C，B，A
B.D，A，B，C
C.A，C，D，B
D.A，B，C，D
19.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为
A.n+l
B.n+2
C.n-1
D.n
20.n个顶点的强连通图中至少含有
A.n条有向边
B.n(n-1)条有向边
C.n(n-1)/2条有向边
D.n-1条有向边
东大19秋学期《数据结构Ⅱ》在线平时作业1[满分答案]历年参考题目如下：
