国家二级(C语言)机试模拟试卷54(题后含答案及解析).pdfVIP

国家二级（C语言）机试模拟试卷54(题后含答案及解析)

题型有：1.选择题2.程序填空题3.程序修改题4.程序设计题

选择题

1．下列叙述中错误的是

A．数据结构中的数据元素不能是另一数据结构

B．数据结构中的数据元素可以是另一数据结构

C．空数据结构可以是线性结构也可以是非线性结构

D．非空数据结构可以没有根结点

正确答案：A

解析：数据元素是一个含义很广泛的概念，它是数据的”基本单位”，在计算

机中通常作为一个整体进行考虑和处理。数据元素可以是一个数据也可以是被抽

象出的具有一定结构数据集合，所以数据结构中的数据元素可以是另一数据结

构。满足有且只有一个根结点并且每一个结点最多有一个前件，也最多有一个后

件的非空的数据结构认为是线性结构，不满足条件的结构为非线性结构。空数据

结构可以是线性结构也可以是非线性结构。非空数据结构可以没有根结点，如非

性线结构”图”就没有根结点。故选A选项.

2．为了降低算法的空间复杂度，要求算法尽量采用原地工作(inplace)。所

谓原地工作是指

A．执行算法时所使用的额外空间固定（即不随算法所处理的数据空间大小

的变化而变化）

B．执行算法时所使用的额外空间随算法所处理的数据空间大小的变化而变

化

C．执行算法时不使用额外空间

D．执行算法时不使用任何存储空间

正确答案：A

解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括输入数

据所占的存储空间、程序本身所占的存储空间、算法执行过程中所需要的额外空

间。如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，

即额外空间量不随问题规模的变化而变化，则称该算法是原地工作的。故选A

选项.

3．某循环队列的存储空间为Q(1:m)，初始状态为front=rear=m。现经过一

系列的入队操作和退队操作后，front=m，rear=m-1，则该循环队列中的元素个数

为

A．m-1

B．m

C．1

D．0

正确答案：A

解析：循环队列长度为m，由初始状态为front=rear=m，可知此时循环队列

为空。入队运算时，首先队尾指针进1（即rear+1），然后在rear指针指向的位

置插入新元素。特别的，当队尾指针rear=m+1时，置rear=1。退队运算时，排

头指针进1（即front+1），然后删除front指针指向的位置上的元素，当排头指针

front=m+1时，置front=1。从排头指针front指向的后一个位置直到队尾指针rear

指向的位置之间所有的元素均为队列中的元素。如果rear-front＞0，则队列中的

元素个数为rear-front个；如果rear-front＜0，则队列中的元素个数为

rear-front+m。该题中m-1＜m，即rear-front＜0，则该循环队列中的元素个数为

（m-1）-m+m=m-1。故选A选项.

4．某棵树只有度为3的结点和叶子结点，其中度为3的结点有8个，则该

树中的叶子结点数为

A．15

B．16

C．17

D．不存在这样的树

正确答案：C

解析：树是一种简单的非线性结构，直观地来看，树是以分支关系定义的层

次结构。在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中

最大的度称为树的度。由于只有度为3的结点和叶子结点，可知最后一层都为叶

子结点，倒数第二层一部分结点度为3，一部分为叶子结点，其余的结点的度均

为3，计算度为3的结点总数(33-1-1)/2＜8＜(34-1-1)/2可知，树共有4层，前两

层有度为3的结点(33-1-1)/2=4个，第三层有33=9个结点，其中4个是度为3

的结点，5个是叶子结点，所以该树中的叶子结点数为4×3+5=17。故选C选项.

5．某二叉树共有530个结点，其中度为2的结点有250个，则度为1的结

点数为

A．29

B．30

C．249

D．251

正确答案：A

解析：在树结构中，一个结点所拥有的后件个数