    a2m,2m1    a2m,2m  
 
按以下方式存储于一维数组 B[4m]中：
0    1    2    3    4    k    4m－2    4m－1

a1,1    a1,2    a2,1    a2,2    a3,3    ......    ai, j    ......    a2m,2m◻1    a2m,2m
写出由一对下标（i，j）表示的 k 的转换公式。
答：
i 为奇数时 k=i+j-2
 
i 为偶数时 k=i+j-1
合并后可写成 k=i+j-(i%2)-1    或    k=2(i/2)+j-1

2、特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ 答：
特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配 单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标 i 和 j 和 该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。 而稀疏 矩阵是指非零元素和矩阵容量相比很小（t<<m*n），且分布没有规律。用十字链表 作存储 结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为 i 和 j 的元 素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间 为 O(1)，最差情况下是 O(n)，因此也失去了随机存取的功能。

3、有人说，采用循环链表作为存储结构的队列就是循环队列，你认为这种说法对吗？说明 你的理由。
答： 这种说法是错误的。队列（包括循环队列）是一个逻辑概念，而链表是一个存储概念
，一 个队列是否是循环队列。不取决于它将采用何种存储结构。根据实际的需要，循环队列 可以 采用顺序存储结构，也可以采用链式存储结构，包括采用循环链表作为存储结构。

4、指出下列程序段的功能是什么？
(1)    void demo1(seqstack *s)
{
int I;arr[64];n=0;
while (!stackempty(s)) arr[n++]=pop(s); for(I=0;<n;I++) push(s,arr[I]);
}
(2)    void demo2(seqstack *s,int m)
{
seqstack t; int i; initstack(t);
while(! Stackempty(s)) if(I=pop(s)!=m) push(t,I);
while(! Stackempty(t)) { i=pop(t);
push(s,I);
}
}


（三）算法设计题

1． 试利用循环队列编写求 k 阶斐波那契序列中前 n+1 项（ f0 , f1 ,...... f n ）的算法，要求
 
满足 f n max 且 f n1 max ，其中 max 为某个约定的常数。循环队列的容量为 k，因此， 在算法执行结束时，留在循环队列中的元素应是所求 k 阶斐波那契序列中的最后 k 项
f nk 1 ,...... f n 。 答：
void GetFib(int k,int n)
{
InitQueue(Q); for(i=0;k<k-1;i++)
Q.base[i]=0;
Q.base[k-1]=1; for(i=0;i<k;i++)
printf(“%d”,Q.base[i]); for(i=k;i<=n;i++)
{
m=i%k; sum=0;
for(j=0;j<k;j++) sum+=Q.base[(m+j)%k];
Q.base[m]=sum; printf(“
%d”,sum);
}
}

2. 已知 num 为无符号十进制整数，请写一非递归算法，该算法输出 num 对应的 r 进制的各 位数字。要求算法中用到的栈采用线性链表存储结构（1<r<10）。
解：
typedef struct node{ int data;
struct node *next;
}link;
void trans(int num,int r)
{ link *head=NULL,*s; int n;
while (num>0)
{
n=num%r;
s=(link *)malloc(sizeof(link)); s-
>data=n;
s->next=head;head=s; num=num/r;
}
printf(“输出 r 进制的各位数字：”)；
s=head;
 
while (s!=NULL)
{
printf(“%d”,s->data); s=s->next;
}
}

三、树与二叉树

大纲要求：

（一） 树的概念
（二） 二叉树

1    1.    二叉树的定义及其主要特征
2    2.    二叉树的顺序存储结构和链式存储结构
3    3.    二叉树的遍历
4    4.    线索二叉树的基本概念和构造
5    5.    二叉排序树
6    6.    平衡二叉树

（三） 树、森林
7    1. 树的存储结构
8    2. 森林与二叉树的转换
9    3. 树和森林的遍历
（四） 树的应用
10 1. 等价类问题
11 2. 哈夫曼（Huffman）树和哈夫曼编码
知识点：

1.    二叉树的概念、性质
（1）掌握树和二叉树的定义。
（2）理解二叉树与普通双分支树的区别。二叉树是一种特殊的树，这种特殊不仅仅在 于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的。 即 二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换 之后  的二叉树与原二叉树是不相同的两棵二叉树。但是，对于普通的双分支树而言
，不具 有这种性质。
（3）满二叉树和完全二叉树的概念。
（4）重点掌握二叉树的五个性质及证明方法，并把这种方法推广到K叉树。普通二叉 树的五个性质：第i层的最多结点数，深度为k的二叉树的最多结点数，n0=n2+1的性 质，n个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算 关系（序号i结点的左孩子为：2*i，右孩子为：2*i+1）。
2.  掌握二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合，
 
