[考研类试卷]2008年大连理工大学计算机专业基础综合（数据结构）真题试卷及答案与解析.doc

2008年大连理工大学计算机专业基础综合（数据结构）真题试卷及答案与解析 一、单项选择题 1 2 3 4 5 6 7 8 9 10 二、简答题 11 n阶对称阵 (aij)nn，采用压缩存储放于一维数组 Fm中。从 F0开始存储，给出矩阵的压缩存储方式及任一矩阵元素 aij(O=i， j=n-1)的地址计算公式，并求算 m。 12 顺序队列如何解决假溢出问题。 13 已知一组关键字 (10， 26， 14， 25， 17， 36， 37， 44， 27， 34， 60)设哈希函数 H(x)=x13，表长 m=13，请写出用线性探测法处理冲突构造所得的哈希表。 14 给定一个由 n个关键字不同的记录构成的序列，你能否用比 2n-3少的比较次数找出 n个元素中的最大值和最小值 ?如果有，请描述你的方法。最快需要多少次比较 ?(无需写算法 ) 三、设计题 15 什么是堆 ?设计算法判定给定的存于数组 r中的 n个数据是否为堆。 16 设 u、 v是有向图的两个顶点，设计算法判读有向图中是否存在从顶点 u到 v的长度为k的简单路径。要求给出图的存储形式及其类型定义。 17 设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的最大值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。 2008年大连理工大学计算机专业基础综合（数据结构）真题试卷答案与解析