东北大学13春学期《数据结构Ⅱ》在线作业3

13春学期《数据结构Ⅱ》在线作业3
试卷总分：100
单选题
一、单选题（共 20 道试题，共 100 分。）
V
1.
一个具有 1025 个结点的二叉树的高 h 为
A. 11
B. 10
C.
11 至 1025 之间
D. 10 至 1024 之间
满分：5 分
2.
在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是
A.
G 中有弧 Vi ， Vj
B.
G 中有一条从 Vi 到 Vj 的路径
C. G 中没有弧 Vi,Vj
D. G 中有一条从 Vj 到 Vi 的路径
此题选: D 满分：5 分
3.
已知在一棵度为 3 的树中，度为 2 的结点数为 4 ，度为 3 的结点数为 3 ，则该树中的叶子结点数为
A. 5
B. 8
C. 11
D. 18
满分：5 分
4.
for （ i=0 ； i m ； i++ ）
for （ j=0 ； j t ； j++ ）
c ［ i ］［ j ］ =0 ；
for （ i=0 ； i m ； i++ ）
for （ j=0 ； j t ； j++ ）
for （ k=0 ； k n ； k++ ）
c ［ 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
此题选: D 满分：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
此题选: D 满分：5 分
11.
树的先根序列等同于与该树对应的二叉树的
A. 先序序列
B. 中序序列
C.
后序序列
D.
层序序列
满分：5 分
12.
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A. 不一定相同
B. 都相同
C.
都不相同
D.
互为逆序
满分：5 分
13.
带行表的三元组表是稀疏矩阵的一种
A. 顺序存储结构
B. 链式存储结构
C.
索引存储结构
D.
散列存储结构
满分：5 分
14.
无向图中一个顶点的度是指图中
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
此题选: D 满分：5 分
15.
如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A. 深度优先搜索算法
B. 广度优先搜索算法
C.
求最小生成树的 prim 算法
D. 拓扑排序算法
满分：5 分
16.
下列查找算法中，平均查找长度与元素个数 n 不直接相关的查找方法是
A. 分块查找
B. 顺序查找
C.
二分查找
D.
散列查找
此题选: D 满分：5 分
17.
对长度为 n 的关键字序列进行堆排序的空间复杂度为
A.
O （ log 2 n ）
B.
O （ 1 ）
C.
O （ n ）
D.
O （ n*log 2 n ）
满分：5 分
18.
含 n 个关键字的二叉排序树的平均查找长度主要取决于
A. 关键字的个数
B. 树的形态
C.
关键字的取值范围
D.
关键字的数据类型
满分：5 分
19.
n 个顶点的有向完全图中含有向边的数目最多为
A.
n-1
B.
n
C.
n(n-1)/2
D.
n(n-1)
此题选: D 满分：5 分
20.
．用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.
逆拓扑有序
B.
拓扑有序
C.
无序的
D.
A 和 B
满分：5 分