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

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2008 年山东曲阜师范大学数据结构考研真题一、简答题（共 36 分） 1、算法的含义是什么?有哪些重要特性?一个算法的优劣应从哪些方面进行衡量?（6 分） 2、已知广义表 LS=（a，b，c），（d，e），（h，（i，j），g），写出利用求表头、求表尾操作从 LS 表中取出原子项 i 的运算序列。（6 分） 3、解释关节点、重连通图的含义。（6 分） 4、若元素的进栈序列为∶ A、B、C、D、E，运用栈操作，能否得到出栈序列 B、C、A、E、 D 和 D、B、A、C、E?为什么?一共能得到多少种合法的出栈序列?（6 分） 5、试推导出当总盘数为 n 时 Hanoi 塔的移动次数。（6 分） 6、快速排序是在所有情况下，排序速度最快吗?为什么?在何种情况下使用此排序方法最好? （6 分）二、应用题（共 90 分） 7、设任意 n 个整数存放于整型数组 A【0.n-1】中，试设计算法，在 O（n）│的时间复杂度之内，将数组 A 中的元素划分为两部分，使得左边的所有元│素均为奇数，右边的所有元素均为偶数（要求给出算法思想、算法描述和时间复杂度分析）。（10 分） 8、已知对一棵二叉树进行先序遍历得到的结果序列为（从根开始）∶ A、B、│ D、E、G、 H、C、F，而对它进行中序遍历得到的结果序列为∶ D、B、G、│ E、H、A、C、F。请画出该二叉树的树形图，并给出对该二叉树进行后序遍历的结果序列。（10 分） 9、已知一组记录的关键字为{18，2，10，6，78，56，45，50，110，8}。按输入顺序建立此组记录的平衡二叉树，并求出等概率情况下查找成功的

平均查找长度。（10 分） 10、将本题图中的森林转化成相对应的二叉树。（10 分） 11、如下图所示是一个 3 阶 B-树，试画出依次插入 65、15、40、30 之后 B-树的最终形态。（10 分） 12、有如下图所示的带权有向图 G，试求出从顶点 1 到顶点 8 的关键路径及关键路径的长度。（10 分）

13、设散列表为 HT【13】，散列函数为 Hkey）=key%13，用闭散列方法中的│线性探查法解决冲突，试对关键码序列 12，23，45，57，20，03，78，31， 15，36 造表，画出相应的散列表，并计算等概率情况下搜索成功的平均搜索长度和搜索不成功（失败）的平均搜索长度。（10 分） 14、判断序列{12，70，33，65，24，56，48，92，86，33}是否是最小堆，如果不是，将它调整为最小堆。（10 分） 15、假定用于通信的电文由 8 个字母 cl，c2，c3，c4，c5，c6，c7，c8 组成，各字母在电文中出现的频率分别为 5，25，3，6，10，12，35，4。试为这 8 个字母设计不等长 Huffian 编码，并给出该电文的总码数（约定，在构造 Huffiman 树时保证左分支小于右分支，且左分支编码为 0，右分支编码为 1）。（10 分）三、算法设计题（共 24 分） 16、若矩阵 Amx，中的某个元素 aij 是第 i 行中的最小值，同时又是第 j 列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵 Amx，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。（算法要求∶给出算法思想、算法描述）（12 分） 17、已知一棵完全二叉树存放于一个一维数组 T【n】中，T【i】（i>=0）中存放的是结点 i 的值。试设计一个算法，从 T【n】中读出各结点的值，建立二叉│树的二叉链表存储表

示。（算法要求∶给出算法思想、相关结构的定义、算法描述）（12 分）

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料