【计算机类职业资格】国家二级C语言（公共基础知识）机试模拟试卷9及答案解析.doc

1、国家二级 C 语言（公共基础知识）机试模拟试卷 9 及答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.下列叙述中正确的是( )。（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间2.下列叙述中正确的是( )。（分数：2.00）A.算法的复杂度包括时间复杂度与空间复杂度B.算法的复杂度是指算法控制结构的复杂程度C.算法的复杂度是指算法程序中指令的数量D.算法的复杂度是指算法所处理的数据量3.下列叙述中正确的是( )。（分数：2.00）A.算法的时间复杂度与

2、计算机的运行速度有关B.算法的时间复杂度与运行算法时特定的输入有关C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关4.下列叙述中正确的是( )。（分数：2.00）A.非线性结构可以为空B.只有一个根结点和一个叶子结点的必定是线性结构C.只有一个根结点的必定是线性结构或二叉树D.没有根结点的一定是非线性结构5.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，fR=(f，8)，(d，b)，(e，d)，(e，e)，(a，c)该数据结构为( )。（分数：2.00）A.线性结构B.循环队列C.循环链表D.非线性结构6.下列叙述中正确的是( )。（分

3、数：2.00）A.矩阵是非线性结构B.数组是长度固定的线性表C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同7.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数( )。（分数：2.00）A.不同，但元素的存储顺序与逻辑顺序一致B.不同，且其元素的存储顺序可以与逻辑顺序不一致C.相同，元素的存储顺序与逻辑顺序一致D.相同，但其元素的存储顺序可以与逻辑顺序不一致8.下列叙述中正确的是( )。（分数：2.00）A.能采用顺序存储的必定是线性结构B.所有的线性结构都可以采用顺序存储结构C.具有两个以上指针的链表必定是非线性结构D.循环队列是队列的链式存储结构9.下列叙

