软考-非线性结构（上）

1.二维数组与三对角矩阵

1.1：二维数组 a[1..N,1..N]可以按行存储或按列存储。对于数组元素a[i,j]（1<=i,j<=N），当_______时，在按行和按列两种存储方式下，其偏移量相同。
A i != j
B i==j
C i>j
D i<j

1.2：设有n阶三对角矩阵A，即非零元素都位于主对角线以及与主对角线平行且紧邻的两条对角线上，现对该矩阵进行按行压缩存储，若其压储空间用数组B表示，A的元素下标从0开始，B的元素下标从1开始。已知A[0,0]存储在B[1]，A[n-1,n-1]存储在B[3n-2]，那么非零元素A[i,j]（0≤i<n，0≤j<n，|i-j|≤1）存储在B[（ ）]。
A.2i+j-1
B. 2i+j
C.2i+j+1
D.3i-j+1

2.树

2.1：某二叉树的先序遍历序列为ABCDEF，中序遍历 序列为BADCFE，则该二叉树的高度（即层数）为（ ）。
A 3 B 4 C 5 D 6

2.2：对于n个元素的关键字序列{k1,k2,...,kn}，当且仅当满足关系ki<=k2i且ki<=k2i+i{i=1.2...[n/2]}时称其为小根堆（小顶堆）。以下序列中（ ）不是小根堆。
A 16,25,40,55,30,50,45
B 16,40,25,50,45,30,55
C 16,25,39,41,45,43,50
D 16,40,25,53,39,55,45

2.3：具有3个节点的二叉树有（ ）种形态。
A 2 B 3 C 5 D 7

2.4：以下关于二叉排序树（或二叉查找树、二叉搜索树）的叙述中，正确的是（ ）。
A 对二叉排序数进行先序、中序和后序遍历，都得到结点关键字的有序序列
B 含有n个结点的二叉排序树高度为log2n+1
C 从根到任意一个叶子结点的路径上，结点的关键字呈现有序排列的特点
D 从左到右排列同层次的结点，其关键字呈现有序排列的特点

下表为某文件中字符的出现频率，采用霍夫曼编码对下列字符编码，则字符序列“bee”的编码为（ ）；编码“110001001101”的对应的字符序列为（ )

image.png

2.5：A 10111011101 B 10111001100 C 001100100 D 110011011
2.6：A bad B bee C face D bace

2.7：对下面的二叉树进行顺序存储（用数组MEM表示），已知结点A、B、C在MEM中对应元素的下标分别为1、2、3，那么结点D、E、F对应的数组元素下标为（ ）

image.png

A 4、5、6 B 4、7、10 C 6、7、8 D 6、7、14

2.8：假设某消息中只包含7个字符{a,b,c,d,e,f,g}，这7个字符在消息中出现的次数为{5，24，8，17，34，4，13} ,利用哈夫曼树（最优二叉树）为该消息中的字符构造符合前缀编码要求的不等长编码。各字符的编码长度分别为_______。
A. a:4,b:2,c:3,d:3,e:2,f:4,g:3
B. a:6,b:2,c:5,d:3,e:1,f:6,g:4
C. a:3,b:3,c:3,d:3,e:3,f:2,g:3
D. a:2,b:6,c:3,d:5,e:6,f:1,g:4

2.9：设某二叉树采用二叉链表表示（即节点的两个指针分别指示左、右孩子）。当该二叉树包含k个节点时，其二叉链表节点中必有______个空的孩子指针。
A k-1
B k
C k+1
D 2k

可以构造出下图所示二叉排序树（二叉检索树、二叉查找树）的关键码序列是___(2.10)____。

image.png

（2.10）
A.10 13 17 19 23 27 31 40 65 91
B.23 40 91 17 19 10 31 65 27 13
C.23 19 40 27 17 13 10 91 65 31
D.27 31 40 65 91 13 10 17 23 19
【试题分析：根据排序二叉树的构造过程，可知A选项的根结点为10，D选项的根结点为27，因此可以排除。对于C选项，构造根结点的子结点可知19为其左孩子结点，与图不符。本题只有B选项可以构造出如图所示的排序二叉树。】

3.图

3.1：拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧<v,w>或存在人顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是（ ）

image.png

A 41235 B 43125 C 42135 D 41325

3.2：以下关于无向连通图G的叙述中，不正确的是（ ）。
A G中任意两个顶点之间均有边存在
B G中任意两个顶点之间存在路径
C 从G中任意顶点出发可遍历图中所有顶点
D G的临接矩阵是对称矩阵

3.3：已知某带权图G的邻接表如下所示，其中表结点的结构为：

image.png

则图G是_______。
A 无向图
B 完全图
C 有向图
D 强连通图

3.4：在具有n（n>0）个顶点的简单无向图中，最多含有_____条边。
A n(n-1)
B n(n+1)
C n×(n-1)/2
D n×(n+1)/2

3.5：以下关于图的遍历的叙述中，正确的是_____.
A 图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程
B 图的深度优先遍历方法不适用于无向图
C 使用队列对图进行广度优化遍历
D 图中有回路时则无法进行遍历

图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是____(3.6)____。对G进行广度优先遍历（从v0开始），可能的遍历序列为____(3.7)____。

image.png

（3.6）
A.无向图
B.有向图
C.完全图
D.强连通图
（3.7）
A.v0、v1、v2、v3、v4、v5
B.v0、v2、v4、 v5、v1、v3
C.v0、v1、v3、v5、v2、v4
D.v0、v2、v4、v3、v5、v1
【试题分析：由题可以作序列图如下图所示，由图可知，G是有向图。对G进行广度优先遍历，可能的遍历序列为v0、v1、v2、v3、v4、v5。

image.png
】