(完整word版)四川大学计算机学院数据结构与算法分析期末试题(2013级B)

1、(完整word版)四川大学计算机学院数据结构与算法分析期末试题(2013级b)(完整word版)四川大学计算机学院数据结构与算法分析期末试题(2013级b) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整word版)四川大学计算机学院数据结构与算法分析期末试题(2013级b)）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步

2、，以下为(完整word版)四川大学计算机学院数据结构与算法分析期末试题(2013级b)的全部内容。本题8页，本页为第8页教务处试题编号： （完整word版）四川大学计算机学院数据结构与算法分析期末试题(2013级b）亲爱的读者：本文内容由我和我的同事精心收集整理后编辑发布到文库，发布之前我们对文中内容进行详细的校对，但难免会有错误的地方,如果有错误的地方请您评论区留言，我们予以纠正，如果本文档对您有帮助，请您下载收藏以便随时调用。下面是本文详细内容.最后最您生活愉快 o（_)o 四川大学期末考试试题（2014-2015学年第1学期）课程号: 课程名称： 数据结构与算法分析（b卷）任课教师： 适

3、用专业年级： 学号： 姓名： 考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行四川大学考试工作管理办法和四川大学考场规则。有考试违纪作弊行为的，一律按照四川大学学生考试违纪作弊处罚条例进行处理。四川大学各级各类考试的监考人员，必须严格执行四川大学考试工作管理办法、四川大学考场规则和四川大学监考人员职责。有违反学校有关规定的，严格按照四川大学教学事故认定及处理办法进行处理。题 号123456789卷面成绩得 分201010101010101010阅卷教师阅卷时间一、单项选择题（每小题 2 分，共20分）1在数据类型中，值不可分解的类型为（ ）。a)原子类型b）结构类型c

4、)固定聚合类型d）可变聚合类型（）。2如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点,则（）存储方式最节省运行时间。a）单链表 b）带头结点的单链表 c）单循环链表 d）带头结点的双循环链表3在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（)结构。a)栈b）队列c）数组d)线性表 4串的长度是（）。a)串中不同字母的个数b）串中不同字符的个数c）串中所含数字的个数d）串中所有字符的个数5一棵深度为5的满二叉树的结点数为（）。a）16b)15c)32d）

5、316采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的(）。a)先序遍历b）中序遍历c）后序遍历d）层次遍历7某二叉树的先序遍历序列与后序遍历序列相反，则此二叉树一定为(）。a）高度等于其结点数b）空或只有一个结点c)任一点无左孩子d）任一结点无右孩子8堆排序的时间复杂度是（）。a）o（1)b）o(n）c）o(n2)d）o(nlogn)9每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（)。a）冒泡排序b）简单选择排序c）希尔排序d）直接插入排序10若需在o（nlogn）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是(）。a）快速排序 b）堆排

6、序 c）归并排序 d）直接插入排序 二、（本题10分）有二叉树中序序列为:abcefghd；后序序列为：abfhgedc;请画出此二叉树。三、（本题10分)已知序列7，31，13，11，20，35,25,8，4，11，24，40，27,请画出此序列列的排序二叉树，分别给出下列操作后的二叉树： (1）插入数据9；（2）删除结点17；（3）再删除结点13.四、(本题10分)如图所示，用prim算法从结点1出发构造出一棵最小生成树，要求图示出每一步的变化情况。五、（本题10分）已知哈希表地址空间为0.8，哈希函数为h(key)=key % 7,采用线性探测再散列处理冲突，将数据序列100，20,21

7、,35,3，78，99,45依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。六、（本题10分）具有n个叶结点的哈夫曼树共有多少个结点？并说明原因。七、（本题10分）给出一组关键字t=(12,2,16,30,8,28，4,10,20,6，18）。写出用下列算法从小到大排序时第一趟结束时的序列。（1）希尔排序（第一趟排序的增量为6）（2)快速排序(选第一个记录为枢轴）八、（本题10分）已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点，nm个度为m的结点.试问该树中有多少个叶子结点？ 九、(本题10分）假设二叉树中每个结点所含数据元素均为单字母,以二叉链表为存储

8、结构,试编写算法按如下图所示的树状显示二叉树.结尾处,小编送给大家一段话。米南德曾说过，“学会学习的人，是非常幸福的人。在每个精彩的人生中，学习都是永恒的主题。作为一名专业文员教职，我更加懂得不断学习的重要性，“人生在勤，不索何获”，只有不断学习才能成就更好的自己.各行各业从业人员只有不断的学习，掌握最新的相关知识,才能跟上企业发展的步伐，才能开拓创新适应市场的需求.本文档也是由我工作室专业人员编辑，文档中可能会有错误，如有错误请您纠正,不胜感激！at the end, xiao bian gives you a passage. minand once said， people who le

9、arn to learn are very happy people.”。 in every wonderful life, learning is an eternal theme。 as a professional clerical and teaching position， i understand the importance of continuous learning, life is diligent, nothing can be gained， only continuous learning can achieve better self. only by consta

10、ntly learning and mastering the latest relevant knowledge, can employees from all walks of life keep up with the pace of enterprise development and innovate to meet the needs of the market. this document is also edited by my studio professionals， there may be errors in the document, if there are errors, please correct, thank you！此处将被文件名替换 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布