4、述中正确的是( )。（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度10.设栈的顺序存储空间为 S(1：m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为( )。（分数：2.00）A.0B.mC.不可能D.m+111.设栈的存储空间为 S(1：m)，初始状态为 top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈中退出一个元素后，栈顶指针 top 值为

5、( )。（分数：2.00）A.0B.m-1C.m+1D.产生栈空错误12.下列处理中与队列有关的是( )。（分数：2.00）A.二叉树的遍历B.操作系统中的作业调度C.执行程序中的过程调用D.执行程序中的循环控制13.设有栈 S 和队列 Q，初始状态均为空。首先依次将 A，B，C，D，E，F 入栈，然后从栈中退出三个元素依次入队，再将 X，Y，Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为( )。（分数：2.00）A.DEFXYZABCB.FEDZYXCBAC.FEDXYZCBAD.DEFZYXABC14.设循环队列的存储空间为 Q(1：50)，初始状态

6、为 front=Fear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为( )。（分数：2.00）A.3B.1C.2D.5215.设循环队列的存储空间为 Q(1：m)，初始状态为空。现经过一系列正常的人队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为( )。（分数：2.00）A.m-1B.m-2C.0D.116.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有( )。（分数：2.00）A.节省存储空间B.插入与删除运算效率高C.便于查找D.排序时减少元素的比较次

7、数17.在线性表的链式存储结构中，其存储空间一般是不连续的，并且( )。（分数：2.00）A.前件结点的存储序号小于后件结点的存储序号B.前件结点的存储序号大于后件结点的存储序号C.前件结点的存储序号可以小于也可以大于后件结点的存储序号D.以上三种说法均不正确18.下列叙述中正确的是( )。（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.循环链表是循环队列的链式存储结构D.循环链表是非线性结构19.下列叙述中正确的是( )。（分数：2.00）A.带链栈的栈底指针是随栈的操作而动态变化的B.若带链队列的队头指针与队

8、尾指针相同，则队列为空C.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D.不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的20.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为( )。（分数：2.00）A.0B.1C.20D.不确定21.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的人队与退队操作后。front=rear=10。该队列中的元素个数为( )。（分数：2.00）A.0B.1C.1 或 0D.不确定22.某带链的队列初始状态为 front=rea

9、r=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为( )。（分数：2.00）A.4B.5C.6D.不确定23.下列叙述中错误的是( )。（分数：2.00）A.循环链表中有一个表头结点B.循环链表是循环队列的存储结构C.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点D.循环链表实现了空表与非空表运算的统一24.某棵树中共有 25 个结点，且只有度为 3 的结点和叶子结点，其中叶子结点有 7 个，则该树中度为 3 的结点数为( )。（分数：2.00）A.6B.7C.8D.不存在这样的树25.度为 3 的一棵树共有 30 个结点，其中

10、度为 3，1 的结点个数分别为 3，4。则该树中的叶子结点数为( )。（分数：2.00）A.14B.15C.16D.不可能有这样的树26.深度为 7 的二叉树共有 127 个结点，则下列说法中错误的是( )。（分数：2.00）A.该二叉树是满二叉树B.该二叉树有一个度为 1 的结点C.该二叉树是完全二叉树D.该二叉树有 64 个叶子结点27.深度为 5 的完全二叉树的结点数不可能是( )。（分数：2.00）A.15B.16C.17D.1828.某完全二叉树共有 256 个结点，则该完全二叉树的深度为( )。（分数：2.00）A.7B.8C.9D.1029.在具有 2n 个结点的完全二叉树中，叶

11、子结点个数为( )。（分数：2.00）A.nB.n+1C.n-1D.n230.下列叙述中正确的是( )。（分数：2.00）A.非完全二叉树可以采用顺序存储结构B.有两个指针域的链表就是二叉链表C.有的二叉树也能用顺序存储结构表示D.顺序存储结构一定是线性结构国家二级 C 语言（公共基础知识）机试模拟试卷 9 答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.下列叙述中正确的是( )。（分数：2.00）A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法 C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间解析：解析：算法是指对

12、解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。算法设计需要考虑可行陛、确定性、有穷性与足够的情报，不能只考虑计算结果。算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的，。算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。2.下列叙述中正确的是( )。（分数：2.00）A.算法的复杂度包括时间复杂度与空间复杂度 B.算法的复杂度是指算法控制结构的复杂程度C.算法的复杂度是指算法程序中指令的数量D.算法的复杂度是指算法所处理的数据量解析：解析：算法复杂度是指算法在编写成可执

13、行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。3.下列叙述中正确的是( )。（分数：2.00）A.算法的时间复杂度与计算机的运行速度有关B.算法的时间复杂度与运行算法时特定的输入有关 C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关解析：解析：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多

14、细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。4.下列叙述中正确的是( )。（分数：2.00）A.非线性结构可以为空 B.只有一个根结点和一个叶子结点的必定是线性结构C.只有一个根结点的必定是线性结构或二叉树D.没有根结点的一定是非线性结构解析：解析：如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都

15、可以是空的数据结构。树只有一个根结点，但不论有几个叶子结点，树都是非线性结构。5.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，fR=(f，8)，(d，b)，(e，d)，(e，e)，(a，c)该数据结构为( )。（分数：2.00）A.线性结构 B.循环队列C.循环链表D.非线性结构解析：解析：数据的逻辑结构有两个要素：一是数据元素的集合，通常记为 D；二是 D 上的关系，它反映了 D 中各数据元素之间的前后件关系，通常记为 R。即一个数据结构可以表示成 B=(D，R)。其中 B 表示数据结构。为了反映 D 中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设 a 与 b 是

16、 D 中的两个数据，则二元组(a，b)表示 a 是 b 的前件，b 是 a 的后件。本题中 R 中的根结点为 f，元素顺序为facedb，满足线性结构的条件。6.下列叙述中正确的是( )。（分数：2.00）A.矩阵是非线性结构B.数组是长度固定的线性表 C.对线性表只能作插入与删除运算D.线性表中各元素的数据类型可以不同解析：解析：矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。7.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数( )。（分数：2.00）A.不同，但元素的存

17、储顺序与逻辑顺序一致B.不同，且其元素的存储顺序可以与逻辑顺序不一致C.相同，元素的存储顺序与逻辑顺序一致 D.相同，但其元素的存储顺序可以与逻辑顺序不一致解析：解析：在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，在存储空间中是按逻辑顺序依次存放的。8.下列叙述中正确的是( )。（分数：2.00）A.能采用顺序存储的必定是线性结构B.所有的线性结构都可以采用顺序存储结构 C.具有两个以上指针的链表必定是非线性结构D.循环队列是队列的链式存储结构解析：解析：所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存(按层次依次存放到数

18、据元素中)，但完全二叉树不属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。9.下列叙述中正确的是( )。（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度解析：解析：在栈中，通常用指针 top 来指示栈顶的位置，用指针 bottom 指向栈底。栈顶指针 top 动态反应了栈中元素的变化情况。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。链式存储结构中，各数据结

19、点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，故头指针和尾指针或栈顶指针无法决定链表长度。10.设栈的顺序存储空间为 S(1：m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为( )。（分数：2.00）A.0B.mC.不可能 D.m+1解析：解析：栈为空时，栈顶指针 top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为top=0，当栈满 top=m，无法继续入栈，top 值不可能为 m+1。11.设栈的存储空间为 S(1：m)，初始状态为 top=m+1。经过一系列入栈与退栈操作后，top=m。现又在栈

20、中退出一个元素后，栈顶指针 top 值为( )。（分数：2.00）A.0B.m-1C.m+1 D.产生栈空错误解析：解析：栈的顺序存储空间为 s(1：m)，初始状态 top=m+1，所以这个栈是 m 在栈底(也可理解为开口向下的栈)。经过一系列入栈与退栈操作后 top=m，则栈中有 1 个元素，若现在又退出一个元素，那么栈顶指针下移一位，回到 m+1 的位置。12.下列处理中与队列有关的是( )。（分数：2.00）A.二叉树的遍历B.操作系统中的作业调度 C.执行程序中的过程调用D.执行程序中的循环控制解析：解析：队列是指允许在一端进行插入，而在另一端进行删除的线性表。由于最先进入队列的元素将

21、最先出队，所以队列具有“先进先出”的特性，体现了“先来先服务”的原则。操作系统中的作业调度是指根据一定信息，按照一定的算法，从外存的后备队列中选取某些作业调入内存分配资源并将新创建的进程插入就绪队列的过程。13.设有栈 S 和队列 Q，初始状态均为空。首先依次将 A，B，C，D，E，F 入栈，然后从栈中退出三个元素依次入队，再将 X，Y，Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为( )。（分数：2.00）A.DEFXYZABCB.FEDZYXCBA C.FEDXYZCBAD.DEFZYXABC解析：解析：栈是一种特殊的线性表，它所有的插入与删除都限定

22、在表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将 A，B，C，D，E，F 入栈后，栈中元素为 ABCDEF，退出三个元素入队，队列元素为 FED，将 X，Y，Z 入栈后栈中元素为 ABCXYZ，退栈全部入队后，队列元素为FEDZYXCBA。14.设循环队列的存储空间为 Q(1：50)，初始状态为 front=Fear=50。现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为( )。（分数：2.00）A.3B.1C.2 D.52解析：解析：由初始状态为 front=rear=50 可知此时循环队列为空。经过一系

23、列正常的入队和退队操作，由 front=rear=1 可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为 2。15.设循环队列的存储空间为 Q(1：m)，初始状态为空。现经过一系列正常的人队与退队操作后，front=m，rear=m-1，此后从该循环队列中删除一个元素，则队列中的元素个数为( )。（分数：2.00）A.m-1B.m-2 C.0D.1解析：解析：在循环队列中，如果 rear-front0，则队列中的元素个数为 rear-front 个；如果 rear-front0，则队列中的元素个数为 rear-front+m。该题中 m-1m，即

24、rear-front0，则该循环队列中的元素个数为(m-1)-m+m-1。此后从该循环队列中删除一个元素，则队列中的元素个数为 m-1-1=m-2。16.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有( )。（分数：2.00）A.节省存储空间B.插入与删除运算效率高 C.便于查找D.排序时减少元素的比较次数解析：解析：线性表的顺序存储结构称为顺序表，线性表的链式存储结构称为链表，两者的优缺点如下表所示。17.在线性表的链式存储结构中，其存储空间一般是不连续的，并且( )。（分数：2.00）A.前件结点的存储序号小于后件结点的存储序号B.前件结点的存储序号大于后件结点的存储序号C.

25、前件结点的存储序号可以小于也可以大于后件结点的存储序号 D.以上三种说法均不正确解析：解析：在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致，因此前件结点的存储序号与后件结点的存储序号之间不存在大小关系。18.下列叙述中正确的是( )。（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C.循环链表是循环队列的链式存储结构D.循环链表是非线性结构解析：解析：结点中具有两个指针域的链表既可以是双向链表也可以是二叉链表，双向链表是线性结构，二叉链表属于非线性结构。

26、循环链表是线性链表的一种形式，属于线性结构，采用链式存储结构，而循环队列是队列的一种顺序存储结构。19.下列叙述中正确的是( )。（分数：2.00）A.带链栈的栈底指针是随栈的操作而动态变化的 B.若带链队列的队头指针与队尾指针相同，则队列为空C.若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素D.不管是顺序栈还是带链的栈，在操作过程中其栈底指针均是固定不变的解析：解析：由于带链栈利用的是计算机存储空间中的所有空闲存储结点，因此随栈的操作栈顶栈底指针动态变化。带链的队列中若只有一个元素，则头指针与尾指针相同。20.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的

27、入栈与退栈操作后，top=bottom=20。该栈中的元素个数为( )。（分数：2.00）A.0B.1 C.20D.不确定解析：解析：带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针和尾指针都为 NULL；栈中只有一个元素时，头指针和尾指针都指向这个元素。21.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的人队与退队操作后。front=rear=10。该队列中的元素个数为( )。（分数：2.00）A.0B.1 C.1 或 0D.不确定解析：解析：带链队列空时，头指针和尾指针都为 NULL；队列中只有一个元素时，头指针和尾指针都

28、指向这个元素。22.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=10，rear=5。该队列中的元素个数为( )。（分数：2.00）A.4B.5C.6D.不确定 解析：解析：带链的队列使用了链表来表示队列，而链表中的元素存储在不连续的地址中，因此当front=10，rear=5 时，不能确定队列中元素的个数。23.下列叙述中错误的是( )。（分数：2.00）A.循环链表中有一个表头结点B.循环链表是循环队列的存储结构 C.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点D.循环链表实现了空表与非空表运算的统一解析：解析：循环

29、链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由 NULL 改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队列的一种顺序存储结构。24.某棵树中共有 25 个结点，且只有度为 3 的结点和叶子结点，其中叶子结点有 7 个，则该树中度为 3 的结点数为( )。（分数：2.00）A.6B.7C.8D.不存在这样的树 解析：解析：根据题意，树中只有度为 3 的结点和叶子结点(7 个)，则度为 3 的结点有 25-7=18 个；又根据树中的结点数=树中所有结点的度之和+1，设度为 3 的结点数为 n，则 3n+1=25，得 n=8。两种

30、方式得到的度为 3 的结点数不同，故不存在这样的树。25.度为 3 的一棵树共有 30 个结点，其中度为 3，1 的结点个数分别为 3，4。则该树中的叶子结点数为( )。（分数：2.00）A.14B.15 C.16D.不可能有这样的树解析：解析：设叶子结点数为 n，则度为 2 的结点数为 30-3-4-n=23-n，根据树中的结点数=树中所有结点的度之和+1，得 33+2(23-n)+14+0n+1=30，则 n=15。26.深度为 7 的二叉树共有 127 个结点，则下列说法中错误的是( )。（分数：2.00）A.该二叉树是满二叉树B.该二叉树有一个度为 1 的结点 C.该二叉树是完全二叉树

31、D.该二叉树有 64 个叶子结点解析：解析：满二叉树满足深度为 m 的二叉树最多有 2 m -1 个结点，本题中二叉树深度为 7 且有 127 个结点，满足 2 7 -1=127，达到最大值，故此二叉树为满二叉树，也是完全二叉树。满二叉树第 k 层上有 2 k-1 结点，则该二叉树的叶子结点数为 2 7-1 =64 个。满二叉树不存在度为 1 的结点。27.深度为 5 的完全二叉树的结点数不可能是( )。（分数：2.00）A.15 B.16C.17D.18解析：解析：设完全二叉树的结点数为 n，根据深度为 k 的二叉树至多有 2 k -1 个结点，再根据完全二叉树的定义可知，2 k-1 -1n

32、2 k -1。本题中完全二叉树的深度为 5，则 2 5 -1n2 5 -1，15n31。因此，结点数不能为 15。28.某完全二叉树共有 256 个结点，则该完全二叉树的深度为( )。（分数：2.00）A.7B.8C.9 D.10解析：解析：根据完全二叉树的性质：具有 n 个结点的完全二叉树的深度为log 2 n+1。本题中完全二叉树共有 256 个结点，则深度为log 2 256+1=8+1=9。29.在具有 2n 个结点的完全二叉树中，叶子结点个数为( )。（分数：2.00）A.n B.n+1C.n-1D.n2解析：解析：由二叉树的定义可知，树中必定存在度为 0 的结点和度为 2 的结点，

33、设度为 0 结点有 a 个，根据度为 0 的结点(即叶子结点)总比度为 2 的结点多一个，得度为 2 的结点有 a-1 个。再根据完全二叉树的定义，度为 1 的结点有 0 个或 1 个，假设度 1 结点为 0 个，a+0+a-1=2n，得 2a=2n-1，由于结点个数必须为整数，假设不成立；当度为 1 的结点为 1 个时，a+1+a-1=2n，得 a=n，即叶子结点个数为 n。30.下列叙述中正确的是( )。（分数：2.00）A.非完全二叉树可以采用顺序存储结构B.有两个指针域的链表就是二叉链表C.有的二叉树也能用顺序存储结构表示 D.顺序存储结构一定是线性结构解析：解析：在计算机中，二叉树为非线性结构，通常采用链式存储结构，但对于满二叉树和完全二叉树来说，可以按层进行顺序存储。因此 A 项错误，C 项正确。虽然满二叉树和完全二叉树可以采用顺序存储结构，但仍是一种非线性结构，因此 D 项错误。双向链表也有两个指针域，因此 B 项错误。