当前位置:首页 >> 其它课程 >>

数据结构期末6


班密 级 :
封 装 订 线

4.

下图所示二叉树存储在一维数组中,则元素 F 的下标位置为______。 A B C

信息技术学院 2006-2007 学年第二学期期末考试 数据结构 试卷 6(适用班级: )
(答题时间:100 分钟,满分:100 分)
题 得 号 分 5. 得 分 第一部分 第二部分 第三部分 第四部分 总 分 核分人 D E

专业: 姓名: 考号:

F

对于一个具有 n 个顶点的图,若采用邻接矩阵表示,则矩阵大小为______。

6. 若要对某二叉排序树进行遍历,保证输出元素的值序列按增序排列,应对该二叉排 序树采用____________遍历法。 7. 元素关键字转换为该元素存储位置的函数 f 称为____________。 8. 先将整个待排序列分割成若干子序列分别进行直接插入排序,待整个序列“基本有 序”时,再对全体进行一次直接插入排序,此种排序方法叫做____________排序。 9. 假定一组数据的关键字为{46,79,56,38,40,84},则以第一个记录为枢轴,对其进 行第一趟快速排序的结果为__________________。 10. 对 20 个记录进行归并排序时,共需要进行______趟归并。

评卷人 一、判断题(10 分,每题 1 分) 1. 进行折半搜索的表必须是顺序存储的有序表。 ( ) 2. 对于同一组记录,生成二叉搜索树的形态与插入记录的次序无关。 ( ) 3.用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中 的顶点个数有关,而与图的边数无关。 ( ) 4. 在 AOE 网络中一定只有一条关键路径。 ( ) 5. 对一个有向图进行拓扑排序,一定可以将图的所有顶点按其关键码大小排列到一个拓扑 有序的序列中。 ( ) 6. 当输入序列已经基本有序时,起泡排序需要比较关键码的次数,比快速排序还要少。 ( ) 7. 装载因子是散列表的一个重要参数,它反映了散列表的装满程度。 ( ) 8. 若用 m 个初始归并段参加 k 路平衡归并排序,则归并趟数应为?log2m?。( ) 9. 堆排序是一种稳定的排序算法。( ) 10. 任何基于排序码比较的算法,对 n 个数据对象进行排序时,最坏情况下的时间复杂度都 不会大。( ) 得 分 二、填空题(20 分,每题 2 分) 1. 假定一棵树的广义表表示为 A(B(C, D(E, F,G), H(I, J))),





评卷人 三、选择题(20 分,每题 2 分) 1. A. 0 2. 在一棵树中,每个结点最多有______个直接前驱结点。 B. 1 C. 2 D. 任意多个

评卷人

由权值分别为 3, 8, 6, 2, 5 的叶子结点生成一颗赫夫曼树,它的带权路径长度为______。 B. 48 C. 72 D. 53

A. 24 3. A. 2 4.

则结点 D 的双亲结点为______。 2. 在一棵二叉树中, 度为 2 的结点有 5 个, 度为 1 的结点有 6 个, 那么叶子结点有______ 个。 3. 一棵深度为 5 的满二叉树的结点总数为______个。

一棵树的广义表表示为 a(b(c), d(e(g(h)), f)),则该二叉树度为 2 的结点数为______。 B. 3 C. 4 D. 5

一个连通图的生成树是包含图中所有顶点的一个______子图。 B. 连通 C. 极小连通 D. 无环

A. 极小 5.

具有 e 条边的有向图,它的邻接表中有______个弧结点。

第 1 页 共 3 页

A. e-1 6.

B. e

C. 2(e-1)

D. 2e

