2009学院信息学院数据结构期末试题A卷.docVIP

信息学院本科生2008－2009学年第二学期 数据结构期末考试试卷(A卷) 专业：______________年级：______________学号：______________ 姓名：______________成绩：______________ 得 分 一、单项选择题（每小题2分，共20分） 1．线性表表元存储方式有和链接两种。试指出使用的存储方式____C______。 表元编号 数量 表元联系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 2 5781 17 6 6 910 24 3 A．单向链接B．双向链接C．循环链接D．循环链接 ___B_____。 A．栈 B．队列 C．树 D．图 3．设栈S和队列Q的初始状态为空，元素ab, c, d, e, f依次进入栈S若个元素出栈后即进入队列Q，且个元素出队的顺序是b, d, c, fe, a，则栈S是________。 A．1 B．2 C．3 D．4 4．5．给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3, 7, 6, 5, 4, 2, 1，则其遍历方式是________。 A．LRN B．NRL C．RLN D．RNL 6．下列关于无向连通图特性的叙述中，正确的是________。 I．所有顶点的度之和为偶数 II．边数大于顶点个数减1 III．顶点个数为偶数（注：零也为偶数） A．只有I B．只有IIC．I和II D．I和III ．已知关键字序列84, 68, 23, 55, 14, 2, 19, 27, 1, 11是最大堆，插入关键字73，调整后得到的最大堆是_________。 A．84, 68, 73, 55, 14, 23, 19, 27, 1, 11, 2 B．84, 73, 68, 55, 27, 23, 19, 14, 11, 2,1 C．84, 73, 68, 55, 27, 23, 19, 14, 11, 2,1 D．84, 73, 23, 55, 68, 2, 19, 27, 1, 11, 14 8．___B______。 A．起泡排序排序排序．下列叙述中，不符合m阶B树定义要求的是________。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 ．K=2789465，允许存储地址为三位十进制数，现得到的散列地址为149，则所采用的构建哈希函数的方法是____B_____。 A． B．C． D．得 分 二、（本题分）得 分 三、（本题分） 四、（本题12分）哈希表中使用哈希函数H（key）=(3 * key) % 11，并采用闭哈希方法使用随机探测再散列方法处理冲突，随机探测再散列的下一地址公式为：d1=H (key )，di=( di-1 +7 * key ) % 11 （i=2,3…..）。试在0到10的散列地址空间中对关键字序列（22, 41, 53, 46, 30, 13, 01）画出哈希表示意图，并求在等概率情况下查找成功的平均查找长度。 22 41 53 46 30 13 1 d1 0 2 5 6 2 6 3 d2 3 9 10 1 1 1 1 2 2 2 0 1 2 3 4 5 6 7 8 9 10 22 41 30 53 46 13 1 查找成功的平均查找长度ASL=(4+6)/7=10/7 得 分 五、（本题9分）使用有向无环图表示表达式，图中所含顶点尽可能少： ((a+b)*c+((a+b)+e)*(e+g))*((a+b)*c) 得 分 六、（本题12分）设由空树开始，依次插入关键字D、E、F、K、G、B、C、J、A、I，构成3阶B树。要求画出这棵B树的生成过程，每插入一个关键字画出一个树形。  得 分 七、（本题12分）对下面加权无向图，回答下列问题。 ① 画出邻接表。 ② 求顶点a到其余各顶点的最短路径，叙述所使用的算法，并给出求解过程。 邻接表： 最短路径求解过程： 终点 从a到各顶点的dist值和最短路径 b 4 (a, b) 3 (a, d, b) c 5 (a, c) 5 (a, c) 5 (a, c) d 3 (a, d) e ∞ 5 (a, d, e) 5 (a, d, e) 5 (a, d, e) f ∞ 9 (a, d, f) 9 (a, d, f) 9 (a, d, f) 9 (