2007年山东齐鲁工业大学数据结构考研真题A卷.doc

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2007年山东齐鲁工业大学数据结构考研真题A卷一、填空题（每空 2 分，共 10 分） 1、广义表((a),a)的表头为（1），表尾为（2）。 2、已知二维数组 M，每个元素的存储占 3 个单元，行下标 i 的范围从 1 到 8，列下标 j 的范围从 1 到 10，从首地址 SA 开始连续存放在存储器内，若按行优先存储，则元素 M[8][5]的地址是（3）。 3、深度为 h（h≥1）的完全二叉树至少有（4）个结点。 4、从有序表｛3,6,9,13,21,37,50,78,90｝中，用二分法检索出 13 需要（5）次比较。二、简要回答下列问题（共 88 分） 1、（5 分）有 3 个元素，其入栈次序为：A，B，C，写出各种可能的出栈次序。 2、（5 分）树和二叉树之间有什么样的区别与联系？ 3、（5 分）快速排序是在所有情况下排序速度最快吗？为什么？ 4、（5 分）如果通信字符 a,b,c,d 出现频度分别为：7，5，2，4。请画出哈夫曼树并给出相应的哈夫曼编码。 5、已知一棵二叉树如图 1 所示，要求：(1) （6 分）写出此二叉树的先序、中序、后序遍历序列；（6 分）对此二叉树进行中序线索化；

（4 分）将此二叉树变换为森林；（2 分）用先序遍历该森林，写出遍历后的结点序列。 6、已知一无向图如图 2 所示，要求：（4 分）给出该图的邻接矩阵；（4 分）依据该图的邻接矩阵，写出从顶点 1 出发对图进行深度优先遍历和广度优先遍历得到的顶点序列；（6 分）写出用克鲁斯卡尔（Kruskal）算法构造该图的最小生成树的过程。 7、设哈希表长度 13, 哈希函数为 H （ K ） =K MOD 13 ，给定的键值序列为｛13,41,15,44,06,68,12,25,38,64,19,49｝，用链地址法处理冲突。要求：（12 分）构造哈希表；（4 分）什么是同义词？列出该哈希表中的同义词；（2 分）求出在等概率情况下，查找成功的平均查找长度。 8、给定一组关键字序列（52，70，33，65，24，56，48，92，86， 37），要求：（10 分）根据该序列创建一棵二叉排序树，画出得到的二叉排序树。（4 分）写出对该序列进行快速排序的第一趟的结果。（4 分）将该序列调整为一个小顶堆，画出得到的小顶堆。

（注意事项：以下算法设计题建议采用类 C 语言书写，并对主要数据类型给出声明。所写算法应结构清晰、简明易懂，加上必要的注释）三、算法设计题（共 52 分） 1、斐波那契数列 Fn 定义如下：F0=0,F1=1,Fn=Fn-1+Fn-2,n=2,3,…。分别书写：（6 分）求解 Fn 的递归算法；（8 分）求解 Fn 的非递归算法。 2、（12 分）设有一个由正整数构成的单链表 L(带头结点)，编写算法删除 L 中值等于 x 的所有结点。 3、（10 分）已知含有 n（n≥1）个整数的数组 A，编写算法输出 A 的前 k（k≥1）个最大的元素，并分析算法的时间复杂度。 4、（10 分）已知二叉树 T 采用二叉链表表示，书写算法判断它是否为二叉排序树。 5、（6 分）已知数组 A 中存放了一个由 n（n≥1）个整数组成的序列，判断它是否满足小顶堆的定义。

分享到：

赞收藏

资料库

2007年山东齐鲁工业大学数据结构考研真题A卷.doc

相关推荐

考研

热门标签

最新资料