15-836数据结构

科目代码：836 科目名称：数据结构

注意事项：1．本试卷共5道大题，满分150分；

2．本卷属试题卷，答案一律写在答题纸上，写在该试题卷上或草稿纸上均无效。要注意试卷清洁，不要在试卷上涂划；

3．在本校考试的考生必须用湖北省考试院提供的专用笔答题，其它笔答题均无效。

﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡

一、问答题（共80分，每小题10分）

1、什么是数据的存储结构？常见的存储结构有哪几种？

2、应该从哪几个方面来评价算法的优劣？

3、什么是递归程序？递归程序的优缺点是什么？

4、写出用两个栈模拟一个队列的算法思路。

5、具有三个结点的二叉树共有几种形态？画出这些二叉树。

第1页（共2页）

2015年湖北工业大学硕士研究生入学考试试题

科目代码：836 科目名称：数据结构

6、由二叉树先序遍历序列和后序遍历序列能否唯一确定一棵二叉树？请举例解释。

7、什么情况下可以采用二分查找？若数据元素的个数为n，则查找成功的平均查找长度是多少？

8、简述直接插入排序算法的基本思想，它是不是稳定的排序方法？

二、设以一组权值为｛3、16、20、17、30、6｝的叶子结点构造一棵带权路径长度最小的二叉树。试简述构造方法，画出这棵二叉树，并计算其带权路径长度。（15分）

三、设有向网N=(V(N)，E(N))，其中V(N)={V1, V2, V3, V4, V5, V6, V7}，现用表示弧及弧上的权w，E(N)={，，，，，，，，， }。

1、写出它的邻接矩阵；（5分）

2、求出V2的出度和入度；（5分）

3、求出V1到V7的最短路径，写出求解过程。（10分）

四、设散列表的长度为11，散列函数为H(key)=key MOD 11，采用链地址法解决冲突，输入的关键字序列为：{1，15，27，22，55，63，10，11，23，65}，试画出插入这些数据后的散列表，并求出查

第2页（共2页）

2015年湖北工业大学硕士研究生入学考试试题

科目代码：836 科目名称：数据结构

找成功和查找不成功的平均查找长度。（20分）

五、设有一个以h1为头指针的带头结点的单链表，其结点数据域存放的都是正整数，试用C语言写一个函数把该单链表分解为两个单链表，一个单链表以h1为头指针，只存放奇数，另一个单链表以h2为头指针，只存放偶数。要求只增设一个头结点h2，不再另开辟存储空间。 (15分）

第3页（共2页）