南京理工大学mpacc-南京理工大学mpacc
宁波大学
2019
年硕士研究生招生考 试初试试题
(A
卷
)
(
答案必须写在考点提供的答题纸上
)
科目代码：
916
总分值：
150
科目名称：
数据结构与算法
一、
选择题：
（共< /p>
30
分，每题
2
分）
1.
采用链式存储结构表示数据时，相邻的数据元素的存储地址（
）。
A.
一定不连续
B.
不一定连续
C.
一定连续
D.
部分连续，部分不连续
2.
在一个单链表中，若
*p
节点不是最后节点，在
* p
之后插入节点
*s
，则执行（
）。
A. s->next =
p; p->next = s;
B. s->next = p->next p->next = s;
C. s->next = p->next p = s;
D. p->next = s; s->next = p;
3.
用数组< /p>
r
存储静态链表，结点的
next
域指向后继，工作 指针
j
指向链中结点，使
j
沿链移动
的操作为
(
)
。
A. j=j->next
B. j=r[j].next
C .j=j+1
D. j=r[j]-> next
4.
向一个 栈顶指针为
HS
的链栈（带头结点）中插入一个
s
所指结点时，则执行（
）。
A. s->next = HS
HS = s;
B.
HS->next = s;
C. s -> next = HS->next HS->next = s;
D.
s->next = HS HS = HS->next;
5.
已知一个推入堆栈的字符序列顺序是
a,b,c,d,e,
下列哪个字符序列是不能通过堆栈操作得到的
字符序列（
）。
A. e,d,c,b,a
B. d,e,c,b,a
C. d,c,e,a,b
D. a,b,c,d,e
6.
循环队列存储在数组
A[0..m]
中，则入队时的操作为（
）。
A. rear=rear+1
B. rear=(rear+1) mod (m-1)
C.
rear=(rear+1) mod m
D. rear=(rear+1)mod(m+1)
7.
在一个具有
n
个单元的顺序存储的 循环队列中，
假定
front
和
rear
分别为队首指针和队尾指针，
则判断队空的条件是（
）。
A. front = = (rear +1) % n
B. front = = rear
C. front = =0
D. (front +1) % n = = rear
8.
对顺序存储的线性表 ，
设其长度为
n
，
在任何位置上插入或删除操作都 是等概念的，
插入一个
元素时平均要移动表中的（
）个元素。
A. (n
－
1)/2
B. n
C. n/2
D. (n
＋
1)/2
9.
对广义表
A=
（
（
a,(b)
）
,(c,()),d
）
执行操作
gettail(gethead(gettail(A)))
的结果是：
（
）
。
A.
（）
B.
（（））
C. d
D. (d)
10.
构
造
哈
希
表
的
关
键
< p>字的
输
入
序
列
为
(25,21,30,13,4,43,35,64,5,17,2,8)
，< /p>
哈
希
函
数
H(key)=k
ey%15
，采用链地址法解决冲突。查找
64
的关键字比较次数 是（
）。
A.
1
B.
2
C. 4
D .
3
第
1
页
共
5
页
宁波大学
2019
年硕士研究 生招生考试初试试题
(A
卷
)
(
答案必须写在考点提供的答题纸上
)
科目代码：
916
总分值：
150
科目名称：
数据结构与算法
11.
下图是一个二叉树后序遍历的结果是
（
）。
A
、
abcdef
B
、
cfabde
C
、
dbaecf
D
、
cbfade
12.
现有以下按前序和中序遍历二叉树的结果：
前序：
GAHFDBCE
中 序：
AHGBDCFE
，
该二叉树的后序遍历序列为
(
)
。
A . GHABCDEF
B. HABCDEFG
C. ABCDEFGH
D. HABCGDEF
13.
一棵完全二叉树 的第
6
层（设根为第
1
层）有
8< /p>
个叶结点，则该完全二叉树的结点个数最多
是（
）。
A .
39
B. 119
C.
111
D. 239
14.
一
棵
非
空
二
叉
树
的
< p>先序
遍
历
序
列
与
后
序
遍
历
序
列< /p>
正
好
相
反
，
则
该
二
叉
树
一
定
< p>满足
（
）。
A .
是一棵满二叉树
B.
所有的结点均无右孩子
C.
所有的结点均无左孩子
D.
只有一个叶子结点
15.
任何一个连通图的最小生成树
(
)
。
A
．只有一棵
B.
有一棵或多棵
C.
一定有多棵
D.
可能不存在
二、
填空题：（共
28
分，每空
2
分）
1.
已知某二叉树的先序遍历次序为
abcdefg
，中序遍历次序为
badcgfe
，则该二叉树的后序遍历
次序为
____ ________
，层次遍历次序为
___________
。< /p>
2.
对于长度为
n
的关键字有序的线性 表，若进行顺序查找，则平均时间复杂度为
________
；若
采用二分法查找，则平均时间复杂度为
________
；
3.
在一棵度为
3
的树中，
度为
3
的结点个数为
3
，
度为
2
的结点个数为
2
，
度为
1
的结点个数为
1
，
则度为
0
的结点个数为
________
。
4.
在一棵
m
阶
B-
树中，除根结点外非叶结点至少有
< p>________棵子树，至多有
________
棵子树。
第
2
页
共
5
页