2007年数据结构期末试卷_第1页
2007年数据结构期末试卷_第2页
2007年数据结构期末试卷_第3页
2007年数据结构期末试卷_第4页
全文预览已结束

下载本文档

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

文档简介

PAGEPAGE3软件学院2006级<<数据结构>>期终试题2007.12.30姓名学号12345678得分填充题（20分，每题5分）1)树的机内表示(实现)有、、。2）最小代价生成树有两种实现算法：Prim算法与Kruscal算法。两者分别适用于何种情况,。3）采用堆排序方法将初始序列{8,23,12,5,28}按从小到大顺序排序,则建立初始堆和排序过程中序列依次变化为、、、、。4)在具有6个结点的无向简单图中，边数最少为11条时，才能确保该图一定是连通图。2．算法分析题（10分）利用大“O”记号将下列函数在最坏情况下运行时间表示为n的函数（要求给出推导过程）voidmystery(intn){for(inti=1;i<=n-1;i++)for(intj=i+1;j<=n;j++)for(intk=1;k<=j;k++){SomestatementrequiringO(1)time}}答：3．（15分，每题5分）1）设有一字符串P=”3*y-a/y↑2”,试写出利用栈将P改为”3y*ay2↑/-”的操作步骤。（请用X代表扫描该字符串过程中顺序取一字符进栈的操作，用S代表从栈中取出一字符加入到新字符串尾的出栈操作。例如，要使”ABC”变为”BCA”，则操作步骤为XXSXSS）。答：2)设数组Q[m]表示一个环形队列（下标为0到m–1）,rear为队列中最后一个元素的实际位置，length为队列中元素的个数,求队列中第一个元素的实际位置（要求写出计算公式）答：3)试说明一棵二叉树无论进行先序、中序或后序遍历，其叶结点的相对次序不发生改变。答:4．(10分)对下列无向图，按照Dijkstra算法,写出从顶点1到其它各个顶点的最短路径和最短路径长度。（顺序不能颠倒）10586911710586911777246答：5.（10分）设散列表长度为11,散列函数H(K)=(K的第一个字母在英文字母表中的序号，设A的序号为1)%11,若输入顺序为(B,D,M,CI,I,K,TM,X),处理冲突方法为线性探测法,要求：1)构造此散列表。2).对表中所有键值分别查找1次,求出总的比较次数。答：6.（10分，每题5分）下列各图都是平衡二叉树，请按指定的关键码插入，分别画出插入后的平衡二叉树。1525插入56792036518502）MARAUGMAY插入FEB (按字母顺序)APRJANNOVDECJULY答：7.(10分)假设一棵带索引的二叉搜索树，root指向其根结点，树中每个结点具有如下形式：Lsizeleftdataright其中，Lsize域的值为该结点左子树中的结点个数加1；left,right分别指向该结点的左、右子树，且假设data域为int型。试用java语言写一个递归的findk函数，即搜索这棵带索引的二叉搜索树中第K个小的关键码结点。答：8.（15分）已知（k1,k2,k3,…,kn）是一个最小堆，试写一个函数将（k1,k2,k3

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论