欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > DOC文档下载  

    数据结构形考作业答案.doc

    • 资源ID:5656302       资源大小:145KB        全文页数:12页
    • 资源格式: DOC        下载积分:4
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要4
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构形考作业答案.doc

    数据结构(本)形考作业1参考答案:一、单项选择题1C 2D 3C 4C 5D 6C 7C 8C 9A 10B二、填空题 1n-i+1 2n-i 3.集合、线性表、树、图 4. 存储结构、物理结构 5.线性表 图6. 有穷性、确定性、可行性、有输入、有输出 7. 图 8.树 9. 线性表 10 n-1 O(n)11s->next=p->next; 12head 13q->next=p->next; 14p->next=head; 15单链表 16顺序存储 链式存储 17存储结构 18.两个 后继结点 前驱结点 尾结点 头结点19指向头结点的指针 指向第一个结点的指针 20链式 链表三、问答题1简述数据的逻辑结构和存储结构的区别与联系,它们如何影响算法的设计与实现?答:若用结点表示某个数据元素,则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见,数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同,逻辑上相邻的结点,其物理地址未必相同,但可通过结点的内部信息,找到其相邻的结点,从而保留了逻辑结构的特点。采用的存储结构不同,对数据的操作在灵活性,算法复杂度等方面差别较大。2解释顺序存储结构和链式存储结构的特点,并比较顺序存储结构和链式存储结构的优缺点。答:顺序结构存储时,相邻数据元素的存放地址也相邻,即逻辑结构和存储结构是统一的,要求内存中存储单元的地址必须是连续的。优点:一般情况下,存储密度大,存储空间利用率高。缺点:(1)在做插入和删除操作时,需移动大量元素;(2)由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;(3)表的容量难以扩充。链式结构存储时,相邻数据元素可随意存放,所占空间分为两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。优点:插入和删除元素时很方便,使用灵活。缺点:存储密度小,存储空间利用率低。3什么情况下用顺序表比链表好?答:顺序表适于做查找这样的静态操作,链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大,且其主要操作是查找,则采用顺序表;如果线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。 4解释头结点、第一个结点(或称首元结点)、头指针这三个概念的区别?答:头结点是在链表的开始结点之前附加的一个结点;第一个结点(或称首元结点)是链表中存储第一个数据元素的结点;头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。5解释带头结点的单链表和不带头结点的单链表的区别。答:带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上,带头结点的单链表,不管链表是否为空,均含有一个头结点,不带头结点的单链表不含头结点;在操作上,带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点,算法步骤都相同。不带头结点的单链表,其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空:1(1) p->data=i; (2) p->next=NULL; (3) q->next=p; (4)q=p;2. (1) head=p; (2) q=p; (3) p->next=NULL; (4) p->next=q->next (5) q->next=p;3. (1) p=(NODE *) malloc (sizeof(NODE); (2) p->data=x;五、完成:实验1线性表根据实验要求(见教材P201-202)认真完成本实验,并提交实验报告。数据结构(本)形考作业3参考答案:一、单项选择题1B2B3D4C5B6A7A8B9A10. D11.A12C13D14B15B16B17无18A19C20B21A22B23.B24.B25. C26.A27A28C二、填空题1出度和入度之和2.树中结点的度的最大值3.分支结点非终端结点4.叶子结点终端结点5. 逻辑后继直接后继结点孩子结点 6.祖先结点7.从根结点开始到叶结点的最大路径长度8. Log2n+1(上取整)9. 根结点 左子树 右子树 10. 左子树根结点 右子树11.左子树 右子树根结点 12.权13.带权路径长度之和 14.最优二叉树值最小的二叉树 15.6916.2m-1 17. 多对多m:m 18.每个结点1次19.先根20.后根21.n*n22.邻接矩阵邻接表23.n-124. n-125.栈三、综合题1写出如下图所示的二叉树的先序、中序和后序遍历序列。答:二叉树的定义是递归的,所以,一棵二叉树可看作由根结点,左子树和右子树这三个基本部分组成,即依次遍历整个二叉树,又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分.,这样划分一直进行到树叶结点。(1)先序为“根左右”,先序序列为:fdbacegihl(2)中序为“左根右”,中序序列为:abcdefghij(3)后序为“左右根”,后序序列为:acbedhjigf2已知某二叉树的先序遍历结果是:A,B,D,G,C,E,H,L,I,K,M,F和J,它的中序遍历结果是:G,D,B,A,L,H,E,K,I,M,C,F和J,请画出这棵二叉树,并写出该该二叉树后续遍历的结果。(1)二叉树图形表示如下:(2)该二叉树后序遍历的结果是:G、D、B、L、H、K、M、I、E、J、F、C和A。3答 已知深度为k的二叉树最多有2k-1个结点(K1),29-1<892< 210-1,故树的高度为10 对于完全二叉树来说,度为1的结点只能是0或1因为n=n0+n1+n2和n0=n2+1得:设n1=0,892=n0+0+n2=2n2+1得n2不为整数出错设n1=1,892=n0+1+n2=2n2+2得n2 =445 n0=n2+1=446叶子结点数为446。 由得单支结点数为1 对于n个结点的完全二叉树,最后一个树叶结点,即序号为n的叶结点其双亲结点即为最后一个非终端结点,序号为892/2=446。4(1)先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树(2)中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树(3)先序和后序序列相同的二叉树为空树或仅有一个结点5(1)哈夫曼树如图B-4所示。(2)其带权路径长度WPL值为270。(3)每个字符的哈夫曼编码为:A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:016答(1)深度优先遍历:v1,v2,v3,v8,v5,v7,v4,v6广度优先遍历:v1,v2,v4,v6,v3,v5,v7,v8(2) G的拓扑序列为:v1,v2,v4,v6,v5,v5,v3,v5,v7,v8(3)最短路径为:v1,v2,v5,v7,v87g1的图示和图g1的邻接表如下图所示。图G的邻接矩阵如下图所示:V1、V2、V3、V4、V5的度分别为:2,3,2,3,2四、程序分析题1. (1) return c1+1(2) NodeLevel(BT->right,X)(3) (c2>=1) return c2+12(1)for(j=0; j<n; j+)(2)dfstree(GA,j,n);五、算法设计题1写一个将一棵二叉树复制给另一棵二叉树的算法。define NULL 0typedef struct btnodeelemtype data;struct btnode *lchild, *rchild;bitnode, *bitree;if ( p!=NULL )t=(bitnode *)malloc (sizeof (bitnode);t->data=p->data;t->lchild=CopyTree(p->lchild);t->rchild=CopyTree(p->rchild);return(t);elsereturn(NULL);2.int BTreeLeafCount(struct BTreeNode* BT)if(BT=NULL) return 0;else if(BT->left=NULL && BT->right=NULL) return 1;else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);六、完成:实验3栈、队列、递归程序设计,实验4图的存储方式和应用根据实验要求(见教材P203)认真完成本实验,并提交实验报告。数据结构(本)形考作业4参考答案 (2009-03-31 20:19:06)转载标签:教育分类:作业辅导作业4部分答案一、单项选择题1D 2C3C4C 5D6A7C8D9B10D11A12C 13A14C15D16B17B18D19D20D21D22D23A24A25C26D27B28A29B30C二、填空题1.散列2.特征项数据元素3.主键4.平均值5.顺序6.二分查找 升序有序7.顺序存储8.索引查找顺序查找9.小于根结点的值大于(或大于等于)根结点的值10.自变量地址值11.9, 14, 16 ,1712内部排序外部排序13交换排序143154816堆排序快速排序17主关键字18关键字相等的记录19n-1,n-j20堆尾堆顶向下三、综合题1已知序列(70,83,100,65,10,32,7,9),请写出对此序列采用插入排序法进行升序排序时各趟的结果。答:原始序列:(70),83,100,65,10,32,7,9第1趟: (70,83),100,65,10,32,7,9第2趟:(70,83,100),65,10,32,7,9第3趟:(65,70,83,100),10,32,7,9第4趟:(10,65,70,83,100),32,7,9第5趟:(10,32,65,70,83,100),7,9第6趟:(7,10,32,65,70,83,100),9第7趟:(7,9,10,32,65,70,83,100)2已知序列(10,18,4,3,6,12,1,9,15,8),请写出对此序列采用归并排序法进行升序排序时各趟的结果。答:原始序列:10,18,4,3,6,12,1,9,15,8第1趟:10,18 3,46,121,9 8,15第2趟:3,4,10,18, 1,6,9,12 8,15第3趟:3,4,10,18, 1,6,8,9,12,15第4趟:1,3,4,6,8,9,10,12,15,183已知序列(256,301,751,129,937,863,742,694,076,438)请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。答:原始序列:256,301,751,129,937,863,742,694,076,438第1趟:256,301,129,751,863,742,694,076,438,937第2趟:256,129,301,751,742,694,076,438,863,937第3趟:129,256,301,742,694,076,438,751,863,937第4趟:129,256,301,694,076,438,742,751,863,937第5趟:129,256,301,076,438,694,742,751,863,937第6趟:129,256,076,301,438,694,742,751,863,937第7趟:129,076,256,301,438,694,742,751,863,937第8趟:076,129,256,301,438,694,742,751,863,937第9趟:076,129,256,301,438,694,742,751,863,9374已知序列(503,87,512,61,908,170,897,275,653,462)请给出采用快速排序法对该序列作升序排列时的每一趟结果。原始序列:503,87,512,61,908,170,897,275,653,462第1趟:462,87,275,61,170503897,908,653,512第2趟:170,87,275,61 462,503897,908,653,512第3趟:87,61170275 462,503897,908,653,512第4趟:61 87170275 462,503897,908,653,512第5趟:61 ,87,170,275 462,503897,908,653,512第6趟:61 ,87,170,275,462,503897,908,653,512第7趟:61 ,87,170,275,462,503512,653897908第8趟:61 ,87,170,275,462,503,512,653 897908第9趟:61 ,87,170,275,462,503,653,897908第10趟: 61 ,87,170,275,462,503,653,897,9085设一组记录的关键字序列为(49,83,59,41,43,47),采用堆排序算法完成以下操作:(要求小根堆,并画出中间过程)(1)以二叉树描述6个元素的初始堆(2)以二叉树描述逐次取走堆顶元素后,经调整得到的5个元素、4个元素的堆答:(1)(2)6(1)原序列1615205364715162053764n-1趟15162075364n-j次151672053641571620536471516205364(2)(3)平均查找长度=(1*1+2*2+3*3)/6=14/67(1)(2)中序遍历:2,3,4,5,6,7,14,16,18四、程序填空题1.(1)j>=0(2)aj(3)j-(4)temp2(1)j<=n-1(2)i<=n-j(3)ai=ai+1(4)ai+1=temp(5)当某趟冒泡中没有出现交换则已排好序结束循环。五、算法设计题1编写折半查找算法。折半查找算法如下;int Binary_Search(NODE a,int n, int k)int low,mid,high;low=0;high=n-1;while(low<=high)mid=(low+high)/2;if(amid.key=k)return mid;else if(amid.key<k)low=mid+1;else high=mid-1;return -1;2. 编写顺序查找算法。顺序查找算法如下:int search(NODE a,int n, int k)int i=0;while(i<n && ai.key!=k)i+;if(ai.key=k)return i;else return -1;六、完成:实验3栈、队列、递归程序设计,实验4图的存储方式和应用根据实验要求(见教材P203)认真完成本实验,并提交实验报告。

    注意事项

    本文(数据结构形考作业答案.doc)为本站会员(李医生)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开