北京邮电大学2005 ——2006学年第 1 学期 《数据结构》期末考试试题 考试注意事项 一、学生参加考试须带学生证或学院证明，未带者不准进入考场
学生必须按照监考教师指定座位就坐
二、书本、参考资料、书包等与考试无关的东西一律放到考场指定位置
三、学生不得另行携带、使用稿纸，要遵守《北京邮电大学考场规则》，有考场违纪或作弊行为者，按相应规定严肃处理
四、学生必须将答题内容做在试题答卷上，做在草稿纸上一律无效
考试课程 数据结构 考试时间 2006 年 1 月 6 日 题号 一 二 三 四 五 六 七 八 总分 满分 得分 阅卷教师 （ 一、填空题 (共 17分，每空 1分) 1．在数据结构中，数据元素之间通常有下列四类基本结构：___________、__________、____________和_____________；有两种物理结构（存储结构），分别 _____________、________________
2．n 个顶点的连通图至少有 条边；任何一个具有 n 个结点的完全无 向图有___________条边；n 个结点的完全有向图有__________条弧
3．在无向图 G 的邻接矩阵 A 中，若 A[i][j]等于 1，则 A[j][i]等于
4． 通过建立 Hash 表查找元素，理想情况下，查找元素的时间复杂度为______
5．长度为 11 的有序序列： 1 12 13 24 35 36 47 58 59 69 71进行等概率查找，如 果采用顺序查找，则平均查找长度为_____,如果采用二分查找，则平均查找长 度为_____,如果采用哈希查找，哈希表长为 15，哈希函数为 H(key)=key%13,采 用线性探查解决地址冲突，即 di=（H(key)+i）%15,则平均查找长度为（保留 1 位小数）_____
6．通过衡量一个算
