2013-2014第二学期数据结构期末考试试卷B卷(共4页).doc

《2013-2014第二学期数据结构期末考试试卷B卷(共4页).doc》由会员分享，可在线阅读，更多相关《2013-2014第二学期数据结构期末考试试卷B卷(共4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上合肥学院20 13 至20 14 学年第 2 学期 数据结构与算法设计 课程考试（B）卷 系 级 专业 学号 姓名 题号一二三四五六七八九十总 分得分阅卷大题得分一、选择题：（2分15=30分）1下面关于线性表的叙述错误的是（ ）。A、 线性表采用顺序存储必须占用一片连续的存储空间B、 线性表采用链式存储不必占用一片连续的存储空间C、 线性表采用链式存储便于插入和删除操作的实现装 订 线D、 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。A、 2m-1B、 2mC、 2m+1

2、D、 4m3设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。A、 R-FB、 F-RC、(R-F+M)MD、(F-R+M)M4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。A、 BADCB、 BCDAC、 CDABD、CBDA5设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。A、 n(n-1)/2B、 n(n-1)C、 n2 D、 n2-16设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。A、 9B、 10

3、C、 11D、 127设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。A、 n-1B、 nC、n+1D、2n-18设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。A、 2，3，5，8，6B、 3，2，5，8，6C、 3，2，5，6，8D、 2，3，6，5，89. 设散列表长m=14,散列函数H（K）=K11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是（ ）。 命题教师 胡春玲 共 4 页，第 1 页A、

4、8 B、 3 C、 5 D、 910设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是（ ）。A、线性结构B、 树型结构C、 物理结构D、图型结构11下面程序的时间复杂为（ ）。for（i=1，s=0； i=n； i+） t=1；for(j=1；jnext=head后，该单链表构成 链表。3设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是 。4.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较 次。5.设一棵完全二叉树有128个结点，则该完全二叉树的深度为

5、 ，有 个叶子结点。6.设一组初始记录关键字序列(k1，k2，kn)是小根堆，则对i=1，2，n/2而言满足的条件为 。7.设完全有向图中有n个顶点，则该完全有向图中共有 条有向条。8.解决散列表冲突的两种方法是 和 。大题得分三、应用题：（5分7=35分）1. 在如下数组A中链接存储了一个线性表，表头指针为A0.next，试写出该线性表。小题得分 A 0 1 2 3 4 5 6 7 data605078903440next3572041 2设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找

6、成功时的平均查找长度。小题得分 共 4 页，第 2 页小题得分3下图所示的森林：(1) 求树（a）的先根序列和后根序列； 装 订 线(2) 求森林先序序列和中序序列；3）将此森林转换为相应的二叉树； 小题得分4、请画出下图的邻接矩阵和邻接表。小题得分5已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7；E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 小题得分6画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 共 4 页，第 3 页小题得分7.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。大题得分四、算法设计题：（ 15分）小题得分1设计判断单链表中元素是否是递增的算法。（7分） 小题得分2.设计一个在链式存储结构上统计二叉树中结点个数的算法。（8分） 共 4 页，第 4 页专心-专注-专业