2015年度福州大学863数据结构与程序设计模拟题1标准答案.doc

《2015年度福州大学863数据结构与程序设计模拟题1标准答案.doc》由会员分享，可在线阅读，更多相关《2015年度福州大学863数据结构与程序设计模拟题1标准答案.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. 模拟题一参考答案一、单项选择题 1B。考查栈和队列的特点及应用。 C和D直接排除，缓冲区的特点需要先进先出，若用栈，先进入缓冲区的数据则要排队到最后才能打印，不符题意，故选B。 2C。考查栈的最大递归深度。时刻注意栈的特点是先进后出。出入栈的详细过程见表栈内的最大深度为3，故栈S的容量至少是3。3D。考查二叉树的特殊遍历。 分析遍历后的结点序列，可以看出根结点是在中间被访问的，而右子树结点在左子树之前，得遍历的方法是RNL。本题考查的遍历方法并不是二叉树的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。4B。考查平衡二叉树的定义。 根据平衡二叉树的定义有，任意结点的左、右子树高度

2、差的绝对值不超过1。而其余三个答案均可以找到不符合的结点。5C。考查完全二叉树的特点。 完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了82=16个叶结点，故完全二叉树的结点个数最多为27-1-16=111个结点。6B。考查森林和二叉树的转换。 森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。 情形：若结点v是结点u的第二个孩子结

3、点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。 情形：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩子，符合要求。 情形：结点v的父结点要么是原先的父结点或兄弟结点。若结点u的父结点与v的父结点是兄弟关系，则转换之后，不可能出现结点u是结点v的父结点的父结点。7A。考查无向连通图的特性。 每条边都连接了两个结点，则在计算顶点的度之和时，这条边都被计算了两次，故所有顶点的度之和为边数的两倍，显然必为偶数。而和则不一定正确，如对顶点数N1 无向完全图不存在一个顶点的度为1，并且边数与顶点数的差要大于1。8D。

4、考查m 阶B-树的定义。 选项A、B 和C 都是B-树的特点，而选项D 则是B+树的特点。注意区别B-树和B+树各自的特点。9. 解答本题之前要对不同排序算法的特点极为清楚。对于冒泡排序和选择排序而言，每趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案D 中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。10. D。考查限定条件的出栈序列。 A可由in，in，in，in，

5、out，out，in，out，out，in，out，out得到； B可由in，in，in，out，out，in，out，out，in，out，in，out得到； C可由in，in，out，in，out，out，in，in，out，in，out，out得到； D可由in，out，in，in，in，in，in，out，out，out，out，out得到，但题意要求不允许连续三次退栈操作，故D错。11. C。考查受限的双端队列的出队序列。 A可由左入，左入，右入，右入，右入得到；B可由左入，左入，右入，左入，右入得到；D可由左入，左入，左入，右入，左入得到。所以不可能得到C。12.C。考查平衡二叉树

6、的插入算法。 插入48以后，该二叉树根结点的平衡因子由-1变为-2，失去平衡，需进行两次旋转（先右旋后左旋）操作。13. B。考查树结点数的特性。 设树中度为i（i=0，1，2，3，4）的结点数分别为Ni，树中结点总数为N，则树中各结点的度之和等于N-1，即N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4，根据题设中的数据，即可得到N0=82，即树T的叶结点的个数是82。14. A。考查赫夫曼树的特性。 赫夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。赫夫曼树中没有度为1的结点，B正确；构造赫夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C正确

7、；赫夫曼树中任一非叶结点P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点P的左、右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左、右子树构造新的二叉树。综上可知，赫夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。15C。考查图的连通性。 要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1，需15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。16. A。考查小根堆的调整操作。 小根堆在逻辑上可以

8、用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式如图17.C18.B19.D20.B21.A22.A23.D24.D25.C26.B27.C28.D29.B30.D二填空题1 抽象 、 实例 2 public 、 private _ _、 protected 、 private _ _3 virtual _ 4 friend void fun(A &a) 5 静态数据成员 、 静态成员函数 6 结合性 、 优先级_ _7 Template 、 class(或typename) 8 类 、 结构体 _9 在创建对象时初始化对象的数据成员 _10 A operator+(int) 三 1.

