{ n=2*i+1;
s[n]=s[i]->lchild; }
if(s[i]->rchild) { n=2*i+2;
s[n]=s[i]->rchild; } i++; }
return 1; }
第六章
一、单项选择题
(1)-(4)AACA (5)-(9)DBCAD (10)-(11)CB
(12)图G是一个非连通分量，至少有两个连通分量。含8个顶点的完全无向图共需28条边，另外一个顶点构成一个连通分量，所以至少含9个顶点。 二、判断题
1．正确2．错误3．正确 4．错误5．正确6．错误 7．正确 8．正确 9．正确
10．正确(若n个顶点依次首尾相接构成一个环的有向强连通图，至少含n条边，即邻接矩阵中至少有n个小于u的非零元素)。
11．错误 12．正确 13．错误 14．正确 15．正确 16．错误 17．错误 18．错误 19．正确 三、填空题
(1)n(n-1)／2 (2)n(n-1) (3)n-1 (4)e (5)2e (6)出边 (7)人边 (8)n (9)有向图
22
(10)O(n) (11)O(n) (12)O(n+e) (13)O(n+e) (14)Kruscal (15)prim
四、算法题
1．将图的深度优先遍历或广度优先遍历算法稍加改造，另设m保存访问的顶点个数，若已访问顶点个数m小于图中顶点个数n，则图G不连通，否则为连通。现将深度优先遍历的非递归算法改造如下：
采用邻接表表示，类型定义如下： #define MaxV 20 typedef struct node {int adjvex;
struct node *next; }Enode;
typedef struct {int data;
Enode *firste; }Vnode;
typedef struct
{Vnode adjlist[MaxV]; int n; int e; }ALGraph;
int connect(ALGraph *G)
{int i,j,Visited[MaxV],m=0,top=0; Enode *p,*S[MaxV]; For(i=0;i Printf(“%c”,G->adjlist[0].data); m++; 29 S[top++]=p->next; j=p->adjvex; if(visited[j]==0) {visited[j]=1; printf(“%c”,G->adjlist[j].data); m++; s[top++]=G->adjlist[j]->firste; } } } if(m return(1);} 2． (1)解：顺序计算每个顶点链表的表中结点个数，就是该顶点的出度. 算法如下： void outdegree(graph g,int v) {arcnode *p; int n=0; p=g.adjlist[v].firstarc; while(p) { n++; p=p->nextarc;} } return n; } void outds(graph g) { int i; printf(“各顶点出度：、\\n”)； for(i=0;i printf(“顶点%d：%d\\n”,i,outdegree(g,i)); } (2)void maxoutds(graph g) { int maxv=0,maxds=0i,x; for(i=0;i {maxds=x;maxv=1;} } printf(“最大出度：顶点%d的出度%d”,maxv,maxds); } (3)void zerods(graph g) { int i,x; printf(“出度为0的顶点：\\n”); for(i=0;i printf(“%d”,i); } } (4)void arc(graph g) { int i,j; arcnode *p; 30 printf(“输入边：\\n”); scanf(“%d,%d”,i,j); p=g.adjlist[i].firstarc; while(p!=NULL&&p->adjvex!=j) p=p->nextarc; if(p==NULL) printf(“不存在！”)； else printf(“存在<%d,%d>边：\\n”，i,j)； } 第七章 一、单项选择题 (1) 一(5) DDCCD (6)一(9) DCCC 二、填空题 （1）8 （2）15 （3） 4.3 （4）中序 （5）记录的键值 （6）7 （7）63 （8）17 （9）17 （10）O(n) (11)O(log2n) (12)越大 （13）散列函数 （14）处理冲突方法 （15） 装填因子 （16）索引表 （17）该块的起始地址 （18） 100 （19）100 （20）101 （21）?log2(n+1)? (22)同义词 （23）n(n+1)/2 (24) 63 (25) m (26)?m/2? (27)m-1 (28) ?m/2?-1 (29)m (30)?m/2? 三、应用题 1．判定树见下图。 查找成功的平均查找长度 ASL=（1+2*2+3*4+4*6）/13=41/13 查找失败时与键值最多比较次数为4。 2．二叉排序树见右图。在等概率情况下， 查找成功的平均查找长度ASL=29/9≈3.2 查找失败时，与键值最多比较次数是5。 3.构造一棵平衡二叉排序树 的过程见右图。 等概率情况下，查找成功的平均查找长度 ASL=（1+2*2+3*4+4*2）/9≈2.8 查找失败时，与键值的最多比较次数是4。 4.按不同的输入顺序输入4、5、6，建立相应的不同形态的二叉排序树见下图。 5.键值序列：{25，40，33，47，12，66，72，87，94，22，5，58} 31 散列地址： 3 7 0 3 1 0 6 10 6 0 5 3 用拉链法处理冲突，构造的散列表如下图： 33 66 22 ^ 0 12 ^ 1 ^ 2 ^ 25 58 ^ 47 3 4 5 ^ 5 94 ^ ^ 72 6 ^ 7 40 ^ 8 ^ 9 87 ^ 10 在等概率的情况下，查找成功的平均查找长度： ASL=（7+2*3+3*2）/12=19/12=1.4 11 查找失败的平均查找长度： ASL=（4+2*1+3*2）/12=1 6.已知散列表是： 0 1 2 3 4 5 6 7 8 9 10 11 12 50 21 57 45 37 查找key = 21 57 45 50 h0=key = 8 5 6 11 d=key+1 = 11 3 2 7 h1=(h0+d) = 6 8 8 5 h2=(h1+d) = 10 查找成功比较次数 2 2 3 2 查找成功的平均查找长度ASL=（1+2+2+2+3）/5=2 四、算法设计 1．按中序遍历二叉排序树可得到一个按键值从小到大排列的有序表，利用这个特点来判别二叉树是否为二叉排序树，算法如下： #define max 99 #define min 0 int judge(BTnode *bt) { BTnode *s[max],*p=bt; int top=0,preval=min; do { while(p) {s[top++]=p; p=p->lchild; } if(top>0) {p=s[--top]; if(p->data preval=p->data; p=p->rchild; } }while(p||top>0) return 1; } 32