《数据结构》模拟试卷五

《《数据结构》模拟试卷五》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模拟试卷五一、选择题（20分）1．设循环队列中数组的下标范围是l～n，头尾指针分别为f和r，则其元素个数为。a．r－fb.r－f＋Ic．（r－f＋1）modnd.（r－f＋n）modn2．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是。a．23415b．54231c．23145d．154323．用十字链表表示一个有K个非0元素的m×n的稀疏矩阵，则其总结点数为。a.m×nb．m×n＋m＋nc．K＋max（m，n）＋1d．K＋m＋n＋14．对矩阵压缩存储是为了。a.方便运算b.节省空间c．方便存储d．提高

2、运算速度5．一棵左右子树均不空的二叉树在先序前趋和后序后继线索化后，其空链域数为。a．ob．1c．2d．不确定6．判断线索二叉树中某结点P今有左孩子的条件是。a.p<>nilb．p^.Lchild<>nilc．P^.Ltag=0d.P^.Ltag=17.在图G用邻接矩阵存储时，求最短路径的DIJKSTRA算法的时间复杂度为。a．O（n）b．O（n＋e）c．O（n2）d．O（n×e）8．设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。a．O（n）b．O（n＋e）c．O（n2）d．O（n×e）9．快速排序算法在最好情况下的

3、时间复杂度为。a．0（n）b．O（n2）c．O（nlog2n）d．O（log2n）10.下列排序算法中，时间复杂度为O（＂log。n）且占用额外空间最少的是。a．堆排序b．冒泡排序c．快速排序d．SHELL排序二、填空题（10分）1.双循环锭表L中某结点P^为尾结点的条件是。2.已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为。3．高度为K的m阶B树至少有个结点。4．有n个顶点的连通图至少有条边。5．取出广义表A=（x，（a，b，c，d））中原子b的函数是。三、解答下列各题（20分）1．一棵二叉树的先序、

4、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。（6分）失序：BFICEHG中序：DKFIAEJC后序：KFBHJGA2．已知哈希表地址空间为0..14，哈希函数为H（k）=kmod13，采用线性探查法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。（6分）24O，29，345，189，10O，ZO，汛，35，3，208，78，99，45，350012345678910111213143．对下面的递归算法，要求：（8分）（1）写出调用P（4）的执行

5、结果。（2）将其转换为等价的非速归算法。procedurep（w：Integer）；beginifw＞0thenbeginwrite（w）；p（w-1）；p（w-1）endend；四、算法设计（50分，每题10分）1．设计算法将数组A［1．．N］按从大到小的次序进行排序，要求一旦发现有序即停止。2．设计算法求两个带有头结点的递增单循环链表A，B的公共元素，并建成另一相同结构的链表C。要求时间尽可能少。3．已知T为一棵二叉排序树。（l）设计算法按递减次序打印各结点的值。（2）设计算法以产生一个序列，要求该序列满足：依次将这些

6、元素插入到初值为空的二叉排序树中所得的结果与原二叉排序树相同。4．一棵树T采用二叉链表表示，其中指针及结点的类型说明如下：typetreelink=^tnode；tnode＝recorddata：datatype；flrstson，nextbrother：treelink；｛第一个孩子和下一个兄弟｝end；设计算法按层次遍历树t的各结点，并给出离根结点最远的一个结点的指针。5．设计算法判断图G中是否存在从顶点V；到V；的长度为K简单路径。