A卷第卷第卷第卷第1页页页页山东轻工业学院山东轻工业学院山东轻工业学院山东轻工业学院2002002002007777年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题年攻读硕士学位研究生入学考试试题(答案一律写在答题纸上,答在试题上无效,试题附在答卷内交回)考试科目:数据结构试题适用专业:计算机应用技术A卷共卷共卷共卷共2页页页页一一一一、、、、填空填空填空填空题题题题((((每空每空每空每空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分)写出此二叉树的先序、中序、后序遍历序列;(2)(6分)对此二叉树进行中序线索化;(3)(4分)将此二叉树变换为森林;(4)(2分)用先序遍历该森林,写出遍历后的结点序列。6、已知一无向图如图2所示,要求:(1)(4分)给出该图的邻接矩阵;(2)(4分)依据该图的邻接矩阵,写出从顶点1出发对图进行深度优先遍历和广度优先遍历得到的顶点序列;(3)(6分)写出用克鲁斯卡尔(Kruskal)算法构造该图的最小生成树的过程。ABCDEGF图1A卷第卷第卷第卷第2页页页页16752436718423252015128图25107、设哈希表长度13,哈希函数为H(K)=KMOD13,给定的键值序列为{13,41,15,44,06,68,12,25,38,64,19,49},用链地址法处理冲突。要求:(1)(12分)构造哈希表;(2)(4分)什么是同义词?列出该哈希表中的同义词;(3)(2分)求出在等概率情况下,查找成功的平均查找长度。8、给定一组关键字序列(52,70,33,65,24,56,48,92,86,37),要求:(1)(10分)根据该序列创建一棵二叉排序树,画出得到的二叉排序树。(2)(4分)写出对该序列进行快速排序的第一趟的结果。(3)(4分)将该序列调整为一个小顶堆,画出得到的小顶堆。(注意事项:以下算法设计题建议采用类C语言书写,并对主要数据类型给出声明。所写算法应结构清晰、简明易懂,加上必要的注释)三三三三、、、、算法设计题算法设计题算法设计题算法设计题((((共共共共52分分分分)1、斐波那契数列Fn定义如下:F0=0,F1=1,Fn=Fn-1+Fn-2,n=2,3,…。分别书写:(1)(6分)求解Fn的递归算法;(2)(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)个整数组成的序列,判断它是否满足小顶堆的定义。