福州大学《863数据结构与程序设计》考研模拟题3答案.doc

模拟卷三参考答案 1． C。 【解析】考查时间复杂度。在程序中，执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次，根据循环结束条件，有n2*3k≥n/3，由此可得算法的时间复杂度为O(log3n)。 2． A。 【解析】考查出入栈操作的性质。当P1=3，表示3最先出栈，前面1、2应在栈中，此时若出栈操作，则p2应为2；此时若进栈操作（进栈1次或多次），则p2为4、5、?、n都有可能，故选A。 3. B。 【解析】考查队列的应用。图的广度优先搜索类似于树的层序遍历（形象地想象成一个扇形，以搜索起点为中心，逐层向相连的外圈搜索），同样需要借助于队列。前序遍历二叉树是一个递归的过程，通常可以借助于栈，将递归算法转换为非递归算法。图的深度优先搜索类似于树的前序遍历，也是一个递归的过程，通常也可以借助栈来实现。 4． C。 【解析】考查平衡二叉树的性质。在平衡二叉树的结点最少情况下，递推公式为N0=0，N1=1，N2=2，Nh=1+Nh-1+Nh-2（h为平衡二叉树高度，Nh为构造此高度的平衡二叉树所需最少结点数）。通过递推公式可得，构造5层平衡二叉树至少需12个结点，构造6层至少需要20个。 5． C。 【解析】考查二叉排序树的构造过程。画出三个选项ABC构造的二叉排序树的草图即可知道答案，C和AB构造的树形不同；再画出最后一个选项D构造的二叉排序树即可验证答案，D和AB两项的相同。 6． B。 【解析】考查几种特殊二叉树的特点。二叉判定树描述了折半查找的过程，肯定是高度平衡的，因此不可能是A。对于B，此图中所有结点的关键值均大于左子树中结点关键值， 且均小于右子树中所有结点的关键值，B 符合。对于C，此图中存在不平衡子树，错误。对于D，此图不符合小根堆或大根堆的定义。 7． C。 【解析】考查哈夫曼树的构造。将16个权值相等（设为m）的字母看成16个独立的结点；从中任选两个结点构成一棵新的二叉树（共8棵），新树的权值为2m；再从8棵树中任选2棵构成新的二叉树（共4棵），新树的权值为4m，??，如此继续，刚好能构成一棵满二叉树。 8． C。 【解析】考查图的基本性质。强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若E’中的边对应的顶点不是V’中的元素时，则V’和{E’}无法构成图，D错误。 9． D。 【解析】考查邻接矩阵的定义。一个含有n个顶点和e条边的简单无向图的邻接矩阵为n×n矩阵，共有n2个元素，其中非零元素个数为2e，则零元素个数为n2-2e。 10． D。 【解析】考查图的基本性质。n 个顶点构成连通图至少需要n-1 条边（生成树），但若再增加1 条边，则必然会构成环。如果一个无向图有n 个顶点和n-1 条边，可以使它连通但没有环（即生成树），但再加一条边，在不考虑重边的情形下，就必然会构成环。 11． C。 【解析】考查散列表的性质。不同冲突处理方法对应的平均查找长度是不同的，I错误。散列查找的思想是通过散列函数计算地址，然后再比较关键字确定是否查找成功，II正确。平均查找长度与填装因子（即表中记录数与表长之比）有关，III错误。在开放定址的情况下，不能随便删除表中的某个元素（只能标记为删除状态），否则可能会导致搜索路径被中断，IV错误。 12．C。 【解析】考查各种内部排序算法的性能。选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。各种排序方法对应的时间复杂度见下表。 13．C。 【解析】考查初始堆的建立。首先对以第?n/2? 个结点为根的子树（也即最后一个结点的父结点为根的子树）筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。 14． A。 【解析】考查查折半查找的平均查找长度。假设有序表中元素为A[0…11]，不难画出对它所对应的折半查找判定树如下图所示，圆圈是查找成功结点，方形是虚构的查找失败结点。从而可以求出查找成功的ASL=(1+2×2+3×4+4×5)/12 =37/12，查找失败的ASL=(3×3+4×10)/13。 15．B。 【解析】考查快排过程。以28 为基准元素，首先从后向前扫描比28 小的元素，此元素位置为L0，把此元素放到前面基准元素位置，而后再从前向后扫描比28 大的元素，此元素位置L1,并将其放到L0 位置，从而得到了（5,16,L1,12,60,2,32,72）。而后继续重复从后向前扫描，记录找到的比28 小的元素位置L2，把此元素放到L1，再从前往后扫描的操作找到比28 大的元素，此元素位置L3,并