-、单项选择题，在括号内填写所选择的标号{每小题2分，共18分)
1.下面算法的时间复杂度为( )。
int f(unsignedint n) {
if(n==0II n==1)return 1;
elsereturn n赞f(n-1);
A. 0(1)
c. 0(n
2
)
B. O(n)
'0. O(n!)
2. 在产个长度为n的线性表中顺序查找一个值为x的元素时，在等概率的情况下，查找
成功时的平均查找长度为( )。
A. ri
C. (n+1)/ 2
B. n/2
D. (n一1) /2
3. 己知L是一个单链表的表头指针， 在表头插入结点铸p的操作是( )。
A. p=L;p一>1ink=L;
B. p--二>link=L; p=L;
c. p一>1ink=L; L=p;
D. L=p;p一>1ink=L;
81
4. 在一棵二叉树的链接存储中，每个存储结点至少要包含( )个指针域。
1144qJ 叮L
ABCD
5. 在一棵完全二叉树中，若编号为i 的结点存在左子女，则左子女结点的编号为( ) ,
假定树根结点的编号为0。
A.2i B. 2i-1
C. 2i+1 D. 2i+2
6. 对长度为10的线性有序表A[10]进行折半查找，若查找到元素A[l]时成功，则查找
长度为( )。
A. 1
C. 3
B. 2
D. 4
7. 若一棵二叉树共有5层结点，则最后一层的结点数最多为( )个结点。
nLPO
A斗 。o nd 1A
ABCD
8. 设一个有向 图具有n个顶点和E条边，若采用邻接表作为其存储结构，则空间复杂度
为(\)。
A. O(nX!ogze)
B. O(n+e)
C. O(n)
D. O(nZ
)
9. 在一棵m阶B树中，树根结点所包含的关键码个数至少为( )。
A. 1 B. 2
C. m/2 D. m一l
82
得分|评卷人
二、判断题，在每小题后面的括号内打对号(.J)表示叙述正确或打叉
号( X)表示叙述错误{每小题2分，共14分}
10. 钱和队列都是运算受到限制的线性表。 ( )
11. 用字符数组存储长度为n的字符串，该数组长度至少为no ( )
12. 在用循环单链表表示的链式队列中， 可以不设队头指针，仅在链尾设置队尾指针。
( )
13. 邻接矩阵最适用于稀疏图的表示，邻接表最适用于稠密图 的表示。 ( )
14. 对一个元向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。
( )
15. 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。
( )
16. 图 中各个顶点的编号是人为的，不是它本身固有的， 因此可以根据需要进行改变。
( )
得分i评卷人
三、填空题，在横线处填写合适的内容(每小题2分，共14分)
17. 在队列数据结构中，对数据操作的特点是先进 。
。
个结点。假定树根结点的高
。
18. 设顺序钱的最大容量为MaxSize， top==一1 表示战空，则判断找满的条件是top=
-、 。
19. 在一棵高度为4的完全二叉树中， 最多包含有
度为0。
20. 在一个最大堆中，堆顶结点的值是所有结点中的
21. 具有n个顶点的连通图的生成树含有 条边。
22. 在对n个结点进行的堆排序中，对任意一个分支结点进行调整(筛)运算的时阅复杂
度为
23. 假定一个线性表的关键码序列为(12，23，74，55 ，63，4日，若按key%3条件进行划分，
使得同一余数的元素成为一个子表，则元素74所在子表的长度为
83
得分|评卷人
四、运算题{每小题8分，共40分}
24. 假定一棵二叉树的广义表表示为A(B(， D(G? ,C(E,F? ， 分别写出对它进行先序、
中序和按层遍历的结果。
先序:
中序z
按层:
25. 已知一个有序表(15，26，34，39， 屿，56 ，58 ，63，74，76， 邸，94)顺序存储于一维数组
a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34、56、58、63时的 比较次数。
元素 | 34 I56 I58 I63
比较次数
26. 假定一个线性表为(56，27 ，34，95，73，16，50，62)，根据此线性表中元素次序生成一棵
二叉搜索树，分别求出该二叉搜索树中的分支结点数和叶子结点数。
分支结点数:
叶子结点数:
27. 已知一个带权图的顶点集V和边集G分别为z
V={0,1,2 ,3 ,1,5};
.,
、tpL
nhu' 、BJ
F气U
,
A哇
，，‘、
,
n6 Ti 、‘/
A哇
,
qJ r飞
,
唱'A
42A 、‘，，，
A哇
,
?午
，，‘、
'
俨气U
、‘，，，
F气U
,
咱EA
f飞
,
PO 咽'4
、‘/
内/
,
咱EA
''飞
,
A哇
TI 、，/
句气U
,
nu rz飞
,
咱EA
q臼
、sj
nL
,
nu f飞
,
QU 唱'A
、‘，，，
唱i
,
AU ra飞
{ E
试根据普里姆算法，从顶点O出发，求出其最小生成树，在下面横线上填写依次得到的最
小生成树中的每条边。
, , , , 。
84
得分|评卷人
五、算法分析题(每小题7分，共14分}
29. 该算法功能为:从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同
的多余元素(只保留一个结点)，并释放被删结点的动态存储空间。阅读算法，在划有横线的上
面填写合适的内容。
voidpurge-linkstCListNode铸&. la)
ListNode铃p， 铃q;
ifCIa= =NULL)return;
;
\
q=la;p=la一>link;
whileCp){
if(p一>data>q一>data){q=p;p=p一>link;}
else{ //删除并回收p结点
q一>link=
deleteCp);
p=
85
30. 已知二叉树中的结点类型BinTreeNode定义为2
structBinTreeNode{ElemTypedata; BinTreeNode铃left，祷right; } ;
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。 下面函数的功
能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算
法，在划有横线的上面填写合适的内容。
BinTreeNode铸BTF(BinTreeNode铃BT， ElemTypex)
if(BT==NULL)NULL;
else{
if(BT一>data==x)
else{
BinTreeNode秘t;
86
jf(t=BTF(BT一>left, x))return t;
if(t= ) return t;
return NULL;
，、
试卷代号: 1010
中央广播电视大学2011 2012学年度第二学期 开放本科 期末考试
数据结构试题答案及评分标准
(供参考)
2012年7月
一、单项选择题，在括号内填写所选择的标号(每小题2分，共18分}
1. B
6. B
2. C
7. D
3. C
8. B
4. D
9. A
5. C
二、判断题，在每小题后面的括号内打对号( .J)表示叙述正确或打叉号(X)表示叙述错误(每
小题2分，共14分}
10. .J(对) 11. X(错) 12. .J(对) 13. X(错)
14. .J(对) 15. X(错) 16. .J(对)
三、填空题，在横线处填写合适的内容(每小题2分，共14分)
17. 先出
18. MaxSize-1
19. 31
20嗖 最大值
21. i'l,- 1
22. 。叫ogz n)
23. 2
四、运算题(每小题8分，共40分)
24.先序:A，B，D，G，C ，E，F //3分
中序: B， G， D， A， E， C， F 1/3分
按层: A， B. C， D， E， F， G //2分
25. 元素 34 56 58 63
比较次数
/1得分
2 1 3 4
2分2分2分2分
87
26. 分支结点数: 5 114分
叶子结点数: 3 114分
27. (0,3)14, (3,4)18, (4,5)6, (5,1)5, (4,2)11
II得分:2分
28.
2分 2分 1 分 1分
19 40 68
5 6 l
1 2 4
3分 3分 2分
元素z
存储位置z
查找长度z
得分z
五、算法分析题( 7分，共14分}
评分标准:每小题对一空得4分，全对得7分。
29. p一>l ink、q一>link
30. return BT、BTF(BT一>right， 对