1、国家二级 C 语言（公共基础知识）机试模拟试卷 7 及答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.下列叙述中正确的是( )。（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上 3 种说法都不对2.算法的有穷性是指( )。（分数：2.00）A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用3.算法的空间复杂度是指( )。（分数：2.00）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程
2、序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数4.定义无符号整数类为 UInt，下面可以作为类 UInt 实例化值的是( )。（分数：2.00）A.一 369B.369C.0369D.整数集合1，2，3，4，55.下列叙述中正确的是( )。（分数：2.00）A.程序执行的效率与数据的存储结构密切相关B.程序执行的效率只取决于程序的控制结构C.程序执行的效率只取决于所处理的数据量D.以上说法均错误6.下列叙述中正确的是( )。（分数：2.00）A.有一个以上根节点的数据结构不一定是非线性结构B.只有一个根节点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结
3、构7.下列叙述中正确的是( )。（分数：2.00）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间8.下列选项中，( )不是一般算法应该有的特征。（分数：2.00）A.无穷性B.可行性C.确定性D.有穷性9.下列叙述中正确的是( )。（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构10.一个栈的初始状态为
4、空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是( )。（分数：2.00）A.12345ABCDEB.EDCBA54321C.ABCDEl2345D.54321EDCBA11.下列关于栈的叙述中确的是( )。（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据12.下列叙述中正确的是( )。（分数：2.00）A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D.
5、以上说法都不正确13.下列关于栈的叙述中正确的是( )。（分数：2.00）A.栈顶元素最先被删除B.栈顶元素最后才能被删除C.栈底元素永远不能被删除D.栈底元素最先被删除14.下列关于栈的叙述中正确的是( )。（分数：2.00）A.栈底元素定足最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则D.以上说法均错误15.下列与队列结构有关联的是( )。（分数：2.00）A.函数的递归调用B.数组元素的引用C.多重循环的执行D.先到先服务的作业调度16.下列数据结构中，属于非线性结构的是( )。（分数：2.00）A.循环队列B.带链队列C.二叉树D.带链栈17.下列关于循环队
6、列的叙述中正确的是( )。（分数：2.00）A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针既可以大于队尾指针，也可以小于队尾指针18.下列叙述中正确的是( )。（分数：2.00）A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构19.设循环队列的存储空间为 Q(1：35)，初始状态为 front=rear=35。现经过一系列入队与出队运算后，front=15，rear=15，则循环队列中的元素个数为( )。（分数：2.00）A.15B.16C.20D.0 或 3520.下列关于
7、线性链表的叙述中正确的是( )。（分数：2.00）A.各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素D.以上说法均不正确21.下列链表中，其逻辑结构属于非线性结构的是( )。（分数：2.00）A.二叉链表B.循环链表C.双向链表D.带链的栈22.支持子程序调用的数据结构是( )。（分数：2.00）A.栈B.树C.队列D.二叉树23.某二叉树有 5 个度为 2 的节点，则该二叉树中的叶子节点数是( )。（分数：2.00）A.10B.8C.6D.424.下列关于二叉树
8、的叙述中正确的是( )。（分数：2.00）A.叶子节点总是比度为 2 的节点少 1 个B.叶子节点总是比度为 2 的节点多 1 个C.叶子节点数是度为 2 的节点数的两倍D.度为 2 的节点数是度为 l 的节点数的两倍25.对下列二叉树： （分数：2.00）A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZD.ABCDEFXYZ26.在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。（分数：2.00）A.O(n)B.O(n 2 )C.O(log 2 n)D.O(nlog2n)27.对长度为 n 的线性表排序，在最坏情况下，比较次数不是 n(n1)2 的
9、排序方法是( )。（分数：2.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序28.下列选项中不属于结构化程序设计原则的是( )。（分数：2.00）A.可封装B.自顶向下C.模块化D.逐步求精29.面向对象方法中，实现对象的数据和操作结合于统一体中的是( )。（分数：2.00）A.结合B.封装C.隐藏D.抽象30.结构化程序所要求的基本结构不包括( )。（分数：2.00）A.顺序结构B.GOTO 跳转C.选择(分支)结构D.重复(循环)结构国家二级 C 语言（公共基础知识）机试模拟试卷 7 答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1
10、.下列叙述中正确的是( )。（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上 3 种说法都不对 解析：解析：算法是指解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以 A 选项错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。2.算法的有穷性是指( )。（分数：2.00）A.算法程序的运行时间是有限的 B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用解析：解析：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性是指算法程序的运
11、行时间是有限的。3.算法的空间复杂度是指( )。（分数：2.00）A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数解析：解析：算法的空间复杂度是指算法在执行过程中所需要的内存空间，所以选择 A 选项。4.定义无符号整数类为 UInt，下面可以作为类 UInt 实例化值的是( )。（分数：2.00）A.一 369B.369 C.0369D.整数集合1，2，3，4，5解析：解析：只有 B 选项 369 可以用无符号整数来表示和存储。A 选项一 369 有负号，C 选项 0369 是小数，都不能用无符号整数类存
12、储。D 选项是一个整数集合，得用数组来存储。5.下列叙述中正确的是( )。（分数：2.00）A.程序执行的效率与数据的存储结构密切相关 B.程序执行的效率只取决于程序的控制结构C.程序执行的效率只取决于所处理的数据量D.以上说法均错误解析：解析：程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关。6.下列叙述中正确的是( )。（分数：2.00）A.有一个以上根节点的数据结构不一定是非线性结构B.只有一个根节点的数据结构不一定是线性结构 C.循环链表是非线性结构D.双向链表是非线性结构解析：解析：线性结构应满足：有且只有一个根节点；每个节点最多有一个前件，也最多
13、有一个后件，所以 B 选项正确。有一个以上根节点的数据结构一定是非线性结构，所以 A 选项错误。循环链表和双向链表都是线性结构的数据结构。7.下列叙述中正确的是( )。（分数：2.00）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间解析：解析：链式存储结构既可以针对线性结构，也可以针对非线性结构，所以 B 选项与 C 选项错误。链式存储结构中的每个节点都由数据域与指针域两部分组成，增加了存储空间，所以 D 选项
14、错误。8.下列选项中，( )不是一般算法应该有的特征。（分数：2.00）A.无穷性 B.可行性C.确定性D.有穷性解析：解析：作为一个算法，一般应具有以下几个基本特征：可行性、确定性、有穷性、拥有足够的情报。本题答案为 A 选项。9.下列叙述中正确的是( )。（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 解析：解析：栈是先进后出的线性表，所以 A 选项错误；队列是先进先出的线性表，所以 B 选项错误；循环队列是线性结构的线性表，所以 C 选项错误。10.一个栈的初始状态为空。现将
15、元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是( )。（分数：2.00）A.12345ABCDEB.EDCBA54321 C.ABCDEl2345D.54321EDCBA解析：解析：栈按先进后出的原则组织数据，入栈最早的最后出栈，所以选择 B 选项。11.下列关于栈的叙述中确的是( )。（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据 C.只能在栈底插入数据D.不能删除数据解析：解析：栈是按先进后出的原则组织数据的，数据的插入和删除都在栈顶进行操作。12.下列叙述中正确的是( )。（分数：2.00）A.在栈中，栈中元素随栈底
16、指针与栈顶指针的变化而动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D.以上说法都不正确解析：解析：栈是先进后出的数据结构，在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来操作，所以选择 C 选项。13.下列关于栈的叙述中正确的是( )。（分数：2.00）A.栈顶元素最先被删除 B.栈顶元素最后才能被删除C.栈底元素永远不能被删除D.栈底元素最先被删除解析：解析：栈是先进后出的数据结构，所以栈顶元素最后人栈却最先被删除，栈底元素最先入栈却最后被删除，所以选择 A 选项。14.下列关于栈的叙述中正确
17、的是( )。（分数：2.00）A.栈底元素定足最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则 D.以上说法均错误解析：解析：栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。栈的修改是按后进先出的原则进行的，因此，栈称为先进后出表，或后进先出表，所以选择 C 选项。15.下列与队列结构有关联的是( )。（分数：2.00）A.函数的递归调用B.数组元素的引用C.多重循环的执行D.先到先服务的作业调度 解析：解析：队列的修改是依先进先出的原则进行的，故 D 选项正确。16.下列数据结构中，属于非线性结构的
18、是( )。（分数：2.00）A.循环队列B.带链队列C.二叉树 D.带链栈解析：解析：树是简单的非线性结构，所以二叉树作为树的一种，也是一种非线性结构。17.下列关于循环队列的叙述中正确的是( )。（分数：2.00）A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针既可以大于队尾指针，也可以小于队尾指针 解析：解析：循环队列的队头指针与队尾指针都不是固定的，随着入队与出队操作要进行变化。因为是循环利用的队列结构，所以队头指针有时可能大于队尾指针，有时也可能小于队尾指针。18.下列叙述中正确的是( )。（分数：2.00）A.循环队列是队列的一种链式存储结
19、构B.循环队列是队列的一种顺序存储结构 C.循环队列是非线性结构D.循环队列是一种逻辑结构解析：解析：在实际应用中，队列的顺序存储结构一般采用循环队列的形式。19.设循环队列的存储空间为 Q(1：35)，初始状态为 front=rear=35。现经过一系列入队与出队运算后，front=15，rear=15，则循环队列中的元素个数为( )。（分数：2.00）A.15B.16C.20D.0 或 35 解析：解析：在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置。在循环队列中进行出队、人队操作时，头、尾指针仍要加 1，朝前移动，只不过当头、尾
20、指针指向向量上界时，其加 l 操作的结果是指向向量的下界 0。由于入队时队尾指针向前追赶队头指针，出队时队头指针向前追赶队尾指针，故队空和队满时，头尾指针均相等，故答案为 D 选项。20.下列关于线性链表的叙述中正确的是( )。（分数：2.00）A.各数据节点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据节点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素 D.以上说法均不正确解析：解析：一般来说，在线性表的链式存储结构中，各数据节点的存储序号是不连续的，并且各节点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插
21、入和删除都不需要移动表中的元素，只需改变节点的指针域即可。21.下列链表中，其逻辑结构属于非线性结构的是( )。（分数：2.00）A.二叉链表 B.循环链表C.双向链表D.带链的栈解析：解析：在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。带链的栈可以用来收集计算机存储空间中所有空闲的存储节点，是线性表。在单链表中的节点中增加一个指针域指向它的直接前件，这样的链表就称为双向链表(一个节点中含有两个指针)，也是线性链表。循环链表具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活，属于线性链表。二叉链表是二叉
22、树的物理实现，是一种存储结构，不属于线性结构。答案为 A 选项。22.支持子程序调用的数据结构是( )。（分数：2.00）A.栈 B.树C.队列D.二叉树解析：解析：栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返同到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为 A 选项。23.某二叉树有 5 个度为 2 的节点，则该二叉树中的叶子节点数是( )。（分数：2.00）A.10B.8C.6 D.4解析：解析：根据二叉树的性质 3：在任意一棵二叉树中，度为 0 的
23、叶子节点总是比度为 2 的节点多一个，所以本题中是 5+1=6(个)。24.下列关于二叉树的叙述中正确的是( )。（分数：2.00）A.叶子节点总是比度为 2 的节点少 1 个B.叶子节点总是比度为 2 的节点多 1 个 C.叶子节点数是度为 2 的节点数的两倍D.度为 2 的节点数是度为 l 的节点数的两倍解析：解析：根据二义树的性质 3：在任意一一棵二又树中，度为 0 的叶子节点总是比度为 2 的节点多一个，所以选择 B 选项。25.对下列二叉树： （分数：2.00）A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZ D.ABCDEFXYZ解析：解析：前序遍历是指在访问根节
24、点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树。并且，在遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作。否则，访问根节点；前序遍历左子树；前序遍历右子树，故 C 选项正确。26.在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。（分数：2.00）A.O(n)B.O(n 2 )C.O(log 2 n) D.O(nlog2n)解析：解析：当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为 n 的有序线性表。在最坏情况下，二分法查找只需要比较 log 2 n 次，
25、而顺序查找需要比较 n 次。27.对长度为 n 的线性表排序，在最坏情况下，比较次数不是 n(n1)2 的排序方法是( )。（分数：2.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序 解析：解析：除了堆排序算法的比较次数是 O(nlog 2 n)外，其他的都是 n(n1)2。28.下列选项中不属于结构化程序设计原则的是( )。（分数：2.00）A.可封装 B.自顶向下C.模块化D.逐步求精解析：解析：结构化程序设计的原则包括：自顶向下、逐步求精、模块化、限制使用 GOTO 语句，所以选择 A 选项。29.面向对象方法中，实现对象的数据和操作结合于统一体中的是( )。（分数：2.00）A.结合B.封装 C.隐藏D.抽象解析：解析：对象的基本特点是：标识唯一性、分类性、多态性、封装性、模块独立性好。封装是指隐藏对象的属性和实现细节，将数据和操作结合于统一体中，仅对外提供访问方式。B 选项正确。30.结构化程序所要求的基本结构不包括( )。（分数：2.00）A.顺序结构B.GOTO 跳转 C.选择(分支)结构D.重复(循环)结构解析：解析：1966 年 Boehm 和 Jacopini 证明了程序设计语言仅仅使用顺序、选择和重复 3 种基本控制结构就足以表达出各种其他形式结构的程序设计方法。
