-
华
中
农
业
大
学
2018
年
硕
士
研究生
入
学
考
试
试
题
纸
科
目
代码及名称
:
867
数据
结
构与算法
第
1
页
共
4
页
注
意
:
所
有
答
案
必
须
写
在
答
题
本
上
,
不
得
写
在
试
题
纸
上
,
否
则
无
效
。
一
、名词解释
(
共
2
0
分
,
每题
4
分)
1
、
算法及算
法的特性
2
、
树的度及深度
3
、
完全二叉树
4
、
索引文件
5
、强连通性
二
、
选择题
(
共
30
分
,
每题
2
分)
1
、设核
S
和队列
Q
的初始状态均为
空
,
元
素
AB
CD
E
FG
依次进技
S
。若
每
个
元素
出
校后立即进入队列
Q
,
且
7
个元
素的出队
顺
序是
BDCFE p>
A
G
,
则
核
S
的容量
至少是
:
A.
1
B.
2
C
.
3
D.
4
2
、
已知一棵完全二叉树的第六
层
(
根为
第一层〉
有
8
个
叶
子结点
,
则完
全
二叉
树
的结点个数最多是
:
A.
3
9
B. 5
2
C
.
111
D. 119
3
、
下
列叙述中不符
合
m
阶
B
树定义要求的是
:
A
.
根结点最多有
m
棵子树
C.
各结点内关键
字均
升
序或降序< /p>
排
列
B
.
所有叶结点在同
一层上
D
.
叶结点之间
通过指针链接
4
、若无向图中含有
7
个顶点
,
贝
。保证图在
任何情
况
下
都是连通的
,
需要的
边数最少是
:
A
.
6
B. 1
5
C
.
16
D
.
2
1
5
、
对一组数据
(
7
,
1
7
,
2
1,
9
3
,
1
0
,
1
6
)
进行排序
,
若前三趟排序结果如
下
,
则采用的排序方法是
:
第一趟
:
7
,
1
7
,
2
1,
1
0
,
1
6,
9
3
第
二
趟
:
7
,
1
7
,
1
0,
16
,
21,
93
第
二趟
:
7
,
1
0
,
1
6
,17
,
21
,93
A
.
冒泡
排
序
B
.
希尔
排
序
C
.
归并排序
D.
基数
排
序
6
、
已知一
才
果有
2
01
1
个结点的树
,
其叶结
点
个数
为
11
6
,
该树
对
应的二叉
树
中无右孩
子的结点个数是
:
A
. 11
5
B
.
1
16
C
.
189
5
D.
18
9
6
7
、
已知字
符
串
S
为
“
a
b p>
aa
b
aa
ba
ca
c
aabaabcc
.
模式串
t
为
“
a
b p>
a
abc
”
,
采
用
K
M
P
算
法进行匹配
,
第一次出现
“
失
自
己
”
(
s
[i
]
!
=
t
[
i
]
)
时
,
i
j
习
,
则
下
次
开始
匹
配时
,
i
和
j
的
值
分别是
:
A
.
i
=
l
;
j
=
O
;
B
.
i
二
5
;
j
=
O
;
C
.
i=5
;
j
=
2
;
D
.
i
=
6
;
j
=
2
;
下列选项
中,
会受堆积现象直接影响的是
:
A
.
存储效率
B
.
数列函数
C
.
装填
(
装
载
〉
因子
D
.
平
均查找长度
8
、
用哈希
(
散
列
〉
方法处理冲突
(
碰
撞〉
时可能出现堆积
(
聚
集)
现象
,
华
中
农
业
大
学
2018
年
硕
士
研究生
入
学
考
试
试
题
纸
科
目
代码及名称
:
867
数据
结
构与算法
第
2
页
共
4
注
意
:所
有
答
案
必
须
写
在
答
题
本
上
,不
得
写
在
试
题
纸
上
页
,
否
则
无
效
。
9
、
循环队列放在一维数组
A
[
O
·
·
·
M
-
1
< br>]
中
,
endl
指向队头元
素
,
end2
指向
队尾元素的后一个位置
。
假设队列
两
端均可
进
行
入队
和出队操作
,
队列中
最多
能容纳
M-
1
个
元素
。
初始时为
空
。
下列判断队空和队满的条件中
,
正确的是
:
A
.
队空
:
endl
==
end2
;
队满
:
en
dl
==
(end2+1) mo
d
M
B
.
队空
:
endl
==
end2
;
队满
:
end2
=
=
(endl
+
1
)
mod
(
M
-
1
)
队空
:
end
2
==
(endl
+
l
)
mod
M
;
队满
:
endl
==
(
end2+
1
)
mod
M
D
.
队空
:
endl
=
=
(end2+
1
)
m
o
d M
;
队满
:
end2
==
(
en
d
1
+1)
m
od (M-
1
)
c
.
10
、
非
空
的循环单
链
表
he
ad
的尾
结
点
(
由
p
所指向〉
满足
:
A
.
P
一
>
n
ex
t=
=
N
1 JLL
;
B
.
p==
N
ULL;
C
.
p
->
nex
t
==
h
ead
;
D.
p
==
h
ea
d
11
、
查
找效率最高的
二叉排序树是
:
A
.
所有结点的左
子树都为
空
的
二
叉排序树
B
.
所有结点的右子树都为
空的
二
叉排序树
c
.
平
衡二叉树
D
.
没有
左子
树的二叉排序树
12
、
下面关于求关
键
路径的说法不正确的
是
:
A
.
求关
键
路径
是
以拓扑排序为基础的
B
.
关键活动一定位于关键路径上
C
.
一个事件的最早开始时间
同
以该事件为
尾的弧的活
动最早开始时
间
相同
D
.
一个事
件的最迟开
始时间
为
以该事件为
尾的弧的活
动
最迟开
始时
间与该活
动的持续时间的差
1
3
、
在< /p>
一
个
单
链表
中
,
若
q
结点是
p
结
点的前驱结点
,
若在
q
和
p
之
间插
入结点
s
,则执
行
:
A
.
P
甲
>
nex
t=s
一
>
nex
t
;
s->nex
t
=
p
:
B
.
s-
>
next
=
p
一
>
nex
t
;
p
>
ne
xt=
s
;
C.
P<
/p>
一
>
n
ex
t
=s
;
s
一
>
nex
t
=q;
D
.
q
一 >
nex
t
=
s
;
s->
n
e
x
t
=p;
1
4
、
设
有
一个对称
矩阵
A
,
采用压
缩存储方式
,
以行序为
主序存储
,
a
l
l
为
第
一个元
素
,
其存储地址为
1
,
每个元
素
占
一个地
址空
间
,
则
a8
5
地
址
为
:
A
.
23
B.
33
C
.
1
8
D
.
40
15
、
就平均
查找速度
而
言,
下列几种查找速度从慢
至快的关系是
:
A
.
J
I
顶序
折半
哈希
分块
B.
分块
折半
哈希
顺序
C
.
顺序
分块
折半
哈希
D.
顺序
哈希
分块
折
半
三
、
填空
题
(
共
2
0
分
,
每题
2
分
)
1
、广义表
A=
(x
,
旬
,
b,
c
,
d
)
)
的表尾
是
一
一
一
2