2006年山东曲阜师范大学数据结构考研真题.doc

发布时间：2022-09-15 发布人：admin 分类：说明书资料大小：0.28M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2006 年山东曲阜师范大学数据结构考研真题一、简答题（共 48 分） 1、算法的含义是什么?有哪些重要特性?一个算法的优劣应从哪些方面进行衡量?（6 分） 2、简述线性结构、树型结构、网状结构的不同点。（6 分） 3、简述栈与队列的不同之处。（6 分） 4、已知广义表，从 A 表中取出原子项 e 的运算序列是什么? （6 分） 5、设 T 是一棵二叉树，共有 11 个结点，除叶子结点外其它结点的度数皆为 2，试同 T 的最大可能高度 he.和最小可能高度 h。是多少? T 中共有多少非叶结点?（6 分） 6、解释关节点、重连通的含义。（6 分） 7、求模式串 p-"dedecgdedegF"的 next 和 nextval 数组各元素的值?（6 分） 8、如果有向图含有路径长度为负的回路（如下图所示），试间用 Floyd 方法求每对顶点之间的最短路径能否正常工作?为什么?（6 分）二、应用题（共 84 分） 9、已知一组记录的关键字为{18，2，10，6，78，56，45，50，110，8）。按输入顺序画出此组记录的平衡二叉树，求等概率情况下查找成功的平均查找长度。若查找每个元素的概率不等，此时的平衡二叉树是否是最佳查找树?为什么?（12 分）

10、将本题图中的树转化成相对应的二叉树，（12 分） 11、某工程的 AOE 网络如下图所示。图中边上的权值为活动 a1-a10。的期限（即完成活动所需的天数），完成此项工程至少需要多少时间?并求出该工程的关键活动和关键路径。（12 分） 12、给定下图，请用克鲁斯卡尔算法求出最小代价生成树，（12 分） 13、试利用 Dijkstra 算法求解本题图中从顶原 A 到其他各顶点间的最短路径及路径长度。（12 分）

14、有一组记录的关键字为{78，12，45，98，23，109，85，68.89，256，34}，写出对这组记录进行一趟快速排序的结果，并说明这越排序中关键字比较的次数为多少?（12 分） 15、下面的算法是将整型数组 A【0..n-1】中的元素划分为两部分，使得左边的所有元素均为奇数，右边的所有元素均为偶数，选择适当语句填入下面算法中，完成本算法。（12 分）三、算法设计题（18 分） 16、已知一棵二叉树的中序遍历序列和按层次遍历的序列，编写算法生成此二叉树的二义链表。（18 分）（1）写出该算法的算法思想（8 分）。（2）写出该算法的具体实现（10 分）。

分享到：

赞收藏

资料库

2006年山东曲阜师范大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料