发布时间 : 星期五 文章全国自考数据结构历年试题及部分答案(2009--2013) - 图文更新完毕开始阅读
14. 分块查找方法将表分为多块，并要求()
A. 块内有序 B. 块间有序 C. 各块等长 D. 链式存储
答案：B
15.
便于进行布尔查询的文件组织方式是()
A. B. C. D.
答案：
顺序文件 索引文件 散列文件
多关键字文件
二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请 在每个空格中填上正确答案。错填、不填均无分。
1. 数据的链式存储结构的特点是借助___表示数据元素之间的逻辑关系。
答案：指针
2. 如果需要对线性表频繁进行___或___操作，则不宜采用顺序存储结构。
答案：插入 删除
3. 如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是
top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是___。
答案：top1>top2(或top2=top1-1或top1=top2+1)
4. 静态存储分配的顺序串在进行插入、置换和___等操作时可能发生越界。
答案：联接
5. 广义表L=（a，（b，( )））的深度为___。
答案：3
6. 任意一棵完全二叉树中，度为1的结点数最多为___。
答案：1
7. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中___的数目正相关。
答案：边
8. 在5阶B树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含___个关键字。
答案：2
9. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是___的。
答案：稳定
10. 常用的索引顺序文件是___文件和___文件。
答案：ISAM VSAM
三、解答题(本大题共4小题，每小题5分，共20分)
1.
答案：
2. 由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电
文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。 答案：eatst(说明：每个字母1分)（5分）
3. 已知无向图G的邻接表如图所示，
(1)画出该无向图；
(2)画出该图的广度优先生成森林。 (1) (2)
答案：(1)
(说明：每错1个顶点或边，扣0.5分， 扣完3分为止) （3分） (2)
(说明：每错1个顶点或边，扣0.5分，
扣完2分为止) （2分）
4. 对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根
)堆及前两趟重建堆之后的序列状态。 初始堆： 第1趟：
第2趟：
答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分） 第1趟：（63，55，50，48，22，31，11，37，96）（2分）
第2趟：（55，48，50，37，22，31，11，63，96）（1分）
(本大题共4小题，每小题5分，共20分)
1. 阅读下列算法，并回答问题：
(1)无向图G如图所示，写出算法f30(&G)的返回值； (2)简述算法f30的功能。 #define MaxNum 20
int visited［MaxNum］；
void DFS(Graph *g，int i)；
/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited［j］为1*/ int f30(Graph *g) {int i，k；
for (i=0； i
for (i=k=0； i
DFS(g，i)；
}
return k；
}
(1) (2)
答案：（1）3（3分）
（2）返回无向图g中连通分量的个数。（2分）
四、算法阅读题