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