1、2008 年大连理工大学计算机专业基础综合（数据结构）真题试卷及答案解析(总分：34.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1. （分数：2.00）A.B.C.D.2. （分数：2.00）A.B.C.D.3. （分数：2.00）A.B.C.D.4. （分数：2.00）A.B.C.D.5. （分数：2.00）A.B.C.D.6. （分数：2.00）A.B.C.D.7. （分数：2.00）A.B.C.D.8. （分数：2.00）A.B.C.D.9. （分数：2.00）A.B.C.D.10. （分数：2.00）A.B.C.D.二、简答题(总题数：4，分数：8.0
2、0)11.n 阶对称阵(aij)nn，采用压缩存储放于一维数组 Fm中。从 F0开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij(O=i，j=n-1)的地址计算公式，并求算 m。（分数：2.00）_12.顺序队列如何解决假溢出问题。（分数：2.00）_13.已知一组关键字(10，26，14，25，17，36，37，44，27，34，60)设哈希函数 H(x)=x13，表长m=13，请写出用线性探测法处理冲突构造所得的哈希表。（分数：2.00）_14.给定一个由 n 个关键字不同的记录构成的序列，你能否用比 2n-3 少的比较次数找出 n 个元素中的最大值和最小值?如果有，请描述你的方法。
3、最快需要多少次比较?(无需写算法)（分数：2.00）_三、设计题(总题数：3，分数：6.00)15.什么是堆?设计算法判定给定的存于数组 r中的 n 个数据是否为堆。（分数：2.00）_16.设 u、v 是有向图的两个顶点，设计算法判读有向图中是否存在从顶点 u 到 v 的长度为 k 的简单路径。要求给出图的存储形式及其类型定义。（分数：2.00）_17.设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。（分数：2.00）_2008 年大连理工大学计算机专业基础综合（数据结构）真题试卷答案解析(总分：34.00，做
4、题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1. （分数：2.00）A.B.C.D. 解析：2. （分数：2.00）A.B. C.D.解析：3. （分数：2.00）A.B. C.D.解析：4. （分数：2.00）A.B.C. D.解析：5. （分数：2.00）A.B.C.D. 解析：6. （分数：2.00）A. B.C.D.解析：7. （分数：2.00）A.B.C. D.解析：8. （分数：2.00）A. B.C.D.解析：9. （分数：2.00）A. B.C.D.解析：10. （分数：2.00）A.B.C.D. 解析：二、简答题(总题数：4，分数：8.00)11.n
5、阶对称阵(aij)nn，采用压缩存储放于一维数组 Fm中。从 F0开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij(O=i，j=n-1)的地址计算公式，并求算 m。（分数：2.00）_正确答案：(正确答案： )解析：12.顺序队列如何解决假溢出问题。（分数：2.00）_正确答案：(正确答案：在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次人队列和出队列操作后出现的有存储空间，但不能进行人队列操作的溢出称为假溢出。假溢出是由于队尾rear 的值和队头 front 的值不能由所定义数组下界值自动转为数组上界值而产生的解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾
6、相连的循环队列，因此，顺序队列通常都采用顺序循环队列结构。)解析：13.已知一组关键字(10，26，14，25，17，36，37，44，27，34，60)设哈希函数 H(x)=x13，表长m=13，请写出用线性探测法处理冲突构造所得的哈希表。（分数：2.00）_正确答案：(正确答案： )解析：14.给定一个由 n 个关键字不同的记录构成的序列，你能否用比 2n-3 少的比较次数找出 n 个元素中的最大值和最小值?如果有，请描述你的方法。最快需要多少次比较?(无需写算法)（分数：2.00）_正确答案：(正确答案： )解析：三、设计题(总题数：3，分数：6.00)15.什么是堆?设计算法判定给定的存于数组 r中的 n 个数据是否为堆。（分数：2.00）_正确答案：(正确答案： )解析：16.设 u、v 是有向图的两个顶点，设计算法判读有向图中是否存在从顶点 u 到 v 的长度为 k 的简单路径。要求给出图的存储形式及其类型定义。（分数：2.00）_正确答案：(正确答案： )解析：17.设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。（分数：2.00）_正确答案：(正确答案： )解析：
