东大17秋学期《数据结构Ⅱ》在线作业1答案满分答案
17秋学期《数据结构Ⅱ》在线作业1
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1.
若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
A.
2，4，3，1，5，6
B.
3，2，4，1，6，5
C.
4，3，2，1，5，6
D.
专业答案:----
正确答案:----
专业答案:----
专业答案:----
正确选项:----
正确答案:----
正确答案:----
专业答案:----
正确答案:----
正确答案:----
专业答案:----
2，3，5，1，6，4
满分：5 分
2.
已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是
专业答案:----
A.
head(tail(LS))
正确答案:----
B. tail(head(LS))
正确选项:----
C.
head(tail(head(tail(LS))))
正确选项:----
D. head(tail(tail(head(LS))))
正确答案:----
满分：5 分
3.
有关二叉树下列说法正确的是
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C.
二叉树中至少有一个结点的度为2
D.
二叉树中任何一个结点的度都为2
满分：5 分
4.
假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A. (rear-length+m+1)％m
B. (rear-length+m)％m
C.
(rear-length+m-1)％m
D.
(rear-length)％m
满分：5 分
5.
若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A. 4
B. 5
C. 8
D. 9
正确答案:----
满分：5 分
6.
已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为
专业答案:----
A. a d b e f c
正确答案:----
B. a d c e f b
专业答案:----
C.
a d c b f e
正确选项:----
D.
a d e f c b
正确答案:----
满分：5 分
7.
假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
A. (rear-front-1)％n
B. (rear-front)％n
C. (front-rear+1)％n
D. (rear-front+n)％n
专业答案:----
满分：5 分
8.
一个具有1025个结点的二叉树的高h为
A. 11
B. 10
C.
11至1025之间
D. 10至1024之间
专业答案:----
满分：5 分
9.
在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是
正确答案:----
A. p=p->next;
B. p->next=p->next->next;
C.
p->next=p;
D.
p=p->next->next;
满分：5 分
10.
下面的叙述不正确的是
A.
线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
专业答案:----
满分：5 分
11.
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A. 有向完全图
B. 连通图
C.
强连通图
D.
有向无环图
满分：5 分
12.
在VSAM文件的控制区间中，记录的存储方式为
A. 无序顺序
B. 有序顺序
C.
无序链接
D.
有序链接
满分：5 分
13.
对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为
A.
（1，2，3，4，5，6，7，8）
B.
（1，4，3，2，5，7，8，6）
C.
（2，1，4，3，5，7，8，6）
D.
（8，7，6，5，4，3，2，1）
满分：5 分
14.
深度为h的满m叉树的第k层的结点(1=<k=<h)数有
A. mk-1
B. mk-1
C.
mh-1
D. mh-1
正确答案:----
满分：5 分
15.
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A.
数组的元素处在行和列两个关系中
B.
数组的元素必须从左到右顺序排列
C.
数组的元素之间存在次序关系
D.
数组是多维结构，内存是一维结构
满分：5 分
16.
用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A. n-1
B. n
C.
n+l
D.
2n
满分：5 分
17.
已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为
A. 0
B. 1
C. 48
D. 49
专业答案:----
满分：5 分
18.
若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A. 层次遍历算法
B. 前序遍历算法
C.
中序遍历算法
D. 后序遍历算法
正确答案:----
满分：5 分
19.
在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
正确答案:----
head,则
正确答案:----
A. p指向头结点
B. p指向尾结点
C. p的直接后继是头结点
D. P的直接后继是尾结点
正确答案:----
满分：5 分
20.
若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A.
n-1
B.
?n/m?-1
C.
é(n-1)/(m-1)ù
D.
én/(m-1)ù-1
满分：5 分
东大17秋学期《数据结构Ⅱ》在线作业1答案历年参考题目如下：
