2015福州大学863_数据结构与程序设计_模拟题3答案

模拟题三参考答案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。个结点为根的子树（也即最后一个结点的父结点为根的子树）筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。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,并将其放到L2位置，直到扫描到相同元素，一趟排序完毕。最后得到（5,16,2,12)28(60,32,72).16.D构造函数没有类型说明修饰符的，他是一类特殊的函数。函数名跟类名一样。17.D。首先A肯定错的，int表示整型，char表示字符型，都不是答案。无返回值的话，就用void来修饰，表示返回类型是空的。18.B。复用不能派生出新的类，只有继承才可以派生新类，多继承和单继承都是继承，最佳答案是B。19.C。默认参数必须是从形参表的右边开始定义的，答案C违背了这个原则。20.B。回忆一下视频里面讲过的，虚基类之所以被提出来就是为了解决在一个多继承体系中，对于一个派生类多次继承于某个类，当调用某个继承而来的函数时，如果他的父类们都有这个函数，编译器不知道要调用哪个的问题。比如有一个类D，他继承与B和C，而B和C又继承于A，同时A里面有个函数叫display，当我们调用d.display时，就有可能会出错，这时候就要考虑用虚基类了。21.B。B之外的其他操作符都是逻辑操作符，&与操作，|或操作，^异或操作。可以参考一下操作符优先级的表。一般优先级的表我们记不住也没必要记，对于这题，逻辑运算的&，|，^肯定比逻辑判断&&更高级，毕竟一个是运算一个是判断。22.C.这道题比较简单了。C++的输出到屏幕的语句也就是输出流ostream的对象，cout就是ostream的对象。C只不过是个普通的运算语句。23.C.函数的定义形式是类似这样的voidfun(){},其中void就是题目中提到的所谓的函数的类型，事实上很少有什么函数的类型这种说法。一般都说函数的返回类型。函数的返回类型除了void外，还有int，char等内置类型，还可以是自定义的类类型。24.D.友元函数函数可以申明在一个类A的任意位置，他没有共有私有的区别，什么在什么地方都是一样的；友元函数可以是这个类A外面的某个函数，所以他没有this指针，因为他不是类的成员，只是一个函数，this指针只有类的成员函数才有。友元函数是具有特权的函数，他可以访问定义了他为友元函数的类的私有成员。25.A.在while(inti=0)这句里面，定义了一个变量i，并且给他赋值0，然后编译器就会把i和0进行比较，如果i==0，那么就直接跳过循环体了，没在循环体里面执行，所以答案是0次。这道题比较怪，如果有兴趣知道为什么这样的话请继续看下去，否则可以直接跳过。我们建立一个工程test，源程序只有while(inti=0)i--;这行代码，然后编译运行，发现程序很快就运行结束了。然后找到这个程序的PE文件，也就是test.exe，对他进行反汇编。其中[ebp-8]就是变量i。分析汇编代码movdwordptr[ebp-8],0//将0赋值给iCmpdwordptr[ebp-8],0//将i和0比较Jeshort009F1386//如果i和0相等则跳转到009F1386继续执行好了，分析完毕。跳转到009F1386也就是xoreax，eax所在那行，程序再执行几行代码也就返回了。由此可以看出，程序没有跳入到循环体里面，也就是009F137B~009F1384所在的代码，因此循环体没有被执行，循环0次。26.A。你会发现这道题在两份试卷里面都有，意思就是要让你分清楚const修饰函数和变量的区别。做个总结：指针使用cosnt：（1）指针本身是常量不可变(char*)constpContent;const(char*)pContent;(2)指针所指向的内容是常量不可变const(char)*pContent;(char)const*pContest;(3)两者都不可变constchar*constpContent;(4)还有其中区别方法，沿着*号划一条线：如果const位于*的左侧，则const就是用来修饰指针所指向的变量，即指针指向为常量；如果const位于*的右侧，const就是修饰指针本身，即指针本身是常量。函数中使用CONST(1)const修饰函数参数a.传递过来的参数在函数内不可以改变(无意义，因为Var本身就是形参)voidfunction(constintVar);b.参数指针所指内容为常量不可变voidfunction(constchar*Var);c.参数指针本身为常量不可变(也无意义，因为char*Var也是形参)voidfunction(char*constVar);d.参数为引用，为了增加效率同时防止修改。修饰引用参数时：voidfunction(constClass&Var);//引用参数在函数内不可以改变voidfunction(constTYPE&Var);//引用参数在函数内为常量不可变27.A.比较简单，不解释了。28.B.经过编辑、编译、连接和运行四个步骤。编辑是将C++源程序输入计算机的过程，保存文件名为cpp。编译是使用系统提供的编译器将源程序cpp生成机器语言的过程，目标文件为obj，由于没有得到系统分配的绝对地址，还不能直接运行。连接是将目标文件obj转换为可执行程序的过程，结果为exe。运行是执行exe，在屏幕上显示结果的过程。29.A。This指针是隐藏的，比如说有一个类A，那么他的对象比如说有a，b，c。。。非常多，那么这些对象，每一个都有一个this指针，可以用来访问他们自己的成员变量。this指针跟他的子类没有一毛钱关系，他的子类的对象有他们自己的this指针。30.C。首先要看懂这句a=aa--，a--的返回值是a本身，--a的返回值是（a-1）。剩下的没难度了，请自行分析。二、填空题1．继承，封装和多态性2．C3．包含头文件4．105．0解释：AB*a[10]={&a1,&a2}这句话的意思是定义10个AB类型的指针。其中a[0],a[1]指向a1和a2，其中a1,a2前面的&是取址符号。从a[3]~a[9]还没有指向任何对象，也就没有调用任何构造函数了。调用构造函数的情况发生在类似这样的语句中a[3]=newAB()6.intAB::bb=10;7.重载虚函数8.抽象类9.1310.delete[]ptr;三、阅读程序1、13422.n=11n=12解析：int*pn=&n;这句说明pn是个指针，并且他指向n。int*&rn=pn;这句看起来比较复杂，我们可以这样理解，既然可以把pn的值赋值给rn，那rn首先是个指针，而且是整型指针也就是int*。然后看到rn的前面有&，这个符号位于等号的左边，所以他是个引用符号。综上就是，rn是个指向整型指针的pn的引用，也就是pn的别名而已，可以把它们看成同一个东西。所以(*pn)++;(*rn)++;这两句实际上都在操作n，因为他们都指向n。3、A::a=1A::a=1A::a=1解析：其实这题就是看你对多态性质的理解。B和C都继承于A，并且都定义了各自的show函数，所以B，C从A继承而来的show会被重写。然后定义了一个A类型的指针p，分别用父类指针p去指向a，和他的子类对象b，c。每次都调用一次show（），但是实际上调用的都是A类的show。原因在于指针p是A类型的，他只懂得到A类中去找show函数。其实这也是多态性质提出的原因，人们想通过父类指针来调用它真实对象的函数。在A类的show函数中加上前缀virtual就形成多态了。答案也会变得不同。4、ConstructorofCBase.m_data=abcdConstructorofCDerived.m_data=abcdDestr