欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    数据结构考试题1.doc

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

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

    数据结构考试题1.doc

    #*要求:所有的题目的解答均写在答题纸上,需写清楚题目的序号。每张答题纸都要写 上姓名和学号。一、单项选择题(每小题 1.5 分,共计 30 分)1. 数据结构是指 。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为 。void fun(int n)int i=1;while (i1)个元素的线性表的运算只有 4 种:删除第一个元素;删除最 后一个元素;在第一个元素前面插入新元素;在最后一个元素的后面插入新元素,则最好 使用以下哪种存储结构,并简要说明理由。 (1)只有尾结点指针没有头结点指针的循环单链表 (2)只有尾结点指针没有头结点指针的非循环双链表 (3)只有头结点指针没有尾结点指针的循环双链表 (4)既有头结点指针也有尾结点指针的循环单链表 2. 已知一棵度为 4 的树中,其度为 0、1、2、3 的结点数分别为 14、4、3、2,求该 树的结点总数 n 和度为 4 的结点个数,并给出推导过程。 3. 有人提出这样的一种从图 G 中顶点 u 开始构造最小生成树的方法: 假设 G=(V,E)是一个具有 n 个顶点的带权连通无向图,T=(U,TE)是 G 的最小生成 树,其中 U 是 T 的顶点集,TE 是 T 的边集,则由 G 构造从起始顶点 u 出发的最小生成树 T 的步骤如下: (1)初始化 U=u。以 u 到其他顶点的所有边为候选边。 (2)重复以下步骤 n-1 次,使得其他 n-1 个顶点被加入到 U 中。 从候选边中挑选权值最小的边加入到 TE,设该边在V-U中的顶点是v,将v加入U中。 考查顶点 v,将 v 与 V-U 顶点集中的所有边作为新的候选边。 若此方法求得的 T 是最小生成树,请予以证明。若不能求得最小边,请举出反例。 4. 有一棵二叉排序树按先序遍历得到的序列为:(12,5,2,8,6,10,16,15,18,20)。回答以 下问题: (1)画出该二叉排序树。 (2)给出该二叉排序树的中序遍历序列。 (3)求在等概率下的查找成功和不成功情况下的平均查找长度。#*三、算法设计题(每小题 10 分,共计 30 分)1. 设 A 和 B 是两个结点个数分别为 m 和 n 的单链表(带头结点) ,其中元素递增有 序。设计一个尽可能高效的算法求 A 和 B 的交集,要求不破坏 A、B 的结点,将交集存 放在单链表 C 中。给出你所设计的算法的时间复杂度和空间复杂度。 2. 假设二叉树 b 采用二叉链存储结构,设计一个算法 void findparent(BTNode *b,ElemType x,BTNode */专业、班号或姓名float score;/分数struct node *child;/指向最左边的孩子结点struct node *brother;/指向下一个兄弟结点 TNode; 完成以下算法: (1)设计一个算法求所有的学生人数。 (2)求指定某班的平均分。name:计算机专业 score:0 name:计科 1 score:0 name:王华 score:86 name:李明score:79 name:张兵score:79 name:计科 n score:0 name:陈强 score:85 name:许源score:92 name:张山score:69 图 1 一棵学生成绩树#*“数据结构”考试试题(A)参考答案要求:所有的题目的解答均写在答题纸上,需写清楚题目的序号。每张答题纸都要写 上姓名和学号。一、单项选择题(每小题 1.5 分,共计 30 分)1. D2. A3. A4. A5. C 6. B7. D8. B9. A10. C 11. C12. A13. A14. D15. D 16. C17. D18. A19. A20. C二、问答题(共 4 小题,每小题 10 分,共计 40 分)1. 答:本题答案为(3) ,因为实现上述 4 种运算的时间复杂度均为 O(1)。 【评分说明】选择结果占 4 分,理由占 6 分。若结果错误,但对各操作时间复杂度作 了分析,可给 25 分。 2. 答:结点总数 n=n0+n1+n2+n3+n4,即 n=23+n4,又有:度之和=n-1=0×n0+1×n1+2×n2+3 ×n3+4×n4,即 n=17+4n4,综合两式得:n4=2,n=25。所以,该树的结点总数为 25,度为 4 的结点个数为 2。 【评分说明】结果为 4 分,过程占 6 分。3. 答:此方法不能求得最小生成树。例如,对于如图 5.1(a)所示的带权连通无向 图,按照上述方法从顶点 0 开始求得的结果为 5.1(b)所示的树,显然它不是最小生成树, 正确的最小生成树如图 5.1(c)所示。 在有些情况下,上述方法无法求得结果,例如对于如图 5.1(d)所示的带权连通无向 图,从顶点 0 出发,找到顶点 1(边(0,1) ) ,从顶点 1 出发,找到顶点 3(边(1,3) ) ,再 从顶点 3 出发,找到顶点 0(边(3,0) ) ,这样构成回路,就不能求得最小生成树了。0 1 1 3 2 2 3 4 5 0 1 1 3 2 2 4 3 5 (a) (d) 0 1 1 3 2 3 5 (b) 0 1 1 3 2 3 (c) 4 图 1 求最小生成树的反例#*说明:只需给出一种情况即可。 【评分说明】回答不能求得最小生成树得 5 分,反例为 5 分。若指出可求得最小生成 树,根据证明过程给 12 分。 4. 答:(1)先序遍历得到的序列为:(12,5,2,8,6,10,16,15,18,20),中序序列是一个有 序序列,所以为:(2,5,6,8,10,12,15,16,18,20),由先序序列和中序序列可以构造出对应的二 叉树,如图 2 所示。 (2)中序遍历序列为:2,5,6,8,10,12,15,16,18,20。 (3)ASL成功=(1×1+2×2+4×3+3×4)/10=29/10。 ASL不成功=(5×3+6×4/11=39/11。12 5 2 8 6 10 16 15 18 20 图 2【评分说明】 (1)小题占 6 分, (2) (3)小题各占 2 分。三、算法设计题(每小题 10 分,共计 30 分)1. 设 A 和 B 是两个结点个数分别为 m 和 n 的单链表(带头结点) ,其中元素递增有 序。设计一个尽可能高效的算法求 A 和 B 的交集,要求不破坏 A、B 的结点,将交集存 放在单链表 C 中。给出你所设计的算法的时间复杂度和空间复杂度。 解:算法如下:void insertion(LinkList *A,LinkList *B,LinkList *C=(LinkList *)malloc(sizeof(LinkList);t=C;while (p!=NULL s->data=p->data;t->next=s;t=s;p=p->next;q=q->next;else if (p->datadata)p=p->next;#*elseq=q->next;t->next=NULL; 算法的时间复杂度为 O(m+n),空间复杂度为 O(MIN(m,n)。 【评分说明】算法为 8 分,算法的时间复杂度和空间复杂度各占 1 分。 2. 假设二叉树 b 采用二叉链存储结构,设计一个算法 void findparent(BTNode *b,ElemType x,BTNode *else if (b->lchild!=NULL else if (b->rchild!=NULL elsefindparent(b->lchild,x,p);if (p=NULL)findparent(b->rchild,x,p);else p=NULL; 【评分说明】本题有多种解法,相应给分。 3. 假设一个连通图采用邻接表 G 存储结构表示。设计一个算法,求起点 u 到终点 v 的经过顶点 k 的所有路径。 解:算法如下:int visitedMAXV=0;/全局变量void PathAll(ALGraph *G,int u,int v,int k,int path,int d)/d 是到当前为止已走过的路径长度,调用时初值为-1int m,i;ArcNode *p;visitedu=1;d+;/路径长度增 1pathd=u;/将当前顶点添加到路径中if (u=v for (i=0;iadjlistu.firstarc;/p 指向顶点 u 的第一条弧的弧头节点while (p!=NULL)m=p->adjvex;/m 为 u 的邻接点if (visitedm=0)/若该顶点未标记访问,则递归访问之PathAll(G,m,v,l,path,d);p=p->nextarc;/找 u 的下一个邻接点visitedu=0;/恢复环境:使该顶点可重新使用int In(int path,int d,int k) /判断顶点 k 是否包含在路径中int i;for (i=0;ichild=NULL) return 1;return count(b->child)+count(b->brother); 说明:本题可以从链表的角度求解。 (2)算法如下:int Average(TNode *b,char class,float float sum=0;TNode *p=b->child;/p 指向班号结点while (p!=NULL if (p=NULL) return 0; /没找到该班号,返回 0p=p->child;/p 指向该班的第一个学生while (p!=NULL)n+;/累计人数sum+=p->score;/累计分数p=p->brother;avg=sum/n;/求平均分return 1; 【评分说明】两小题各占 5 分。

    注意事项

    本文(数据结构考试题1.doc)为本站会员(小**)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

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




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开