文档介绍：试卷代号: 1 0 1 0 座位号
中央广播电视大学 2 0 11 2012 学年度第二学期" 开放本科" 期末考试
数据结构试题
2012 年7 月
一
题号一四五总分
一
分数
得分|评卷人
-、单项选择题,在括号内填写所选择的标号{每小题 2分,共 1 8分)
( )。
int f( unsigned int n) {
if(n= =0 II n= = 1) return 1;
else return n 赞f(n- 1) ;
A. 0 (1 ) B. O(n)
2
c. 0(n ) '0. O(n!)
2. 在产个长度为 n 的线性表中顺序查找一个值为 x 的元素时, 在等概率的情况下, 查找
成功时的平均查找长度为( )。
A. ri B. n/2
C. (n+1)/ 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. 在一棵二叉树的链接存储中, 每个存储结点至少要包含( )个指针域。
ABCD1144qJ
叮
L
5. 在一棵完全二叉树中, 若编号为 i 的结点存在左子女, 则左子女结点的编号为( ) ,
假定树根结点的编号为 0。
A. 2i B. 2i-1
C. 2i+1 D. 2i+2
6. 对长度为10 的线性有序表A[10]进行折半查找, 若查找到元素A[l]时成功, 则查找
长度为( )。
A. 1 B. 2
C. 3 D. 4
7. 若一棵二叉树共有5 层结点, 则最后一层的结点数最多为( )个结点。
A
ABCD斗
。
o
n
d1 nLPO
A
8. 设一个有向图具有 n 个顶点和 E 条边, 若采用邻接表作为其存储结构, 则空间复杂度
为(\)。
A. O(nX!ogze)
B. O(n+e)
C. O(n)
Z
D. O(n )
9. 在一棵 m 阶B 树中, 树根结点所包含的关键码个数至少为( )。
A. 1 B. 2
C. m/2 D. m 一 l
82
得分|评卷人
二、判断题,在每小题后面的括号内打对号( .J )表示叙述正确或打叉
号( X )表示叙述错误{每小题 2分,共 1 4分}
10. 钱和队列都是运算受到限制的线性表。( )
1 1. 用字符数组存储长度为 n 的字符串, 该数组长度至少为 n o ( )
12. 在用循环单链表表示的链式队列中, 可以不设队头指针, 仅在链尾设置队尾指针。
( )
13. 邻接矩阵最适用于稀疏图的表示, 邻接表最适用于稠密图的表示。( )
14. 对一个元向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。
( )
15. 在索引顺序结构的搜索中, 对索引表只可以采取顺序搜索, 不可以采用折半搜索。
( )
16. 图中各个顶