1、桂林电子科技大学2015年研究生统一入学考试试题科目代码：910 科目名称：数据结构请注意：答案必须写在答题纸上（写在试题上无效）。一、 单项选择题（每小题2分，共20分）1 每个结点有多个后继结点的数据结构有_ _。A） 线性表 B） 队列 C） 图 D） 栈2 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是_ _。A）2 3 4 1 5 B）5 4 1 3 2 C）2 3 1 4 5 D）1 5 4 3 23 以下的4棵二叉树中，_不是完全二叉树。A）B）C）D）4 一棵非空二叉树的前序序列和中序序列正好相同，则该二叉树一定满足_。A）其中任意一结点均无左孩子
2、B）其中任意一结点均无右孩子C）是一棵完全二叉树 D）是任意一棵二叉树5 一棵度为4的树，n1 ,n2 ,n3 ,n4分别是度为1 ，2 ，3 ，4的结点个数，终端结点个数为n0 ，则有_ _。A）n0 = n1 + n2 + n3 + n4 B）n0 = 2n4 + n3 + 1 C）n0 = 4n4 + 3n3 + 2n2 + n1 D）n0 = 3n4 + 2n3 + n2 + 16 关键码序列K = 23， 40， 28， 19， 20， 42 ，经过筛选法建堆过程后，得到的最小堆为_ _。A）19，20，28，40，23，42 B）19，28，20，40，23，42 C）42，40，
3、28，23，20，19 D）42，28，40，20，23，197 有向图G用邻接矩阵A存储，则顶点i的入度等于A中_ _。A）第i行元素之和 B）第i行的元素之和与第i列元素之和的乘积C）第i行与第i列元素之和 D）第i列元素之和8 有拓扑排序的图，一定是_ _。A）有环图 B）无向图 C）无环有向图 D）无环任意图9 有一个有序表为 2，11，16，23，32，45，51，62，73，79，80，94，97 ，当二分检索关键码值为94的数据元素时，_ _次比较后查找成功。A）1 B）2 C）3 D）410 在待排序的元素序列基本有序的情况下，下面的_算法效率最高。A）插入排序 B）选择排序
4、C）快速排序 D）归并排序二、 已知某二叉树的前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ，请完成：（1） 画出该二叉树；（2） 将该二叉树转换为对应的森林。 （10分）三、 给定序列K = 12，8，10，14，16，6 ，请完成：（1）按K中关键码的顺序依次插入一棵初始为空的二叉搜索树，画出插入完成后的二叉搜索树；（2）以序列K作为一组给定的权值，构造关于K的一棵哈夫曼（Huffman）树，并求它的带权外部路径长度。 （12分）四、 已知一个带权图G的顶点集V和边集E分别为：V = a，b，c，d，e，f ，E =(a，b)，(a，c)，(b，c)，(c，d)，(b，
5、e)，(c，e)，(d，f)，(e，f) ，E中各边对应的权值如下：(a，b)：1， (a，c)：3， (b，c)：3， (c，d)：6，(b，e)：4， (c，e)：5， (d，f)：4， (e，f)：5请完成：（1）画出图G；（2）画出图G的邻接表表示；（3）根据（2）中画出的邻接表，写出从顶点a出发进行深度优先搜索（DFS）产生的深度优先序列；（4）从顶点a开始，用Prim算法构造图G的一棵最小生成树，并画出生成过程。（20分）五、 下图是一带权有向图，试采用Dijkstra算法求从顶点a到其他各顶点的最短路径，要求给出整个计算过程。（13分）六、 若一棵树中有度数为1 至m 的各种结点
6、数为n1,n2,nm(nm 表示度数为m 的结点个数)请推导出该树中共有多少个叶子结点n0 的公式。（10分）七、 在堆排序、快速排序和合并排序中： (1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？ (2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ （10分）八、 已知一组元素的排序码为 42，55，13，46，94，5，17，70 ，利用快速排序，每次都取子序列的中间元素作为轴值，写出每一层划分后的排列结
7、果。（10分）九、 一个线性表关键码值集合为 26，23，40，45，33，55，31，69 ，设散列地址空间为HT11（下标位置为0，1，10），散列函数为 h( K ) = K % 7，并用线性探查法解决冲突。请完成：（1）画出相应的散列表；（2）计算在等概率下成功检索的平均检索长度。 （15分）十、 编写一个函数count（），传入参数为一棵二叉树（不是二叉搜索树BST）和一个较小的值mink和一个较大的值maxk，返回值介于mink和maxk之间的结点数目。（15分）十一、 假设有一个循环链表的长度大于1，结点中数据的数据类型为DataType，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，要求写出：（1） 循环链表的类型定义；（2） 在该循环链表中，删除所有DataType值为X结点的算法。 （15分） 第 4 页 共 4 页
