910桂林电子科技大学2015年研究生统一入学考试试题数据结构(2015-B).doc

桂林电子科技大学2015年研究生统一入学考试试题 科目代码：910 科目名称：数据结构 请注意：答案必须写在答题纸上（写在试题上无效）。 单项选择题（每小题2分，共20分） 每个结点有多个后继结点的数据结构有____ ______。 A） 线性表 B） 队列 C） 图 D） 栈 一个栈的输入序列为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 2 以下的4棵二叉树中，_________不是完全二叉树。 A） B） C） D） 一棵非空二叉树的前序序列和中序序列正好相同，则该二叉树一定满足_______。 A）其中任意一结点均无左孩子 B）其中任意一结点均无右孩子 C）是一棵完全二叉树 D）是任意一棵二叉树 一棵度为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 + 1 关键码序列K = { 23， 40， 28， 19， 20， 42 }，经过筛选法建堆过程后，得到的最小堆为___ ______。 A）19，20，28，40，23，42 B）19，28，20，40，23，42 C）42，40，28，23，20，19 D）42，28，40，20，23，19 有向图G用邻接矩阵A存储，则顶点i的入度等于A中____ _____。 A）第i行元素之和 B）第i行的元素之和与第i列元素之和的乘积 C）第i行与第i列元素之和 D）第i列元素之和 有拓扑排序的图，一定是____ _____。 A）有环图 B）无向图 C）无环有向图 D）无环任意图 有一个有序表为{ 2，11，16，23，32，45，51，62，73，79，80，94，97 }，当二分检索关键码值为94的数据元素时，_____ _______次比较后查找成功。 A）1 B）2 C）3 D）4 在待排序的元素序列基本有序的情况下，下面的____________算法效率最高。 A）插入排序 B）选择排序 C）快速排序 D）归并排序 已知某二叉树的前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ，请完成： 画出该二叉树； 将该二叉树转换为对应的森林。 （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，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 的各种结点数为n1,n2,…,nm(nm 表示度数为m 的结点个数)请推导出该树中共有多少个叶子结点n0 的公式。（10分） 在堆排序、快速排序和合并排序中： (1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？ (2)若只从排序结果的稳定性考虑，