管理科学与工程专业
管理信息系统与数据结构。
数据结构部分（50分）
一、 简要回答下列问题（10分）
1、 简述堆排序的思想方法，以及为实现堆排序需要解决的如下两个问题的过程（以大顶堆为例）（7分）
1） 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
2） 如何由一个无序序列建成一个堆？
2、 什么是asl？写出asl的定义（写出式子）（3分）
二、 单项选择题（10分）
1、 某程序的时间复杂度为（3n+nlog2n+n2+8）,其数量级表示为（ ）
a.0(n) b.(nlog2n) c.0(n2) d. 0 (log2n)
2、设有一个含150个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（ ）个表项。（设查找成功的平均查找长度为sn1=/2其中a为填装因子）
a 。400 b。300 c。 450 d 600
3、对于长度为9的有序顺序表，若采用折半查找，在等概率情况下查找成功的平均长度为（ ）的值除以9.
a.20 b.18 c.25 d.22
4、在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（ ）
a.顶点序列 b.边序列 c.权值总和 d.边的条数。
5、已知一有向图的邻接表储存结构如图所示，根据有向图的深度优先遍历算法，从v1出发的顶点序列为（ ）
三、填空题（5分）
1、在有序表a[1..30]中，按二分查找方法进行查找，查找长度为5的元素个数是___
2、在一个深度为k且具有最小结点数的完全二叉树上，按层次用自然数依次对结点编号，则编号最小的叶子的序号是___编号是i的结点所在的层次号（根在1层）是___
3、为了实现图的广度优先搜索，除了一个标志数组来标志已访问的图的结点外，还需___存放被访问的结点以实现遍历。
4、用单链表表示的链式队列，入队时应该修改链表的链___指针。
四、判断下列叙述的对错（5分）
1、在树中，如果从结点k出发，存在两条分别达到k’,k’’的长度相等的路径，由结点k’和k’’互为兄弟。
2、线性表的链式存储结构式通过指针来间接反映数据元素之间逻辑关系的。
3、**性表的顺序存储结构中，每插入一个数据元素都必须移动相应的数据元素。
4、若连通网络的各边的权值均不相同，则依据prim算法所构造的最小生成树是唯一的。
5、在散列法中采取开散列（链地址）法来解决冲突时，其填装因子的取值一定在（0,1）之间。
五、综合题（20分）
1、在起泡排序、堆排序和快速排序中：（6分）
（1）.若只从排序结果的稳定性考虑，则应选取哪些排序方法？
2）.若只从存储空间考虑，则应选哪些排序方法？
（3）.若只从平均情况下排序最快考虑，则应该选取哪些排序方法？
4）.若只从最坏情况下排序最快考虑，则应该选取哪些排序方法？
2、下图是一个有向图，利用dijkstra算法求图中从顶点a到其他各顶点间的最短路径，要求在答题纸上画出如下表，将执行算法过程中各步的状态和最短路径填入表中。（7分）
a到各点最短路径分别为：
3、下面的函数是输出二叉树的各结点。读程并在每个空格处填写一个语句或一个表达式。（7分）
#define max 100
typedef struct tnode tnode;
typedef struct stackstack;
void print tree(tnode *bt)
if(>0)
武汉大学研究生2023年招生专业
码 名称及研究方向。计划招生人数。考试科目备注。212电子信息学院学术型学位 68778464高层大气物理03日地物理。04空间信息科学与技术05电波传播理论及应用 02微波 毫米波理论与技术03卫星通信与定位技术。101思想政治理论 201英语一 301数学一。932电磁场理论。同等学力加试科目 ...
大连海事大学2023年招生简章
第二章组织机构和人员。第六条大连海事大学设立招生工作领导小组，全面负责大连海事大学的招生工作。招生工作领导小组成员由校领导及相关部门负责人组成，下设招生办公室。第七条学校选拔能模范遵守国家有关招生政策法规的教师和干部参加招生宣传和招生录取工作，招生宣传和招生录取工作人员均须参加学校组织的招生政策法规...
研究生专业目录
授予博士 硕士学位和培养研究生的 学科 专业目录 1997年颁布 学位委员会。国家教育委员会。一九九七年六月。说明 一 授予博士 硕士学位和培养研究生的学科 专业目录 1997年颁布 是 学位委员会学科评议组审核授予学位的学科 专业范围划分的依据。同时，学位授予单位按本目录中各学科 专业所归属的学科...