2016年度福州大学863数据结构与程序设计模拟题1.doc

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

1、2016年福州大学863数据结构与程序设计模拟题一一单项选择题：每小题2 分（共60分）1为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区， 主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 （） A栈 B队列 C树 D图2设栈S 和队列Q 的初始状态均为空，元素a，b，c，d，e，f，g 依次进入栈S。若每个元素出栈后立即进入队列Q，且7 个元素出队的顺序是b，d，c，f，e，a，g，则栈S 的容量至少是 （）A1 B2 C3 D43给定二叉树如下图 所示，设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子

2、树。若遍历后的结点序列是3，1，7，5，6，2， 4，则其遍历方式是 （）ALRN BNRL CRLN DRNL4下列二叉排序树中，满足平衡二叉树定义的是（）A B C D5已知一棵完全二叉树的第6 层（设根为第1 层）有8 个叶结点，则该完全二叉树的结点个数最多是 ()A39 B52 C111 D1196将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点， 则在原来的森林中，u 和v 可能具有的关系是 ()父子关系 兄弟关系 u 的父结点与v 的父结点是兄弟关系 A只有 B和 C和 D、和7下列关于无向连通图特性的叙述中，正确的是( ) 所有顶点的度之和为偶数 边数大

3、于顶点个数减1 至少有一个顶点的度为1 A只有 B只有 C和 D和8下列叙述中，不符合m 阶B 树定义要求的是() A根结点最多有m 棵子树 B所有叶结点都在同一层上 C各结点内关键字均升序或降序排列 D叶结点之间通过指针链接9若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是()A冒泡排序 B插入排序 C选择排序 D二路归并排序10. 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是 ()Ad c e b f a Bc b d a e f Cb c

4、a e f d Da f e d c b11某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是 () Ab a c d e Bd b a c e Cd b c a e De c b a d12在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）A13，48 B24，48 C24，53 D24，9013在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是

5、（）A41 B82 C113 D12214.对n（n2）个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是（） A该树一定是一棵完全二叉树 B树中一定没有度为1的结点 C树中两个权值最小的结点一定是兄弟结点 D树中任一非叶结点的权值一定不小于下一层任一结点的权值。15若无向图G=(V, E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是 （） A6 B15 C16 D2116. 已知关键字序列5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字3，调整后得到的小根堆是 （）A3，5，12，8，28，20，15，22，19 B3，

6、5，12，19，20，15，22，8，28 C3，8，12，5，20，15，22，28，19 D3，12，5，8，28，20，15，22，1917.下面的循环体哪个执行的次数与其他不同( )A for(i=0; i10; i+) couti=1; i-) couti ; C i=10; do couti0);D i=0; while(+i=10) couti ; 18.有如下定义语句：int a=1,2,3,4,5;，则对语句int *p=a;正确的描述是( )。A 语句 int *p=a;定义不正确B 语句 int *p=a;初始化变量p，使其指向数组对象a的第一个元素C 语句int *p=

7、a; 是把a0的值赋给变量pD 语句int *p=a; 是把a1的值赋给变量p19. 若有以下定义和语句，则不能合法表示a数组元素的是：( ) char a=”abcdefg”；int *p=a; A p7 B ap-a C *a D a820. 下列程序中错误的语句是：（）#include#includeusing namespace std;main( )char *pt1=1234;char pt2 =12;char *pt3=34;A.pt3=pt2; B.strcpy(pt1, pt2); C.strcpy(pt2, pt3); D.coutpt2; 21.系统在调用重载函数时往往根

8、据一些条件确定哪个重载函数被调用，在下列选项中，不能作为依据的是（ ）。A函数的返回值类型 B参数的类型 C函数名称 D参数个数22. 已知：int m=10; 下列表示引用的方法中，（ ）是正确的。Aint &x=m; Bint &y=10; Cint &z; Dfloat &t=&m;23. 下列有关C+类的说法中，不正确的是（ ）。A类是一种用户自定义的数据类型B只有类中的成员函数或类的友元函数才能存取类中的私有成员C在类中，如果不做特别说明，所有成员的访问权限均为私有的D在类中，如果不做特别说明，所有成员的访问权限均为公用的24.已知X类，则当程序执行到语句X array3;时，调用了

