小
数据结构(C语言版)
习题答案
(教师版)
淮北师范大学计算机科学与技术学院《数据结构》课程组
2011.8
目 录
习 题 1 ..................................................................................................................................... 1
一、简答题 ....................................................................................................................... 1 二、计算以下算法的时间复杂度 ................................................................................... 1 三、算法设计题 ............................................................................................................... 1 习 题 2 ..................................................................................................................................... 3
一、单选题 ....................................................................................................................... 3 二、算法设计题 ............................................................................................................... 3 习 题 3 ..................................................................................................................................... 6
一、单选题 ....................................................................................................................... 6 二、填空题 ....................................................................................................................... 6 三、简答题 ....................................................................................................................... 6 四、算法设计题 ............................................................................................................... 6 习 题 4 ..................................................................................................................................... 8
一、单选题 ....................................................................................................................... 8 二、填空题 ....................................................................................................................... 8 三、简答题 ....................................................................................................................... 8 习 题 5 ..................................................................................................................................... 9
一、填空题 ....................................................................................................................... 9 二、解答题 ....................................................................................................................... 9 三、算法设计题 ............................................................................................................. 11 习 题 6 ................................................................................................................................... 13
一、解答题 ..................................................................................................................... 13 二、算法设计题 ............................................................................................................. 17 习 题 7 ................................................................................................................................... 20
一、填空题 ..................................................................................................................... 20 二、解答题 ..................................................................................................................... 21 三、算法设计题 ............................................................................................................. 24 习 题 8 ................................................................................................................................... 28
一、单选题 ..................................................................................................................... 28 二、填空题 ..................................................................................................................... 28 三、解答题 ..................................................................................................................... 28 四、算法设计题 ............................................................................................................. 32
习 题 1
一、简答题
1．数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
2．集合中，数据元素同属于一个集合，除此之外别无其它关系；线性结构中的数据元素之间存在一个对一个的关系；树形结构中的数据元素之间存在一个对多个的关系；图形结构中的数据元素之间存在多个对多个的关系。线性结构是树形结构的特例，树形结构是图形结构的特例。所有100以内的正整数是一个集合；某班级所有同学的学号是线性结构的；一个学校包含多个学院，每个学院多个系，每个系多个专业，是一种树形结构；全国内的中国银行各个分行构成图形结构。
3．顺序存储结构的优点是节省存储空间，因为不需要额外的存储空间来保存数据间的逻辑关系，可以进行随机访问；缺点是进行数据的插入和删除时可能需要移动大量的结点。链式存储结构的优点是在进行数据的插入和删除时，仅需修改指针，不需要移动结点；缺点是需要额外的存储空间来存储结点之间的逻辑关系。索引存储结构的优点是在进行插入和删除操作时，只需移动存储在索引表中对应结点的存储地址，而不必移动存放在结点表中结点的数据，因此保持了较高的数据修改运算效率；缺点是创建和维护索引表增加了时间和空间的开销。散列存储结构的优点是查找速度快，只要给出待查找的关键字，即可计算出该结点的存储地址。与上述三种方法不同的是，散列存储方式只适合要求对数据进行快速查找和输出的场合，其关键是要选择一个好的散列函数和处理“冲突”的方法。
4．抽象数据类型的定义：ADT <抽象数据类型名> {
数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 }ADT 抽象数据类型名
抽象数据类型较之一般数据类型抽象层次更高、定义范畴更广。抽象数据类型不再局限于计算机系统中已经实现的数据类型，可以是用户所定义的数据类型，它可以由计算机系统已经实现的数据类型来表示和实现。抽象数据类型必须先定义后使用，定义抽象数据类型只描述数据的逻辑结构及允许进行的操作，不考虑数据的物理存储及其操作的具体实现。
5．算法的基本特征是有穷性、确定性、可行性、输入、输出。算法的设计目标是正确性、可读性、健壮性（鲁棒性）和高效性。
二、计算以下算法的时间复杂度
1．O（n） 2．O（n2） 3．O（n）
三、算法设计题
1．#define M 10
void matrixadd(int n,int A[M][M],int B[M][M],int C[M][M])
1
{
int i,j;
for(i=0;i 2．#include { int a,i,min=0,max=0; for (i=1;i<=10;i++) {scanf(“%d”,&a); if(min>a) min=a; if(max 2 习 题 2 一、单选题 1.A 2.C 3.C 4.D 5.B 6.B 7.B 8.D 9.A 10.B 二、算法设计题 1．算法如下： int Length_LinkList(LinkList L) { int l; //l记录L的表长 LNode *p; p=L; l=1; while(p->next) { p=p->next; l++; } return l; } 2．算法参见算法2.10 3．算法如下： void Insert_pre(LinkList *L,DataType x,DataType y) { LNode *s,*p; p=L->next; While(p->next->data!=y&&p->next!=NULL)//找到值y结点的直接前驱p p=p->next; s=(LinkList)malloc(sizeof(LNode));//为新插入结点分配空间 s->data=x; s->next=p->next;//在值y结点之前插入结点 p->next=s; } 4．分析：判断一个顺序表是否有序，也即判断该表要么是非递增顺序表或非递减顺序表。 算法如下： void Judge(Sq_List *L) { int len; len=L->length; int i=1; 3 if(L->data[0] printf(“该表是有序表！”); } 5．参见例2.3算法 6．分析：依次扫描单链表的每个结点，判断该结点值是否是奇数，若是奇数则从单链表里摘除并作为尾结点插入新链表，直到扫描完为止。 算法如下： void Divide_L(LinkList L,LinkList nL) { LNode *p,*pre,r; p=L->next; pre=L;//pre指向p的前驱 r=nL;//r作为新链表的尾指针 while(p) { if(!(p->data)%2) {/*如果当前结点值是奇数，则插入新链表表尾，并继续扫描链表的下一个结点*/ r->next=p; r=r->next; p=p->next; } else {/*如果当前结点值是偶数，则继续扫描链表的下一个结点*/ pre=p; p=p->next; } } r->next=NULL; 4 } 7．参见例2.5算法 8．略。 9．提示：依次扫描链表每一个结点，判断该结点值与前面所有结点值是否有重复，有重复就删除该结点，直到扫描完毕。算法略 10．分析：以原链表的头结点组成一个空表，然后对原链表的每个结点进行有序插入空表。 算法如下： void Sort_L(LinkList L) { LNode *p,*q,*r; p=L->next; L->next->next=NULL; p=p->next; while(p) { r=L->next;//指向新链表的第一个结点 while(r) { if(p->data<=r->data)r=r->next; else r->next=p; } p=p->next; } } 11．参见例2.6算法。 12．略 13．提示：先找到值为y的结点的直接前驱，然后插入值为x的新结点。算法略。 14．提示：首先通过双链表的向右指针找到最后一个结点，然后从右到左利用向左指针打印每个结点值。算法略。 5 习 题 3 一、单选题 1.B 2.A 3.C 4.B 5.C 6.B 7.C 8.A 9.D 10.C 二、填空题 1．线性、任何、栈顶、队尾、队首 2．栈顶、栈底 3．队列 4．前一个 5．n-1 6．移动栈顶指针、存入元素 7．移动队首指针、取出元素 8．0 三、简答题 1．相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。 不同点：(1) 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。(2) 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。 2．至少有14种。 (1) 全进之后再出情况，只有1种：4，3，2，1 (2) 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 (3) 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 (4)进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3 3．输出为“stack”。 4．a + b * (c - d) – e (略) 5．答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：(1) 设置一个布尔变量以区别队满还是队空；(2) 浪费一个元素的空间，用于区别队满还是队空；(3) 使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法(2)，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N 四、算法设计题 1．int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 6 { InitStack(S);InitQueue(Q); while((c=getchar())!='@') { Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; } return OK; }//Palindrome_Test 2．解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他两种见简答题）； 思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1； 若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。 Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法 { if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示\"空\表示\"满\" return OVERFLOW; Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=1; //队列满 }//EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法 { if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front]; if(Q.front==Q.rear) Q.tag=1; //队列空 return OK; }//DeCyQueue 分析:当循环队列容量较小而队列中每个元素占的空间较多时，此种表示方法可以节约较多的存储空间，较有价值。 7 习 题 4 一、单选题 1.D 2.C 3.B 4.A 5.D 6.A 7.B 8.B 9.C 10.A 二、填空题不 1．顺序存储方式、链式存储表示 2．4、defg 3．STUDENT└┙teacher、I└┙AM 4．LOC(aij)=LOC(a00)+(i×n+j)×k 5．b、( ) 三、简答题 1. 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。但串的基本操作和线性表却有很大的差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，例如在线性表中查找某个元素、取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，例如在串中查找某个子串、取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。 2. 广义表（Lists，又称列表）是线性表的推广。线性表定义为n(n≥0)个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，即不可分割；而广义表中的元素既可以是原子项，也可以是子表。 8 习 题 5 一、填空题 1．8 2．4 3．n-1 4．501 5．2k-1、2k-1、2k-2+1 6．2i+1、2i+2 7．2n、n-1、n+1 8．不发生改变 9．n+1 10．中序 11．4 二、解答题 1．总结点数n = n0 + n1 + n2 + „ + nm 总分支数 B= n-1 = n0 + n1 + n2 + „ + nm-1 = 1*n1 + 2*n2+ „ +(m-1)*nm-1+ m*nm 则有 n0=((i1)ni)1 i2m2． 具有3个结点的树具有3个结点的二叉树 3． （1）二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； （2）二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； （3）二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 4． 9 EBACDGFHIKJ 5． ABCDGEHFIJK 6． 森林转换成的二叉树： 先序前驱线索化： 123456871513148671910111232104591112131514 中序线索化： 后序后继线索化： 123456871513141091112NULL123456871513141091112NULL 7．构造哈夫曼树： 10 000000.02c110.10h11010.32e0.19b0.21g10.03f100.060.07da c d 0001 e 01 f 00001 g 11 h 0011 哈夫曼编码： 字母 哈夫曼编码 a 0010 b 10 00000 三、算法设计题 1．利用二叉树的结构特点，将二叉树根结点的左右指针互换，同时分别递归地对左子 树和右子树进行同样的操作，相应的算法如下： void BTreeExchangeChild(BiTree BT) { //交换二叉树BT中各结点的左右子树 BiTree p; if (BT!=NULL) { p=BT->lchild; BT->lchild=BT->rchild; BT->rchild=p; BTreeExchangeChild(BT->lchild); BTreeExchangeChild(BT->rchild); } } 2．二叉树T1和T2相似的递归模型： f(T1,T2)=True 若T1=T2=NULL f(T1,T2)=False 若T1、T2之一为空，另一棵不为空 f(T1,T2)=f(T1->lchild, T2->lchild)&& f(T1->rchild, T2->rchild) 若T1、T2均不为空 对应的算法如下： int Similar( BiTree T1, BiTree T2) { if (T1==NULL && T2==NULL) return (1); else if (T1==NULL||T2==NULL) return (0); else return (Similar(T1->lchild, T2->lchild)&&Similar(T1->rchild, T2->rchild)); } 11 3．设置一个静态变量max，初值为0，在某种遍历时，访问结点的时候判断其数据域值是否大于max，如果是就赋值给max，遍历结束后，max中就是最大值。 int FindMaxValue(BiTree BT) { //在先序遍历下求二叉树数据域的最大值(递归算法） static int max=0; //最大值 if(BT!=NULL) { if(BT->data>max) max=BT->data; FindMaxValue(BT->lchild); FindMaxValue(BT->rchild); } return max; } 4．计算一棵二叉树的所有结点个数的递归模型f(BT)如下： f(BT)=0 若BT=NULL f(BT)=1 若BT->lchild=NULL且BT->rchild=NULL f(BT)=f(BT->lchild)+f(BT->rchild)+1 其他情况 int Nodes(BiTree BT) { //统计二叉树所有结点个数 if (BT=NULL) return 0; else if (BT->lchild==NULL && BT->rchild==NULL) return 1; else return (Nodes(BT->lchild)+Nodes(BT->rchild)+1); } 5．算法实现如下： BiTree Search (BiTree BT, int x) { //在BT为根结点指针的二叉树中查找数据元素x BiTree p; if (BT->data==x) return BT; //查找成功返回 if (BT->lchild!=NULL) return(Search(BT->lchild,x)); //在BT->lchild为根结点指针的二叉树中查找 if (BT->rchild!=NULL) return(Search(BT->rchild,x)); //在bt->rchild为根结点指针的二叉树中查找 return NULL; //查找失败返回 } 12 习 题 6 一、解答题 1． 21543 该图是强连通图。 2． （1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。 （2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。 （3）任意一个顶点vi的度是第i行或第i列上非0元的个数。 3．void FindInDegree(MGraph G)/*求入度操作*/ { /*indegree为入度,outdegree为出度,degree为度*/ int indegree[VertexMaxNum],outdegree[VertexMaxNum],degree[VertexMaxNum],i,j; for (i = 1; i <= G.vexnum; i++) indegree[i] = outdegree[i] = 0; for (i = 1; i <= G.vexnum; i++) for (j = 1; j <= G.vexnum; j++) if(G.arcs[i][j]>0) { outdegree[i]++; indegree[j]++; } for(i=1;i<=G.vexnum;i++) degree[i]=indegree[i] + outdegree[i]; } 4．void PrintGraph(ALGraph g) { int i; ArcNode *p; printf(\"The arcs are\\n\"); for(i=0;i 13 printf(\"%d->%d\\n\ p=p->nextarc; } } } 5．邻接矩阵和邻接表如下： 逆邻接表如下： 6．邻接矩阵 011000邻接表： 123456211324110000001000110 0101111101001103545355646 7．图6.35 prime算法求解过程 14 1919926526534 314 (a) (b) 199492652694534 334 (c) (d) 199426653 (e) 34 图6.1 prime算法求解过程 kruskal算法求解过程 112652645334 334 (a) (b) 1192664526645334 334 (c) (d) 15 199266453 (e) 34 图6.36 kruskal算法求解过程 8．深度优先1 2 5 3 4 6（答案不唯一） 广度优先：1 2 3 5 4 6（答案不唯一） 9．遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。 10． （1）v1,v2,v3,v8,v4,v5,v7,v6 （2）v1,v2,v4,v6,v5,v3,v7,v8 （3）v1到结点v8的最短路径为：v1,v2,v3,v8 11．拓扑序列为：2 5 7 1 3 4 8 6（答案不唯一） 12．（1）0132465 （2）0123465 13．有两条关键路径（1,2,5,7,10）和（1,2,5,8,10），和关键活动包括a1，a4，a8，a9，a13，a14 14．不能。举例说明：如下图，从1到4，如果按照此算法，将走1-2-3-4，而实际最短为1-4。 21131115． 循环 初态 1 2 3 4 5 6 7 S {1} {1,5} {1,5,6} {1,5,6,2} {1,5,6,2,3} {1,5,6,2,3,7} {1,5,6,2,3,7,8} {1,5,6,2,3,7,8,4} — 5 6 2 3 7 8 4 30 28 25 25 25 25 25 25 24∞ ∞ ∞ ∞ 47 47 47 47 10 10 10 10 10 10 10 10 ∞ 17 17 17 17 17 17 17 w D[2] D[3] D[4] D[5] D[6] D[7] D[8] 50 50 50 27 27 27 27 27 ∞ ∞ 32 31 30 30 30 30 ∞ ∞ ∞ ∞ ∞ 45 45 45 16． 16 6204 53726920264 537722057264 326620264 532772 D(0) D(1) D(2) 16691164 5103772D(3) D(4) 17． （1）每个事件的最早开始时间Ve和最晚开始时间Vl Ve Vl e l l-e <1,2> 0 17 17 ① 0 0 <1,3> 0 0 0 ② 19 19 <3,2> 15 15 0 ③ 15 15 <2,4> 19 27 8 ④ 29 37 <2,5> 19 19 0 ⑤ 38 38 <3,5> 5 7 2 <4,6> 29 37 8 ⑥ 43 43 <5,6> 8 8 0 （2）每个活动的最早开始时间e和最晚开始时间l （3）此工程最早完成时间为43。 （4）关键路径为<1,3><3,2><2,5><5,6> 二、算法设计题 1．void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G { int visited[MAXSIZE]; InitStack(S); Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1); visited=1; while(!StackEmpty(S)) { while(Gettop(S,i)&&i) { j=FirstAdjVex(G,i); if(j&&!visited[j]) { visit(j); visited[j]=1; Push(S,j); //向左走到尽头 17 } }//while if(!StackEmpty(S)) { Pop(S,j); Gettop(S,i); k=NextAdjVex(G,i,j); //向右走一步 if(k&&!visited[k]) { visit(k); visited[k]=1; Push(S,k); } }//if }//while }//Straverse_Nonrecursive 2．图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { VertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) { if( !g.vexnum || !g.arcnum ) return FALSE; Queue Q; InitQueue( Q ); EnQueue( Q, i ); int u; while( ! QueueEmpty ( Q ) ) { DeQueue( Q, u ); visited[u] = 1; ArcNode *p; int k; for( p = g.vertices[u].firstarc; p; p = p->nextarc ) 18 { k = p->adjvex; if( k == j ) return OK; if( !visited[k] ) EnQueue( Q, k ); } } return FALSE; } 3．int visited[N]; void dfstraverse(ALGraph g,int v) { int count=0; for(v=0;v if(count==1) printf(“此图为连通图！\\n”); else printf(“此图不连通，共有%d个连通分量！\\n”,count); } void dfs(ALGraph g,int v) { int w; ArcNode *p; visited[v]=1;printf(“%d”,v); p=g.vertices[v].firstarc; while(p) { w=p->adjvex; if(!visited[w]) dfs(g,w); p=p->nextarc; } } 19 习 题 7 一、填空题 1．n、n+1 2．6,9,11,12、5 分析：长度为12的查找表对应的判定树如图7-1，故查找长度为4的元素有5个，则查A[12]所比较的下标即从根到A[12]结点的路径上所经历下标依次为6,9,11,12。 639147112581012 3．55、55、56、58.5 分析：每块长度最佳取3000=55，此时ASL=n+1=56；若每块长度为40，则分为3000/40=75块，此时平均查找长度为：(75+40)/2+1=58.5 4．26 分析：3阶B-树每个结点中最多2个关键字（对应有3个子树），第1层最多1个结点，第2层最多有3个结点，第3层最多有33个结点，第4层最多有333个结点，（第4层是叶子结点）。故关键字只在前3层上，前3层共有结点：1+3+33=13个，关键字最多有132=26个。 5．形态、呈单支树 6．m-1 m/2-1 7．m路平衡索引树、m、m/2或者(m+1)/2 8．logm(2n1n1)1、logm()1 2229．k(k+1)/2 10．31 分析：3阶B-树，第一层至少有1个结点，第2层至少有2个结点，第3层至少有2m/2个结点„„第5层至少有2m/23个结点，故至少共有1+2+„2m/23=31个结点。 11．随机、顺序 12．散列函数 解决冲突的方法 选择好的散列函数 处理冲突的方法 均匀 简单 13．小于等于表长的最大质数、不包含小于20质因子的合数 14．左子树、右子树 15．插入、删除 16．结点的左子树的高度减去结点的右子树的高度 20 二、解答题 1．三种查找方法对查找表的要求分别如下： （1）顺序查找：查找表既可以顺序方式存储，也可以链式方式存储，且表中数据元素不要求有序； （2）折半查找：查找表必须以顺序方式存储，且表中数据元素必须有序； （3）分块查找：查找表中每块内的元素可任意次序存放，但块与块之间必须按关键字有序存放，并为每个块建立索引构成索引表，索引表有序。 三种方法的查找成功时的平均查找长度分别如下： （1）顺序查找法：(n+1)/2 n1log2(n1)1log(n1)12n（2）折半查找法： （3）分块查找：若用顺序查找确定所在的块，平均查找长度为： ；若用折 半查找确定所在块，平均查找长度为：。其中，t为每块含有的元素的个数。 2．时间复杂度是判断查找方法的一个重要指标，但不是唯一指标。使用什么查找方法 要综合考虑。散列查找时间复杂度为O（1），查找速度最快，但需构建散列函数，进行计算散列地址，查找时要有解决冲突的方法；折半查找时间复杂度为O（log2n），需要元素有序且顺序存储，排序操作的时间开销大；顺时查找时最差间复杂度为O（n），但对查找表无要求，数据有序无序均可，在数据量较小时使用方便。 3．监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。 4．（1）判定树如图7-2所示（图中结点中的数字为元素在有序表中的下标）； 639147112581012 （2）54的位置为8，故查找元素54需依次和6、9、7和8号元素即30、63、42和54进行比较，查找成功。 （3）从根结点6号元素出发，根据比较结果，依次经过9、11和12号元素，即30、63、87和95，查找失败。 （4）ASLsucc=(1+22+34+45)/12=37/12 5．33个 分析：假设用Ni表示深度为i的平衡二叉树中含有的最少结点树。显然，N0=0，N1=1，N2=2，N3=4，并且Ni=Ni-1+Ni-2+1。这个关系和Fibonacci（斐波那契）数列极为相似。故 21 N7=33。 6．（1）二叉排序树如图7-3（a），ASLsucc=(1+2+3+4+5+6+7+8)/8=4.5 （2）平衡二叉树如图7-3（b），ASLsucc=(1+22+34+51)/8=2.75 与（1）相比，可见在同样序列的查找中，平衡二叉树比二叉排序树的平均查找长度要小，查找效率要高。 38121925303447(a)(b)31225344781930 7．由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。 （1）在此可以采用除留余数法设计散列函数，H（key）=key % 7 （2） 散列地址 关键字 比较次数 1 0 25 1 1 10 1 2 36 1 3 35 3 4 20 1 5 46 1 6 27 2 6 7 38 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其散列地址为i(0im-1)时的查找次数。在此m=10。故查找失败时的平均查找长度为： ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6 查找成功时的平均查找长度 ASLsucc=（1+1+1+3+1+1+2+6）=16/8=2 （4）int Delete（int h[n]，int k） /*从散列表h[n]中删除元素k，若删除成功返回1，否则返回0*/ { i=k%7；/*散列函数用上面（1），即H（key）=key % 7*/ if（h[i]== maxint）/*maxint解释成空地址*/ printf（“无关键字%d\\n”，k）；return （0）；} if（h[i]==k）{h[i]=-maxint ；return （1）；} /*被删元素换成最大机器数的负数*/ else /*采用线性探测再散列解决冲突*/ {j=i; for（d=1；d≤n-1；d++） {i=（j+d）%n； /*n为表长，此处为10*/ if（h[i]== maxint）return (0); /*maxint解释成空地址*/ if（h[i]==k）{ h[i]=-maxint ；return （1）；} }//for 22 } printf（“无关键字%d\\n”，k）；return (0) } 8．散列表如下图所示。 ASLsuss =(17+23+3)/11=16/11 ASLunsuss =(0+1+1+3+0+0+1+2+2+1)/11=1 值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、4、5和8均为比较1次失败，而哈希地址1、2、6和10比较2次失败，哈希地址7和9比较3次，哈希地址3比较4次。因此，查找失败时的平均查找长度为22/11。还有一种理解，认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=11/11，我们持这种观点。 9．在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。 10．操作过程如下图： 11．在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(log2n)，在中序遍历输出的序列中顺序查找关键字K，时间复杂度是O(n)；若采用折半 23 查找关键字K，则时间复杂度为O(log2n)，和在二叉排序树上查询类似。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O(n)。 12．链地址法解决冲突时，查找成功时的平均查找长度Snc1+/2，可求出装填因子为0.6。由所给关键字序列知元素个数为10，可求出表长m10/0.6，取m=17。设散列函数H(key)=(key所有位上数字之和+key)%17，构造散列表如图7-6所示。易得其查找成功时的ASL=(110)/10=1<1.3，满足要求。 012345678910111213141516ÙÙÙ 13Ù273215203ÙÙÙ18105424ÙÙÙÙÙÙÙÙÙ 三、算法设计题 1． int insertBST_Recur(BiTree &BT,ElemType e) {/*当二叉排序树BT中不存在关键字等于e.key的数据元素时，插入e对应的结点并返回1，否则返回0*/ S=(BiNode)malloc(sizeof(BiNode));/*申请新结点S，存储记录e*/ S.elem=e;S.lchild=NULL;S.rchild=NULL; if(T==NULL) {BT=S; return 1;} //插入到空树时，插入结点成为根结点 else if(S->elem.key==BT->elem.key) return 0; else if(S->elem.key int BInsert(STable ST,ElemType e) 24 { low=1;high=ST.length;find=0; while(low<=high&&find==0) { mid=(low+high)/2; if(e.key if(find) return 0;/*存在e，则不执行插入操作，返回0*/ pos=low;/*插入点为low*/ for(i=ST.length;i>pos;i--) ST.elem[i+1]=ST.elem[i]; ST.elem[pos]=e; return 1; } 3．编写算法判别给定二叉树是否为二叉排序树。 照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下： int JudgeBST（BiTree t） //判断二叉树t是否是二叉排序树，若是，返回true，否则，返回false {if（t==null）return true； if（Judgebst（t->lchild）&& Judgebst（t->rchild））//若左右子树均为二叉排序树 {m=max（t->lchild）；n=min（t->rchild）；//左子树中最大值和右子树中最小值 return （t->data>m && t->data {if（p==null） return -maxint；//返回机器最小整数 else{while（p->rchild！=null）p=p->rchild； return p->data；} } int min（BiTree p）//求二叉树右子树的最小值 {if（p==null） return maxint；//返回机器最大整数 else{while（p->lchild！=null）p=p->lchild； return p->data；} } 4．[题目分析] 因为二叉树各结点已标明了平衡因子bf，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子bf为0时，任选左右一分枝向下查找，若bf不为0，则沿左（当bf=1时）或右（当bf=-1时）向下查找。 int Height（AVLTree t） // 求平衡二叉树t的高度 25 {level=0；p=t； while（p） {level++； // 树的高度增1 if（p->bf<0）p=p->rchild；//bf=-1 沿右分枝向下 else p=p->lchild； //bf>=0 沿左分枝向下 }//while return （level）；//平衡二叉树的高度 } //算法结束 5．[题目分析] 本题未直接给出哈希表表长，但已给出装填因子小于1，且哈希函数H(k)为关键字第一个字母在字母表中的序号，字母‘A’的序号为1，表长可设为n(n27)。 void Print(HTable ht） {//按关键字第一个字母在字母表中的顺序输出各关键字 int i,j； for（i=0;i26；i++） // 哈希地址0到26 {j=1； while（ht.elem[j].key） {if（Hash(ht.elem[j].key==i） printf（ht.elem[j].key）； j=(j+1)% n； }}} 6．[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。 void HsDelete（HTable ht，KeyType k） //在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K {i=k % P； // 以造表所用的除余法计算关键字k的散列地址 if（ht.elem[i].key==null）{printf（“散列表中无被删关键字”）；exit（0）；} // 此处null代表散列表初始化时的空值 switch {case ht.elem[i].key==K：del(ht，i，i，K)；break； case ht.elem[i].key!=K：di=1；j=(i+ di)%m； // m为 表长 while（ht.elem[j].key!=null && ht.elem[j].key!=K && j!=i） // 查找关键字k {di=di+1； j=(i+di)%m； }// m为 表长 if（ht.elem[j].key ==K）del(ht，i，j，k)； else {printf(“散列表中无被删关键字”)；exit（0）;} }// switch }算法结束 26 void del（HTable ht，in i，int j，KeyType k） //在散列表ht中，删除关键字k，k的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字k的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。 {di=1；last=j；x=(j+di)% m；// 探测地址序列，last记K的最后一个同义词的位置 while（x!=i） //可能要探测一圈 {if（ht.elem[x].key ==null）break； // 探测到空位置，结束探测 else if（ht.elem[x].key %P==i）last=x；// 关键字K的同义词 di=di+1；x=(j+di) % m； // 取下一地址探测 } ht.elem[j]= ht.elem[last]; ht.elem[last]=null; //将散列地址last的记录移到哈希地址j } [算法讨论] 由于用线性探测解决冲突，可能发生“二次聚集”（两个第一哈希地址不同的记录争夺同一后继哈希地址）。象上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其它记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。 27 习 题 8 一、单选题 1.C 2.C 3.D 4.B 5.D 6.C 7.B 8.C 9.D 10.D 11.B 12.C 13.B 14.C 15.C 二、填空题 1．比较、移动 2．5 3．2、4、（23，38，15） 4．插入、选择 5．堆排序、快速排序 6．O(n2)、O(n2) 7．O(nlog2n)、O(n) 8．┌log2n┐ 9．H C Q P A M S R D F X Y P A C S Q H F X R D M Y H Q C Y A P M S D R F X F H C D P A M Q R S Y X A D C R F Q M S Y P H X10．堆排序、快速排序、归并排序、归并排序、快速排序、 堆排序 三、解答题 1．直接插入排序 2．希尔排序（增量为5, 2, 1） 28 大量实验表明，取α=0.45454的增量序列比取其他的增量序列的优越性更显著。计算 0.45454n的一个简单方法是用整数算术计算(5*n-1)/11。需要注意，当a< 1/2时，增量序列可能不以1结束，需要加以判断和调整。 3．冒泡排序 4．快速排序 29 5．直接选择排序 6．堆排序 30 7．二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。 31 8．链式基数排序 四、算法设计题 1．void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while(low change=0; for(i=low;i a[i]<->a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i] low++; //修改下界 }//while }//Bubble_Sort2 2．void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 { for(p=L;p->next->next;p=p->next) { q=p->next;x=q->data; for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if(r->next->data if(s!=q) //找到了值比q->data更小的最小结点s->next { p->next=s->next;s->next=q; t=q->next;q->next=p->next->next; p->next->next=t; } //交换q和s->next两个结点 }//for }//LinkedList_Select_Sort 3．void OE_Sort(int a[ ],int n)//奇偶交换排序的算法 { change=1; while(change) { change=0; for(i=1;i 33 { a[i]<->a[i+1]; change=1; } for(i=0;i a[i]<->a[i+1]; change=1; } }//while }//OE_Sort 分析:本算法的结束条件是连续两趟比较无交换发生 34 因篇幅问题不能全部显示，请点此查看更多更全内容