国家二级MS Office高级应用机试（数据结构与算法）模拟试卷18
选择题
1.下列数据结构中属于非线性结构的是( )。(C)
A. 循环队列
B. 带链队列
C. 二叉树
D. 带链栈
解析：二叉树属于非线性结构，因为二叉树的节点最多有2个后继节点。
2.下列叙述中正确的是( )。(B)
A. 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B. 线性表的链式存储结构所需要的存储结构一般多于顺序存储结构
C. 线性表的链式存储结构所需要的存储空间一般少于顺序存储结构
D. 线性表的链式存储结构所需要的存储空间与顺序存储结构没有任何关系
解析：链式存储结构需要额外的指针域，比顺序存储结构存储密度低，浪费空间。
3.下面叙述中正确的是( )。(D)
A. 循环队列属于队列的链式存储结构
B. 双向链表是二叉树的链式存储结构
C. 非线性结构只能采用链式存储结构
D. 有的非线性结构也可以采用顺序存储结构
解析：顺序存储方式不仅能用于存储线性结构，还能用来存储非线性结构，如完全二叉树属于非线性结构，但是却适合使用顺序存储方式。二叉树的链式存储结构是二叉链表。
4.下列链表中，其逻辑结构属于非线性结构的是( )。(A)
A. 二叉链表
B. 循环链表
C. 双向链表
D. 带链的栈
解析：二叉链表作为二叉树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和第一个孩子的下一个兄弟节点，有2个后继节点，属于非线性结构。
5.下列关于线性表和链表的比较，叙述错误的是( )。(D)
A. 顺序表随机存取表中的任意节点，无须额外的指针域
B. 顺序表插入和删除运算效率低；存储空间不便扩充；不能动态分配存储空间
C. 链表的插入和删除运算不需要移动元素；存储空间易于扩充且可动态分配
D. 链表的存储密度和顺序表一样
解析：链表需要指针域表示数据元素直接的逻辑关系；存储密度比顺序表要低。
6.某系统总体结构图如下图所示：
(C)
A. 6
B. 2
C. 3
D. 2
解析：定义一棵树的根节点所在的层次为1，其他节点所在的层次等于它的父节点所在层次加1，树的最大层次称为树的深度。题目中树的层次为3，故深度为3。
7.下列关于二叉树的叙述中正确的是( )。(B)
A. 叶子节点总是比度为2的节点少一个
B. 叶子节点总是比度为2的节点多一个
C. 叶子节点数是度为2的节点数的2倍
D. 度为2的节点数是度为1的节点数的2倍
解析：二叉树有一个性质：对于任何一棵二叉树而言，度为0的节点(叶子节点)总是比度为2的节点多一个。
8.下列数据结构哪个是非线性结构?( )(C)
A. 栈
B. 队列
C. 二叉树
D. 链表
解析：有且只有一个根节点，且每一个节点最多只有一个前驱和最多只有一个后继，这种被称为线性结构，否则是非线性结构。栈、队列和链表都符合线性结构，二叉树是一种简单的非线性结构。
9.某二叉树度为2的节点数是n，那么度为O的节点数是( )。(B)
A. n
B. n+1
C. n-1
D. 2n
解析：根据二叉树的性质：对于任何一棵二叉树而言，度为O的节点总是比度为2的节点多一个。题目中度为2的节点数为n，那么度为O的节点数就是n+1个。
10.某二叉树有5个度为2的节点，则该二叉树的叶子节点数是( )。(C)
A. 10
B. 8
C. 6
D. 4
解析：根据二叉树的性质：对于任何一棵二叉树而言，叶子节点总是比度为2的节点多一个。题目中度为2的节点有5个，那么叶子节点数就是5+16个。
11.一棵二叉树共有25个节点，其中5个是叶子节点，那么度为1的节点数是( )。(A)
A. 16
B. 10
C. 6
D. 4
解析：二叉树有一个性质：对于任何一棵二叉树而言，度为0的节点(叶子节点)总是比度为2的节点多一个。叶子节点是5个，那么度为2的节点数是4，25-5-4=16，故答案是A。
12.某二叉树共有7个节点，其中叶子节点只有1个，则该二叉树的深度为( )。(D)
A. 3
B. 4
C. 6
D. 7
解析：二叉树的叶子节点比度为2的节点数多1，叶子节点数是1，那么度为2的节点数是0，度为1的节点数是7-1-0=6，这样我们知道这个二叉树除了最后一个叶子节点，其余的节点都只有一个子节点，这个二叉树的深度就是7。
13.某二叉树有10个度为2的节点，那么该二叉树叶子节点数是( )。(B)
A. 10
B. 11
C. 20
D. 不确定
解析：二叉树有一个性质：对于任何一棵二叉树而言，度为0的节点(叶子节点)总是比度为2的节点多一个。因此这棵二叉树的叶子节点数为10+1=11。
14.某二叉树有30个度为2的节点，40个度为1的节点，那么这个二叉树总的节点数是( )。(C)
A. 70
B. 130
C. 101
D. 99
解析：二叉树有一个性质：对于任何一棵二叉树而言，度为0的节点(叶子节点)总是比度为2的节点多一个。度为2的节点数是30，那么度为0的节点数就是31，30+31+40=101。
15.设树T的深度是4，其中度为1，2，3，4的节点是分别为4，2，1，1。则T中的叶子节点数是( )。(D)
A. 5
B. 6
C. 7
D. 8
解析：树中每个节点和子节点连接的线段称为该节点的边，一个节点的度为n，则该节点的边数也是n，度为0的节点边数是0，度为1的节点边数是1，度为2的节点边数是2，依此类推，一个树的总边数等于该树的节点数和其度数乘积，然后求和。一个树的边数总是比节点数少1个。题目中边数总和为4×1+2×2+1×3+1×4=15，那么节点数总和为15+1=16，而度为1、2、3、4的节点数之和是4+2+1+1=8，则叶子节点数为16-8=8。
16.下列关于树的说法中，正确的是( )。(C)
A. 每个节点可以有多于一个父节点
B. 树可以有多个根节点
C. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
D. 只有根节点的不是树
解析：树最多只有一个根节点，且每个节点最多只有一个父节点。根节点是没有父节点的，只有根节点的也是树。满二叉树是指除最后一层外，每一层上的节点数都有2个子节点的二叉树。完全二叉树是指除最后一层外。每一层上的节点数都达到最大值，在最后一层上只缺少右边的若干节点。满二叉树顾名思义就是整个树除了叶子节点的其他节点都是满的，而完全二叉树是从满二叉树移除了一些叶子节点，且移除顺序是从右往左的。满二叉树一定是完全二叉树，但是反过来不一定成立。
17.下列关于二叉树叙述正确的是( )。(B)
A. 二叉树至少有一个节点
B. 二叉树可以为
本文档预览：3600字符，共6910字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
