1000=B+(3*10+5)*4 B=1000-(3*10+5)*4=1000-140=860 （9）广义表是线性表的推广，它们之间的区别在于（ A ）。 A．能否使用子表 B．能否使用原子项 C．是否能为空
D．表的长度
（10）下列广义表属于线性表的是（ B ）。
A．E=(a,E) B．E=(a,b,c) C．E=(a,(b,c))
A．a
D．E=(a,L)；L=()
D．(c,d)
（11）广义表((a,b),c,d)的表尾是( D )。
B．d
C．(a,b)
（12）广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为（ A ）。
A．x A．b
B．（a，b） C．(x,(a,b)) B．（b）
C．(a,b)
D．A D．(d)
（13）tail(head((a,b),c,(c,d)))的结果是（ B ）。 （14）若广义表满足head（L）=tail（L），则L的形式是（ B ）
A．空表
B．若L=(a1,?,an),则a1=(a2,?an)
C．若L=(a1,?,an),则a1=a2=?=an) D．((a1),(a1)) （15）数组是一个（ B ）线性表结构。 A．非
B．推广了的 D．不加限制的
D．8
D．(c,d) D．(a)
C．加了限制的
A．4 A．a A．a
（16）数组A[0:1,0:1,0:1]共有（ D ）元素。
B．5 B．d
C．6
（17）广义表((a,b),c,d)的表头是( C )。
C．(a,b)
C．空表
（18）广义表A=(a),则表尾为( C )。
B．(())
（19）以下（ C ）是稀疏矩阵的压缩存储方法。 A．一维数组 B．二维数组 C．三元组表
A．2
D．广义表
C．4 D．∞
（20）设广义表D=(a,b,c,D), 其深度为（ D ）。
B．3
四．算法阅读题
（1）已知A[]是一个下三角矩阵，下述算法的功能是什么？
int f1(int A[],int n)
{ int i,k,s=0; // 设B[0..(n+1)n/2-1]存放下三角元素
k=0; s=A[0];
for(i=0;i 36 { k=k+i+2; s=s+A[k]; } return s; } 算法功能：求矩阵主对角线上元素之和。 分析：注意k的变化依次为：0，2，5，9，14，正好是aii在A中的存储位置。在循环中k每次增加i+2。 第i行主对角线上的元素aii，其在A中的位置为: i(i+1)/2+i； (1) 第i+1行主对角线上的元素ai+1 i+1，其在A中的位置为: (i+1)(i+2)/2+(i+1), (2) (2)-(1)得i-2。 （2）在按行优先顺序存储的三元组表中，求某列非零元素之和的算法如下，填空以完成算法。 #define SMAX 100 // 定义一个足够大的三元组表 typedef struct { int i,j,v; // 非零元素的行、列、值 }SPNode; // 三元组类型 typedef struct // 定义稀疏矩阵 { int m,n,t; // 矩阵的行、列及非零元素的个数 SPNode data[SMAX]; // 三元组表 }SPMatrix; // 三元组表的存储类型 if f2(SPNode *a,col) { // 求第col列非零元素之和 int k,sum=0; if( ① a->t<=0 ) printf(“a<=0”); if( ② col<0 || col >=a->n ) printf(“列错！”); for(③ k=0 ; kt ; ④ k++ ) if (a->tada[k].j==n) sum= ⑤ sum + a->data[k].v ; return sum; } 五． 编程题 （1）试编写求一个三元组表的稀疏矩阵对角线元素之和的算法。 #include \#define ERROR -99999 37 typedef struct { int row; int col; int data; }Triple; int MDSum(Triple *a) { int i; int sum=0; if(a[0].row!=a[0].col) return ERROR; for(i=1;i<=a[0].data;i++) { if(a[i].row==a[i].col) sum+=a[i].data; } return sum; } （2）试编写求广义表中原子元素个数的算法。 解：设j为原子个数，则求广义表中原子元素个数的算法可递归定义如下： 0 LS为空 j= 表尾原子元素个数+1 LS非空且表头为原子元素 表头子表原子元素个数+表尾原子元素个数+1 LS非空且表头子表 int atomnum(Gnode *head) { if(head==NULL) return 0; if(head->tag==0) return(atomnum(head->next)+1); else return(atomnum(head->next)+atomnum(head->val.sublist)); } （3）试编写求广义表最大中原子元素个数的算法。 int maxele(Gnode *head) { int m=0,a; while(head) { if(head->tag==1) { a=maxele(head->val.sublist); if(a>m) m=a; } else if(head->val.data>m) 38 m=head->val.data; head=head->next; } return m; } 39 单元练习7 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）树结构中每个结点最多只有一个直接前驱。 （ㄨ）（2）完全二叉树一定是满二查树。 （ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 （√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。 （√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 （√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 （ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。 （ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。 （√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。 二．填空题 （1） 在树中，一个结点所拥有的子树数称为该结点的 度 。 （2） 度为零的结点称为 叶（或叶子，或终端） 结点。 （3） 树中结点的最大层次称为树的 深度（或高度） 。 （4） 对于二叉树来说，第i层上至多有 2i-1 个结点。 （5） 深度为h的二叉树至多有 2-1 个结点。 （6） 由一棵二叉树的前序序列和 中序 序列可唯一确定这棵二叉树。 （7） 有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。 （8） 哈夫曼树是带权路径长度 最小 的二叉树。 （9） 由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。 （10） 某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。则前序遍历序列 为：DABEC 。 （11） 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG， 则二叉树中叶结点是： E、F、H 。 （12） 已知完全二叉树的第8层有8个结点，则其叶结点数是 68 。 （13） 由树转换成二叉树时，其根结点无 右子树 。 （14） 采用二叉链表存储的n个结点的二叉树，一共有 2n 个指针域。 （15） 采用二叉链表存储的n个结点的二叉树，共有空指针 n+1 个。 （16） 前序为A，B，C且后序为C，B，A的二叉树共有 4 种。 h 40