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 的容量至少是 （）
A．1 B．2 C．3 D．4
3．给定二叉树如下图 所示，设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是3，1，7，5，6，2， 4，则其遍历方式是 （）
A．LRN B．NRL C．RLN D．RNL
4．下列二叉排序树中，满足平衡二叉树定义的是（）
A B C D
5．已知一棵完全二叉树的第6 层（设根为第1 层）有8 个叶结点，则该完全二叉树的结点个数最多是 ()
A．39 B．52 C．111 D．119 6．将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父
结点， 则在原来的森林中，u 和v 可能具有的关系是 ()Ⅰ．父子关系 Ⅱ．兄弟关系 Ⅲ．u 的父结点与v 的父结点是兄弟关系
A．只有Ⅱ B．Ⅰ和Ⅱ C．Ⅰ和Ⅲ D．Ⅰ、Ⅱ和Ⅲ
7．下列关于无向连通图特性的叙述中，正确的是( )
Ⅰ．所有顶点的度之和为偶数 Ⅱ．边数大于顶点个数减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依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不．可能得到的出栈序列是 () A．d c e b f a B．c b d a e f C．b c a e f d D．a f e d c b
11．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不．可能得到的出队序列是 () A．b a c d e B．d b a c e C．d b c a e D．e c b a d
12在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（） A．13，48 B．24，48 C．24，53 D．24，90
13在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2
的结点，10个度为1的结点，则树T的叶结点个数是（） A．41 B．82 C．113 D．122
14.对n（n≥2）个权值均不相同的字符构造成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是（）
A．该树一定是一棵完全二叉树 B．树中一定没有度为1的结点 C．树中两个权值最小的结点一定是兄弟结点 D．树中任一非叶结点的权值一定不小于下一层任一结点的权值。
15若无向图G=(V, E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是 （）
A．6 B．15 C．16 D．21
16. 已知关键字序列5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字3，调整后得到的小根堆是 （） A．3，5，12，8，28，20，15，22，19 B．3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D．3，12，5，8，28，20，15，22，19 17.下面的循环体哪个执行的次数与其他不同( ) A for(i=0; i<10; i++) { cout< 18.有如下定义语句：int a[]={1,2,3,4,5};，则对语句int *p=a;正确的描述是( )。 A 语句 int *p=a;定义不正确 B 语句 int *p=a;初始化变量p，使其指向数组对象a的第一个元素 C 语句int *p=a; 是把a[0]的值赋给变量p D 语句int *p=a; 是把a[1]的值赋给变量p 19. 若有以下定义和语句，则不能合法表示a数组元素的是：( ) char a[]=”abcdefg”； int *p=a; A p[7] B a[p-a] C *a D a[8] 20. 下列程序中错误的语句是：（） #include char *pt1=\char pt2[ ]=\char *pt3=\ A.pt3=pt2; B.strcpy(pt1, pt2); C.strcpy(pt2, pt3); D.cout< 21.系统在调用重载函数时往往根据一些条件确定哪个重载函数被调用，在下列选项中，不能作为依据的是（ ）。 A．函数的返回值类型 B．参数的类型 C．函数名称 D．参数个数 22. 已知：int m=10; 下列表示引用的方法中，（ ）是正确的。 A．int &x=m; B．int &y=10; C．int &z; D．float &t=&m; 23. 下列有关C++类的说法中，不正确的是（ ）。 A．类是一种用户自定义的数据类型 B．只有类中的成员函数或类的友元函数才能存取类中的私有成员 C．在类中，如果不做特别说明，所有成员的访问权限均为私有的 D．在类中，如果不做特别说明，所有成员的访问权限均为公用的 24.已知X类，则当程序执行到语句X array[3];时，调用了（ ）次构造函数。 A．0 B．1 C．2 D．3 25. 考虑下面的函数原型声明：void testDefaulParam(int a,int b=7,char z='*'); 下面函数调用中，不合法的是（ ）。 A．testDefaulParam(5); B．testDefaulParam(5,8); C．testDefaulParam(5,'#'); D．testDefaulParam(0,0,'*'); 26. 有关析构函数的说法，不正确的是（ ）。 A．析构函数有且仅有一个 B．析构函数和构造函数一样可以有形参 C．析构函数的功能是在系统释放对象之前作一些内存清理工作 D．析构函数无任何函数类型 27. 类定义的内容允许被其对象无限制地存取的是（ ）。 A．private 部分 B． protected 部分 C．public 部分 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++中，三种继承方式的说明符号为 、 和 ，如果不加说明，则默认的继承方式为 。 3、如果只想保留公共基类的一个复制，就必须使用关键字 把这个公共基类声明为虚基类。 4、若要把void fun()定义为类A的友元函数，则应在类A的定义中加入语句 。 5、类的静态成员分为 和 。 6、运算符重载要求保持其原来的操作数个数、 、 和语法结构。 7、通过关键字 可以声明模板，通过关键字 指定函数模板的类型参数，有几个类型参数就有几个类型关键字。 8、列出C++中两种用户自定义的数据类型： 、 。 9、构造函数的作用是 。 10、后置自增运算符“++”重载为类的成员函数（设类名为A）的形式为 。