以及二叉树的顺序存储结构和二叉链表存储结构的相互转换的算法。
3. 熟练掌握二叉树的先序，中序和后序遍历算法以及按层次遍历 二叉树的先序、中序和后序三种遍历算法，划分的依据是视其每个算法中对根结点数 据 的访问顺序而定。不仅要熟练掌握这三种遍历的递归算法，理解其执行的实际步骤， 并 且应该熟练掌握三种遍历的非递归算法。
●按层次遍历二叉树
void LayerOrder(Bitree T)//层序遍历二叉树
{
InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q))
{
DeQueue(Q,p);
visit(p);
if(p->lchild) EnQueue(Q,p->lchild); if(p-
>rchild) EnQueue(Q,p->rchild);
}
}//LayerOrder
4. 遍历是基础，重点掌握在三种基本遍历算法的基础上实现二叉树的其它算法 如求二叉树叶子结点总数，求二叉树结点总数，求度为1或度为2的结点总数，复制二 叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指 定结点等等。
5. 线索二叉树的引出，是为避免如二叉树遍历时的递归求解。递归虽然形式上比较好理
解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险。二 叉 树线索化的实质是建立结点在相应序列中与其前驱和后继之间的直接联系。 对于线索二 叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的 遍历算法，基 本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点 的前驱或后继结 点）。
6. 二叉排序树的中序遍历结果是一个递增的有序序列。二叉排序树的形态取决于元素的
输入顺序，二叉排序树在最差情况下形成单支树。熟练掌握其建立、查找、插入和删除 算法，以及判断某棵二叉树是否二叉排序树这一问题的递归与非递归算法。
7.    平衡二叉树是二叉排序树的优化，平衡二叉树对左右子树的深度有了限定：深度之差 的绝对值不得大于1。掌握平衡二叉树的四种调整算法。
8. 树与森林的遍历，只有两种遍历算法：先根与后根（对于森林而言称作：先序与中序
遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对 应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树使用二叉链表分别 存放它的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也 是利用二叉链表存储孩子及兄弟。掌握树、森林和二叉树间的相互转换。
9.    简单掌握等价类的生成算法。
10. 哈夫曼树为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋 予了权值，这样形成的二叉树按权相加之和是最小的，一般来说，哈夫曼树的形态不 是唯一的。理解哈夫曼编码的基本原理，掌握基于哈夫曼树生成哈夫曼编码的方法。

练习题：
 
（一）选择题：

1.    一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历结果为（ A    ）
A.    CBEFDA    B. FEDCBA
C. CBEDFA    D. 不确定
2.    某二叉树的后序遍历序列为 dabec，中序遍历序列为 debac，则前序遍历序列为（D）。 A．acbed    B．decab
C．deabc    D．cedba
3.    具有 10 个叶子结点的二叉树中有（ B）个度为 2 的结点。
A. 8    B. 9
C. 10    D. 11
4.    树中所有结点的度等于所有结点数加（ C    ）。
A．0    B．1
C．－1    D．2
5.    设 n，m 为一棵二叉树的两个结点，在中序遍历时，n 在 m 前的条件是（ C ）
A. n 在 m 的右方    B. n 是 m 的祖先
C. n 在 m 的左方    D. n 是 m 的子孙
6.        利用逐点插入建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排 序树以后，要查找元素 30 要进行（ B ）次元素间的比较。
A．4    B. 5
C．6    D. 7
7.    在平衡二叉树中，（ C ）。 A．任意结点的左、 右子树结点数目相同 B．任意结点的左、右子树高 度相同 C．任意结点的左右子树高度之差的绝对值 不大于 1 D．不存在度为 1 的结点
8.    由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树 的根（即离插入结点最近且平衡因子的绝对值为 2 的结点）为（ D ）
A．27    B．38
C．51    D. 75
9. 在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存 在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉 链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺 序存储，则最后一个结点下标为 k（起始下标为 1），那么（ A ）时采用顺序存储更 节省空间。
A．d<12n/(k-n)    B. d>12n/(k-n)
C. d<12n/(k+n)    D. d>12n/(k+n)
10. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点（ B ）
A．左指针一定为空    B. 右指针一定为空