《数据结构》模拟试卷五.doc

模拟试卷五一、选择题（20分） 1设循环队列中数组的下标范围是ln，头尾指针分别为f和r，则其元素个数为 。 a rf b. rfI c（rf1）mod n d.（rfn）mod n 2一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是 。 a 2 3 4 1 5 b 5 4 2 3 1 c 2 3 1 4 5 d 1 5 4 3 2 3用十字链表表示一个有K个非0元素的mn的稀疏矩阵，则其总结点数为 。 a. mn bmnmn cKmax（m，n）1 dKmn1 4对矩阵压缩存储是为了 。 a. 方便运算 b. 节省空间 c方便存储 d提高运算速度5一棵左右子树均不空的二叉树在先序前趋和后序后继线索化后，其空链域数为 。 ao b1 c2 d不确定 6判断线索二叉树中某结点P今有左孩子的条件是 。 a. p nil b p.Lchild nil cP.Ltag = 0 d. P.Ltag = 1 7. 在图G用邻接矩阵存储时，求最短路径的DIJKSTRA算法的时间复杂度为 。 aO（n） bO（ne） cO（n2） dO（ne） 8设图G采用邻接表存储，则拓扑排序算法的时间复杂度为 。 aO（n） bO（ne） cO（n2） dO（ne） 9快速排序算法在最好情况下的时间复杂度为 。 a0（n） bO（n2） cO（nlog2n） dO（log2n） 10. 下列排序算法中，时间复杂度为O（log。n）且占用额外空间最少的是 。 a堆排序 b冒泡排序 c快速排序 dSHELL排序二、填空题（10分） 1. 双循环锭表L中某结点P为尾结点的条件是 。 2. 已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 。 3高度为K的m阶B树至少有 个结点。 4有n个顶点的连通图至少有 条边。5取出广义表A =（x，（a，b，c，d）中原子b的函数是 。三、解答下列各题（20分） 1一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求 出空格处的内容，并画出该二叉树。（6分） 失序： B F I C E H G 中序：D K F I A E J C 后序： K F B H J G A2已知哈希表地址空间为 0.14，哈希函数为 H（k）= k mod 13，采用线性探查 法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长 度和失败的查找长度。（6分） 24O，29，345，189，10O，ZO，汛，35，3，208，78，99，45，350 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3对下面的递归算法，要求：（8分） （1）写出调用P（4）的执行结果。 （2）将其转换为等价的非速归算法。 procedure p（w：Integer）； begin if w0 then begin write（w）； p（w - 1）； p（w - 1） endend；四、算法设计（50分，每题10分） 1设计算法将数组A1N按从大到小的次序进行排序，要求一旦发现有序即 停止。 2设计算法求两个带有头结点的递增单循环链表A，B的公共元素，并建成另一相 同结构的链表C。要求时间尽可能少。 3已知T为一棵二叉排序树。 （l）设计算法按递减次序打印各结点的值。 （2）设计算法以产生一个序列，要求该序列满足：依次将这些元素插入到初值 为空的二叉排序树中所得的结果与原二叉排序树相同。 4一棵树T采用二叉链表表示，其中指针及结点的类型说明如下： type treelink = tnode； tnode record data： datatype； flrstson，nextbrother：treelink；第一个孩子