13春学期《数据结构ⅱ》在线作业3

东北大学14春13秋东大13春学期《数据结构Ⅱ》在线作业3
试卷总分：100 测试时间：--
单选题



、单选题（共 20 道试题，共 100 分。）
1.
一个具有1025个结点的二叉树的高h为

A. 11
B. 10
C.
11至1025之间
D. 10至1024之间
满分：5 分作业答案没有上传，先供大家复习使用，如果需要答案的具体看我的注册名字 来找
2.
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A.
G中有弧
B.
G中有一条从Vi到Vj的路径

C. G中没有弧
D. G中有一条从Vj到Vi的路径
满分：5 分
3.
已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为

A. 5
B. 8
C. 11
D. 18
满分：5 分
4.
for（i=0；ifor（j=0；jc［i］［j］=0；
for（i=0；ifor（j=0；jfor（k=0；kc［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为

A. O（m+n×t）
B. O（m+n+t）

C. O作业答案没有上传，先供大家复习使用，如果需要答案的具体看我的注册名字 来找（m×n×t）
D. O（m×t+n）
满分：5 分
5.
按排序过程中依据的原则分类，快速排序属于
A.
插入类的排序方法
B.
选择类的排序方法
C.
交换类的排序方法
D.
归并类的排序方法
满分：5 分
6.
为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为

A. 5
B. 37
C. 41
D. 62
满分：5 分
7.
设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为

A. 5
B. 6
C. 7
D. 8
满分：5 分
8.
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A.
顺序表
B.
双链表
C.
带头结点的双循环链表
D.
单循环链表
满分：5 分
9.
在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作

A. s->next=p->next;p->next=s;
B. s->next=p; q->next=s

C.
q->next=s;s->next=p;
D.
p->next=s;s->next=q;
满分：5 分
10.
对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为

A. 1，2，3
B. 9，5，2，3
C.
9，5，3
D. 9，4，2，3
满分：5 分
11.

树的先根序列等同于与该树对应的二叉树的

A. 先序序列
B. 中序序列

C.
后序序列
D.
层序序列
满分：5 分
12.
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系

A. 不一定相同
B. 都相同

C.
都不相同
D.
互为逆序
满分：5 分
13.
带行表的三元组表是稀疏矩阵的一种

A. 顺序存储结构
B. 链式存储结构

C.
索引存储结构
D.
散列存储结构
满分：5 分
14.
无向图中一个顶点的度是指图中

A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数

C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：5 分
15.
如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用

A. 深度优先搜索算法
B. 广度优先搜索算法

C.
求最小生成树的prim算法
D. 拓扑排序算法
满分：5 分
16.
下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是

A. 分块查找 作业答案没有上传，先供大家复习使用，如果需要答案的具体看我的注册名字 来找
B. 顺序查找

C.
二分查找
D.
散列查找
满分：5 分
17.
对长度为n的关键字序列进行堆排序的空间复杂度为
A.
O（log2n）
B.
O（1）
C.
O（n）
D.
O（n*log2n）
满分：5 分
18.
含n个关键字的二叉排序树的平均查找长度主要取决于

A. 关键字的个数
B. 树的形态

C.
关键字的取值范围
D.
关键字的数据类型
满分：5 分
19.
n个顶点的有向完全图中含有向边的数目最多为
A.
n-1
B.
n
C.
n(n-1)/2
D.
n(n-1)
满分：5 分
20.
．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.
逆拓扑有序
B.
拓扑有序

C.
无序的
D.
A和B
满分：5 分




作业答案没有上传，先供大家复习使用，如果需要答案的具体看我的注册名字 来找