北京邮电大学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．通过衡量一个算法的_________复杂度和_________复杂度来进行判定一个算法的好坏。 7．将下三角矩阵 A[8,8]的下三角部分逐行地存储到起始地址为 1000H 的内存单元中(下标从 0 开始，不存储上三角部分)，已知每个元素占 4 个单元，则 A[5,4]的地址是(要求十六进制数)_____________。 班级： 学号： 班内序号： 姓名： ---------------------------------------------------装--------------------------- --------------订---------------- ----------------------线-------------------------------------------------------- 二、选择题(共 13分，每题 1分) 1、下面带有@标记的语句的频度(n>10)是[ ] for(int i=0;i
