2015年广西桂林电子科技大学数据结构考研真题(A卷).doc

发布时间：2023-11-14 发布人：admin 分类：说明书资料大小：0.08M 资料格式：doc 举报版权申诉

第1页 / 共5页

2015年广西桂林电子科技大学数据结构考研真题(A卷).doc.pdf-第2页.jpg

第2页 / 共5页

2015年广西桂林电子科技大学数据结构考研真题(A卷).doc.pdf-第3页.jpg

第3页 / 共5页

2015年广西桂林电子科技大学数据结构考研真题(A卷).doc.pdf-第4页.jpg

第4页 / 共5页

2015年广西桂林电子科技大学数据结构考研真题(A卷).doc.pdf-第5页.jpg

第5页 / 共5页

文本预览

2015 年广西桂林电子科技大学数据结构考研真题(A 卷) 一、单项选择题（每小题 2 分，共 20 分） 1．每个结点有多个后继结点的数据结构有__________。 A）线性表 B）队列 C）图 D）栈 2．一个栈的输入序列为 12345，则下列序列中不可能是栈的输出序列的是_________。 A）23415 B）54132 C）23145 D）15432 3．以下的 4 棵二叉树中，_________不是完全二叉树。 4．一棵非空二叉树的前序序列和中序序列正好相同，则该二叉树一定满足_______。 A）其中任意一结点均无左孩子 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+1 6．关键码序列 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 7．有向图 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）4 10．在待排序的元素序列基本有序的情况下，下面的____________算法效率最高。 A）插入排序 B）选择排序 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，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)若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？（10 分）八、已知一组元素的排序码为{42，55，13，46，94，5，17，70}，利用快速排序，每次都取子序列的中间元素作为轴值，写出每一层划分后的排列结果。（10分）一个线性表关键码值集合为{26，23，40，45，33，55，31，69}，设散列地址空九、间为 HT[11]（下标位置为 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 分）

分享到：

赞收藏

资料库

2015年广西桂林电子科技大学数据结构考研真题(A卷).doc

相关推荐

考研

热门标签

最新资料