东大19秋学期《数据结构Ⅱ》在线平时作业2[满分答案]满分答案
19秋学期《数据结构Ⅱ》在线平时作业2
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.数据的四种基本存储结构是指
A.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
B.顺序存储结构、链式存储结构、树型存储结构、图型存储结构
C.顺序存储结构、索引存储结构、链式存储结构、散列存储结构
D.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
2.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
A.4，3，2，1，5，6
B.3，2，4，1，6，5
C.2，4，3，1，5，6
D.2，3，5，1，6，4
3.有关二叉树下列说法正确的是
A.二叉树的度为2
B.二叉树中至少有一个结点的度为2
C.二叉树中任何一个结点的度都为2
D.一棵二叉树的度可以小于2
4.算法分析的目的是
A.鉴别算法的可读性
B.辨别数据结构的合理性
C.评价算法的效率
D.研究算法中输入与输出的关系
5.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A.X的左子树中最右结点
B.X的左子树中最右叶结点
C.X的右子树中最左的结点
D.X的双亲
6.在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A.s->next=p; q->next=s
B.s->next=p->next;p->next=s;
C.q->next=s;s->next=p;
D.p->next=s;s->next=q;
7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为
A.49
B.48
C.1
D.0
8.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A.g,d,b
B.g,c,b
C.f,d,b
D.f,c,b
9.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A.O(n logn)
B.O(n)
C.O(logn)
D.O(1)
10.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是
A.4231
B.4213
C.4132
D.1234
11.树的先根序列等同于与该树对应的二叉树的
A.层序序列
B.后序序列
C.先序序列
D.中序序列
12.若<vi, vj>是有向图的一条边，则称
A.vj邻接于vi
B.vi邻接于vj
C.vi和vj相互邻接
D.vi与vj­不相邻接
13.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A.6
B.5
C.17
D.16
14.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A.O(n+e)
B.O(n2)
C.O(n)
D.O(e)
15.导致栈上溢的操作是
A.栈空时执行的出栈
B.栈空时执行的入栈
C.栈满时执行的出栈
D.栈满时执行的入栈
16.在下列存储形式中，哪一个不是树的存储形式
A.顺序存储表示法
B.孩子链表表示法
C.孩子兄弟表示法
D.双亲表示法
17.文件中，主关键字能唯一标识
A.一组记录
B.一个记录
C.一个类型
D.一个文件
18.下面的说法中正确的是
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A.(1)，(2)都错
B.(1)，(2)
C.(2)
D.(1)
19.设给定权值总数有n 个，其哈夫曼树的结点总数为
A.不确定
B.2n-1
C.2n+1
D.2n
20.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到
A.S=″STUDY″
B.S=″SCIENCE″
C.P=″STUDY″
D.P=″SCIENCE″
东大19秋学期《数据结构Ⅱ》在线平时作业2[满分答案]历年参考题目如下：
