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

福州大学863数据结构与程序设计模拟题二 一．单项选择题：每小题2 分（共60分） 1．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（） x=2； while(xn/2) x=2*x； A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2) 2．元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是 ( ) A．3 B．4 C．5 D 3．已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是() A．0，0 B．0，n-1 C．n-1，0 D．n-1 4．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是() A．257 B．258 C．384 D 5．若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是() A．1，2，3，4 B．2，3，4，1 C．3，2，4，1 D．4，3，2 6．已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是() A．115 B．116 C．1895 D 7．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是() A．95，22，91，24，94，71 B．92，20，91，34，88，35 C．21，89，77，29，36，38 D．12，25，71，68，33，34 8．下列关于图的叙述中，正确的是() Ⅰ．回路是简单路径 Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间 Ⅲ．若有向图中存在拓扑序列，则该图不存在回路 A．仅Ⅱ B．仅Ⅰ、Ⅱ C．仅Ⅲ D．仅Ⅰ、Ⅲ 9．为提高散列（Hash）表的查找效率，可以采取的正确措施是() Ⅰ．增大装填（载）因子 Ⅱ．设计冲突（碰撞）少的散列函数 Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象 A．仅Ⅰ B．仅Ⅱ C．仅Ⅰ、Ⅱ D．仅Ⅱ、Ⅲ 11．已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是() A．1 B．2 C．4 D 12. 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（） A．4 B．3 C．2 D 13.已知一个长度为16 的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多的是（） A．4 B．5 C．6 14．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（） A．递归次数与初始数据的排列次序无关 B．每次划分后，先处理较长的分区可以减少递归次数 C．每次划分后，先处理较短的分区可以减少递归次数 D．递归次数与每次划分后得到的分区的处理顺序无关 15.对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是（） A.冒泡排序 B．希尔排序 C．归并排序 D．基数排序 16. C++是（ ）。 A. 面向对象的程序设计语言 B. 面向过程的程序设计语言 C. 既支持面向对象的程序设计又支持面向过程的程序设计的混合型语言 D. 非结构化的程序设计语言 17.面向对象程序设计思想的主要特征中不包括（ ）。 A. 封装性 B. 多态性 C. 继承性 D. 功能分解，逐步求精 18.若定义：string str; 当语句cinstr; 执行时，从键盘输入: Microsoft Visual Studio 6.0! 所得的结果是str=（ ）。 A. Microsoft Visual Studio 6.0! B. Microsoft C. Microsoft Visual D. Microsoft Visual Studio 6.0 19.考虑下面的函数原型声明：void testDefaulParam(int a,int b=7,char z=*);