搜索
B 卷第 1 页山东轻工业学院2005年攻读硕士学位研究生入学考试试题（答案一律写在答题纸上，答在试题上无效，试题附在答卷内交回）考试科目：数据结构试题适用专业：计算机应用技术 B 卷共 3页一、填空（每空 2 分，共 10分） 1、广义表（（a），a）的表头为（1），表尾为（2）。 2、具有n（n1）个结点的满二叉树，其非叶子结点数为（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 C．2n+1 D．2n1 2、一个队列的入对序列是1 2 3 4 5，则队列的输出序列为（2）。 A．5 4 3 2 1 B．1 2 3 4 5 C．4 3 5 1 2 D．4 5 3 21 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）。B 卷第 2 页 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）=keyMOD11，用开放地址法的线性探测再散列方法处理冲突，其冲突后求下一地址的函数为：Hi=（H（key）+di）MOD14，其中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分）写出对此二叉树分别进行先序、中序、后序、层次遍历后的结点序列 2、（9分）画出此二叉树的中序线索化树 3、（3分）将此二叉树转化为森林五、（共 18分）已知一网右图2所示。请给出： 1、（4分）该网的邻接矩阵。 2、（6分）从顶点1出发对网进行广度优先遍历得到的顶点序列和广度优先生成树。 3、（8分）求出该网的一棵最小生成树。图2图1ABCDEFGHB 卷第 3 页（注意事项：以下算法设计题建议采用类C语言书写，并对主要数据类型给出声明）六、（算法设计题，共 42分） 1、（14分）已知存储整型元素的带头结点的单链表，L是其头指针。(1)设计算法输出L中值最小的元素。(2)设计算法输出L的表长 2、（18 分）已知含有 n 个整型元素的线性表按递增有序存放于数组 A[100]的前 n 个位置上（n90）。(1)编写算法求线性表中n个元素的乘积。(2)编写算法向线性表插入一个值等于kx的新元素，并保持线性表的有序性。(3)编写算法删除线性表中值最小的元素。 3、（10分）已知二叉排序树采用二叉链表方式存放，编写算法按递减次序打印输出二叉排序树的所有结点。