一、（10%）
写void getnext(char pat[],int next[]),求模式par的next值（KMP算法）
二、（10%）
构造+，-，*，/，%的huffman编码，它们的权分别是43，27，15，9，6。
三、（20%）
设树用“孩子兄弟链接法”存储，结点结构如下：
struct treenode {int data ;struct treenode *child,*brother;};
1、
写函数void treecopy (struct treenode *root,struct treenode **pt);复制根指针为root的树，复制出的树的跟为*pr。
2、
写函数void leveltraverse(struct treenode *root),逐层（每层按子树顺序）周游指针为root的树。
四、（20%）
用两种排序算法对整数序列58，39，3，94，38，10，70，24，73，52，27进行升序排序，第一趟的结果分别为：
39，58，3，94，10，38，24，70，52，73，27
27，73，70，58，52，10，3，24，39，38，94
1、
它们分别是哪两种排序算法？
2、
它们的平均时间复杂度及空间复杂度各是多少？是否稳定？
五、（20%）
采用拉链法解决冲突的哈希表说明如下：
Struct node {unsigned int data; Struct node *next;};
#define LEN 12
Struct node *hashrab[LEN];
1、
用除留余数法写哈希函数 int hash(unsigned int key).
2、
写Struct node *lookup(unsigned int key)，在表中查找key，返回其结点指针；若未找到，先将其插入表中，再返回其结点指针。
3、
Hashtab的裂填因子是否为已在表中的整数除以LEN？为什么？
六、（20%）
现有有向图G={V，E}，其中V={0，1，2，3，4，5，6，7，8}，E={<0,2>,<0,7>,<1,2>,<1,3>,<1,4>,<2,3>,<2,8>,<3,5>,<3,6>,<4,5>,<7,8>,<8,6>}.
1、
画出该图并写出邻接矩阵。
2、
写void roposort(int adjmat[9][9],int result [] ),根据邻接矩阵adjmat对该图拓扑排序，结果存于result中。
一、判断下列陈述是否正确（每题3分）
1、
正确性是算法的特征之一。
2、
删除单链表中的非头结点，必须知道其前一结点的地址。
3、
二叉树是度不大于2的树。
4、
非空树所对应的二叉树的根没有右子树。
5、
在有n个2度结点、n+1个叶结点的二叉树中没有度为1的结点。
6、
用邻接矩阵存储图时所需的存储空间与图的边数成正比。
7、
有n个结点的强连通有向图至少有n(n-1）条边。
8、
为了较好地对基本有序的待排序序列进行排序，应采用直接插入排序法。
9、
二路归并排序是稳定的排序方法。
10、对n个关键码排序，快速排序法平均时间复杂度为O(nlog2n).
11、m阶B-树具有k个后件的非叶子结点含有k个键值。
12、散列表的平均查找长度与负载因子有关。
二、填空（每题8分）
1、
现有ABCDE进、出栈，若进的顺序为ABCDE。可能出的ABCDE排列有（
）种，不可能的ABCDE排列有（
）种。
2、
二维数组A[10][20]按行优先顺序存储，每个元素占两字节。若第一个元素的存储地址为100，则A[5][10] 的存储地址为（
）
3、
将m阶对称方阵A的下三角元素（含主对角线）逐行逐列依次存于一维数组B（0下标开始）中，则B（ ）存放着aij （i<j）。
4、
用希尔排序法对序列41，29，56，88，67，9，18，39，46，3进行排序，第一趟（增量取4）排序结果为（ ）
5、
用KMP算法进行模式匹配，aabbabba的next序列为（
）
6、
二叉树的中序和后序周游结果分别为5，4，1，6，2，7，3和5，4，6，7，3，2，1。其先序周游结果为（ ）
三、（每题8分）
1、在双链表的p指针所指的结点前插入值为x的结点，写出C语句序列。
结点结构为struct dnode {int data ;struct dnode *pre ,*next;}.
2、C函数如下：
struct dnode (int data ;struct dnode *lc ,*rc;);
void what (struct dnode *r)
{
struct dnode *q;
if (r==NULL)
return;
q=r->k; r->lc->rc; r->rc=q;
what (r->lc) ;
what (r->rc) ;
}
若二叉树BT=(D,R),D={a,b,c,d,e},R={<aLb>,<bLc,<aRd>,<dRe>}采用llink-rlink法存储，结点结构为bnode，最初将a的指针传给what，画出每次调用what前的结果，<xLy>表示y是x的左子树的根，<xRy>表示y是x的右子树的根。
3、a,b,c,d,e的权值分别为22，7，44，10，17，写出它们的huffman编码。
4、往一棵空的AVL树中依次插入关键码35，30，25，20，15，5，10，画出每个关键码插入完成后的AVL树。
5、哈希表采用线性探测再散列解决冲突，表长为20，哈希函数要除留余数法，除数应选几？如果选了20，从空表开始，依次插入关键码18，38，19，80，5，画出每个每个关键码插入完成后的哈希表。
6、网G=（V，E），V=（1，2，3，4，5，6，7），E={<1,2,6>,<1,3,10>,<2,4,12>,<3,4,8>,<3,6,26>,<4,5,4>,<4,6,6>,<5,7,16>,<6,7,4>},<vi,vj,w>表示活动<vi,vj>的权为w。写出所有的关键活动。
四、（18分）
#define N 8
/*顶点个数*/
struct res {int len , int pre}; /*结果数组元素类型*/
1、
利用求最短路径的Dijkstra算法写函数
void Dij_sp(int Adj[][N], struct res p[], int sv);
/* Adj ：邻接矩阵，sv：出发顶点，p：所得结果*/
2、
写反向（从终点ev到起点sv）输出一条最短路径及其长度的函数
Void
point (struct res p[], int sv, int ev);
/*p：由Dij_sp 算出的从sv出发到其余各顶点的最短路径结果*/
|
