桂林理工大学《数据结构及程序设计》2021年硕士研究生入学考试试题

 您现在的位置: 考博信息网 >> 文章中心 >> 考研复习 >> 专业课 >> 正文 桂林理工大学《数据结构及程序设计》2021年硕士研究生入学考试试题

考研试卷库
新闻资讯
普通文章 西南政法大学2012考博报名/考试地点变更
普通文章 武汉科技大学2012博士研究生招生报名
普通文章 考博顺利通过考试须知
普通文章 【考博】博士生入学考试十大必杀技-考博
普通文章 考博成功的因素-考博信息网
普通文章 考博专业课复习应当如何进行-考博信息网
普通文章 考博选择专业与学校的原则和策略-考博信
普通文章 考博要做的准备工作有哪些-考博信息网
普通文章 重庆大学2012年“申请-考核制”考博招生
普通文章 【考博】博士生导师的选择和首次联系-考
调剂信息
普通文章 北方工业大学机电工程学院自动化系2012
普通文章 华南师大光学、光学工程、材料物理与化
普通文章 关于报考中科院大气物理研究所2012年硕
普通文章 广西中医学院2011年硕士研究生调剂信息
普通文章 广西工学院2011年硕士研究生调剂信息公
普通文章 【广西工学院】2012年考研调剂信息
普通文章 【桂林医学院】2012年考研调剂信息
普通文章 广西艺术学院2012拟接收硕士研究生调剂
普通文章 江西科技师范学院2011年硕士研究生调剂
普通文章 【江西科技师范学院】2012年考研调剂信
桂林理工大学《数据结构及程序设计》2021年硕士研究生入学考试试题

桂林理工大学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  66  30   5


                          A=    1   1  20   2


                                1   1   1  77     


图(a):上三角矩阵


1

 2

 3

 4

 5

 6

 7

 8

 9

 10

 11

 
10

 25

 32

 0

 66

 30

 5

 20

 2

 77

 1

 
a11

 a12

 a13

 a14

 a22

 a23

 a24

 a33

 a34

 a44

 
 
图(b):顺序存储


三、A、B、C、D四个元素进S栈的顺序是A、B、C、D,试写出7种可能的出栈序列和相应操作,并给一个不会是出栈序列的实例,并说明理由。(10分)


四、已知一棵二叉树的前序序列的结果是ABDFCEHG,中序序列的结果是DBFAHECG,试画出这棵二叉树。   (10分)


五、使用普里姆(Prim)算法构造出如下图所示的图G的一棵最小生成树。   (10分)


V1V1
 
V3V3
 
                                  60

 

 

                         50


                                         52              45


V2
 
V7V7
 
V4vvVV$
 
                               65                42

 

 

                      40          50          30


V5
 
V6


 
                                        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)快速排序,每划分一次书写一个次序。


   (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分)

 

考博咨询QQ 135255883 考研咨询QQ 33455802 邮箱:customer_service@kaoboinfo.com
考博信息网 版权所有 © kaoboinfo.com All Rights Reserved
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载或引用的作品侵犯了您的权利,请通知我们,我们会及时删除!