2021年桂林理工大学硕士考研真题878数据结构及程序设计.doc

上传人(卖家):雁南飞1234 文档编号:2674624 上传时间:2022-05-17 格式:DOC 页数:3 大小:55.50KB
下载 相关 举报
2021年桂林理工大学硕士考研真题878数据结构及程序设计.doc_第1页
第1页 / 共3页
亲,该文档总共3页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

1、桂林理工大学2021年硕士研究生入学考试试题(A卷)考试科目代码:878考试科目名称:数据结构及程序设计 (总分150分,三小时答完) 考生注意:1请将答题写在答卷纸上,写在试卷上视为无效。2程序设计题仅用C语言答题。一、分析以下所给程序段的时间复杂度。 (10分)a=0;b=1;for(i=2;i=n;i+) s=a+b;b=a;a=s;二、已知上三角矩阵A4x4如图(a)所示,其顺序存储如图(b)所示。若每个存储结点的尺寸为4个字节,元素a11的地址为1。 (10分) (1)求元素a34在顺序存储中的序号以及地址。 (2)求元素a41在顺序存储中的序号以及地址。 10 25 32 0 1

2、66 30 5 A= 1 1 20 2 1 1 1 77 图(a):上三角矩阵1234567891011102532066305202771a11a12a13a14a22a23a24a33a34a44图(b):顺序存储三、A、B、C、D四个元素进S栈的顺序是A、B、C、D,试写出7种可能的出栈序列和相应操作,并给一个不会是出栈序列的实例,并说明理由。(10分)四、已知一棵二叉树的前序序列的结果是ABDFCEHG,中序序列的结果是DBFAHECG,试画出这棵二叉树。 (10分)五、使用普里姆(Prim)算法构造出如下图所示的图G的一棵最小生成树。 (10分)V1V1V3V3 60 50 52 4

3、5V2V7V7V4vvVV$ 65 42 40 50 30V5V6 70 图G:一个无向图六、一棵高度为h的满k叉树有如下性质:第h 层上的结点都是叶结点,其余各层上每个结点都有k棵非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进行编号,试问: (10分)(1)各层的结点个数是多少?(2)编号为i的结点的第m 个孩子结点(若存在)的编号是多少?(3)若结点个数为n,则高度h是n的什么函数关系? 七、给出一组关键字(29,18,25,47,58,12,51,10),分别写出按下列各种排序方法进行排序时的变化过程: (15分) (1)归并排序,每归并一次书写一个次序。 (2)

4、快速排序,每划分一次书写一个次序。 (3)堆排序,先建成一个堆,然后每从堆顶取下一个元素后,将堆调整一次。八、依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素,生成一棵二叉树排序树。 (15分)(1)试画出生成之后的二叉排序树;(2)对该二叉排序树作中序遍历,试写出遍历序列; (3)假定每个元素的查找概论相等,试计算该二叉排序权的平均查找长度。九、设给定权集W=2,3,4,7,8,9,试构造出关于W的一棵哈夫曼树,并求出其加权路径长度WPL。 (15分)十、二叉树采用链接存储结构,试设计一个算法计算一棵给定二叉树的所有结点数。(15分)十一、用递归法求:Y=X+X2/2!+X3/3!+到第n项,n和x的值由键盘输入。 (15分)十二、编写几个函数。(1)输入100个员工的姓名和员工号;(2)按员工号由小到大排序,姓名顺序也随之调整;(3)要求输入一个员工号,用折半查找法找出该员工的姓名,从主函数输入要查找的员工号,输出该项员工姓名。 (15分)2021年 数据结构及程序设计 第3页 共3页

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 大学
版权提示 | 免责声明

1,本文(2021年桂林理工大学硕士考研真题878数据结构及程序设计.doc)为本站会员(雁南飞1234)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|