一、填空题（15分，每小题3分）
1、
若DS=（K，R），其中K=（1，2，3，4），R={<1,3>,<1,2>,<2,4>},则DS的逻辑结构为（ ）
2、
将长度为n的单链表链接在将长度为n的单链表之后的算法时间复杂度为（ ）。
3、
用二分查找在有序表1，5，9，13，17，21，25，29中查找29，需要（ ）次比较。
4、
一种平均复杂度是O（n2）的不稳定排序算法是（ ）。
5、
广义表{a,{b,c,d}}的表尾是（ ）。
二、（35分，每小题7分）
1、稀疏矩阵如下图所示，分别画出存放该矩阵的三元组顺序表和十字链表。
2、用KMP算法进行模式匹配，写出模式abbaabab的next序列。
3、一棵树的先根和后根周游结果分别为a，b，d，e，c，f，g，h和d，e，b，a，f，c，h，g，写出其所对应的二叉树的后序周游结果。
4、哈希表采用线性探测再散列处理冲突，表长为13，哈希函数用除留余数法，除数选择13，从空表开始，依次插入关键码39，15，79，26。画出最终的哈希表。
5、p是带表头的循环双链表中一个结点的指针，用C语句序列，将q指针所指的新结点插入该循环双链表中，使q结点在p结点之前，假定结点的前后指针域名分别为pre和next。
三、（70分，每小题14分）。
1、分别用堆排序和归并排序对序列40，24，55，84，67，8，17，36，22进行升序排序，写出每一趟排序结果。
2、往一棵空的二叉排序树中依次插入关键码8，2，9，5，1，3，4，7，6。画出插入完成后的二叉排序树，从这棵二叉排序树中依次删除关键码9，3，2，分别画出每个关键码删除完成后的二叉排序树。
3、用struct name {int weight, parent, lchild, rchild}数组HT（如下表所示）存放huffman树，其中weight, parent, lchild, rchild分别表示huffman树结点的权、双亲、左右小孩。假定叶结点0，1，2，3，4，5，6，7的权值分别是4，28，6，7，13，22，2，11，在构造huffman树时，任一结点左小孩的权值不小于右孩子的权值，写出huffman树构造完成HT的内容（填写下表），并分别给出0，1，2，3，4，5，6，7的huffman编码。
Weight parent lchild
rchild
4
|
|
|
| 28
|
|
|
| 6
|
|
|
| 7
|
|
|
| 13
|
|
|
| 22
|
|
|
| 2
|
|
|
| 11
|
|
|
| …
| …
| …
| …
|
4、3阶B-树示意如下，分别画出删除关键码60，80，50，30后的B-树。
[
40 ]
[ 20 ]
[ 70，90 ]
[ 10 ]
[ 30 ]
[50，60]
[80]
[100，110]
5、某AOE网的邻接表示意如下，其中i:-->j,w表示活动<i,j>的权为w，写出每一活动的最早开始时间和所以的关键活动。
0：-->1，6-->2，4-->3，5
1：-->4，1
2：-->4，1
3：-->5，2
4：-->6，9-->7，7
5：-->7，4
6：-->8，2
7：-->8，4
8：
四、（30分，每小题15分）
1、完全二叉树用数组顺序存储，写C函数void Ancestors(int BinTree[],int i),输出i的祖先。BinTree是存放完全二叉树的数组。
2、连通无向图用邻接矩阵存储，写函数void DFS(int AdjM[][N],int vi),从顶点vi出发，深度优先遍历（周游）连通无向图。AdjM是连通无向图的邻接矩阵，N是连通无向图的顶点数。
一、（80分，每小题10分）
1、写出算法的五个特征并扼要解释。
2、（1）二维数组A[N][N]（首单元A[0][0]）按列优先顺序存储，每个元素占k字节。若第一个元素的存储地址为1，写出A[j]的存储地址。
（2）若只将对称方阵A的下三角元素（含主对角线）按行优先顺序存储于一维数组B中（0下标开始）中，A[j]（首单元A[0][0]）（i>=j）存于B的哪个单元？
3、用KMP算法进行模式匹配，写出模式ababababba next序列。
4、其二叉树的先根和中根周游结果为1，5，3，6，8，4，2，7和3，5，6，1，4，8，7，2，写出其后跟周游结果。
5、a,b,c,d,e的权分别为1，2，4，5，6，
（1）造（画）出huffman树（要求兄弟之间右边的权不大于左边的权）；
（2）分别给出a,b,c,d,e的编码。
6、哈希表采用链地址法处理冲突，表长为7，哈希函数用除留余数法，除数选7，从空表开始，依次插入关键码38，16，27，80。画出最终的哈希表。
7、3阶B-树示意如下，依次画出插入关键码55，45后的B-树。
[20，50]
[10]
[30，40]
[60]
8、struct node {int pre next;} L[N];实现静态双链表，写C语句序列。将不在静态双链表中的L插在已在静态双链表中的L[j]之前。已知L[j]不是首尾。
二、（60分，每小题20分）
1、分别用快速排序和希尔排序对序列22，36，6，79，26，45，75，13，31进行升序排序，写出每一趟排序结果，希尔排序的增量序列采用5，3，1。
2、从空的开始，依次插入关键码5，2，1，4，6，3，
（1）画出二叉排序树的“生长过程”；
（2）画出平衡二叉排序树的“生长过程”。
3、某AOE网的邻接矩阵A示意图如下：
（1）
画出该网，给出该网的邻接表；
（2）
用Floyd算法求每对顶点间的最短路径，写出矩阵D（0）、D（1）、D（2）、D（0）=A。
三、（10分）
树用孩子兄弟链接法存储，结点结构为
struct TreeNode {int
info ,struct TreeNode *child,*brother;};
写C函数void Travel (struct TreeNode *r),后根遍历树，r是指向树根的指针。
（回忆版，顺序可能有误,起码考了原真题40分，所以大家要注重真题）
一、判断题（10道，每道2分，共20分）
二、选择题（10道，每道2分，共20分）
1、
算法一定（）
A、
程序
B、
可以运行
C、
具有有穷性、确定性、可行性、输入、输出性
2、
已给一段小程序，求时间复杂度
3、
在双链表的p指针所指的结点之后插入结点q下面正确的代码是（）
三、填空题（5空，每空3分，共15分）
1、循环队列用数组A[0,…M-1]存放其数据元素，设t指向其队尾，f指向其队头，队空的条件为_________,队满的条件为______________。
2、向量A已有n个元素（pn为n的指针），在其第i个位置插入元素x的C函数如下：
Void ins (int A[],int *pn,int I,int x)
{
Int j;
For (j= ______;_________;___________)
A[j]=A[______]
A=x
(*pn)++
}
3、快速排序的时间复杂度为___________。
四、简答题：（要求写出详细过程，共8道，每道10分，共80分）
1、哈希表采用线性探测再散列处理冲突，表长为11，哈希函数用除留余数法，除数选择11，从空表开始，依次插入关键码36，17，69，76，19。画出最终的哈希表。
2、用迪杰嘶特拉（Dijkstra）算法求从某个源点到其余各顶点的最短路径
某AOE网的邻接矩阵A示意图如下：
（1）
画出该网，给出该网的邻接表；
（2）
求从某个源点到其余各顶点的最短路径
3、其二叉树的先根和中根周游结果为1，5，3，6，8，4，2，7和3，5，6，1，4，8，7，2，写出其后跟周游结果。
4、
给出了一组数据，要求用堆排序算法进行排序，要求写出详细过程。
5、往一棵空的二叉排序树中依次插入关键码1，3，5，4，6，9，7。画出插入完成后的二叉排序树，从这棵二叉排序树中依次删除关键码9，3，1，分别画出每个关键码删除完成后的二叉排序树。
最后一道：（15分）注：本题和2002年的第五题一模一样。
采用拉链法解决冲突的哈希表说明如下：
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？为什么？
|
