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

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2007 年山东曲阜师范大学数据结构考研真题一、简答题（共 48 分） 2、线性表的顺序存储结构具有三个弱点;其一，在作指入或删除操作时，需移动大量元素;其二，由于难以估计，必须预先分配较大的空间，往往│使存储空间不能得到充分利用;其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。（6 分） 3、若元素的进梭序列为∶A、B、C、D、E，运用钱操作，能否得到出校序列 B、C、A、E、D 和 D、 B、A、C、E? 为什么?一共能得到多少种合法的出栈序列? （6 分） 4、试推导出当总盘数为 n 时 Hanoi 塔的移动次数。（6 分） 5、数组 A 中，每个元素 ALi，j 的长度均为 32 个二进位，行下标从-1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放主存储器中，主存储器字长为 16 位，计算以下各题。（6 分）（1）存放该数组所需多少单元? （2）存放数组第 4 列所有元素至少需多少单元? （3）数组按行存放时，元素 A【7，4】的起始地址是多少? （4）数组按列存放时，元素 A【4，7】的起始地址是多少? 6、设任意 n 个整数存放于数组 A（l∶n）中，试编写程序，在 0（n）的时间复杂度之内，将所有正数排在所有负数的前面（要求给出算法思想、算法描述和时间复杂度分析）。（6 分）

7、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。（6 分） 8、解释什么是倒排文件，并分析其特点。（6 分）二、应用题（共 84 分） 9、设字符串 S='aabaabaabaac'，P='aabaac'（12 分）（1）给出 P 的 next 值和 nextval 值; （2）若 S 作主串，P 作模式串，试给出利用传统 BF 算法和改进 KMP 算法的匹配过程。 11、对一棵二叉树进行广义优先（层次序）通历得到的结果序列为（从根开始）; A、B、C、D、 E、F、G、H，而对它进行中序遍历得到的结果序列为∶ D、B、G、E、H、A、C、F。请画出该二又树的树形图，并给出对该二又树进行前序遍历的结果序列。 12、试利用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小（代价）生成树。（12 分）

13、设有一棵空的 3 阶 B-树，依次插入关键字∶ 30，20，10，40，80，58，47，50，29，22，.56，98，99，请画出该 3 阶 B-树。（12 分） 14、快速排序是在所有情况下，排序速度最快吗?为什么?在何种情况下使用此排序方法最好? （12 分） 15、对于如下图所示的 A0E 网，求出其所有的关键活动和关键路径。（12 分）三、算法设计题（共 18 分）

16、已知一棵高度为 K 具有 n 个结点的二叉树。按顺序方式存储，编写将二叉树中最大序号叶了第点的祖先结点全部打印输出的算法，（要求给出算法思想和算法描述）（8 分） 17、试给出二叉树的自下而上、白右而左的层次序遍历算法。（要求给出算法思想和算法描述）（10 分）

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料