




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
-------------各类专业好文档,值得你下载,教育,管理,论文,制度,方案手册,应有尽有---------------------------各类专业好文档,值得你下载,教育,管理,论文,制度,方案手册,应有尽有--------------武汉工业学院2005–2006学年第1学期期末考试试卷(A卷)标准答案及评分标准课程名称数据结构课程编号05110一、填空题(每空1分,共20分)1.四种类型的数据结构分别是:表、树、图和集合。2.假设按低下标行优先存储整数数组时,第一个元素的字节地址是100,每个整数占四个字节,则的存储地址是100,的存储地址是168。3.在顺序表中插入或删除一个元素,平均需要移动n/2个元素,具体移动的元素个数与位置有关。4.二叉树的五种基本形态是空树、只有根节点、根节点和左子树根节点和右子树和根节点、左子树和右子树。(也可用图表示)5.常用的有向图5种存储方法分别是邻接表、逆邻接表、十字链表、邻接矩阵和多重邻接表。6.内部排序算法中的两种基本操作是比较和交换。二、简答题(每小题8分,共40分)请给出以下有向图的:邻接矩阵;(2分)邻接表;(2分)从顶点a出发的深度优先遍历序列;(2分)从顶点e出发的广度优先遍历序列;(2分)解答:(1)、邻接矩阵(2)(2分)邻接表abb^bff^cdd^dv^v^eeufuf^fvv^ua^a^cvbb^(3)abfvucde(其它符合规则的序列也可得分)(4)eufbvaca(其它符合规则的序列也可得分)2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK,请画出该二叉树。解答:该二叉树为:(画错一个分支扣0.5分)3、假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造一棵哈夫曼树并为这8个字母设计哈夫曼编码。解答:哈夫曼树为(4分):(画错一个分支扣0.5分)哈夫曼编码为(4分):(画一个编码扣0.5分)0.07:100 0.32:010.19:001 0.03:000010.02:00000 0.21:110.06:0001 0.10:1014、试从空树开始,画出按以下次序向2-3树(即3阶B-数)插入关键码的建树过程:20,30,50,52,60,68,70。如果此后删除50和68,画出每一步执行后2-3树的状态。解答:顺序插入20,30,50,52,60,68,70的2-3树的状态分别为:(6分,画错一个状态扣0.5分) 删除50和68后2-3树的状态分别为:(2分,画错一个状态扣1分) 5.求出下图的最小生成树,并计算最小生成树的权值。解答:最小生成树为:(6分)最小生成树的权值为:26(2分)三、计算题(共10分)已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79),假设哈希函数为,分别画出以线形探测再散列(存储空间为a[0..15])和链地址法处理冲突的哈希表,并分别计算在记录查找等概率的条件下的平均查找长度。解答:(1)(4分)线形探测再散列存储结构为:0123456789101112131415017968551920842311101427121211311312等概率的条件下的平均查找长度=(1*7+2*3+3*2)/12=1.583(1分)(2)(4分)链地址法的存储结构为:0^1017979^2^3685555^4^5^6198484^720^8^9^10231010^1111^12^13^14142727^15^等概率的条件下的平均查找长度=(1*7+2*5)/12=1.417(1分)四、算法设计。算法描述可以采用类C语言并给出必要注释。(每题10分,共30分)1.试写一算法在带头节点的单链表上实现length(L)。解答:节点类型定义为(2分)typedefstructureLinkNode{ElemTypedata;LinkNodenext; }LinkNode,*LinkPoint;求单链表长度的算法为:(8分)intlength(LinkPointL){intLength=0;LinkPointp; p=L->next;while(!p){Length++;p=p->next;} returnLength;}2.试写一算法实现顺序表的就地逆置,即利用原表的存储空间将线形表逆置为。解答:节点类型定义为(2分)#defineMAXLENGTH100typedefstructureSqList{ElemTypea[MAXLENGTH];intLength;}SqList,数组逆置的算法为:(8分)statustraverlist(SqListLA){for(i=0;i<LA.Length/2;i++)LA.a[i]LA.a[LA.Length–i-1] returnOK;}3、试以单链表为存储结构实现简单选择排序的算法。解答:节点类型定义为(2分)typedefstructureLinkNode{ElemTypedata;LinkNodenext; }LinkNode,*LinkPoint;简单选择排序的算法为:(8分)statusSelectSortLinkList(LinkPointL){//假设单链表带附加头节点intn=Length(l);//求单链表的长度LinkPointp,q,t;for(i=1;i<n;i++){p=q=L->next;while(!q){q=q->next;;if(qdata<pdata)p=q;}//endwhile pp=GetElement(L,&q);//在链表L中,获取q指向的节点,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025版闭口采购合同精简版:范文解读与实施策略
- 二零二五年度出差人员行为规范与培训合同
- 二零二五年度家居用品购销合同范本:现代智能家居产品采购协议
- 二零二五年金融机构视频监控设备采购合同
- 二零二五版工程地质勘察与设计地勘合同示范
- 二零二五年美容院美容原料与产品供应链合同
- 二零二五年度水电安装工程绿色环保技术服务合同
- 二零二五年度艺术装饰地板砖供货合同书
- 2025版一对一家教服务合同范本
- 2025版夫妻自愿离婚房产分割及补偿协议书
- 中国信息通信研究院-算力中心服务商分析报告(2025年)
- 机电运输考核管理办法
- 2025昆明市公安局经济技术开发区分局第二批勤务辅警模拟题带答案
- 赋能“她”力量:职场女性心理健康与成长专题
- 工行技能练兵活动方案
- 酒店服务意识培训材料
- DB42∕T 2232-2024 湖北省水利工程护坡护岸参考设计图集
- 建筑材料供货计划及运输方案保障措施
- 肿瘤防治中心建设
- 安徽国元农业保险股份有限公司招聘笔试题库2025
- 2025年中国苹果干行业市场前景预测及投资战略研究报告
评论
0/150
提交评论