外校的数据结构试题和部分讲义答案
需积分: 0 145 浏览量
2008-11-01
19:54:16
上传
评论
收藏 112KB PDF 举报
一、填空题(每空 1 分，共 17 分)
1．在一棵树中，
没有前驱结点。
2．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后
的结果为_
_。
3．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为____，整个堆排序过程的时
间复杂度为_____。
4．有向图的邻接矩阵表示法中某一行非 0 元素的个数代表该顶点的 ，某一列非 0 元素的
个数是该顶点的
。
5．对于下面的带权图 G3，若从顶点 0 出发，则按照普里姆（Prim）算法生成的最小生成树中，
依次得到的各条边为
。
6．由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为 。
7．由三个结点构成的二叉树，共有
种不同结构。
8．若频繁地对线性表进行插入和删除操作，该线性表应该采用
存储结构。
9．图的广度优先搜索类似于树的
次序遍历。
10．在散列法查找中，解决冲突的办法有
等三种。
二．单项选择(每个 1 分，共 10 分)
1．快速分类在( )的情况下不利于发挥其长处。
A. 待分类的数据量太大 B. 待分类的数据相同值过多
C. 待分类的数据已基本有序 D. 待分类的数据值差过大.
2．对有 14 个数据元素的有序表 R[13]进行折半查找，搜索到 R[3]的关键字等于给定值，此时元
素比较顺序依次为（ ）。
A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3]
C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]
3．对外部分类的 K 路平衡归并，采用败者树时，归并的效率与 K( )。
A. 有关 B.无关 C. A、B 都不对
题号 一 二 三 四 五 总 分
分数 12 10 10 8 30 70 分
评论0