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

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2005 年山东齐鲁工业大学数据结构考研真题一、填空（每空 2 分，共 10 分） 1、广义表（（a），a）的表头为（1），表尾为（2）。 2、具有 n（n>1）个结点的满二叉树，其非叶子结点数为（3）。 3、从有序表｛3,6,9,13,21,37,50,78,90｝中，用二分法检索出 37 需要（4）次比较。 4、一棵 m 阶 B－树中，每个结点（除根结点外）最少为（5）棵子树。二、选择题（每空 2 分，共 20 分） 1、在有 n 个叶子结点的哈夫曼树中，其结点总数为（1）。 A．不确定 B．2n 输出序列为（2）。 C．2n+1 D．2n1 2、一个队列的入对序列是 1 2 3 4 5，则队列的 A．5 4 3 2 1 B．1 2 3 4 5 C．4 3 5 1 2 D．4 5 3 2 1 3、二维数组 M 中，每个元素是占 6 个存储单元，行下标 i 的范围从 0 到 8，列下标 j 的范围从 1 到 10，则 M 按行优先存储时元素 M[8][5]的起始地址与 M 按列优先存储时元素（3）的起始地址相同。 A．M [8][5] B．M[3][10] C．M[5][8] D．M[0][9] 4、森林的先序遍历序列等同于其对应的二叉树的（4）遍历序列。 A．先序 B．中序 C．后序 D．层次 5、在图的广度优先遍历中，需采用（5）以存储已被访问过的顶点。 A．数组 B．链表 C．栈 D．队列 6、具有 n 个顶点的有向图最多有（6）条边。 A．n B．n(n—1) C．n(n+1) D． n2 7、关键路径是指 AOE(Activity On Edge)网中（7）。 A. 最长的回路 B. 最短的回路 C.从源点到汇点(结束顶点)的最长路径

D.从源点到汇点(结束顶点)的最短路径 8、顺序查找方法适合于存储结构是（8）的线性表。 A．散列存储 B．顺序存储或者链接存储 C．压缩存储 D．索引存储 9、以下序列中不符合堆定义的是（9）。 A．(102，87，100，79，82，62) B．(102，100，87，79，82，62) C．(62，82，79，87， 100，102) D．(102，87，79，82，62，100) 10、在待排序列基本有序的前提下，效率最高的排序方法是 (10) 。 A.直接插入排序 B.选择排序 C.快速排序 D.归并排序三、简答（共 40 分） 1、（10 分）假设用于通讯的电文仅由 a,b,c,d,e,f 6 个字母组成，各字母在电文中出现的频率分别为（2，3，5，7，11，4），试为这 6 个字母设计哈夫曼编码。 2、（10 分）给定关键字序列{47，50，32，13，21，89}，首先创建二叉排序树，然后从二叉排序树中依次删除关键字值是 13、47 的结点。（要求画出创建的二叉排序树和依次删除 13、47 结点后的二叉排序树状态）。 3、（8 分）选取哈希函数 H（key）=key MOD 11，用开放地址法的线性探测再散列方法处理冲突，其冲突后求下一地址的函数为： Hi=（H（key）+di）MOD 14，其中 di=1,2,3...。试在 0~13 的散列地址空间内对关键字序列（03，38，61，84，49，14）造哈希表，并分别求找出 49、14 所需的比较次数。 4、（12 分）给出一组关键字 T＝（12，2，16，30，8，28，4，10，20，6，18），写出用下列算法从小到大排序时第一趟结束时的序列。 (1)直接插入排序 (2)起泡排序 (3)快速排序（选第一个记录为枢轴记录）四、（共 20 分）已知一棵二叉树如右图 1。

1、（8 分）写出对此二叉树分别进行先序、中序、后序、图 1 层次遍历后的结点序列 2、（9 分）画出此二叉树的中序线索化树 3、（3 分）将此二叉树转化为森林五、（共 18 分）已知一网右图 2 所示。请给出： 1、（4 分）该网的邻接矩阵。 2、（6 分）从顶点 1 出发对网进行广度优先遍历得到的顶点序列和广度优先生成树。 2、（8 分）求出该网的一棵最小生成树。图 2 （注意事项：以下算法设计题建议采用类 C 语言书写，并对主要数据类型给出声明）六、（算法设计题，共 42 分） 1、（14 分）已知存储整型元素的带头结点的单链表，L 是其头指针。(1)设计算法输出 L 中值最小的元素。 (2)设计算法输出 L 的表长

2、（18 分）已知含有 n 个整型元素的线性表按递增有序存放于数组 A[100]的前 n 个位置上（n<90）。 (1)编写算法求线性表中 n 个元素的乘积。 (2)编写算法向线性表插入一个值等于 kx 的新元素，并保持线性表的有序性。(3)编写算法删除线性表中值最小的元素。 3、（10 分）已知二叉排序树采用二叉链表方式存放，编写算法按递减次序打印输出二叉排序树的所有结点。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料