9、* 2. 1711717 3.228,64,354 4.2400 * * * *四程序设计题算法题1. （1）算法的基本设计思想（5分）： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想：定义两个指针变量p和q，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。 （2）算法的详细实现步骤（5分）： count=0，p和q指向链表表头结点的下一个结点； 若p为空，转； 若c

10、ount等于k，则q指向下一个结点；否则，count=count+1； p指向下一个结点，转； 若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0； 算法结束。 （3）算法实现（5分）： typedef int ElemType; /链表数据的类型定义 typedef struct LNode /链表结点的结构定义 ElemType data; /结点数据 struct Lnode *link; /结点链接指针 *LinkList;int Search_k(LinkList list,int k) /查找链表list倒数第k个

11、结点，并输出该结点data域的值 LinkList p=list-link,q=list-link; /指针p、q指示第一个结点 int count=0; while(p!=NULL) /遍历链表直到最后一个结点 if(countk) count+; /计数，若countlink;p=p-link; /之后让p、q同步移动 /while if(countdata); return 1; /Search_k 提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。所给出的算法采用一遍扫描方式就能得到正确结

12、果，可给满分15分；若采用两遍或多遍扫描才能得到正确结果的，最高给10分；若采用递归算法得到正确结果的，最高给10分；若实现算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分；若实现的算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分。 参考答案中只给出了使用C语言的版本，使用C+/JAVA语言正确实现的算法同样给分。 若在算法基本思想描述和算法步骤描述中因文字表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照的标准给分。 若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。

