第五章 数组与广义表
班级： 学号： 姓名：
一、选择题
1、稀疏矩阵的一般的压缩方法有(C )。
A)二维数组 B)广义表 C)三元组表 D)一维数组
?a11?a1n???2、设矩阵A??????是一个对称矩阵，为了节省空间，将其下三角部分按行优先
?a??n1?ann?存放在一维数组B中。对下三角矩阵中任一元素aij (i>=j)，在一维数组B中下标ｋ的值是( a )。
A)i(i-1)/2+j-1 B)i(i-1)/2+j C)i(i+1)/2+j-1 D)i(i+1)/2+j 3、在稀疏矩阵的三元组表表示法中，每个三元组表示( )。 A)矩阵中数据元素的行号、列号和值 B)矩阵中非零元素的值
C)矩阵中非零元素的行号和列号 D)矩阵中非零元素的行号、列号和值 4、对稀疏矩阵进行压缩存储是为了( )。
A)便于进行矩阵运算 B)便于输入和输出
C)节约存储空间 D)降低运算的时间复杂度 5、广义表是线性表的推广，它们之间的区别在于( )。 A)能否使用子表 B)能否使用原子项 C)表的长度 D)是否能为空
6、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为( )。
2
A) O(1) B) O(n) C) O(n) D) O(log2n) 7、一个递归算法必须包括（ ）。
A) 递归部分 B)终止条件和递归部分 C)迭代部分 D)终止条件和迭代部分
二、填空题
1、n维数组中的每个元素都最多有( )个直接前趋。
2、对于一个一维数组A[12]，若一个数据元素占用字节数为S，首地址为1，则A[i](i>=0)的存储地址为( )，若首地址为d，则A[i]的存储地址为( )。
3、已知二维数组A[m][n]采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A[0][0]），则A[i][j]的地址是
( )。
4、 多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种
( )存取结构。
5、 阵的压缩存储就是为多个相同的非零元素分配( )个存储空间，零元素不分配空间。 6、递归是算法设计的重要方法，递归由（ ）项和（ ）项构成。用递归的方法求广义表LS的深度DEPTH(LS)，写出基本项和递归项。 基本项：DEPTH(LS)=1 当LS是空表 DEPTH(LS)=0 当LS是原子
11
递归项： DEPTH(LS)=1+MAX(DEPTH(?i))，1?i?n.
7、广义表( a , ( a , b ) , d , e , ((i , j ) , k ) ) 的长度是（ ），深度是（ ）。 8、广义表((a) , (( b ) , c ) , (((d )))) 的长度是（ ），深度是（ ）。
9、设广义表S=((a , b) , ( c , d))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则 GetHeat(GetTail(S)) = ( ) ， GetTail (GetHeat (S)) =( )。
10、设广义表S=(a , b , ( c , d) , (e , (f , g )))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则GetHeat(GetTail(GetHeat (GetTail(GetTail(S)))))= ( )
三、问答题与算法题
１、给出C语言的三维数组A[m][n][s]地址计算公式。
?a11??a21２、设有三对角矩阵 An╳n=?0????0?a12a22a32?00a23a33?0????ann?10??0?0?，将其三条对角线上的元素逐行???ann??地存储到向量B[0...3n-3]中，使得B[k]=aij,求：
(1)用i , j 表示k的下标变换公式。
(2)用 k 表示 i,j 的下标变换公式。
３、设二维数组A5╳6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点A45的起始地位为何? 按行和按列优先存储时，A25的起始地址分别为何? 4、已知一个稀疏矩阵如下图所示：
0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0
(1) 写出它的三元组顺序存储表示；
(2) 给出它的行逻辑链接的顺序存储表示； 5、画出下列广义表的图形表示：
(1) A=((a,b),(c,d)) (2)B=(a,(b,(c,d)),(e))
6、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。
7、画出广义表LS=(( (b , c) , d ), (a) , ((a) , ( (b , c) , d )) , e , ( ))的具有共享结构的存储表示。 8、设广义表LS=(soldier , (teacher , student) , ( worker , farmer ) )，用取表头函数GetHead ( ) 和
取表尾函数GetTail ( )分离出原子student 。 10、画出下列矩阵的十字链表
12
?0??7 ?0??2?203080060??9? ?0?2??
13
第六章 树和二叉树
班级： 学号： 姓名：
一、选择题
1、设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少有（ ）个，至多有（ ）个。
A)2h ； B)2h-1 ； C)2h+1；D)2 h-1； E)2 h -1； F)2 h +1。
2、高度为h的完全二叉树至少有（ ）个结点，至多有（ ）个结点。 A)2 h ； B)2 h -1 ； C)2 h +1； D)2 h –1 。 3、具有n个结点的满二叉树有（ ）个叶结点。
A)n/2 ； B)(n+1)/2； C)(n-1)/2； D)n/2+1。 4、一棵具有n个叶结点的哈夫曼树，共有（ ）个结点。 A)2n B)2n-1 C)2n+1 D)2 n -1； 5、一棵具有25个叶结点的完全二叉树最多有（ ）个结点。 A)48； B)49； C)50； D)51。 6、已知二叉树的前序和中序遍历序列分别是abdgcefh，dgbaecfh，则后序遍历序列是（ ）。 A)bdgcefha； B)gdbecfha； C)bdgaechf； D)gdbehfca。 ７、已知二叉树的中序遍历序列是debac，后序遍历序列是dabec，则前序遍历序列是（ ）。 A)acbed； B)decab； C)deabc； D)cedba。 8、在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）。
A)t->lefu=null B)t->ltag=1 C)t->ltag=1且t->left=null D)以上都不对 9、如图所示的4棵二叉树中，（ ）不是完全二叉树。
A B C D
二、填空题
1、含有100个结点的树有( )条边。
2、一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个。
3、含A、B、C三个结点的不同形态的树有（ ）棵，不同形态的二叉树有（ ）棵。 4、一棵含有n个结点的2叉树，可能达到的最大深度是（ ）和最小深度是（ ）。 5、一棵哈夫曼树有19个结点，则其叶子结点的个数是( )。
6、设二叉树的中序遍历序列是：ABCDEFG，后序遍历序列是：BDCAFGE。则该二叉树的前序遍历序列是：（ ），该二叉树的对应的森林包含（ ）棵树。
7、将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素( )中。
8、已知一棵树T的边集为{（I ，M），（I ，N），（E ，I），（B ，E），（B ，D），（C ，B），（G ，J），（G ，K），（A ，G），（A ，F），（H ，L），（A ，H），（C ，A）}。则该树的
14
根结点是（ ）、叶结点是：（ ）、树的深度是：（ ）。 三、问答题与算法题
１、void ABC(BiTree BT)
{ if (BT==NULL) return; ABC(BT->lchild);
Printf(“%c”,BT->data); ABC(BT->rchild); }
该算法的功能是______________________________________
请模仿写出另外两个类似此算法的算法，并标明这两个算法的功能。 2、写出下列算法的功能．
TelemType LevelOrderTraverse (BiTree T, Status (*vist)(TelemType e)) {InitQueue(Q);EnQueue(Q,T); max=T->data;
While(!QueueEmpty(Q))
{DeQueue(Q,p);if(p->data>max) max=p->data; if(p->lchild) EnQueue(Q, p->lchild); if(p->rchild) EnQueue(Q, p->rchild); }
return max; }
3、写出下列算法的功能．
Status PreOrderTraverse (BiTree T, Status (* Visit)(TelemType(e))) { InitStack(S);Push(S,T);
While(!StackEmpty(Q)) {Pop(S,p);
if(p->data!=?A?)
{e=p;if(p->rchild) Push(S, p->rchild); if(p->lchild) Push(S, p->lchild);} }
else return e; return OK; }
4、写出下列算法的功能．
void ABC ( BiTree BT , int & c1, int & c2 ) {
if ( BT ! = NULL) {
ABC ( BT-> lchild , c1,c2 ); c1 ++ ;
if ( BT -> lchild = = NULL && BT ->rchild = = NULL ) c2 ++; ABC ( BT -> rchild , c1 , c2 ); } }
15