4、已知关键字集合：{ 50，52，85，22，96，17，36，55 }，用选择排序从小到大排序，则第二趟排序结束为 。
时
的
序
列
5.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为1000,则元素A[4][5]的存储地址为 。
6、一棵满二叉树采用顺序存储，若编号为i(根结点的编号为1)的结点存在右孩子，则其右孩子的编号为______________。
7、对二叉排序树进行 遍历，可以得到该二叉树所有结点构成的从小到大排序序列。
8、假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top= =-1为1表示栈空，那么 为1表示栈满。
9、图的最小生成树算法常用的有 和克鲁斯卡尔算法两种。 10、n个顶点的完全有向图中含有 条边。
三、简答题（本题共4小题，第1小题6分，第2小题7分，第3小题5分，第4小题6分，满分24分）
1、给定权值集合{4，3，8，2，6，10}，构造相应的哈夫曼树，并计算它的带权路径长度WPL。（6分）
2、假定一棵二叉树树的括号表示为A(B(D,E(G，H)),C(,F(I))),试构造该二叉树，并写出先序遍历序列和层次遍历序列。（7分）
3、设哈希函数H（K）=K% 11 ，哈希表长度为13，若关键字K输入顺序为（14，12，30，3，20，40，35，18，28），处理冲突方法为线性探测再散列法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。（5分）
序号 0 1 2 3 4 5 6 7 8 9 10 11 12 关键字 值K 比较次 数
4有向图G＝（V，E），其中V＝｛a,b,c,d,e｝,E={,,
40
四、算法阅读题。（本题3小题共10个空，每空2分，满分20分） 1、 下面是二分法（折半）查找算法。在给定有序（从 小到大）的顺序表中，查找关键字值为k的记录，若找 到，返回记录下标，否则返回-1。请填空完成该算法。 typedef int KeyType; typedef struct
{ KeyType key; /*存放关键字*/ ElemType data; /*其他数据, */ } LineList;
int BinSearch(LineList R[],int n,KeyType k) { int i,low=0,high=n-1,mid; while (low<=high)
{ mid=( )/2; if (k
； }
2、假设以带头结点的单链表表示线性表, 阅读下列算法f30,并回答问题:
(1)设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表； (2)简述算法f30的功能。 typedef struct NODE { ElemType data; struct NODE *next; } LinkList;
void f30(LinkList *&L)
{ //L为带头结点单链表的头指针 LinkList *p,*q; p =L;
while (p !=NULL&&p–>next!=NULL) {q = p–>next; p–>next =q–>next; p =q–>next; free(q);
41
} }
(1)____________________________
(2)____________________________
3、 已知有向图用邻接表为存储结构（定义如下）， 请填空完成连通图的广度优先搜索遍历算法。 typedef char VertexType[3]; typedef struct edgenode { int adjvex;
int value; struct edgenode *next;
/*邻接点序号*/
/*边的权值*/
/*下一条边的顶点*/
/*边结点类型*/
} ArcNode;
typedef struct vexnode
{ VertexType data; /*结点信息*/
ArcNode *firstarc;
/*指向第一条边结点*/ /*单链表的头结点类型*/
} VHeadNode; typedef struct
{int n,e; /*n为顶点数,e为边数*/ VHeadNode adjlist[MAXVEX]; /*单链表头结点数组*/ } AdjList;
/*图的邻接表类型*/
void BFS(AdjList *G, int vi)
{/*对邻接表g从顶点vi开始进行广宽优先遍历*/
int i,v,visited[MAXVEX]; int Qu[MAXVEX],front=0,rear=0; ArcNode *p;
for (i=0;i
printf(\ visited[vi]=1;
/*初始顶点进队*/
/*循环队列*/
rear=(rear+1)%MAXVEX; Qu[rear]=vi;
while ( ) /*队列不为空时循环*/ { front=( ) % MAXVEX; v=Qu[front];
/*顶点v出队*/
/*找v的第一个邻接点*/ /*找v的所有邻接点*/
p= ; while (p!=NULL) {
42
}
} }
if (visited[p->adjvex]==0) { }
visited[p->adjvex]=1; printf(\
rear=(rear+1) % MAXVEX; Qu[rear]=p->adjvex;
/*找v的下一个邻接点*/
五、算法设计题（本题共2小题，每小题8分，满分16分）
1、已知n个元素存放在下列类型的数组中，请按照插入排序思想设计算法void
InsertSort(LineList R[],int n)，并写出该算法的时间复杂度。 typedef int KeyType; typedef struct {
2、设带头结点的单链表L中的结点按data域数值递减排列，试设计一个算法将L中的结点按data域数值递增加排列，统计单链表L中的结点数存入头结点的数据域中，要求算法的时间复杂性为O（n）。 typedef int ElemType; typedef struct NODE { ElemType data; struct NODE *next; } linklist;
KeyType key; ElemType data;
/*关键字域*/
/*关键字类型*/
typedef char ElemType[10]; /*其他数据项类型*/
} LineList;
43