国家二级C语言（数据结构与运算）机试模拟试卷4 (题后含答案及解析)
题型有：1. 选择题
选择题
1． 下列各序列中不是堆的是
A．(91,85,53,36,47,30,24,12)
B．(91,85,53,47,36,30,24,12)
C．(47,91,53,85,30,12,24,36)
D．(91,85,53,47,30,12,24,36)
正确答案：C
解析：堆可以看成一棵完全二叉树：任一根节点＞=左右孩子（或者＜=），（大的叫大根堆，小的叫小根堆）。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。
此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的根，而选项C是“左根右”的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，所以选项C不是堆。 知识模块：数据结构与运算
2． 深度为5的完全二叉树的结点数不可能是
A．15
B．16
C．17
D．18
正确答案：A
解析：对于满二叉树，叶子结点的数目等于2n-1，n为深度，这里就是2的5-1=4次方，就是16。所以选项A为正确答案。 知识模块：数据结构与运算
3． 有二叉树如下图所示： 则前序序列为
A．ABDEGCFH
B．DBGEAFHC
C．DGEBHFCA
D．ABCDEFGH
正确答案：A
解析：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项A正确，选项B为中序遍历，选项C为后序遍历，选项D不正确。 知识模块：数据结构与运算
4． 下列叙述中正确的是
A．循环队列是顺序存储结构
B．循环队列是链式存储结构
c语言的冒泡排序算法
C．循环队列是非线性结构
D．循环队列的插入运算不会发生溢出现象
正确答案：A
解析：循环队列属于队列的特例和栈同属于线性结构，所以选项C不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项A正确，选项B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项D不正确。 知识模块：数据结构与运算
5． 下列叙述中正确的是
A．所有数据结构必须有根结点
B．所有数据结构必须有终端结点（即叶子结点）
C．只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构
D．没有根结点或没有叶子结点的数据结构一定是非线性结构
正确答案：D
解析：只有一个空节点的结构也属数据结构，所以选项A和选项B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项C不正确，选项D正确。 知识模块：数据结构与运算
6． 下列关于算法的描述中错误的是
A．算法强调动态的执行过程，不同于静态的计算公式
B．算法必须能在有限个步骤之后终止
C．算法设计必须考虑算法的复杂度
D．算法的优劣取决于运行算法程序的环境
正确答案：D
解析：算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项D错误。 知识模块：数据结构与运算
7． 设有二叉树如下图所示：则中序序列为
A．ABDEGCFH
B．DBGEAFHC
C．DGEBHFCA
D．ABCDEFGH
正确答案：B      涉及知识点：数据结构与运算
8． 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有
A．节省存储空间
B．插入与删除运算效率高
C．便于查
D．排序时减少元素的比较次数
正确答案：B
解析：顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大（＝1），存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小（＜1），存储空间利用率低，故选项B正确。 知识模块：数据结构与运算
9． 深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为
A．62
B．63
C．64
D．65
正确答案：B
解析：对于满二叉树，结点的数目等于2n-1，叶子结点数目为2n-1，n为深度，这里就是2的7次方-1，就是127个结点，叶子结点是64个。然而题目中只有125个结点，说明少了两个结点，那么就少了一个叶子结点，即63个。 知识模块：数据结构与运算
10． 下列叙述中正确的是
A．所谓有序表是指在顺序存储空间内连续存放的元素序列
B．有序表只能顺序存储在连续的存储空间内
C．有序表可以用链接存储方式存储在不连续的存储空间内
D．任何存储方式的有序表均能采用二分法进行查
正确答案：C
解析：有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查只适用于顺序存储的有序表。故选项C正确。 知识模块：数据结构与运算
11． 设有二叉树如下图所示： 则后序序列为
A．ABDEGCFH
B．DBGEAFHC
C．DGEBHFCA
D．ABCDEFGH
正确答案：C
解析：后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项C正确。 知识模块：数据结构与运算
12． 下列叙述中正确的是
A．结点中具有两个指针域的链表一定是二叉链表
B．结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C．二叉树只能采用链式存储结构
D．循环链表是非线性结构
正确答案：B
解析：结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项A不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。
它可采用顺序存储结构和链式存储结构，故选项C不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点的线性结构，故选项D不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项B正确。 知识模块：数据结构与运算
13． 设某二叉树中共有140个结点，其中有40个度为1的结点。则
A．该二叉树中有51个叶子结点
B．该二叉树中有50个叶子结点
C．该二叉树中有51个度为2的结点
D．不可能有这样的二叉树
正确答案：D
解析：140个结点除去40个度为1的结点，说明有100个度为2的结点，而根据二叉树性质，这个数值无法得出一棵二叉树，故本题答案选D。 知识模块：数据结构与运算
14． 带链的栈与顺序存储的栈相比，其优点是
A．入栈与退栈操作方便
B．可以省略栈底指针
C．入栈操作时不会受栈存储空间的限制而发生溢出
D．所占存储空间相同
正确答案：C
解析：带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故选项C正确。 知识模块：数据结构与运算
15． 某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为
A．BADC
B．DCBA
C．CDAB
D．ABCD
正确答案：B
解析：在二叉树前序遍历中ABCD中A是根节点，而在后序遍历中根结点位于最后，所以选项B正确。 知识模块：数据结构与运算
16． 下列叙述中正确的是
A．算法的时间复杂度与运行算法时特定的输入有关
B．算法的时间复杂度与计算机的运行速度有关
C．算法的时间复杂度与算法程序中的语句条数成正比
D．算法的时间复杂度与算法程序编制者的水平有关
正确答案：B
解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项A正确。 知识模块：数据结构与运算
17． 下列各排序法中，最坏情况下的时间复杂度最低的是
A．堆排序
B．快速排序
C．希尔排序
D．冒泡排序
正确答案：A
解析：堆排序法，最坏情况需要O(nlog2n)次比较。相比以上几种“除希尔排序法外”，堆排序法的时间复杂度最小，故选项A正确。 知识模块：数据结构与运算
18． 设栈的存储空间为S(1:50)，初始状态为top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。