新疆医科大学第二附属医院-新疆医科大学第二附属医院
大连海事大学
2005
年硕士研究生招生考试试题
考试科目：数据结构
适用专业：计算机应用技术、计算机软件与理论
考生须知：
1
、所有答案必须写在答题纸上，写在试题纸上无效；
2
、考生不得在答题纸上作与答题内容无关的标记，否则试卷作废。
< p>
一、判断下列叙述是否正确。请写出题号并用“
√
”“×”回答（共
20
分，每小题
1
分）
1
、若（
u,v
）是连通网络的一条权值最大的边 ，是不论采用何种方法构造该网络的最小生
成树，所构造出的最小生成树一定不包含（<
/p>
u,v
）这条边。
2
、算 法是具有有穷性、确定性、可行性、
0
个或多个输入、
1
个或多个输出特性的一组规
则。操作系统一旦被启动后就永远处在工作或等待状态
，所以，实现“操作系统”的一组
规则不能称为算法。
3
、给定
n
个不同权值的结点，则依据这
n
个结点构造的
Huffman
树的结构是唯一的。
4
、在线索二叉树中，根据线索可以找到树中任何一个结点在相应遍 历序列中的直接前驱或
直接后续。
5
、在线性表的顺序存储结构中，每删除一个数据元素都必须移动表中的数据元素。
6
、在一个
AOE
网中，若某一尘埃的最早开始 时间和最迟开始时间相同，则该活动为关键
活动。
7
、对有序表而言，采用折半查找方法查找表中的数据元素，其查找成功的平均工长度一定< /p>
采用顺序查找方法时的平均查找长度要小。
8<
/p>
、在非空完全二叉树中，若某结点不存在左孩子，则该结点一定是叶子结点。
9
、设
L
是广义表，则取表头运算
< p>Head（
L
）的运算结果一定是单元素，而取表尾运算
Tail
（
L
）的运算结果一定是广义表。< /p>
10
、将一棵树转换成二叉树后，根结点没有右子树。
11
、就平均时间性能而言，快速排序是最优的。所以，对于任意的待排 序序列，选择快速
排序方法进行排序，其执行时间将是最少的。
12
、由于希尔排序的最后
一趟与直接 插入排序过程相同，因此前者一定比后者花费的时间
多。
13
、存在着这样的非空二叉树，不论采用怎样的遍历算法其所得到的遍历序列均相同 。
14
、假设图已经以邻接表存储，，则按深度优先遍 历该图所得到的生成树唯一的。
15
、有向无环图的顶点拓扑排序序列一定是唯一的。
16
、健壮的算法不会因非法的架得住数据而出现莫名其妙的状态。
17
、归并排序算法是稳定的排序算法。
18
、算法的优劣与所用计算机无关，也与所用的算法描述语言无关。< /p>
19
、提高外排序速度的核心工作是减少记录在内外存之 间的
I
／
O
次数。
20
、平衡二叉树中所有结点的平衡因子都不超过
1
。
第
1
页
共
5
页
二、选择填空。（共
20
分，每小题
2< /p>
分）
1
、设循环队列顺序存放在一维数组
[0…m]
中，采用牺牲一个存储的单元的方式区
分队满
与队空的条件，且假设
指向队头元素的位置，
指向 队尾元素的下一个
位置，则判断该队列队满的条件是
________< /p>
。
A. =(+1)MOD m
B
．
=(+1)MOD m+1
C. =(+1) MOD m
D. =(+1)
MOD m+1
E. =(-1) MOD m+1
2
、设
T
是具有
3
个结点的二叉树 ，且
T
的后序序列与中序序列相同，则
T
的形态为
_______
A B C
D E
3
、利 用广义表的
Head(L)
和
Tail(L)
的运 算，将元素
C
从广义表
L
＝
((( (a,b),e,(c,d))))
中分离
出来，其运算表达式为
________
(Head(Tail(Tail(Head(Head(L))))))
(Head(Tail(Tail(Head)))))
(Tail(Tail(Head(Head(L)))))
(Head(Tail(Head(Head(Head(L))))))
(Head(Tail(Tail(Tail(L))))))
4
、设四维数组
B[1..3,2..8,0..5,1..8]
以行主序顺序方法存储在一个连续的存储空间内，每一
个数据元素占一个存储单元，且
B[1,2,3,4]
的存储地址是
2000,
则
B[2,3,4,5]
的存储地址是
________
A.2391
B.2392
C.2393
D.2394
E.
全错
< br>5
、设
T
是一棵二叉树，
Nh
表示深度为
h
的平衡二叉树的最少结点数，则深度为
h(h>0 )
的
T
中最少结点数是
________ _
B.
N
h-1
+
N
h-2
-1
C.
N
h-1
+N
h-2
+2 D.
N
h-1
+N
h-2
+1
A.N
h-1
+N
h-2
-2
E.
N
h-1
+N
h-2
6
、若一棵哈夫曼
(Huffman)
树中共有
9
个结点，则其叶子结点数为
____
个。
A.3 B.4 C.5 D.6 E.7
7
、在一棵深度为
3
的树中，若有
2
个度为
3
的结点和
1
个为
2
的结点 ，则度为
0
的结点有
_______
个。
A.4 B.5 C.6 D.7 E.3
8
、设结点
x
和
y
是二叉树中的任 意两个结点，在该二叉树的先根遍历序列中
x
在
y
之前，
而在其后根遍历序列中
x
在
y
之后，则
x
和
y
的关系是
________
。
A.x
是
y
左兄弟
B. x
是
y
右兄弟
C
.
x
与
y
没有必然关系
D.
x
是
y
的后裔
E.
< p>x是
y
的
祖先
9
、以下给定的序列中，不满足堆定义的是
________ __
。
A.(97,87,93,79,82,62,84,42,22,12,68)
B.(97,93,87,84,82,79,68, 62,42,22,12)
C.(97,87,42,79,82,62,68,93,84,12,22)
D.(12,22,42,62,68,79,82,84,87,93,97)
E.(97,93,87,79,82,62,84,42,22,12,68)
10
、若一个具有
n
个结点、
k
条边的非连通无向图是一个森林
(n>k)
，则该森林中必有< /p>
_____
第
2
页
共
5
页