有向图的一个顶点的度为该顶点的______。 B. 出度 C. 入度与出度之和 D. (入度+出度)/2 先序序列: 中序序列: 2. 利用克鲁斯卡尔算法,画出构造下图最小生成树的过程。 分) (6 12 0 6 4 1 12 2 5 9 6 16 20 3 10 4 8 15 5 13

A. 入度

7. 适于对动态查找表进行高效率查找的组织结构是______。 A. 有序表 B. 顺序表 C. 二叉排序树 D. 链表

8. 对线性表进行折半查找时,要求线性表必须______。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储,且元素按关键字有序排序 D. 以链接方式存储,且元素按关键字有序排序 9. 用某种排序方法对关键字序列(23,72,21,47,15,27,59,35,20)进行排序时, 前三趟的结果情况如下: 23,21,47,15,27,59,35,20,72 21,23,15,27,47,35,20,59,72 21,15,23,27,35,20,47,59,72 则所采用的排序方法是______。 A.选择排序 B.起泡排序 C.归并排序 D.快速排序

10. 在对 n 个元素进行简单选择排序的过程中,需要进行______趟选择和交换。 A. n/2 得 分 B. n-1 C. n D. n+1

3.已知树 T 的中序遍历序列为 GDBHEIACF,先序遍历序列为 ABDGEHICF,请画出树 T, 写出后序遍历序列。 分) (6

评卷人 四、应用题(30 分) 1. 写出下图所示森林的先序、中序序列。 分) (6 1 9 11 12

2

10

13

14

3

4

5

15

6

7

4. 已知一组关键字为(26,36,41,38,44,15,68,12,06,51,25),用线性探测 第 2 页 共 3 页

8

再散列解决冲突, 构造这组关键字的哈希表。 其中, 表长取 13, 哈希函数 f(k)=k mod 13。 分) (6

int Search_Bin(SSTable ST, KeyType key){ //在有序表 ST 中折半查找其关键字等于 key 的数据元素,若找到,则返回该元素 //在表中的位置,否则返回 0 low=1;high=ST.length; while(low<=high){ mid=____________; if(EQ(key, ST.elem[mid].key)) return ____________; else if(LT(key, ST.elem[mid].key)) high=____________; else low=____________;

5. 已知一组元素的关键字{46,74,16,53,14,26,40,38,86,65,27,34},利用堆排序法, 画出建立小顶堆和利用堆排序的过程。 分) (6 }

} return ____________;

2. 将下面算法填完整。(10 分,每空 2 分) void InsertSort(SqList &L){ //对顺序表 L 作直接插入排序 for(i=2;i<=L.length;++i) if(LT(L.r[i].key, L.r[i-1].key)){ L.r[0]= ____________; L.r[i]= ____________; for(j=____________;LT(L.r[0].key, L.r[j].key);--j) L.r[j+1]= ____________; L.r[j+1]= ____________; } }





评卷人 五、程序题(20 分) 1. 将下面算法填完整。(10 分,每空 2 分) 第 3 页 共 3 页


相关文章:
数据结构与算法分析_六套期末复习题(含答案)
数据结构与算法分析_六套期末复习题(含答案)_工学_高等教育_教育专区。数据结构与算法分析_期末复习题(含答案) 四川大学试题一一、单项选择题(每小题 2 分,共...
《数据结构》期末考试试题及答案
数据结构期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院...(A) 、k-1 (B) 、k (C) 、k-1 和 k (D) 、1 至 k 6. 具有 ...
数据结构试卷及答案6
数据结构试卷及答案6_IT认证_资格考试/认证_教育专区。数据结构有关试卷中...原 工 学第 院 2 学期 课程期末试卷重修标识 A卷 2006~2007 学年 7. 若...
长沙理工大学 2014-2015学年一学期数据结构期末考试试卷6
长沙理工大学 2014-2015学年一学期数据结构期末考试试卷6_研究生入学考试_高等教育_教育专区。长沙理工大学计算机与通信工程学院 2014-2015 学年一学期数据结构期末...
数据结构期末复习题及答案6
十套数据结构试题及答案 40页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 数据结构期末复习题及答案6 数据结构复...
数据结构期末习题答案
数据结构期末习题答案_工学_高等教育_教育专区。数据结构期末习题答案 ...√ 8.× 9. √ 10.× 2.C 3.D 4.C 5.C 6.B 7.D 8.C 9.D ...
《数据结构》期末考试试题及答案
数据结构期末考试试题及答案 (2003-2004 学年第 2 学期) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1.对于...
大学数据结构期末考试试题(有答案)
大学数据结构期末考试试题(有答案)_计算机软件及应用_IT/计算机_专业资料。大学...· 6.在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定——该结点...
数据结构期末考试复习总结
} } 5 1204 班 学委精心整理 数据结构期末复习 该算法的功能是: 递归地后序...(___BST->right __,item); }//if } 六、编写算法(共 8 分) 统计出单...
数据结构期末考试题
数据结构期末考试题_从业资格考试_资格考试/认证_教育专区。一、 单选题(每题 ...已知一个图的顶点集 V 和边集 E 分别为: V={1,2,3,4,5,6,7}; E=...
更多相关标签: