习题五
一、选择题
l．数组常用的两种基本操作是（D）。
A．建立与查找 B．删除与查找 C．插人与索引 D．查找与修改 2．对稀疏矩阵进行压缩存储，常用的两种方法是（ B ）。
A．二元组和散列表 B．三元组和十字链表 C．三角矩阵和对角矩阵 D．对角矩阵和十字链表
3．采用稀疏矩阵的三元组表形式进行压缩存储，若要完对三元组表进行成转置，只要将行和列对换，这种说法（ B ）。
A．正确 B．错误 C． 无法确定 D．以上均不对 4．一个广义表的表头总是一个广义表，这种说法（ B ）。
A．正确 B．错误 C．无法确定 D．以上均不对 5．一个广义表的表尾总是一个广义表，这种说法（ A ）。
A．正确 B．错误 C．无法确定 D．以上均不对 6．广义表((a))的表头是（ C ）。 A．（ ） B．a C．（a） D．（（a））
7．广义表（（a））的表尾是（ A ）。 A．（） B．a C．（a） D．（（a））
8．广义表（（a），a）的表头是（ C ）。 A．（ ） B．a C．（a） D．（（a））
9．广义表（（a），a）的表尾是（ C ）。
A．( ) B．a C．（a） D．（（a））
10．广义表（a，b，c）的表头是（ A ）。 A．a B．（a） C．a，b D．（a，b）
11．广义表（a，b，c）的表尾是（ B）。 A．b，c B．（b，c） C．a．b，c D．（a，b，c）
12．广义表A满足Head（）= Tail（），则A为（B）。 A．（） B．（（）） C（（），（）） D．（（），（），（）） 二、填空题
1．数组（array）是n（n＞1）个__相同类型数据_的有序组合，数组中的数据是按顺序存储在一块___地址连续__的存储单元中。
2．数组中的每一个数据通常称为_数组元素_，__数组元素_用下标区分，其中下标的个数由数组的___维数__决定。
3．由于计算机内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺 序存储到计算机存储单元中就必须有一个排列顺序问题。对于二维数组，有两种排列形式：一种是__以行序为主序_；另一种是___以列序为主序_。
4．对于需要压缩存储的矩阵可以分为特殊矩阵和___稀疏矩阵_。对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为__特殊矩阵__；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为___稀疏矩阵__。
5．在一个n阶方阵 a中，若元素满足性质：aij＝aji（0<=i，j<=n-l），则称A为n阶__对称矩阵__。
6．采用顺序存储结构表示三元组表(Trope Table)，以实现对稀疏矩阵的一种压缩存储形式，称为__三元组顺序表_，简称____三元组__表。
7．___矩阵转置__运算是矩阵运算中最基本的一项，它是将一个m*n的矩阵变成另外
17
一个n*m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。
8．广义表是n（n>=0）个元素的序列。记作：A＝（a1，a2，?，an），其中，A是广义表的__名称_，n是它的__长度__，当n=0的时候称为__空表__。
9．在一个非空的广义表中，其元素ai可以是某一确定类型的单个元素，称为___原子__，也可以又是一个广义表，称为____子表___。
10．广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素al为广义表A的___表头__，称其余元素组成的表（a2，a3，?，an）是A的____表尾__。
11．广义表的深度一般定义为广义表元素___最大的层数__，或者说是广义表__括号的重数___。利用递归的定义，广义表的深度就是所有子表中_____最大深度加1____。 三、判断题
1．十字链表不是顺序存储结构。（ √ ） 2．三元组表不是一个随机存储结构。（ √）
3．稀疏矩阵压缩存储后，必然会失去随机存取功能。（ √ ） 4．若一个广义表的表头为空表，则此广义表也为空表。（ × ） 5．广义表是线性表的推广，是一类线性数据结构。（ × ）
6．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。 （ √ ）
7．一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ × ）
8．数组中每个元素必定具有相同的数据类型。（ √ ） 9．线性表是广义表的特例。（ √ ）
10．如果广义表中的每个元素都是原子，则广义表便成为线性表。（√） 11．广义表中原子个数即为广义表的长度。（×） 12．广义表最大子表的深度为广义表的深度。（×） 13．广义表中元素最大的层数称为广义表的深度。（√） 14．广义表是一种多层次结构。（√） 15．广义表是一种线性结构。（×） 16．广义表是一种共享结构。（√） 17．广义表是一种递归结构。（√） 18．广义表是一种单链表结构。（√） 四、综合题
1．用二维数组实现“魔方阵”的打印，所谓“魔方降’是指满足每一行、每一列和对角线上的元素之和均相等的方阵。例如：
8 1 6 3 5 7 4 9 2
就是一个三阶的魔方阵。现在要求编程实现任意输人一个自然数n，打印出相应的n阶魔方阵。
2．找出并打印一个二维数组中的鞍点，所谓鞍点是指该位置上的元素在该行上最大，在该列上最小。
3．写一个创建稀疏矩阵相应三元组的算法。
4．假设三元组元素值为整型，写一个查找三元组元素值为n的算法。
5．有两个稀疏矩阵的三元组triple_a和triple_b，请写出利用三元组这种数据结构，实
18
现将两个稀疏矩阵相加，最后的和存入三元组表triple_c之中的算法。
6．有两个稀疏矩阵的三元组triple_a和triple_b，请写出利用三元组这种数据结构，实现将两个稀疏矩阵相乘，并将最后的乘积存人二元组表triple_c之中的算法。
7．现有稀疏矩阵A如图所示，要求画出以下各种表示法。 ?01400?5??0?700? 0??
??3600280??
(1)三元组表示法 (2)十字链表表示法
习题六
一、选择题
l．在二叉树后序遍历中，任一个结点均在其子女结点后面，这种说法（ ）。 A．正确 B．不正确 C．无法判断 D．以上均不对
2．在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（ ）。 A．正确 B．不正确 C．无法判断 D．以上均不对
3．设深度为h的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少为（ ）。
A．2h B．2h C．2h＋1 D．2h-l
4．二叉村第k层上最多有（ ）个结点。
A．2k B．2k-1 C．2k-1 D．2k-1
5．二叉树的深度为k，则二叉树最多有（ ）个结点。
A．2k B．2k-1 C．2k-1 D．2k -1
6．设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。
A．abdec B．debac C．debca D．abedc
7．设某一二叉树中序遍历为badce，后序遍历为bdeca，则该三叉树先序遍历的顺序是（ ）。
A．adbec B．decab C．debac D．abode
8．设某一二叉树先序遍历为abdecf，后序遍历为debfca，则该二叉树中序遍历的顺序是（ ）。
A．adbecf B．dfecab C．dbeacf D．abcdef
9．将一棵树T转换为一棵二叉树T2，则T的先序遍历是T2的（ ）。
A．先序 B．中序 C．后序 D．无法确定 10．将一棵树T转换为一棵二叉树T2，则T的后序遍历是T2的（ ）。
A．先序 B．中序 C．后序 D．无法碉定 ll．树最适合于用来表示（ ）。
19
A．线性结构的数据 B．顺序结构的数据
C．元素之间无前驱和后继关系的数据 D．元素之间有包含和层次关系的数据 12．二叉树的叶于结点在先序、中序和后序遍历过程中的相对秩序（ ）。
A．发生改变 B．不发生改变 C．无法确定 D．以上均不正确
13． 设一棵二叉树度2的结点数是7，度为1的结点数是6，则叶子结点数是（ ）。
A．6 B．7 C．8 D．9
14．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有左孩子，则其左孩子是（ ）。
A．R[2i-1] B．R[2i+1] C．R[2i] D．R[2/i] 15．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有右孩子，则其右孩子是（ ）。
A．R[2i-1] B．R[2i＋l] C．R[2i] D．R[2/i]
16．一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（ ）。 A．无左孩子 B．无右孩子
C．只有一个叶子结点 D．任意二叉树
17．设a、b为一棵二叉树的两个结点，在后序遍历中，a在b前的条件是（ ）。 A．a在b上方 B．a在b下方 C．a在b左方 D．a在b右方
18．线索二叉树是一种（ ）。
A．逻辑结构 B．线性结构 C．逻辑和线性结构 D．物理结构 19．N个结点的线索二叉树中，线索的数目是（ ）。
A．N-1 B．N＋1 C．2N D．2N－1
20．权值为｛l，2，6，8｝的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A．18 B．28 C．19 D．29 21．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉村采用（ ）存储结构。
A．二叉链表 B．广义表存储结构 C．三叉链表 D．顺序存储结构
22．对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ ）。 A．n＝m＋1 B．m+1=2n C．m＝k-1 D．n=2k+1 23．具有五层结点的二叉平衡树至少有（ ）个结点。
A．10 B．12 C．15 D．17
24．设n，m为一棵二叉树上的二个结点，在中序遍历时，n在m前的条件是（ ）。 A．n在m右方 B．n是m祖先
C．n在m左方 D．n是m子孙
25．线索二又树是一种（ ）结构。
A．逻辑 B．逻辑和物理 C．物理 D．线性 26．将一棵有100个结点的完全二又树从根这一层开始，每一层上从左到有依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）。 A．98 B．99 C．50 D．48 二、填空题
1．树(Tree)是n(n≥0)个结点的_____________集。
20