9、（ ）次构造函数。A0 B1 C2 D325. 考虑下面的函数原型声明：void testDefaulParam(int a,int b=7,char z=*);下面函数调用中，不合法的是（ ）。AtestDefaulParam(5); BtestDefaulParam(5,8);CtestDefaulParam(5,#); DtestDefaulParam(0,0,*);26. 有关析构函数的说法，不正确的是（ ）。A析构函数有且仅有一个B析构函数和构造函数一样可以有形参C析构函数的功能是在系统释放对象之前作一些内存清理工作D析构函数无任何函数类型27. 类定义的内容允许被其对象无限制地存取

10、的是（ ）。Aprivate 部分 B protected 部分 Cpublic 部分 D以上都不对28. 可以在类外用p.a的形式访问派生类对象p的基类成员a，其中a是（ ）。A私有继承的公用成员 B公用继承的私有成员C公用继承的保护成员 D公用继承的公用成员29. 设置虚基类的目的是（ ）。A简化程序 B消除二义性 C提高运行效率 D减少目标代码30. 在C+中，用于实现动态多态性的是（ ）。A内联函数 B重载函数 C模板函数 D虚函数二填空题（每空两分，共32分）1、类和对象的关系可表述为：类是对象的 ，而对象则是类的 。2、在C+中，三种继承方式的说明符号为 、 和 ，如果不加说明，则

11、默认的继承方式为 。3、如果只想保留公共基类的一个复制，就必须使用关键字 把这个公共基类声明为虚基类。4、若要把void fun()定义为类A的友元函数，则应在类A的定义中加入语句 。5、类的静态成员分为 和 。6、运算符重载要求保持其原来的操作数个数、 、 和语法结构。7、通过关键字 可以声明模板，通过关键字 指定函数模板的类型参数，有几个类型参数就有几个类型关键字。8、列出C+中两种用户自定义的数据类型： 、 。9、构造函数的作用是 。10、后置自增运算符“+”重载为类的成员函数（设类名为A）的形式为 。三阅读程序，写出下列程序的运行结果（共20分，每题5分）1.#include void

12、 main()int i,j;for( i=5;i0;i-) for(j=i*2-1;j0;j-)cout*;coutendl;2. #include #include void fun(char *w,int m)char s,*p1,*p2;p1=w;p2=w+m-1;while(p1p2)s=*p1+;*p1=*p2-;*p2=s;void main()char a =”1234567”,;fun(a,strlen(a);coutaendl;3. 假设输入10个整数为32,64,53,87,54,32,98,56,87,83，写出下列程序的运行结果。#include void main(

13、)int a,b,c,x;a=b=c=0;for(int i=0;ix;switch(x%3) case 0:a+=x;break; case 1:b+=x;break; case 2:c+=x;break;couta,b,cendl;4.#includeint w=2;fun(int k)if(k=0) return w;return (fun(k-1)*k);void main()int w=10;coutfun(5)*w;四算法和程序设计题（共58分）1.（13分）已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法

14、，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想。 （2）描述算法的详细实现步骤。 （3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C+语言实现），关键之处请给出简要注释。2（ 15分） 设有五个数据 do， for， if， repeat， while，它们排在一个有序表中，其查找概率分别为 p1=0.2， p2=0.15， p3=0.1， p4=0.03， p5=0.01。而查找它们之间不存在数据的概率分别为 q0=0.2， q1=0.15， q2=0.1， q3=0.

15、03， q4=0.02， q5=0.01。（ 1） 试画出对该有序表分别采用顺序查找和折半查找时的判定树。（ 2） 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。（ 3） 判定是顺序查找好？还是折半查找好？3.（15分）对于一个堆栈、若其入栈序列为 1,2,3,n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n 的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入（固定为 1,2,3,n） / 输出序列对应一种二叉树形态的方法，并以入栈序列 1,2,3（即 n=3）为例加以说明。4.（15分）二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为：其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求： 1）给出算法的基本设计思想； 2）使用C或C+语言，给出二叉树结点的数据类型定义； 3）根据设计思想，采用C或C+语言描述算法，关键之处给出注释。