国家二级C语言机试（公共基础知识）模拟试卷11
选择题
1.下列叙述中正确的是( )。(B)
A. 有一个以上根节点的数据结构不一定是非线性结构
B. 只有一个根节点的数据结构不一定是线性结构
C. 循环链表是非线性结构
D. 双向链表是非线性结构
解析：在数据结构中，树这类的数据结构只有一个根节点，但它不是线性结构。
2.下列叙述中错误的是( )。(B)
A. 循环队列有队头和队尾两个指针
B. 循环队列是非线性结构
C. 循环队列中元素的动态变化由队头和队尾指针共同反映
D. 循环队列中元素的个数是由队头指针和队尾指针共同决定
解析：循环队列是线性结构，包含队头和队尾两个指针。循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。
3.下面叙述中正确的是( )。(A)
A. 线性表是线性结构
B. 栈与队列是非线性结构
C. 线性链表是非线性结构
D. 二叉树是线性结构
解析：线性表是最简单的、最常用的一种线性结构。所谓线性链表指的是采用链式存储结构的线性表。栈和队列其实是一种特殊的线性表。树是一种简单的非线性结构，二叉树是树的一种。
4.下列关于栈的叙述中，正确的是( )。(C)
A. 栈底元素一定是最后入栈的元素
B. 栈顶元素一定是最先入栈的元素
C. 栈操作遵循先进后出的原则
D. 以上三种说法都不对
解析：栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出”的规则操作元素。
5.按照“后进先出”原则组织数据的数据结构是( )。(B)
A. 队列
B. 栈
C. 双向链表
D. 二叉树
解析：栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素。也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。即栈是按照“后进先出”(Last In First Out，简称LIFO)或“先进后出”(First In Last Out，简称FILO)的原则组织数据的。因此，栈也称为“后进先出表”或“先进后出表”。
6.下列描述中正确的是( )。(D)
A. 一个逻辑数据结构只能有一种存储结构
B. 数据的逻辑结构属于线性结构，存储结构属于非线性结构
C. 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
D. 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
解析：数据的逻辑结构是指数据集合中各数据元素之间所固有的逻辑关系，数据的存储结构是在对数据进行处理时，各数据元素在计算机中的存储关系。数据的存储结构是指数据的逻辑结构在计算机中的表示，一种逻辑结构可以表示成多种存储结构，而采用不同的存储结构，其数据处理的效率是不同的。
7.设树T的深度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1。则T中的叶子节点数为( )。(B)
A. 8
B. 7
C. 6
D. 5
解析：深度为m，二叉树其总节点数为2m一1=24一1=15。总节点数减去度为1，2，3，4的节点个数就是叶子节点数。15—4一2—1—1=7。
8.下列叙述中正确的是( )。(C)
A. 线性表链式存储结构的存储空间一般要少于顺序存储结构
B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的
C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的
D. 以上都不正确
解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
9.算法的空间复杂度是指( )。(A)
A. 算法在执行过程中所需要的计算机存储空间
B. 算法所处理的数据量
C. 算法程序中的语句或指令条数
D. 算法在执行过程中所需要的临时工作单元数
解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
10.一棵二叉树共有31个节点，其中8个是叶子节点，则度为1的节点数为( )。(A)
A. 16
B. 10
C. 6
D. 4
解析：根据二叉树的性质，在任意二叉树中，度为0的节点(叶子节点)总是比度为2的节点多一个。故此度为Ⅰ的节点个数=总节点数一叶子节点数一度为2的节点数：31—8—7=16。
11.下列叙述中正确的是( )。(C)
A. 栈是一种先进先出的线性表
B. 队列是一种后进先出的线性表
C. 栈与队列都是非线性结构
D. 栈与队列都是线性结构
解析：栈是先进后出，队列是先进先出。栈和队列都是一种线性表，属于线性结构。
12.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为( )。(C)
A. log2n
B. n／2
C. n
D. n+1
解析：在进行顺序查找过程中，如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中的所有元素进行比较，这是顺序查找的最坏情况，需要比较的次数为n次。
13.下列选项中不属于面向对象程序设计特征的是( )。(C)
A. 继承性
B. 多态性
C. 类比性
D. 封装性
解析：面向对象程序设计的三个主要特征是：封装性、继承性和多态性。封装性即只需知道数据的取值范围和可以对该数据施加的操作，而无须知道数据的具体结构以及实现操作的算法。继承性是指使用已有的类定义作为基础建立新类的定义技术。对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行动，该现象称为多态性。
14.下列排序方法中，最坏情况下比较次数最少的是( )。(D)
A. 冒泡排序
B. 简单选择排序
C. 直接插入排序
D. 堆排序
解析：冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为：n(n—1)／2。而堆排序法在最坏的情况下需要比较的次数为O(nlog2n，)。其中堆排序的比较次数最少。
15.下面属于白盒测试方法的是( )。(B)
A. 等价类划分法
B. 逻辑覆盖
C. 边界值分析法
D. 错误推测法
解析：白盒测试的主要方法有逻辑覆盖、基本路径测试等。
16.下列选项中属于面向对象设计方法主要特征的是( )。(A)
A. 继承
B. 自顶向下
C. 模块化
D. 逐步求精
解析：面向对象设计方法的主要特征有封装性、继承性和多态性。而结构化程序设计方法的主要原则有自顶向下，逐步求精，模块化，限制使用goto
本文档预览：3600字符，共6606字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
