模拟题数据结构与算法答案及评分标准_第1页
模拟题数据结构与算法答案及评分标准_第2页
模拟题数据结构与算法答案及评分标准_第3页
全文预览已结束

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

长江师范学院课程考核参考答案及评分标准数据结构与算法XXXX-XXXX学年第X学期第3页共3页数学与计算机学院出题教师：XXXXX课程考核 参考答案及评分标准 考试课程：数据结构与算法模拟试题 学年学期：20XX-20XX学年第1学期试卷类型：X考试用时：120分钟适用专业：数学与计算机学院计算机科学与技术(软件)专业XXXX级层次：本科一、选择题（每小题2分，共30分）123456789101112131416CACDBABCBDCBBDA二、判断题（每小题1.5分，共9分）123456×××√×√三、填空题（每空1分，共25分）1、集合、线性结构、树型结构、图状结构2、时间复杂度、空间复杂度3、p->next!=NULL4、n-i+1、n-i5、2，3、1006H6、表中的数据元素全部是字符，通常是一个串整体作为操作对象7、串长相等、对应字符相等8、2i-1、(n+1)/2、(n-1)/29、2n、n-1、n+110、n(n-1)/2、n(n-1)11、邻接矩阵、邻接链表12、{D,Q,F,X,A,P,B,N,M,Y,C,W}四、设有数据结构（D，R），其中D={1,2,3,4,5,6}，R={<1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}。试画出其逻辑结构图并指出属于何种结构。（5分）12123456属于图状结构五、将下面图1所示的树转换为二叉树，图2所示的二叉树转换为树或森林。（6分）解答：图1转换成的二叉树 图2所示的二叉树转换成的森林六、对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度，并写出各个权对应的哈夫曼编码。（6分）解答：构造的哈夫曼树如图3图3树的带权路径长度为：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=120各个权对应的哈夫曼编码：5（001），2（1111），9（10），11（11），8（101），3（1110），7（100）七、图3所示是一个无向带权图，请分别按Prim算法求最小生成树，并计算生成树的代价。（5分）解答：生成的最小生成树如图4，最小生成树的代价为：3+4+1+4+2=14114423abcdef图4生成的最小生成树八、设散列函数hashf(x)=xmod11,散列表的地址空间为0-10，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。（6分）（1）使用线性探测再散列法构造的散列表。012345678910331131234382722（2）使用链地址法构造散列表。022343322343311211212131334272753838678910九、设要将序列（12，5，9，20，6，31，24）中的关键码按升序排列（8分）（1）起泡排序一趟扫描的结果：（5，9，12，6，20，24，31）（2）是增量为4的希尔排序一趟扫描的结果：（6，5，9，20，12，31，24）（

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论