13、算法题2:答：采用顺序查找的判定树如下：采用折半查找的判定树如下：（ 2）根据各数据查找所需的比较次数，以及查找概率可得到平均查找长度为：ASL 顺序成功 = (1p1+2p2+3p3+4p4+5p5)/(p1+p2+p3+p4+p5)=0.97/0.49=1.98 ASL 顺序失败 = (1q0+2q1+3q2+4q3+5q4+5q5)=1.07/0.51=2.10 ASL 折半成功 = (1p3+2(p1+p4)+3(p2+p5)/(q0+q1+q2+q3+q4+q5)=1.04/0.49=2.12 ASL 折半失败 = (2q0+3q1+3q2+2q3+3q4+3q5)=1.30/0.5

14、1=2.55（ 3）由上题的计算结果可知，本题采用顺序查找更好。算法题3:答：（ 1）算法的基本设计思想：本题要找 p 和 q 的最近父结点 r，不失一般性，设 p 在 q 的左边。采用后序遍历，后序遍历最后访问根结点，即在递归算法中，根是压在栈底的，当访问到某结点时，栈中所有结点均为该结点的祖先。后序遍历必然先遍历到结点 p，栈中元素均为 p 的祖先。先将栈复制到另一辅助栈中。继续遍历到结点 q 时，将栈中元素从栈底开始逐个到辅助栈中去匹配，第一个失配的元素前面元素就是结点 p 和 q 的共同父结点。算法的步骤如下：设要匹配结点是 p 和 q，设置当前工作指针 bt，初始化为 root，栈顶

15、指针 top 为 0。顺着 bt 的左分支查找元素。 如果 bt 与 p 和 q 都不相等， 则把 bt 的左分支进栈；如果bt 的左子树为空，转向。如果栈非空，栈顶元素右子树没有进栈，执行，如果右子树进栈， 那么判断栈顶元素是否与 p 和 q 中一个第一次相等， 如果和 p 和 q 都不相等则退栈，重复执行。如果找到第一个相等，则保存此时的栈中元素和剩余的指针。如果栈顶元素与 p 和 q 中剩余那个指针相等，则从栈底开始逐个到辅助栈中去匹配，返回第一个失配前的元素。结束。栈顶元素的右子树进栈， bt 指向栈顶元素的右子结点，执行。（ 2）算法的实现如下：typedef structBiTre

16、e t;int tag; /tag=0表示左子女已被访问， tag=1表示右子女已被访问stack;stack s,s1; /栈，容量足够大BiTree CommonParent(BiTree ROOT,BiTNode *p,BiTNode *q) /求二叉树中p和q的最近公共父节点int top=top1=0; /栈顶指针BiTree bt=ROOT; /初始化bt工作指针Bool first=false; /第一次找到p或者qBiTree rest=NULL; /找到p或者q后的剩余的指针while(bt!=NULL|top0) while(bt!=NULL&(bt!=p|bt!=q) /

17、结点入栈。s+top.t=bt;stop.tag=0;bt=bt-lchild; /沿左分支向下if（bt!=NULL&bt=p&bt=q) return top0? stop.t:NULL;/如果p和q相同，直接返回父结点while(top!=0&stop.tag=1) /如果右孩子树已经遍历过，遍历本结点，实现后序遍历If(!first)if(stop.t=p)/假定遇到p时，栈中元素均为p的祖先for(i=1;itop;i+)s1i=si; /复制到辅助栈top1=top-1;first=true;rest=q; /设置剩余指针 /将栈s的元素转入辅助栈s1保存其父节点else if(s

18、top.t=q) 假定遇到q时，栈中元素均为q的祖先for(i=1;itop;i+)s1i=si; /复制到辅助栈top1=top-1;first=true;rest=p; /设置剩余指针else if(stop.t=rest) /找到剩余结点int min=top1top-1? top1:top-1;for(int i=1;imin) return smin;top-; /退栈 /while(top!=0&stop.tag=1)if(top!=0)/此时， stop.tag=0，所以右孩子进栈。stop.tag=1;bt=stop.t-rchild; /沿右分支向下遍历 /while(bt!

19、=NULL|top0)【思路（ 2）】 从根结点开始，判断以当前结点为根的左右子树中是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那么最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那么最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那么当前的结点就是最低的共同父结点。 可以采用树的后序遍历。【思路（ 3）】 本题可以求出从根结点到 p 和 q 的路径（看成是单向链表），然后设想每个结点都有一个指向其父结点的指针（建 2 个辅助链表，也即将单向链表逆置），于是可以从任何一个结点出发，得到一个到达根结点的单向链表

20、，因此这个问题转换为求两个单链表的第一个公共结点。算法题4. 考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。 1）算法的基本设计思想： 基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下： 若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积； 若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加一； 最后返回计算出的wpl即可。 基于层次遍历的算法思想是使用队列进行层

21、次遍历，并记录当前的层数， 当遍历到叶子结点时，累计wpl； 当遍历到非叶子结点时对该结点的把该结点的子树加入队列； 当某结点为该层的最后一个结点时，层数自增1； 队列空时遍历结束，返回wpl 2)二叉树结点的数据类型定义如下：typedef struct BiTNode int weight; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;3)算法代码如下： 基于先序遍历的算法： int WPL(BiTree root) return wpl_PreOrder(root, 0); int wpl_PreOrder(BiTree root, i

22、nt deep) static int wpl = 0; /定义一个static变量存储wplif(root-lchild = NULL & root-lchild = NULL)wpl += deep*root-weight; /若为叶子结点，累积wplif(root-lchild != NULL) /若左子树不空，对左子树递归遍历 wpl_PreOrder(root-lchild, deep+1); if(root-rchild != NULL) /若右子树不空，对右子树递归遍历 wpl_PreOrder(root-rchild, deep+1); return wpl; 若考生给出能够满

23、足题目要求的其他算法，且正确，可同样给分。 考生答案无论使用C或者C+语言，只要正确同样给分。 若对算法的基本设计思想和主要数据结构描述不十分准确，但在算法实现中能够清晰反映出算法思想且正确，参照的标准给分。 若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他数值，可视同使用整型类型。 若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。 注意：上述两个算法一个为递归的先序遍历，一个为非递归的层次遍历，读者应当选取自己最擅长的书写方式。直观看去，先序遍历代码行数少，不用运用其他工具，书写也更容易，希望读者能掌握。 在先序遍历的算法中，static是一个静态变量，只在首次调用函数时声明wpl并赋值为0，以后的递归调用并不会使得wpl为0，具体用法请参考相关资料中的static关键字说明，也可以在函数之外预先设置一个全局变量，并初始化。不过考虑到历年真题算法答案通常都直接仅仅由一个函数构成，所以参考答案使用static。