第一章 绪论
一、问答题
1. 什么是数据结构？
2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。
6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。
8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。
二、判断题（在各题后填写“√”或“×”）
1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ） 2. 算法就是程序。（ ）
3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ） 三、计算下列程序段中X=X+1的语句频度
for(i=1;i<=n;i++) for(j=1;j<=i;j++)
for(k=1;k<=j;k++) x=x+1;
【解答】
i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2 …
i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2
x=x+1的语句频度为：
f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3
区分语句频度和算法复杂度： O(f(n)) = O(n3)
四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：
（1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出 【解答】
（1）通过参数表中的参数显式传递
优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通
用性强，移置性强。
缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递
优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数
PolyValue() { int i,n;
float x,a[],p; printf(“\\nn=”); scanf(“%f”,&n); printf(“\\nx=”); scanf(“%f”,&x); for(i=0;i scanf(“%f ”,&a[i]); /*执行次数：n次 */ p=a[0]; for(i=1;i<=n;i++) { p=p+a[i]*x; /*执行次数：n次*/ x=x*x;} printf(“%f”,p); } 算法的时间复杂度：T(n)=O(n) 通过参数表中的参数显式传递 float PolyValue(float a[ ], float x, int n) { float p,s; int i; p=x; s=a[0]; for(i=1;i<=n;i++) {s=s+a[i]*p; /*执行次数:n次*/ p=p*x;} return(p); } 算法的时间复杂度：T(n)=O(n) 第二章 线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1） 在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿元素，具体移动的元 素个数与＿＿插入或删除的位置＿＿有关。 （2） 在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻 辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。 （3） 在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点 的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿其直接前趋的next域＿＿指示。 2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：＿（4）、（1）＿。 b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。 c. 在表首插入S结点的语句序列是：（5）、（12）。 d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 2.4 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。 Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 { if(va.length+1>va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2.5 写一算法，从顺序表中删除自第i个元素开始的k个元素。 [提示]：注意检查i和k的合法性。 （集体搬迁，“新房”、“旧房”） < 方法1 > 以待移动元素下标m（“旧房号”）为中心， 计算应移入位置（“新房号”）： for ( m= i－1+k; m<= L－>last; m++) L－>elem[ m－k ] = L－>elem[ m ]; < 方法2 > 同时以待移动元素下标m和应移入位置j为中心： < 方法2 > 以应移入位置j为中心，计算待移动元素下标： 2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 { p=L; while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 { q=p->next; while(q->data }//Delete_Between 2.7试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2） 以单链表作存储结构。 [方法1]:在原头结点后重新头插一遍 [方法2]:可设三个同步移动的指针p, q, r，将q的后继r改为p 2.8 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编 写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C. [提示]：参P.28 例2-1 < 方法1 > void merge(LinkList A; LinkList B; LinkList *C) { …… pa=A－>next; pb=B－>next; *C=A; (*C)－>next=NULL; while ( pa!=NULL && pb!=NULL ) { if ( pa－>data <= pb－>data ) { smaller=pa; pa=pa－>next; smaller－>next = (*C)－>next; /* 头插法 */ (*C)－>next = smaller; } else { smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; } while ( pa!=NULL) { smaller=pa; pa=pa－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; } while ( pb!=NULL) { smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C)－>next = smaller; } < 方法2 > LinkList merge(LinkList A; LinkList B) { ?? LinkList C； pa=A－>next; pb=B－>next; C=A; C－>next=NULL; ?? ?? return C; while(pa||pb) { if(pa->data pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表 } else { pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表 } pre=pc; } C=A;A->next=pc; //构造新表头 }//reverse_merge 分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。 [提示]：设指针p指向s结点的前趋的前趋，则p与s有何关系？ Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱 { p=s; while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p p->next=s; return OK; }//Delete_Pre 2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型. { s=L->next; A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B; C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点 while(s) { if(isalphabet(s->data)) { p->next=s;p=s; } else if(isdigit(s->data)) { q->next=s;q=s; } else { r->next=s;r=s; } }//while p->next=A;q->next=B;r->next=C; //完成循环链表 }//LinkList_Divide 2.11 设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得： C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时； 或者 C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。 线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。 [提示]：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B) void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 { p=A->next;q=B->next;C=A; while(p&&q) { s=p->next;p->next=q; //将B的元素插入 if(s) { t=q->next;q->next=s; //如A非空,将A的元素插入 } p=s;q=t; }//while }//merge1 2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。 [提示]：注明用头指针还是尾指针。 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B { p=L->next; A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) { if(p->data.exp!=2*(p->data.exp/2)) { pa->next=p;pa=p; } else { pb->next=p;pb=p; } p=p->next; }//while pa->next=A;pb->next=B; }//Divide_LinkedPoly 2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算 。 [提示]：可将低位放在前面。 2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。 [提示]：float PolyValue(Polylist p; float x) {……} 第三章 栈和队列 1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴ 如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 【解答】 （1）可能得到的出站车厢序列是：123、132、213、231、321。 (2)不能得到435612的出站序列。 因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为X(2)X(1)。 能得到135426的出站序列。 因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。 2. 设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执 行下列4步操作： （1） 输出队首元素； （2） 把队首元素值插入到队尾； （3） 删除队首元素； （4） 再次删除队首元素。 直到队列成为空队列为止，则是否可能得到输出序列： （1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C [提示]： A、B、C、D、E （输出队首元素A） A、B、C、D、E、A （把队首元素A插入到队尾） B、C、D、E、A （删除队首元素A） C、D、E、A （再次删除队首元素B） C、D、E、A （输出队首元素C） C、D、E、A、C （把队首元素C插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D） 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式 求值时操作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 【解答】 5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符’&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 [提示]： （1） 边读边入栈，直到& （2） 边读边出栈边比较，直到?? int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 { InitStack(s); while((e=getchar())!='&') push(s,e); while((e=getchar())!='@') { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1; }//IsReverse 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形 式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。 void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new { p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号 InitStack(s); //s为运算符栈 while(*p) { if(*p是字母)) *q++=*p; //直接输出 else { c=gettop(s); if(*p优先级比c高) push(s,*p); else { while(gettop(s)优先级不比*p低) { pop(s,c);*(q++)=c; }//while push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while }//NiBoLan //参见编译原理教材 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设 头指针），试编写相应的队列初始化、入队列和出队列的算法。 void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q { Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q; }//InitCiQueue void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素 { p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x; p->next=Q->next; //直接把p加在Q的后面 Q->next=p; Q=p; //修改尾指针 } Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x { if(Q==Q->next) return INFEASIBLE; //队列已空 p=Q->next->next; x=p->data; Q->next->next=p->next; free(p); return OK; }//DeCiQueue 8. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1 来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 [提示]： 初始状态：front==0, rear==0, tag==0 队空条件：front==rear, tag==0 队满条件：front==rear, tag==1 其它状态：front !=rear, tag==0（或1、2） 入队操作： ? ?（入队） if (front==rear) tag=1；（或直接tag=1） 出队操作： ? ?（出队） tag=0； [问题]：如何明确区分队空、队满、非空非满三种情况？ 9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0; while(!EmptyStack(S)) {n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); } 将栈S逆序。 （2）void proc_2(Stack S, int e) { Stack T; int d; InitStack(&T); while(!EmptyStack(S)) { Pop(&S, &d); if (d!=e) Push( &T, d); } while(!EmptyStack(T)) { Pop(&T, &d); Push( &S, d); } } 删除栈S中所有等于e的元素。 （3）void proc_3(Queue *Q) { Stack S; int d; InitStack(&S); while(!EmptyQueue(*Q)) { DeleteQueue(Q, &d); Push( &S, d); } while(!EmptyStack(S)) { Pop(&S, &d); EnterQueue(Q，d) } } 将队列Q逆序。 第四章 串 1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); [参考答案] StrLength(s)=14; SubString(sub1,s,1,7) sub1=’I AM A ’; SubString(sub2,s,7,1) sub2=’ ’; StrIndex(s,4,’A’)=6; StrReplace(s,’STUDENT’,q); s=’I AM A WORKER’; StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=’I AM A GOOD WORKER’。 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 StrCat(S,T)； SubString(Sub,S,pos,len)。 int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 { for(n=0,i=1;i<=S[0]-T[0]+1;i++) { for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++); if(k>T[0]) //找到了与T匹配的子串:分三种情况处理 { if(T[0]==V[0]) for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l]; else if(T[0] for(l=S[0];l>=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } else //新子串长度小于原子串时:先将后部左移 { for(l=i+V[0];l<=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if }//for return n; }//String_Replace 3. 假设以块链结构表示串，块的大小为1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。 [说明]：用单链表实现。 StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； typedef struct{ char ch; LStrNode *next; } LStrNode,*LString; //链串结构 void StringAssign(LString &s,LString t)//把串t赋值给串s { s=malloc(sizeof(LStrNode)); for(q=s,p=t->next;p;p=p->next) { r=(LStrNode*)malloc(sizeof(LStrNode)); r->ch=p->ch; q->next=r;q=r; } q->next=NULL; }//StringAssign void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在. { for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next) { p->ch=q->ch;pre=p; } while(q) { p=(LStrNode*)malloc(sizeof(LStrNode)); p->ch=q->ch; pre->next=p;pre=p; } p->next=NULL; }//StringCopy char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next); if(!p&&!q) return 0; else if(!p) return -(q->ch); else if(!q) return p->ch; else return p->ch-q->ch; }//StringCompare int StringLen(LString s)//求串s的长度(元素个数) { for(i=0,p=s->next;p;p=p->next,i++); return i; }//StringLen LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针 { p=malloc(sizeof(LStrNode)); for(q=p,r=s->next;r;r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串s for(r=t->next;r;r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for //复制串t q->next=NULL; return p; }//Concat LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串 { p=malloc(sizeof(LStrNode));q=p; for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r for(i=1;i<=len;i++,r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; } //复制串t q->next=NULL; return p; }//Sub_String 4． 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名 字和串变量的值。 char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++); if(i>s[0]&&i>t[0]) return 0; else if(i>s[0]) return -t[i]; else if(i>t[0]) return s[i]; else return s[i]-t[i]; }//StrCompare 5． 已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为 T. int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数 { for(n=0,i=0;i<=S.length-T.length;i++) { for(j=i,k=0;k if(k==T.length) //找到了与T匹配的子串:分三种情况处理 { if(T.length==V.length) for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换 S.ch[i+l-1]=V.ch[l-1]; else if(T.length for(l=S.length-1;l>=i+T.length;l--) S.ch[l+V.length-T.length]=S.ch[l]; for(l=0;l else //新子串长度小于原子串时:先将后部左移 { for(l=i+V.length;l S.length+=V.length-T.length; i+=V.length;n++; }//if }//for return n; }//HString_Replace 6． S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T 匹配的子串逆置。 7． S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及 从第k个字符删除len个字符。 以下算法用定长顺序串： 8． 写下列算法： （1） 将顺序串r中所有值为ch1的字符换成ch2的字符。 （2） 将顺序串r中所有字符按照相反的次序仍存放在r中。 （3） 从顺序串r中删除其值等于ch的所有字符。 （4） 从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5） 从顺序串r中删除所有与串r1相同的子串。 9． 写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 [提示]：（1）用静态顺序串 （2）先移位，后复制 10． 写算法，实现顺序串的基本操作StrCompare(s,t)。 11． 写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 [提示]： （1） 被替换子串定位（相当于第9题中i） （2） 被替换子串后面的字符左移或右移（为替换子串准备房间） （3） 替换子串入住（复制） （4） 重复上述，直到?? 实习题 1． 一、已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。 （1） 利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。 （2）以顺序串作为存储结构来实现。 void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r { StrAssign(r,''); for(i=1;i<=Strlen(s);i++) { StrAssign(c,SubString(s,i,1)); for(j=1;j for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中 if(k>Strlen(t)) StrAssign(r,Concat(r,c)); } }//for }//String_Subtract 第五章 数组和广义表 1． 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的 基地址为1000，计算： （1） 数组A共占用多少字节； （288） （2） 数组A的最后一个元素的地址； （1282） （3） 按行存储时，元素A36的地址； （1126） （4） 按列存储时，元素A36的地址； （1192） [注意]：本章自定义数组的下标从1开始。 2． 设有三对角矩阵（aij）n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得 B[k]= aij ，求： （1） 用i,j表示k的下标变换公式； （2） 用k表示i,j的下标变换公式。 i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或： i = k/3 + 1, j = k - 2×( k/3 ) 3. 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 { C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1; for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 { while(A.data[pa].i while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 { if(A.data[pa].j==B.data[pb].j) { ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if else if(A.data[pa].j>B.data[pb].j) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } }//while while(A.data[pa]==x) //插入A中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } while(B.data[pb]==x) //插入B中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc; }//TSMatrix_Add 4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法 只占用一个辅助向量空间。 5．写一个在十字链表中删除非零元素aij的算法。 [提示]：“删除”两次，释放一次。 6．画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 7．求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2） TAIL[((a,b),(c,d))]; （3） TAIL[HEAD[((a,b),(c,d))]]; （4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d) 实习题 若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 { for(i=0;i for(min=A[i][0],j=0;j if(A[i][j] if(A[i][j]==min) //判断这个(些)最小值是否鞍点 { for(flag=1,k=0;k printf(\ } }//for }//Get_Saddle 第六章 数和二叉树 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点？ [提示]：参考 P.116 性质3 ∵ n=n0 + n1 + …… + nk B=n1 + 2n2 + 3n3 + …… + knk n= B + 1 ∴ n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1 ∴ n0 = n2 + 2n3 + …… + (k-1)nk + 1 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 [提示]：参考 P.148 6． 已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ [提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。 7． 给出满足下列条件的所有二叉树： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 [提示]：去异存同。 a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，?。 b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。 c) D L R 与L R D 的相同点：D，如果无 L R，则完全相同。 （如果去D，则为空树） 7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ [提示]：参考 P.119 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 [提示]： （1）先画出对应的二叉树 （2）树的后根序列与对应二叉树的中序序列相同 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 （1）请为这8个字母设计哈夫曼编码， （2）求平均编码长度。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是 否可不用递归且不用栈来完成?请简述原因. [提示]：无右子的“左下端” 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 [提示]： [方法1]：（1）按先序查找；（2）超前查看子结点（3）按后序释放； void DelSubTree(BiTree *bt, DataType x) { if ( *bt != NULL && (*bt) ->data==x ) { FreeTree(*bt); *bt =NULL; } else DelTree( *bt, x) void DelTree(BiTree bt, DataType x) { if ( bt ) { if (bt->LChild && bt->LChild->data==x) { FreeTree(bt->LChild); bt->LChild=NULL; } if (bt->RChild && bt->RChild->data==x) { FreeTree(bt->RChild); bt->RChild=NULL; } DelTree(bt->LChild, x); DelTree(bt->RChild, x); } } [方法2]：（1）先序查找；（2）直接查看当前根结点（3）用指针参数； [方法3]：（1）先序查找；（2）直接查看当前根结点 （3）通过函数值，返回删除后结果； （参示例程序） 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 [提示]： （1）先查看线索，无线索时用下面规律： （2）结点*p在先序序列中的后继为其左子或右子； （3）结点*p在后序序列中的前驱也是其左子或右子。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。（参例题） 16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 [提示]： （1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。 （2）可利用返回值，或全局变量。 17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 （参课本） 19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。 [提示]：可利用任何递归、非递归遍历算法。 20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。 [提示]： [方法一]： （1）利用队列，初值为根 （2）出队访问，并将左、右子入队，直到队空 （3）记录每一层中最后一个结点在队中的位置 （4）第i层最后一个结点的右子，必是第i+1层的最后一个结点 （5）第1层最后一个结点在队中的位置为0 [方法二]：利用层号和全局数组，任意遍历、统计 21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 23. 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。 第七章 图 7.1 已知如图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 十字链表； （6） 强连通分量。 7.2 已知如图所示的无向图，请给出该图的： （1） 邻接多重表；（要求每个边结点中第一个顶点号小于第二个顶点号，且每个顶点 的各邻接边的链接顺序，为它所邻接到的顶点序号由小到大的顺序。） （2） 从顶点1开始，深度优先遍历该图所得顶点序列和边的序列；（给出深度优先搜 索树） （3） 从顶点1开始，广度优先遍历该图所得顶点序列和边的序列。（给出广度优先搜 索树） 7.3 已知如图7.31所示的AOE-网，试求： （1） 每个事件的最早发生时间和最晚发生时间； （2） 每个活动的最早开始时间和最晚开始时间； （3） 给出关键路径。 7.4 已知如图7.30所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径， 并给出算法执行过程中各步的状态。 7.5 编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf(\ if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\ if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 7.6 试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v); InsertArc(G, v, w); DeleteVertex(G,v)和DeleteArc(G, v, w)。 //本题中的图G均为有向无权图,其余情况容易由此写出 Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) { G.arcs[i][j].adj=1; G.arcnum++; } return OK; }//Insert_Arc Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v { n=G.vexnum; if((m=LocateVex(G,v))<0) return ERROR; G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i G.arcs[i][m]=G.arcs[i][n]; G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换 } G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加. Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 7.7 试对邻接表存储结构重做题6。 //为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出. Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL; if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc 7.8 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else }//exist_path_DFS 7.9 同上题要求。试基于图的广度优先搜索策略写一算法。 int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 { int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) { DeQueue(Q,u); visited[u]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j) return 1; if(!visited[k]) EnQueue(Q,k); }//for }//while return 0; }//exist_path_BFS 7.10 试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的、非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。 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); //向左走到尽头 } }//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 分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点. 7.11 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。 [提示]：利用深度搜索，增设一个深度参数，深度超过k 则停止对该结点的搜索。 int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 { if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 7.12 下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。 其中A、B、C的选择有： ① V1,V2,V3,V4,V5,V6,V7,V8 ② V1,V2,V4,V6,V5,V3,V7,V8 ③ V1,V2,V4,V6,V3,V5,V7,V8 ④ V1,V2,V4,V6,V7,V3,V5,V8 ⑤ V1,V2,V3,V8,V4,V5,V6,V7 ⑥ V1,V2,V3,V8,V4,V5,V7,V6 ⑦ V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 V1,V2,V5,V7,V8 1 6 0 v1 ④ 3 1 4 6 5 50 ∧ 3 11 ∧ 1 2 v2 v3 v4 v5 v6 v7 v8 ∧ 2 43 7 8 ∧ 4 12 ∧ 2 38 7 20 ∧ 题12图 4 1 3 4 5 6 24 ∧ 6 12 ∧ 6 7 7.13 已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 第八章 查找 8.1 若对大小均为n的有序的顺序表和无序的顺序表分别进行查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？ （1） 查找不成功，即表中没有关键字等于给定值K的记录。 （2） 查找成功，且表中只有一个关键字等于给定值K的记录。 （3） 查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出 所有记录。 [提示]：均用顺序查找法。 8.2 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查 找长度。 [提示]：根据P.191 ASL定义计算平均查找长度。 8.3 试推导含12个结点的平衡二叉树的最大深度并画出一棵这样的树。 [提示]：沿最左分支生长，前提是：其任一祖先的右分支与左分支等深，如不等深，则先生长右分支，而生长右分支的前提是：其任一祖先的左分支与右分支等深，如不等深，则先生长左分支，如此交互考虑，逐步生长，直到12个结点。 8.4 试从空树开始，画出按以下次序向2-3树，即3阶B-树中插入关键码的建树过程：20， 30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。 8.5 选取哈希函数H(k)=(3k)，用线性探测再散列法处理冲突。试在0～10的散列地址 空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时的平均查找长度。 [提示]：平均查找长度参考P.225。 0 22 1 1 2 41 1 3 30 2 4 01 2 5 53 1 6 46 1 7 13 2 8 67 6 9 10 ASLsucc = (1×4 + 2×3 + 6) / 8 = 2 ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11 8.6 试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的 平均查找长度。 （ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG，CHANG，CHAO，YANG，JIN） [提示]：（1）由装填因子求出表长，（2）可利用字母序号设计哈希函数， （3）确定解决冲突的方法。 8.7 试编写利用折半查找确定记录所在块的分块查找算法。 8.8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链表作存储结 构，且树中结点的关键字均不同。 [提示]：检验中序遍历序列是否递增有序？ [方法1]：用非递归中序遍历算法，设双指针pre, p 一旦pre->data > p->data 则返回假 [方法2]：用递归中序遍历算法，设全局指针pre，（参中序线索化算法） 一旦pre->data > p->data 则返回假 [方法3]：用递归（中序或后序）算法 （1）空树是（2）单根树是（3）左递归真（4）右递归真 （5）左子树的右端小于根（6）右子树的左端大于根 int last=0,flag=1; int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree 8.9 编写算法，求出指定结点在给定的二叉排序树中所在的层数。 8.10 编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结点A、B中，A是B的祖先，则认为A是A、B的最近公共祖先）。 [提示]： （1） 假设A<=B， （2） 从根开始，左走或右走，直到A在左（或根），B在右（或根）。 8.11 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。 [提示]：（1）表中已经有x，（2）表中没有x 参P. 231 8.12 已知长度为12的表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。 （1） 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的 二叉排序树并求其等概率的情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折 半查找时查找成功的平均查找长度。 （3） 按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率的情况下查找 成功的平均查找长度。 [提示]：画出判定树或排序树，根据P.191 ASL定义计算平均查找长度。 8.13 含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？ [提示]：叶子结点对应空指针。 8.14 写一时间复杂度为O(log2n + m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 [提示]： （1） p=root （2） 如果p->key大于、等于x，则删除p->rchild和p， （3） 左走一步，转（2） （4） 如果p->key小于x，则反复右走， （5） 转（2） （6） 直到p==NULL void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间 { if(T->rchild) Delete_NLT(T->rchild,x); if(T->data T=T->lchild; free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T) Delete_NLT(T,x); //继续在左子树中执行算法 }//Delete_NLT 8.15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中的结点数加1。编写一时间复杂度为O(log n)的算法，确定树中第k个结点的位置。 [提示]：先画图手工求。 （1）sum=0, （2）从当前根开始沿左链找sum + lsize<=k的最大结点a， （3）沿a的右链求sum=sum + lsize，直到结点b，sum + lsize(b)>=k 重复（2）、（3），直到sum=k typedef struct { int data; int bf; int lsize; //lsize域表示该结点的左子树的结点总数加1 BlcNode *lchild,*rchild; } BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型 BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针 { if(!T) return NULL; //k小于1或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k) return Locate_BlcTree(T->lchild,k); //在左子树中寻找 else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值 }//Locate_BlcTree 第九章 内部排序 9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手 工执行以下排序算法，写出（前三趟）每一趟排序结束时的关键码状态： （1）直接插入排序； （2）希尔排序（增量d[1]=5）； （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。 9.2 一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。 9.3 不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n 个元素的初始排列。 n=7时在最好情况下需进行多少次比较？请说明理由。 对n=7给出一个最好情况的初始排列实例。 （保证每个基准记录都是中间记录） 9.4 假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k< 9.5 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后 的插入排序算法。 9.6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 [提示]：（1）参快速排序（2）“水底”、“水面”相遇时结束。 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] a[i]<->a[i-1]; change=1; } low++; //修改下界 }//while }//Bubble_Sort2 9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： 采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度O(n)； 讨论算法中记录的最大移动次数。 [提示]：r[0]=r[1]，以0为分界值，参快速排序划分过程，但不要求对元素排序。 void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前 { low=0;high=n-1; while(low while(low while(low a[low]<->a[high]; } }//Divide 9.8试以单链表为存储结构实现简单选择排序的算法 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 x=r->next->data; s=r; } 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 9.9假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。 void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序 { int number[w+1],pos[w+1]; for(i=0;i pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置 for(i=0;i 分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用. 9.10 已知两个有序序列(a1, a2 ,..., am)和(am+1 , am+2 ,..., an),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。 void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列 { start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;i for(j=start2;j RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位 start1+=k+1; start2=j; //修改两序列尚未归并部分的起始位置 } }//SL_Merge void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18 { len=end-start+1; for(i=1;i<=k;i++) if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p for(i=0;i j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) { a[j]=temp; temp=a[l]; a[l]=a[j]; j=l;l=start+(j-start+k)%len; //依次向右移 } a[start+i]=temp; }//for }//RSh 9.11 偶交换排序如下所述：第一趟对所有奇数i,将a[i]和a[i+1]进行比较；第二趟对所有偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1],则将两者交换；第一趟对所有奇数i, 第二趟对所有偶数i，…,依次类推直至整个序列有序为止。 （1） 这种排序方法的结束条件是什么？ （2） 分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关 键字比较的次数。 （3） 写出奇偶交换排序的算法。 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 x=r->next->data; s=r; } 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 9.12 设计一个用链表表示的直接选择排序算法。（与9.8重） 9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。 （与9.5重复） 9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。 （与9.7类似） 9.15 为什么通常使用一维数组作为堆的存放形式？ 9.16 已知（k1,k2,?，kn）是堆，写一个算法将（k1,k2,?，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。 void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 { for(i=2;i { //此时从H.r[1]到H.r[i-1]已经是大顶堆 j=i; while(j!=1) //把H.r[i]插入 { k=j/2; if(H.r[j].key>H.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for }//Build_Heap 9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。 9.18 在供选择的答案中填入正确答案： 1）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_。 供选择答案 ① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序 ⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79 3）、下列排序算法中， C 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序 9.19 判断正误： （ ）在一个大堆中，最小元素不一定在最后。 （ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。 （ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。