国家二级C语言机试（公共基础知识）模拟试卷9
选择题
1.下列叙述中正确的是( )。(C)
A. 链式存储结构的存储空间一定是连续的
B. 链式存储结构只针对非线性结构
C. 顺序存储结构和链式存储结构都能存储有序表
D. 链式存储结构比顺序存储结构节省存储空间
解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，节点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。链式存储结构既可用于表示线性结构，也可用于表示非线性结构，故A和B选项错误；链式存储结构比顺序存储结构每个元素多了一个或多个指针域，因此比顺序存储结构要多耗费一些存储空间，故D选项错误。
2.下列叙述中正确的是( )。(C)
A. 队列是“先进后出”的线性表
B. 栈是“先进先出”的线性表
C. 数据可分为线性结构和非线性结构
D. 循环队列是非线性结构
解析：本题主要考查了栈、队列、循环队列的概念。栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
3.下列数据结构中，属于非线性结构的是( )。(C)
A. 循环队列
B. 带链队列
C. 二叉树
D. 带链栈
解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。
4.下列数据结构中，能够按照“先进先出”原则存取数据的是( )。(C)
A. 循环队列
B. 栈
C. 队列
D. 二叉树
解析：栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据；队列是“先进先出”(EIFO)或“后进后出”(LILO)的线性表。
5.一个栈的初始状态为空。现将元素1，2，3，A，B，C依次入栈，然后再依次出栈，则元素出栈的顺序是( )。(C)
A. 1，2，3，A，B，C
B. C，B，A，1，2，3
C. C，B，A，3，2，1
D. 1，2，3，C，B，4k
解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是CBA321。
6.下列叙述中正确的是( )。(D)
A. 一个算法的空间复杂度大，则其时间复杂度也必定大
B. 一个算法的空间复杂度大，则其时间复杂度必定小
C. 一个算法的时间复杂度大，则其空间复杂度必定小
D. 算法的时间复杂度与空间复杂度没有直接关系
解析：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知。算法的时间复杂度与空间复杂度并不相关。
7.某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为(假设根节点在第1层)( )。(D)
A. 3
B. 4
C. 6
D. 7
解析：根据二叉树的性质，度为0的节点(叶子节点)总是比度为2的节点多一个。题目中的二叉树的叶子节点为1，因此度为2的节点的数目为0。故该二叉树为7层，每层只有一个节点。
8.下列叙述中正确的是( )。(A)
A. 循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B. 循环队列中的元素个数随队头指针的变化而动态变化
C. 循环队列中的元素个数随队尾指针的变化而动态变化
D. 循环队列中的元素个数不会变化
解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针front指向的后一个位置与队尾指针：rear指向位置之间的元素数量。
9.算法的有穷性是指( )。(A)
A. 算法程序的运行时间是有限的
B. 算法程序所处理的数据量是有限的
C. 算法程序的长度是有限的
D. 算法只能被有限的用户使用
解析：算法的有穷性是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
10.某二叉树中有n个度为2的节点，则该二叉树中的叶子节点数为( )。(A)
A. n+1
B. n一1
C. 2n
D. n／2
解析：在任意一棵二叉树中，度为0的节点，即叶子节点。总是比度为2的节点多一个。所以该二叉树的叶子节点数等于n+1。
11.设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为( )。(D)
A. 15
B. 16
C. 20
D. 0或35
解析：循环队列的队头指针和尾指针都等于15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达15，此时元素个数为0；第二种情况是队头指针第一次到达15，而尾指针第二次到达15，此时元素个数为35。
12.对下列二叉树( )。
(C)
A. DYBEAFCZX
B. YDEBFZXCA
C. ABDYECFXZ
D. ABCDEFXYZ
解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则，①访问根节点；②前序遍历左子树；③前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。
13.下面对对象概念描述正确的是( )。(A)
A. 对象间的通信靠消息传递
B. 对象是名字和方法的封装体
C. 任何对象必须有继承性
D. 对象的多态性是指一个对象有多个操作
解析：对象是面向对象方法中最基本的概念。操作描述了对象执行的功能，通过消息传递，还可以为其他对象使用。操作过程是被封装在对象中，用户看不到，称之为对象的封装性。对象的多态性是指同一个操作可以是不同对象的行为。不是所有的对象都必须有继承性。
14.对长度为n的线性表做快速排序，在最坏情况下，比较次数为( )。(D)
A. n
B. n－1
C. n(n一1)
D. n(n一1)／2
解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n(n－1)／2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称为快速排序法。最坏情况下快速排序退化为冒泡排序。
15.在黑盒测试方法中，设计测试用例的主要根据是( )。(B)
本文档预览：3600字符，共7391字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
