当前位置:首页 >> 理学 >>

数据结构实用教程 第二版 徐孝凯 课后答案


第一章绪习 题 一
一、单选题 1.一个数组元数a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 2.对于两个函数,若函数名相同,但只是( C) 不同则不是重载函数。 A 参数类型 B 参数个数 C 函数类型 3.若需要利用形参直接访问实参,则应把形参变量说明为 (B) 参数。 A 指针 B 引用 C 值 4.下面程序段的复杂度为 (C )。 for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=i*j; A O(m2) B O(n2) C O(m*n) D O(m+n) 5.执行下面程序段时,执行S语句的次数为 (D )。 for(int i=1;i<=n;i++) for(int j=1; j<=i;j++) S; A n2 B n2/2 C n(n+1) D n(n+1)/2 6.下面算法的时间复杂度为( B) 。 int f(unsigned int n){ if(n==0||n==1) return 1; Else return n*f(n-1); } A O(1) B O(n) C O(n2) D O(n!) 二、填空题 1.数据的逻辑结构被除数分为 集合结构 、 线性结构 、 树型结构 和 图形结构 四种。 2.数据的存储结构被分为 顺序结构 、 链接结构 、 索引结构 和 散列结构 四种。 3.在线性结构、树型结构和图形结构中,前驱和后继结点之间分别存在着 1对1 、 1对N 和 M对N 的关系。 4.一种抽象数据类型包括 数据 和 操作 两个部分。 5.当一个形参类型的长度较大时,应最好说明为 引用 ,以节省参数值的传输时间和存储参数的空间。 6.当需要用一个形参访问对应的实参时,则该形参应说明为 引用 。 7.在函数中对引用形参的修改就是对相应 实参 的修改,对 值(或赋值)形参的修改只局限在该 函数的内部,不会反映到对应的实参上。

8.当需要进行标准I/O操作时,则应在程序文件中包含 iostream.h 头文件,当需要进行文件I/O操作时, 则应在程序文件中包含 fstream.h 头文件。 9.在包含有 stdlib.h 头文件的程序文件中,使用 rand()%21 能够产生0-20之间的一个随机数。 10.一个记录r理论上占有的存储空间的大小等于所有域的 长度之和 ,实际上占有的存储空间的大小即 记录长度为 sizeof(r) 。 11.一个数组a所占有的存储空间的大小即数组长度为 sizeof(a) ,下标为i的元数a[i]的存储地址为 a+1 , 或者为 (char*)a+i*sizeof(a[i]) 。 12.函数重载要求 参数类型 、 参数个数 或 排列顺序 有所不同。 13.对于双目操作符,其重载函数带有 2 个参数,其中至少有一个为 用户自定义 的类型。 14.若对象ra和rb中至少有一个属于用户定义的类型,则执行ra==rb时,需要调用 等于 号(==) 重载函数,该函数第一个参数应与 ra ,的类型相同,第二个参数应与 rb 的类型相同。 15.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为 O(n) ,输出一个二维 数组b[m][n]中所有元素值的时间复杂度为 O(m*n) 。 16.在下面程序段中,s=s+p语句的执行次数为 n ,p*=j语句的执行次数为n(n+1)/2,该 程序段的时间复杂度为 O(n2) 。 int i=0,s=0; while(++i<=n){ int p=1; for(int j=1;j<=i;j++) P*=j; s=s+p; } 17.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为 O(n) 。 18.从一个数组a[7]中顺序查找元素时,假定查找第一个元素a[0]的概率为1/3,查找第二 个元素a[1]的概率为1/4,查找其余元素的概率均相同,则在查找成功时同元素的平均比 较次数为 35/12 。 三、普通题 1.有下列几种用二元组表示的数据结构,试画出它们分别对应的图形表示(当出现多个关系时, 对每个关系画出相应的结构图),并指出它们分别属于何种结构。 ⑴ A=(K,R)其中 K={a1,a2,a3...,an} R={} ⑵ B=(K,R)其中

K={a,b,c,d,e,f,g,h} R={r} r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>} ⑶ C=(K,R)其中 K={a,b,c,d,f,g,h} R={r} r={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>} ⑷ D=(K,R)其中 K={1,2,3,4,5,6} R={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} ⑸ E=(K,R)其中 K={48,25,64,57,82,36,75,43} R={r1,r2,r3} r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>} r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>} r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>} 解:⑴是集合结构;⑵是线性结构;⑶⑷是树型结构;⑸散列结构。只作为参考。 2.设计二次多项式ax2+bx+c的一种抽象数据类型,假定起名为QIAdratic, 该类型的数据部分分为三个系数项a、b和c,操作部分为:(请写出下面每一个 操作的具体实现)。 ⑴ 初始化数据成员ab和c(假定用记录类型Quadratie定义成员),每个数据成 员的默认值为0。 Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0); 解: Quadratic InitQuadratic(float aa,float bb,float cc) { Quadratic q; q.a=aa; q.b=bb; q.c=cc; return q; } ⑵ 做两个多项式加法,即使对应的系数相加,并返回相加的结果。 Quadratic Add(Quadratic q1,Quadratic q2); 解: Quadratic Add(Quadratic q1,Quadratic q2); { Quadratic q; q.a=q1.a+q2.a; q.b=q1.b+q2.b; q.c=q1.c+q2.c;

return q; } ⑶ 根据给定x的值计算多项式的值。 float Eval(Quadratic q,float x); 解: float Eval(Quadratic q,float x) { return(q.a*x*x+q.b*x+q.c); } ⑷ 计算方程ax2+bx+c=0的两个实数根,对于有实根、无实根和不是实根方程 (即a==0)这三种情况要返回不同的整数值,以便于工作调用函数做不同的处理。 int Root(Quadratic q,float& r1,float& r2); 解: int Root(Quadratic q,float& r1,float& r2) { if(q.a==0)return -1; float x=q.b*q.b-4*q.a*q.c; if(x>=0){ r1=(float)(-q.b+sqrt(x))/(2*q.a); r2=(float)(-q.b-sqrt(x))/(2*q.a); return 1; } else return 0; } ⑸ 按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式,在输出时要注意 去掉系数为0的项,并且当b和c的值为负时,其前不能出现加号。 void Print(Quadratic q) 解: void Print(Quadratic q) { if(q.a) cout<<q.a<<"x**2"; if(q.b) if(q.b>0) cout<<"+"<<q.b<<"x"; else cout<<q.b<<"x"; if(q.c) if(q.c>0) cout<<"+"<<q.c; else cout<<q.c; cout<<end1; }

3.用c++函数描述下列每一个算法,并分别求出它们的时间复杂度。 ⑴ 比较同一简单类型的两个数据x1和x2的大小,对于x1>x2,x1=x2和x1<x2这三种不同 情况分别返回'>''='和'<'字符。假定简单类型用SimpleType表示,它可通过typedef 语句定义为任一简单类型。 解: char compare(SimpleType x1,SimpleType x2) { if(x1>x2) return'>'; else if(x1==x2) return '='; else return'<'; } 其时间复杂度为O(1) ⑵ 将一个字符串中的所有字符按相反方的次序重新放置。 解: void Reverse(char*p) { int n=strlen(p); for(int i=0;i<n/2;i++){ char ch; ch=p[i] p[i]=p[n-i-1]; p[n-i-1]=ch; } } 其时间复杂度为O(n) ⑶ 求一维double型数组a[n]中的所有元素之乘积。 解: double product(double a[],int n) { double p=1; for(int i=0;i<n;i++) p*=a[i]; return p; } 其时间复杂度为O(n) ⑷ 计算∑ni=0xi/i+1的值。 解: double Accumulate(double x,int n) { double p=1,s=1; for(int i=1;i<=n;i++){ p*=x; s+=p/(i+1);

} return s; } 其时间复杂度为O(n) ⑸ 假定一维数组a[n]中的每个元素值均在[0,200]区间内,分别统计出落在[0,20) ,[20,50),[50,80),[80,130),[130,200]等各区间的元素个数。 解: int Count(int a[],int n,int c[5])//用数组c[5]保存统计结果 { int d[5]={20,50,80,130,201};//用来保存各统计区间的上限 int i,j; for(i=0;i<5;i++)c[i]=0;//给数组c[5]中的每个元素赋初值0 for(i=0;i<n;i++) { if(a[i]<0||a[i]>200) return 0;//返回数值0表示数组中数据有错,统计失败 for(j=0;j<5;j++)//查找a[i]所在区间 if(a[i]<d[j]) break; c[j]++;//使统计相应区间的元素增1 } return 1;//返回数值1表示统计成功 } 其时间复杂度为O(n) ⑹ 从二维整型数组a[m][n]中查找出最大元素所在的行、列下标。 解: void find(int a[M][N],int m,int n,int&Lin,int&Col) //M和N为全局常量,应满足M>=n和N>=n的条件,Lin和Col为引用 //形参,它是对应实参的别名,其值由实参带回 { Lin=0;Col=0; for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(a[i][j]>a[Lin][Col]){Lin=i;Col=j;} } 其时间复杂度为O(m*n) 4.指出下列各算法的功能并求出其时间复杂度。 ⑴ int prime(int n) { int i=2; int x=(int)sqrt(n); while(i<=x){ if(n%i==0)break; i++; }

if(i>x) return 1; else return 0; } 解: 判断n是否是一个素数,若是则返回数值1,否则返回0。该算法的时间复杂度为 O(n1/2)。 ⑵ int sum1(int n) { int p=1,s=0; for(int i=1;i<=n;i++){ p*=i; s+=p; } return s; } 解: 计算∑i!(上标为n,下标为i=1)的值,其时间的复杂度为O(n)。 ⑶ int sum2(int n) { int s=0; for(int i=1;i<=n;i++){ int p=1; for(int j=1;j<=i;j++) p*=j; s+=p; } return s; } 解: 计算∑i!的值,时间复杂度为O(n2) ⑷ int fun(int n) { int i=1,s=1; while(s<n) s+=++i; return i; } 解: 求出满足不等式1+2+3...+i≥n的最小i值, 其时间复杂度为O(n1/2)。 ⑸ void UseFile(ifstream& inp,int c[10]) //假定inp所对应的文件中保存有n个整数

{ for(int i=0;i<10;i++) c[i]=0; int x; while(inp>>x){ i=x%10; c[i]++; } } 解: 利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个 数,时间复杂度为O(n) ⑹ void mtable(int n) { for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++) cout<<i<<"*"<<j<<"=" <<setw(2)<<i*j<<""; cout<<end1; } } 解: 打印出一个具有n行的乘法表,第i行(1≤i≤n)中有n-i+1个乘法项,每个乘法项为i与j( i≤j≤n)的乘积,时间复杂度为O(n2)。 ⑺ void cmatrix(int a[M][N],int d) //M和N为全局整型常量 { for(int i=0;i<M;i++) for(int j=0;j<N;j++) a[i][j]*=d; } 解: 使数组a[M][N]中的每一个元素均详细以d的值,时间复杂度为O(M*N) ⑻ void matrimult(int a[M][N],int b[N][L],int c[M][L]) // { int i,j,k; for(i=0;i<M;i++) for(j=0;j<L;j++) c[i][j]=0; for(i=0;i<M;i++) for(j=0;j<L;j++) for(k=0;k<N;k++) c[i][j]+=a[i][k]*b[k][j];

} 解: 矩阵相乘,即a[M][N]×b[N][L]→c[M][L],时间复杂度为O(M×N×L)。 5.题目略 ⑴解: void InitSet(Set& s) { for(int i=1;i<=SETSIZE;i++) s.m[i]=0; }

⑵解:void InitSet(Set& s,int a[],int n) { fot(int i=0;i<n;i++) s.m[a[i]]=1; } ⑶解: Set operator + (Set s1,Set s2) { Set s; InitSet(s); for(int i=1;i<=SETSIZE;i++) if((s1.m[i]==1)||s2.m[i]===1)) s.m[i]=1; return s; } ⑷解: Set operator*(Set s1,Set s2) { Set s; InitSet(s); for(int i=1;i<=SETSIZE;i++) if((s1.m[i]==1)&&(s2.m[i]==1)) s.m[i]=1; return s; ⑸解: Boolean operator^(int elt,Set s) { if(s.m[elt]==1) return True; else

return False; } ⑹解: void Inisert(Set& s,int n) { s.m[n]=1; } ⑺解: void Delete(Set& s,int n) { s.m[n]=0; } ⑻解: ostream& operator<<(ostream& ostr,Set& s) { ostr<<'{' for(int i=1;i<=SETSIZE;i++) if(s.m[i]==1) ostr<<i<<','; ostr<<'}'<<end1; return ostr; }

类别:数据结构

习题二 一、单选题 1.在一个长度为n的顺序存储的线性表中,向第i个元素(1≤i≤n+1)之前插入一个新元素时, 需要从年向前依次移 B 个元素。 A n-i B n-i+1 C n-i-1 D i 2.在一个长度为n的顺序存储的线性表中,删除第i个元素(1≤i≤n+1)时,需要从前向后依次 前移 A 个元素。 3.在一个长度为n的线性表中顺序查找值为x的元素时,查找成功的平均查找长度(即x同元素 的平均比较次数,假定查找每个元素的概率都相等)为 C 。 A n B n/2 C (n+1)/2 D (n-1)/2 4.在一个单链表HL中,若要向表头插入一个自由指针p指向的结点,则执行 B 。 A HL=p;p->next=HL; B p=next=HL; HL=p; C p->next=HL; p=HL; D p->next=HL->next;HL->next=p; 5.在一个单链表HL中,若要在指针q所指结点的后面插入一个自由指针p所指向的结点,则执行 D。 A q->next=p->next;p->next=q; B p->next=q->next;q=p; C q->next=p->next;p->next=q D p->next=q->next;q->next=p; 6.在一个单链表HL中,若要删除由指针q所指向结点的后继结点,则执行 C 。 A p=q->next;p->next=q->next; B p=q->next;q->next=p; C p=q->next;q->next;q->next=q; D q->next=q=->Next->next;q->next=q; 二、填空题 1.在线性表的单链接存储结构中,每个结点包含有两个域,一个叫 值 ,另一个叫 指针 域。 2.在下面数组a中链接存储着一个线性表,表头指针为a[0].next,则该线性表为 (38,56,25, 60,42,74) 。 a 012345678 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 3.对于一个长度为l的顺序存储的线性表,在表头插入元素的时间复杂度帾 o(n) ,在表尾插 入元素的时间复杂度为 O(1) 。 4.对于一个单链接存储的线性表,在表头插入结点祫时话里有话复杂度为 o(1) ,在表尾插入 元素的时间复杂度为 o(n) 。 5.在线性表的顺序存储中,若一个元素的下标为i,则它的前驱元素的下标为 i-1 ,后继元素 的下标为 i+1 。

6.在线性表的单链接存储中,若一个元素所在结点的地址为p,则后继结点的地址为 p->next , 若假定p为一个数组a中的下标,则其后继结点的下标为 a[p].next 。 7.在循环单链接表中,最后一个结点的指针域指向 表头 结点。 8.在双向链接表中每个结点包含有两个针域,一个指向其 前驱 结点,另一个指向其 后继 结点。 9.在循环双向链接表中表头结点的左指针域指向 表尾 结点,最后一个结点的右指针域指 向 表头 结点。 10.在以HL为表头指针的带表头附加结点的单链接表中,链表为空的条件分别为 HL->next==NULL HL->next==HL 。 11.在由数组a中元素结点构成的单链表中,删除下标为i的结点后,需要把该结点插入到空闲表的 表头,具体操作为 a[i].next=a[1].next;a[1].next=i; 。 12.在由数组a中元素结点构成的单链表中,在插入下标为i的结点后,需要从空闲表头中删除一个 结点,并将该结点下标赋给i,具体操作为 i=a[1].next;a[1].next=a[i].next; 。 13.在由数组a中元素结点构成的单链表中,删除下标为i的后继结点并将被删除结点的下标赋给i时 ,所进行的操作描述为 p=a[i].next;a[i].next=a[p].next;i=p; 。 14.在由数组a中元素结点构成的单链表中,在下标为i的结点的后面插入一个下标为j的结点时,需 要进行的操作为 a[j].next=a[i].next;a[i].next=j; 。 三、普通题 1. ⑴解:(79,62,34,57,26,48) ⑵解:(26,34,48,57,62,79) ⑶解:(48,56,57,62,79,34) ⑷解:(56,57,79,34) ⑸解:(26,34,39,48,57,62) 2. 解:

为了排版方便,假定采用以下输出格式表示单链接表的示意图;每个括号内的数据表示一个元 素结点,其中第一个数据为元素值,第二个数据为后继结点的指针,第一个元素结点前的数值为 表头指针。 ⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)) ⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)) ⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)) ⒋(8(56,4),(57,7),(79,5),(34,0)) 3.对于List类型的线性表,编写出下列每个算法。 ⑴ 从线性表中删除具有最小值的元素并由函数返回,空出的位置由最后一个元素填补,若 线性表为空则显示出错信息并退出运行。 解: ElemType DMValue(List&L) //从线性表中删除具有最小值的元素并由函数返回,空出的位置 //由最后一个元素填补,若线性表为空则显示出错信息并退出运行 { if(ListEmpty(L)){ cerr<<"List is Empty!"<<end1; exit(1); } ElemType x; x=L.list[0]; int k=0; for(int i=1;i<L.size;i++){ ElemType y=L.list[i]; if(y<x){x=y;k=i;} } L.list[k]=L.list[L.size-1]; L.size--; return x; } ⑵ 从线性表中删除第i个元素并由函数返回。 解:int Deletel(List& L,int i) //从线性表中删除第i个元素并由函数返回 { if(i<1||i>L.size){ cerr<<"Index is out range!"<<end1; exit(1); } ElemType x; x=L.list[i-1]; for(int j=i-1;j<L.size-1;j++) L.list[j]=L.list[j+1]; L.size--;

return x; } ⑶ 向线性表中第i个元素位置插入一个元素。 解:void Inser1(List& L,int i,ElemType x) //向线性表中第i个元素位置插入一个元素 { if(i<1||i>L.size+1){ cerr<<"Index is out range!"<<end1; exit(1); } if(L.size==MaxSize) { cerr<<"List overflow!"<<end1; exit(1); } for(int j=L.size-1;j>i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; } ⑷ 从线性表中删除具有给定值x的所有元素。 解:void Delete2(List& L,ElemType x) //从线性表中删除具有给定值x的所有元素 { int i=0; while(i<L.size) if(L.list[i]==x){ for(int j=i+1;j<L.sizr;j++) L.list[j-1]=L.list[j]; L.size--; } else i++; } ⑸ 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 解:void Delete3(List& L,ElemType s,ElemType t) //从线性表中删除其值在给定值s和t之间的所有元素 { int i=0; while(i<L.size)

if((L.list[i]>=s)&&(L.list[i]<=t)){ for(int j=i+1;j<L.size;j++) L.list[j-i]=L.list[j]; L.size--; } else i++; } ⑹ 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 解:void Delete4(List& L,ElemType s,ElemType t) //从有序表中删除其值在给定值s和t之间的所有元素 { int i=0; while(i<L.size)//从有序表L中查找出大于等于s的第一个元素 if(L.list[i]<s)i++; else break; if(i<L.size){ While((i+j<L.size)&&(L.list[i+j]<=t)) j++;//求出s和t之间元素的个数 for(int k=i+j;k<L.size;k++) L.list[k-j]=L.list[k]; L.size-=j; } } ⑺ 将两个有序表合并成一个新的有序表并由变量返回。 解:void Merge(List& L1,List& L2,List& L3) //将两个有序表合并成一个新的有序表并由变量返回 { if(L1.size+L2.size>MaxSize){ cerr<<"List overflow!"<<end1; exit(1); } int i=0,j=0,k=0; while((i<L1.size)&&(j<L2.size)){ if(L1.list[i]<=L2.list[j]) { //将L1中的元素赋给L L.list[k]=L1.list[i]; i++; } else{ //将L2中的元素赋给L L.list[k]=L2.list[j]; j++;

} k++; } while(i<L1.size){ //将L1中剩余的元素赋给L L.list[k]=L1.list[i]; i++;k++; } while(j<L2.size){ //将L2中剩余的元素赋给L L.list[k]=L2.list[j]; j++;k++; } L.size=k; } ⑻ 从线性表中删除所有其值重复的元素,使其所有元素的值均不同,如对于线性表(2,8,9, 2,5,5,6,8,7,2),则执行此算法后变为(2,8,9,5,6,7)。 解:void Delete5(List& L) //从线性表中删除所有其值重复的元素,使其所有元素的值均不同 { int i=0; while(i<L.size){ int j=i+1; while(j<L.size) { //删除重复值为L.list[i]的所有元素 if(L.list[j]==L.list[i]){ for(int k=j+1;k<L.size;k++) L.list[k-1]=L.list[k]; L.size--; } else j++; } i++; } } 4.对于结点类型为LNode的单链接表,编写出下列每个算法。 ⑴ 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则 逆序链接后变为an,an-1,...a1。 解:void Contrary(LNode*&HL) //将一个单多办实事有按逆序链接 { LNode*p=HL;//p指向待逆序的第一个结点,初始指向原表头结点 HL=NULL;//HL仍为逆序后的表头指针,禄始值为空

while(p!=NULL) { //把原单链表中的结点依次进行逆序链接 LNode*q=p; //q指向待处理的结点 p=p->next; //p指向下一个待逆序的结点 //将q结点插入到已陈序单链表的表头 q->next=HL; HL=q; } } ⑵ 删除单链表中的第i个结点。 解:void Delete1(LNode*&HL,int i) //删除单链表中的第i个结点 { if(i<1||HL==NULL){ cerr<<"Index is out range!"<<end1; exit(1); } LNode*ap,*cp; ap=NULL;cp=HL; //cp指向当前结点,ap指向其前驱结点 int j=1; while(cp!=NULL) if(j==i) break; //cp结点即为第i个结点 else{ //继续向后寻找 ap=cp; cp=cp->next; j++; } if(cp==NULL){ cerr<<"Index is out range!"<<end1; exit(1); } if(ap==NULL) HL=HL->next; else ap->next=cp->next; delete cp; } ⑶ 从单链表中查找出所有元素的最大值,该值由函数返回,若单链表为空,则显示出错信息 并停止运行。 解:ElemType MaxValue(LNode*HL) //从单链表中查找出所有元素的最大值,该值由函数返回

{ if(HL==NULL){ cerr<<"Linked list is empty!"<<end1; exit(1); } ElemType max=HL->data; LNode*p=HL->next; while(p!=NULL){ if(max<p->data) max=p->data; p=p->next; } return max; } ⑷ 统计出单链表中结点的值等于给定值x的结点数。 解:int Count(LNode*HL,ElemType x) //统计出单链表中结点的值等于给定值x的结点数 { int n=0; while(HL!=NULL){ if(HL->data==x) n++; HL=HL->next; } return n; } ⑸ 根据一维数组a[n]建立一个单链表,使单链表中元素的次序与a[n]中元素的次序相同, 并使该算法的时间复杂度为O(n)。 解:void Create(LNode*&HL,ElemType a[],int n) //根据一维数组a[n]建立一个单链表 { InitList(HL); for(int i=n-1;i>=0;i--) InsertFront(HL,a[i]; } ⑹ 将一个单链表重新链接成有序单链表。 解:void OrderList(LNode*&HL) //将一个单链表重新链接成有序单链表 { LNode* p=HL;//p指向待处理的第一个结点,初始指向原表头结点 HL=NULL; //HL仍为待建立的有序表的表头指针,禄始值为空 while(p!=NULL) { //把原单链表中的结点依次进行有序链接

LNode* q=p; //q指向待处理的结点 p=p->next; //p指向下一个待处理的结点 LNode* ap=NULL,*cp=HL; //cp指向有序表中待比较的结点,ap指向其前驱结点 while(cp!=NULL) { //为插入q结点寻找插入位置 if(q->data<cp->data) break; else{ ap=cp; cp=cp->next; } } //将q结点插入到ap和cpxf hko pp uj q->next=cp; if(ap==NULL) HL=q; else ap->next=q; } } ⑺ 将两个有序单链表合并成一个有序单链表,合并后使原有单链表为空。 解:LNode*Mergel(LNode*&p1,LNode*&p2) //将两个有序单链表合并成一个有序单链表 { LNode a; //a结点作为结果的有序单链表的表头附加结点,这样便于处理,处理 //结束后返回a结点的镄针域的值 LNode*p=&a; //p指向结果的有序单链表的表尾结点 p->next=NULL;//初始指向表头附加结点 while((p1!=NULL)&&(p2!=NULL)) {//处理两个表非空的情况 if(p1->data<p2->data){ p->next=p1;p1=p1->next; } else{ p->next=p2;p2=p2->; } p=p->next; } if(p1!=NULL)p->next=p1; if(p2!=NULL)p->next=p2; p1=p2=NULL; return a.next; }

⑻ 根据两个有序单链表生成一个新的有序单链表,原有单链表保持不变。如假定两个有序单链 表中的元素为(2,8,10,20)和(3,8,9,15,16),则生成的新单链表中的元素为(2,3,8,8,9,10,15, 16,20)。 解:LNode*Merge2(LNode*p1,LNode*p2) //根据两个有序单链表生成一个新的有序单链表 { LNode a; //用a作为新的有序单链表的表头附加结点 LNode*p=&a; //p指向结果有序单链表的表尾结点 p->next=NULL; //初始指向表头附加结点 while((p1!=NULL&&(p2!=NULL)) { //处理两个表非空时的情况 LNode*newptr=new LNode; if(p1->data<p2->data) { //由p1->data建立新结点,然后p1指针后移 newptr->data=p1->data; p1=p1->next; } else { //由p2->data建立新结点,然后p2指针后移 newptr->data=p2->data; p2=p2->next; } //将newptr结点插入到结果的有序表的表尾 p->next=newptr; p=newptr; } while(p1!=NULL) { //继续处理p1单链表中剩余的结点 LNode*newptr=new LNode; newptr->data=p1->data; p1=p1->next; p->next=newptr; p=newptr; } while(p2!=NULL) { //继续处理p2单链表中剩余的结点 LNode*newptr=new LNode; newptr->data=p2->data; p2=p2->next; p->next=newptr; p=newptr; } p->next=NULL;

return a.next; } ⑼ 根据一个元素类型为整型的单链表生成两个单链表,使得第一个单链表中包含原单链表中所有 元素值为奇数的结点,使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表 保持不变。 解:void Separate(LNode*HL,LNode*&p1,LNode*&p2) //根据一个单链表HL按条件拆分生成两个单链表p1和p2 { LNode a,b; //a和b结点分别作为p1和p2单链表的表头附加结点 LNode*t1=&a,*t2=&b; //t1和t2分别作为指向p1和p2单链表的 //表尾结点,初始指向表头附加结点 Lnode*p=HL; while(p!=NULL) { //每循环一次产生一个新结点,并把它加入到p1或p2单链表 //的未尾 LNode*newptr=new LNode; if(p->data%2==1){ newptr->data=p->data; t1->next=newptr; t1=newptr; } else{ newptr->data=p->data; t2->next=newptr; t2=newptr; } p=p->next; } t1->next=t2->next=NULL; p1=a.next;p2=b.next; //把指向两个单链表的表头结点的指针分别赋给 //p1和p2返回 } 6.编写一个算法,使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是 :设有n个人围坐在一张圆桌周围,现从某个人开始从1报数,数到m的人出列(即离开坐位, 不参加以后的报数),接着从出列的下一个人开始重新从1报数,数到m的人又出列,如此下 去直到所有人都出列为止,试求出它们的出列次序。 假如,当n=8、m=4时,若从第一个人(假定每个人的编号依次为1,2...,n)开始报数,则得 到的出列次序为:4,8,5,2,1,3,7,6。 此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。 解: void Josephus(int n,int m,int s) //使用带表头附加结点的循环单链表解决约瑟夫问题

{ //生成表头附加结点,此时循环单链表为空 LNode*HL=new LNode; HL->next=HL; int i; //生成含有n个结点、结点依次为1,2,...n的带表头结点的循环单链表 for(i=n;i>=1;i--){ //生成新的结点 LNode*newptr=new LNode; newptr->data=i; //把新的结点插入到表头 newptr->next=HL->next; HL->next=newptr; } //从表头开始顺序查找出第s个结点,对应第一个开始报数的人 LNode*ap=HL,*cp=HL->next; for(i=1;i<s;i++){ //ap和cp指针后移一个位置 ap=cp; cp=cp->next; //若cp指向了表头附加结点,则仍需后移ap和cp指针,使之指向表头结点 if(cp==HL){ap=HL;cp=HL->next;} } //依次使n-1个人出列 for(i=1;i<n;i++){ //顺序查找出待出列的人,即为循环结束后cp所指向的结点 for(int j=1;j<m;j++){ ap=cp; cp=cp->next; if(cp==HL){ap=HL;cp=HL->next;} } //输出cp结点的值,即出列的人 cout<<cp->data<<""; //从单链表中删除cp结点 ap->next=cp->next; delete cp; //使cp指向被删除结点的后继结点 cp=ap->next; //若cp指向了表头附加结点,则后移ap和cp指针 if(cp==HL){ap=HL;cp=HL->next;} } //使最后一个人出列 cout<<HL->next->data<<end1; //删除表头结点和表头附加结点

delete HL->next; delete HL; } 7.对于在线性表抽象数据类型中定义的每一个操作,写出结点类型为LNode的带头附加结点 的循环单链表上实现的对应算法。 ⑴初始化单链表 解:void InitList(LNode*HL) { HL->next=HL;//将单链表置空 } ⑵删除单链表中的所有结点,使之成为一个空表 void ClearList(LNode*HL) { LNode*cp,*np; cp=HL->next;//将指向第一个结点的指针赋给cp while(cp!=HL)//遍历单链表,向系统交回每一个结点。 { np=cp->next;//保存下一个结点的指针。 delete cp;//删除当前结点。 cp=np;//使下一个结点成为当前结点。 } HL->next=HL;//置单链表为空 } ⑶得到单链表的长度 int ListSize(LNode*HL) { LNode*p=HL->next; int i=0; while(p!=HL){i++;p=p->next;} return i; } ⑷检查单链表是否为空 int ListEmpty(LNode*hl) { return(HL->next==HL); } ⑸得到单链表中第pos个结点中的元素 ElemType GetElem(LNode*HL,int pos) {

if(pos<1){ cerr<<"pos is out range!"<<end1; exit(1); } LNode* p=HL->next; int i=0; while(p!=HL){ i++; if(i==pos)break; p=p->next; } if(p!=HL)return p->data; else{ cerr<<"pos is out range!"<<end1; exit(1); } } ⑹遍历单链表 void TraverseList(LNode*HL) { LNode* p=HL->next; while(p!=HL){ cout<<p->data<<""; p=p->next; } cout<<end1; } ⑺从单链表查找具有给定值的第一个元素 int Find(LNode* HL,ElemType& item) { LNode* p=HL->next; while(p!=HL) if(p->data==item){ item=p->data; return 1; } else p=p->next; return 0; } ⑻更新单链表中具有给定值的第一个元素

int Updata(LNode* HL,const ElemType& item) { LNode* p=HL->next; while(p!=HL)//查找元素 if(p->data==item)break; else p=p->next; if(p==HL)return 0; else{//更新元素 p->data=item; return 1; } } ⑼向单链表的未尾插入一个元素 void InsertRear(LNode* HL,const ElemType& item) { LNode* newptr; newptr=new LNode; newptr->data=item;//把新元素赋给动态结点*newptr的值域。 LNode* p=HL; while(p->next!=HL)//从表头开始遍历到最后一个结点为止。 p=p->next; newptr->next=HL;p->next=newptr;//把新结点链接到表尾。 } ⑽向单链表的表头插入一个元素 void InsertFront(LNode* HL,const ElemType& item) { LNode* newptr; newptr=new LNode; newptr->data=item; newptr->next=HL->next; HL->next=newptr; } (11)向单链表中插入一个元素 void Insert(LNode* HL,const ElemType& item) { LNode* newptr; newptr=new LNode; newptr->data=item; LNode *ap,*cp; ap=HL;cp=HL->next; while(cp!=HL)

if(item<cp->data)break; else{ap=cp;cp=cp->next;} newptr->next=cp; ap->next=newptr; } (12)从单链表中删除表头元素 ElemType DeleteFront(LNode* HL) { if(HL->next==HL){ cerr<<"Deleteing from an empty list!"<<end1; exit(1); } LNode* p=HL->next; HL->next=p->next; ElemType temp=p->data; delete p; return temp; } (13)从单链表中删除等于给定值的第一个元素 int Delete(LNode* HL,const ElemType& item) { LNode*ap=HL,*cp=HL->next; while(cp!=HL) if(cp->data==item)break; else{ap=cp;cp=cp->next;} if(cp==HL){ cerr<<"Deleted element is not exitst!"<<end1; return 0; } else{ ap->next=cp->next; delete cp; return 1; } } (14)利用单链表进行数据排序 void LinkSort(ElemType a[],int n) { LNode* head=new LNode; InitList(head); int i;

for(i=0;i<n;i++) Insert(head.a[i]); LNode* p=head->next; i=0; while(p!=head){ a[i++]=p->data; p=p->next; } ClearList(head); delete head; } *8.对于结点类型为DNode的双向链表,编写出下列每一个算法。 ⑴向双向链表的未尾插入一个值为x的结点。 解:void InsertRear(DNode*&DL,ElemType x) { //建立值为x的结点 DNode* newptr=new DNode; newptr->data=x; newptr->left=newptr->right=newptr; //当链表为空时完成插入 if(DL==NULL){DL=newptr;return;} //当链表不为空时完成插入 DNode*p=DL->left; newptr->right=p->right; DL->left=newptr; newptr->left=p; p->right=newptr; } ⑵向双向循环表的第i个结点位置插入一个值为x的结点。 解:void Insert(DNode*&DL,int i, ElemType x) { //i值越界,退出执行 if(i<=0){ cerr<<"i is out range!"<<end1; exit(1); } //建立值为x的新结点 DNode*newptr=new DNode; newptr->data=x; newptr->left=newptr->right=newptr; //当链表为空同时i等于1时进行插入,i不为1则退出 if(DL==NULL)if(i==1){DL=newptr;return;}

else{out<<"i is range!"<<end1; exit(1); } //实现i等于1时的插入 if(i==1){newptr->right=DL; newptr->left=DL->left; DL->left->right=newptr; DL->left=newptr; DL=newptr; return; } //查找第i个结点 int k=1; DNode*p=DL->right; while(p!=DL){ k++; if(k==i)break; p=p->right; } //i值越界,退出执行 if(i>k+1){ cerr<<"i is out range!"<<end1; exit(1); } //把newptr结点插入到p结点之前 newptr->right=p; newptr->left=p->left; p->left->right=newptr; p->left=newptr; return; } ⑶从双向循环链表中删除值为x的结点。 解:bool Delete(DNode*&DL,ElemType x) { if(DL==NULL)return 0; //当表头结点为x时则删除之 DNode*p=DL; if(DL->data==x){ DL=DL->right; p->left->right=DL; DL->left=p->left; delete p; return 1;

} //查找值为x的结点 p=p->right; while(p!=DL){ if(p->data==x)break; else p=p->right; } //不存在值为x的结点则返回0 if(p==DL)return 0; //删除值为x的结点 p->left->right=p->right; p->right->left=p->left; delete p; return 1; } 9.假定有一种带头附加结点的链表,每个结点含三个域:data、next和range,其中data 为整型值域,next和range均为指针域,现在所有结点已经由next域链接起来,试编一算法 ,利用range域把所有结点按照其值从小到大的顺序链接起来,当然由此域链接得到的单链 表的表头指针保存在表头附加结点的range域中。 解:void OrderList(SLNode* SL) //假定SLNode类型为按题目要求所定义的结点类型,SL为指向表头附加结点的指针 { SL->range=NULL; for(SLNode*p=SL->next;p!=NULL;p=p->next) { //每循环一次把p所指向的结点按序插入到以range域链接的有序表中 SLNode*ap,*cp; //为p结点寻找合适的插入位置 ap=SL;cp=ap->range; while(cp!=NULL) if(p->data<cp->data) break; else{ ap=cp; cp=cp->range; } //插入位置在ap和cp之间,把结点插入其中 p->range=cp; ap->range=p; } } 10.编一程序,实现下列功能: ⒈按照9题对结点的要求生成一个具有10个整数元素结点的带表头附加结点的根据next域

链接的链表,元素值由随机函数产生; ⒉按照next域链接的次序输出链表中每个结点的值; ⒊调用按第9题要求编写的操作算法; ⒋按照range域链接的次序输出链表中每个结点的值。 解: //lx2-7.cpp #include<isotream.h> #include<stdlib.h> typedef int ElemType;//规定元素类型为整型 struct SLNode//定义单链表结点 { ElemType data; SLNode*next; SLNode*range; }; void OrderList(SLNode* SL) { SL->range=NULL; for(SLNode*p=SL->next;p!=NULL;p=p->next) { SLNode *ap,*cp; //为p结点寻找合适的插入位置 ap=SL;cp=ap->range; while(cp!=NULL) if(p->data<cp->data) break; else{ ap=cp; cp=cp->range; } //插入位置在ap和cp之间,把p结点插入其中 p->range=cp; ap->range=p; } } void main() { //按next域链接生成具有10个整数元素结点的链表 SLNode*a=new SLNode; a->next=NULL; int i; SLNode* p;

for(i=0;i<10;i++){ p=new SLNode; p->data=range()%30; //假定产生30以内的随机整数 p->next=a->next; a->next=p; } //按next域链接的次序输出单链表 for(p=a->next;p!=NULL;p=p->next) cout<<p->data<<""; cout<<end1; //调用按第9题要求编写的操作算法 orderList(a); //按range域链接的次序输出单链表 for(p=a->range;p!=NULL;p=p->range) cout<<p->data<<""; cout<<end1; } 类别:数据结构.

.

第三章 稀疏距阵和广义表

一、单选题 1.在稀疏矩阵的带行指针指向量的链接存储中,每个行单链表中的结点都具有相同的 A。 A 行号 B 列号 C 元素值 D 地址 2.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储,求其转置矩阵的普通 转置算法的时间复杂度为 D 。 A O(m) B O(n) C O(n+t) D O(n*t) 3.设一个广义表中结点的个数为n,则求广义表深度算法的时间复杂度为 B。 A O(1) B O(n) C O(n2) D O(log2n) 二、填空题 1.在一个稀疏矩阵中,每个非零元素所对应的三元组包括该元素的 行号 、 列号 、和 元素值 。 2.在稀疏矩阵所对应的三元组线性表中,每个三元组元素按 行号 为主序、 列号 为辅 助的次序排列。 3.在初始化一个稀疏矩阵的函数定义中,矩阵形参应说明为 引用 参数。 4.在稀疏矩阵的顺序存储中,利用一个数组来存储非零元素,该数组的长度应 大于 等于 对应的三元线性表的长度。 5.在稀疏矩阵的带行指针向量的链接存储中,每个结点包含有 4 个域,在相应的 十字链接存储中,每个结点包含有 5 个域。 6.在稀疏矩阵的十字链接存储中,每个结点的down指针域指向 行号 相同的下一个结点, right指针指向 列号 相同的下一个结点。 7.一个广义表中的元素为 单 元素和 表 元素两类。 8.一个广义表的深度等于 括号 嵌套的最大层数。 9.在广义表的存储结构中,每个结点均包含有 3 个域。 10.在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为 值 域和 子表指针域 。 11.若把整个广义表也看为一个表结点,则该结点的tag域的值为 true或1 、next域的值 为 NULL或0 。 三、普通题 1.已知一个稀疏矩阵如下图所示:

0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0 图3-1 具有6行×7列的一个稀疏矩阵 ⑴写出它的三元组线性表; 解:((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,,2,-7),(5,6,2),(6,4,6)) ⑵给出它的顺序存储表示; 解: 下标 1 2 3 4 5 6 7 8 ... MaxTerms row(行号) 1 2 2 3 4 5 5 6

col(列号) 2 4 7 1 4 2 6 4

val(元素值) 4 -3 1 8 5 -7 2 6

⑶给出它的转置矩阵的三元组线性表和顺序存储表示; 解:((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1)) ⑷给出对它进行快速转置时,num向量中各分量的值; ⑸给出对它进行快速转置前和转置后,pot向量中各分量的值。 解: Col 1 2 3 4 5 6 7 Num[col] 1 2 0 3 0 1 1 pot[col](前) 1 2 4 4 7 7 8 pot[col](后) 2 4 4 7 7 8 9 2.采用顺序存储方式实现稀疏矩阵M1和M2相加的运算,运算结果由变量M返回。 解: void Add(SMatrix& M1,SMatrix& M2,SMatrix& M) //采用顺序存储方式实现稀疏矩阵M1和M2相加的运算,运算结果由变量M返回 { InitMatrix(M); //若两个矩阵尺寸不同,则给出错误信息并停止运行 if ((M1.m!=M2.m)||(M1.n!=M2.n)){ cerr<<"tow matrix measurenents are different!"<<end1; exit(1); } M.m=M1.m;M.n=M1.n; //若两个矩阵均为零矩阵,则无须计算 if(M1.t==0)&&(M2.t==0)) return; int i=1,j=1; //用i,j 分别指示M1.smt M2.sm数组中待比较元素的下标,初值均 //为1 int k=1; //用k指示M.sm数组中待写入元素的下标,初值为1 while((i<=M1.t)&&(j<=M2.t)) {//把行号较小元素写入到结果矩阵中,若行号相同进行列号的比较,使列号 //较小的元素写入到结果矩阵中,若行、列号均相等,则当相应元素的 //和不为0时才把这个和写入到结果矩阵中

if(M1.sm[i].row<M2.sm[j].row){ M.sm[k]=M1.sm[i]; i++;k++; } else if(M1.sm[i].row>M2.sm[j].row){ M.sm[k]=M2.sm[j]; j++;k++; } else{ if(M1.sm[i].col<M2.sm[j].col){ M.sm[k]=M1.sm[i]; i++;k++; } else if(M1.sm[i].col>M2.sm[i].col{ M.sm[k]=M2.sm[j]; j++;k++; } else{//此时相应元素的行列号必然相等 if(M.sm[i].val+M2.sm[j].val!=0){ M.sm[k].row=M1.sm[i].row; M.sm[k].col=M1.sm[i].col; M.sm[k].val=M1.sm[i].val+M2.sm[j].val; k++; } i++;j++; } } } while(i<=M1.t) { //把M1中的剩余元素写入到结果矩阵M中 M.sm[k]=M1.sm[i]; i++;k++; } while(j<=M2.t) { // 把M2中的剩余元素写入到结果矩阵M中 M.sm[k]=M2.sm[j]; j++;k++; } M.t=k-1;//把写入到结果矩阵M中元素的个数赋给M中保存元素个数的 //变量域 return; } 3.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。 ⑴ A=(()) ⑵ B=(a,b,c) ⑶ C=(a,(b,(c)))

⑷ D=((a,b),(c,d)) ⑸ E=(a,(b,(c,d)),(e)) ⑹ F=((a,(b,(),c),((d)),e))) 解:每小题的长度和深度如下表示。 题号 1 2 3 4 5 6 长度 1 3 2 2 3 1 深度 2 1 3 2 3 4 4.编写一个建立广义表链接存储结构的算法,假定广义表由字符串值提供。 解: void Create(GLNode*&GL,char*a) //根据在字符串a中保存的广义表生成其对应的存储结构 { static int i=0;//定义静态变量i指示a中待处理的字符串位置,每处理一 //个字符后i值增1 if(a[i]=='\0') return; //当字符串处理结束后返回 if(a[i]=='#'){ GL=NULL; i++; } else if(a[i]=='('){ GL=new GLNode; GL->tag=True; i++; Create(GL->sublist,a); } if(GL=new GLNode; GL->tag=False; GL->data=a[i]; i++; } else{ GL=new GLNode; GL->tag=False; GL->data=a[i]; i++; } if(GL==NULL) //此时的a[i]必然为')'字符 i++; else if(a[i]==','){ i++; Create(GL->next,a); } else if((a[i]==')')||(a[i]==',')){ i++; GL->next=NULL; } }

5.编写一个广义表中查找元素字等于给定值的算法,若查找成功则返回数值1, 否则返回数值0。 解: int Find(GLNode*GL,char ch) //从广义表GL中查找单元素字符等于ch的算法,若查找成功,则返回数值1, //否则返回数值0 { while(GL!=NULL){ if(GL->tag==0){//处理单元素结点 if(GL->data==ch) return 1;//查找成功返回1 else GL=GL->next; //否则继续向后查找 } else{//处理子表结点 int x=Find(GL->sublist,ch);//向子表中继续查找 if(x)//若在子表中查找成功则返回1,否则继续向后查找 return 1; else GL=GL->next; } } return 0; //当查找到表为空时返回0 } 类别:数据结构 .

.

第四章 栈和队列.习 题 四

一、单选题 1.栈的插入与删除操作在 A 进行. A 栈顶 B 栈底 C 任意位置 D 指定位置 2.当利用大小为N的数组顺序存储一个栈时,假定用top==N表示栈空,则向这个栈 插入一个元素时,首先应执行 B 语句修改top指针。 A top++1; B top--; C top=0; D top; 3.若让元素1,2,3依次进栈,则出栈次序不可能出现 C 种情况。 A 3,2,1 B 2,1,3 C 3,1,2 D 1,3,2 4.在一个顺序队列中,队首指针指向队首元素的 A 位置。 A 前一个 B 后一个 C 当前 D 后面 5.当利用大小为N的数组顺序存储一个队列时,该队列的最大长度为 B 。 A N-2 B N-1 C N D N+1 6.从一个顺序队列删除元素时,首先需要 B 。 A 前移一个队首指针 B 后移一位队首指针 C 取出队首指针所指位置上的元素 D 取出队尾指针所指位置上的元素 7.假定一个顺序队列的队首和队尾指针分别为f和r,则判断队空指针的条件为 D 。 A f+1==r B r+1==f C f==0 D f==r 8.假定一个链队的队首和队尾指针分别为fron和rear,则判断队空的条件为 D 。 A fron==rear B fron!=NULL C rear!=NULL D fron==NULL 二、填空题 1.队列的插入操作在 队首 进行,删除操作在 队尾 进。 2.栈又称为 后进先出 表,队列又称为 先进先出 表。 3.向一个顺序栈插入一个元素时,首先使 栈顶指针 后移一个位置,然后把待插入元素 写入 到这个位置上。 4.从一个栈删除元素时,首先取出 栈顶元素 ,然后再前移一位 栈顶指针 。 5.在一个顺序队列Q中,判断对空的条件为 Q.front==Q.next ,判断队满的条件为 (Q.rear+1)%QueueMaxSize+1==Q.front 。*

6.在一个顺序栈中,若栈顶指针等于 -1 ,则为空栈;若栈顶指针等于 StackMaxSize-1 , 则为满栈。 7.在一个链栈中,若栈顶指针等于NULL则为 空栈 ;在一个链队中,若队首指针与队尾指针的 值相同,则表示该队为 空 或该队 只含有一个结点 。 8.向一个链栈插入一个新结点时,首先把栈顶指针的值赋给 新结点的指针域 ,然后把新结点的 存储位置赋给 栈顶指针 。 9.从一个链栈中删除一个结点时,需要把栈顶结点 指针域 的值赋给 栈顶指针 。 10.向一个顺序队列中插入元素时,需要首先移动 队尾指针 ,然后再向所指位置 写入 新 插入的元素。 11.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满的条件为 top==0 。 12.向一个栈顶指针为HS的链栈中插入一个新结点*p时,应执行 p->next=HS; 和 HS=p; 操作。 13.从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时, 应执行 HS=HS->next; 操作。 14.假定front和rear分别为一个链队的队首和队尾指针,则该链队中只有一个结点的条件 为 (front==rear)&&(front!=NULL)或者(front==rear)&&(rear!=NULL) 。 15.中缀表达式3*(x+2)-5所对应的后缀表达式为 3x2+*5- 。 16.后缀表达式“45*32+-”的值为 15 。 17.在求解迷宫问题的递归算法中,输出每一个位置的坐标是按照从入口到出口的 相反 次顺 进行的。 18.在进行函数调用时,需要把每个实参的值和调用后的 返回地址 传送给被调用的函 数中。 19.当被调用的函数执行结束后,将自动按所保存的 返回地址 执行。 三、普通题 1.假定有四个元素A、B、C、D,按所列次序进栈,试写出所有可能的出栈列,注意,每一 个元素进栈后都允许出栈,如ACDB就是一种出栈序列。 解: ABCD ABDC ACBD ADCB BACD BADC BCAD BCDA BDCA CBAD CDBA DCBA

2.在一个数组空间stack[StackMaxSize]中可以同时存放两个顺序栈,栈底分别在数组的两端 ,当第一个栈的栈顶指针top1等于-1时则栈1为空,当第二个栈的栈顶指针top2等于StackMax Size时栈2为空。两个栈均向中间增长,当向栈1插入元素时,使top1增1得到新的栈顶位置, 当向栈2插入元素时,则使top2减1才能够得到新的栈顶位置。当top1等于top2-1或者top2等 于top1+1时,存储空间用完,无法再向任一栈插入元素。用于双栈操作的顺序存储类型可定 义为: struct Bothstack{ ElemType stack[stackMaxSize]; int top1,top2; }; 双栈操作的抽象数据类型可定义为: DAT BSTACK is Data:采用顺序结构存储的双栈,其存储类型为Bothstack operations: void InitStack(Bothstack& BS,int k); //初始化栈。当k=1或2时对应置栈1或栈2为空,k=3时置两个格均为空 void Clearstack(BothStack& BS,int k) //清除栈。当k=1或2时对应栈1或栈2被清除,k=3时两个栈均被清除 int StackEmpty(BothStack& BS,int k) //判断栈是否为空。当k=1或2时判断对应的栈1或栈是否为空,k=3时 //判断两个栈是否同时为空。若判断结果为空则返回1,否则返回0 ElemType Peek(BothStack& BS,int k) //取栈顶元素。当k=1或2时对应返回栈1或栈2的栈顶元素 void Push(BothStack& Bs,int k,const ElemType& item) //进栈。当k=1或2时对应向栈1或栈2的顶端压入元素item End BSTACK 1.试写出上述抽象数据类型中每一种操作的算法。 解: void InitStack(BothStack& BS,int k) { if(k==1) BS.top1=-1; else if(k==2) BS.top2=StackMaxSize; else if(k==3){ BS.top1=-1; BS.top2=StackMaxSize; } } void ClearStack(BothStack& BS,int k)

{ //函数体同上 } int StackEmpty(BothStack& BS,int k){ if(k==1) return BS.top1==-1; else if(k==2) return BS.top2==StackMaxSize; else if(k==3) return(BS.top1==-1)&&(BS,top2==StackMaxSize); else{ cerr<<"k的值不正确!"'; exit(1); } } ElemType peek(BothStack& BS,int k) { if(k==1){ if(BS.top1==-1){ cerr<<"Stack 1 is empty!"<<end1; exit(1); } return BS,stack(bs,top1); } else if(k==2){ if(BS.top2==StackMaxSize){ cerr<<"Stack 2 is empty!"<<end1; exit(1); } return BS,stack[BS,top2]; } else{ cerr<<"k的值不正确!"; exit(1); } } void push(BothStack& BS,int k,const ElemType& item) { if(BS.top1==BS.top2-1){ cerr<<"Stack overflow!"<<end1; exit(1); } if(k==1){

BS.top1++; Bs.stack[BS.top1]=item; } else if(k==2){ BS.top1--; BS.stack[BS.top2]=item; } } ElemType pop(BothStack& BS,int k] { if(k==1){ if(BS.top==-1){ cerr<<"Stack 1 is empty!"<<end1; exit(1); } BS.top--; return BS,stack[BS.top1+1]; } else if(k==2){ if(BS.top==StackMaxSize){ cerr<<"Stack 2 is empty!"<<end1; exit(1); } BS.top2++; return BS.stack[BS,top2-1]; } else{ cerr<<"k的值不正确!"; exit(1); } } 2.假定上述所有操作的算法已存于头文件"bstack.h"中,试编写一个程序,让计算机随机 产生出100以内的20个正整数并输出,同时把它们中的偶数依次存入到第一个栈中,奇数 依次存入到第二个栈中,接着按照存入每个栈中元素的次序分别输出每个栈中的所有元素 (此操作不改变栈的状态),然后按照后进先出的原则输出每个栈中的所有元素。 解: #include<iostream.h> #include<stdlib.h> const int StackMaxSize=50; typedef int ElemType; struct BothStack{ ElemType stack[StackMaxSize];

int top1,top2; }; #include"bstack.h" void main() { BothStack a; InitStack(a,3);//初始化两个栈 int i,j,k; //计算机产生20个随机数并输出,同时按奇偶数不同分别放入不同的栈中 for(i=0;i<20;i++){ j=rand()%100; cout<<j<<""; if(j%2==0) push(a,1,j); else push(a,2,j); } cout<<end1; //按照存入栈1中元素的次序输出栈1中的所有元素 cout<<"栈1:"; for(i=0;i<=a.top1;i++) cout<<a.stack[i]<<""; cout<<end1; //按照存入栈2中元素的次序输出栈2中的所有元素 cout<<"栈2:"; for(i=StackMaxSize-1;i>=a.top2;i--) cout<<a.stack[i]<<""; cout<<end1; //按照后进先出的原则输出每个栈中的所有元素 for(k=1;k<=2;k++){ if(k==1) cout<<"栈1:"; else cout<<"栈2:"; while(!StackEmpty(a,k)) cout<<Pop(a,k)<<""; cout<<end1; } } 该程序输入并运行后将得到如下结果(由于机器系统和C++版本不同,你得到的结果可能 与此不同): 41 67 34 0 69 24 78 58 62 5 45 81 27 61 91 95 42 27 36 栈1:34 0 24 78 58 62 64 42 36

栈2:41 67 69 5 45 81 27 61 91 95 27 栈1:36 42 64 62 58 78 24 0 34 栈2:27 95 91 61 27 81 45 5 69 67 41 3.设用第二章定义的类型为AlinkList的一维数组MS[MaxSize]建立三个链接堆栈,其中前三个元 素的next域用来存储三个栈顶指针,从下标为3的元素起作为空闲元素提供给三个栈共同使用, 试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同的栈: ⑴若输入的整数x小于60,则进第一个栈; ⑵若输入的整数x大于等于60同时小于100,则进第二个栈; ⑶若输入的整数大于100,则进第三个栈。 解: void MoreStack(ALinkList MS,int n) //把从键盘上输入的n个整数按不同条件分别进入到三个不同的链接栈中 { if(n>MaxSize-3){ cerr<<"存储空间不足!"; exit(1); } int i,x,av; for(i=0;i<3;i++) MS[i].next=0//置空栈,即给三个栈顶指针赋0 av=3;//av指向可利用元素的下标,赋初值为3 cout<<"输入"<<n<<"个整数:"<<end1; for(i=0;i<n;i++){ //从键盘读入一个整数并把它赋给av元素的值域 cin>>x; MS[av].data=x; //按条件把av元素压入不同的栈,即链接到相应栈的栈顶 if(x<60){ Ms[av].next=MS[0].next; MS[0].next=av; } else if(x>=60&&x<=100){ MS[av].next=MS[1].next; MS[1].next=av; } else{ MS[av].next=MS[2].next; MS[2].next=av; } //使av指向下一个可利用元素 av++; }

} 4.编写一个程序,首先调用上题算法,然后分别打印出每个栈中的内容。 解: #include<iostream.h> #include<stdlib.h> const int MaxSize=50;//要至少定义为比输入的整数个数大3 typedef int ElemType; struct ALNode{ ElemType data; int next; }; typedef ALNode ALinkList[MaxSize]; void MoreStack(ALinkList MS,int n) {//函数体在此省略 } void main() { ALinkList a; int n; cout<<"从键盘输入的整数个数(1~47):"; cin>>n; MoreStack(a,n); for(int i=0;i<3;i++) { //依次将每个栈中的元素全部出栈并打印出来 int j=a[i].next; while(j!=0){ cout<<a[j].data<<""; j=a[j].next; } cout<<end1; } } 一次输入和运行结果如下: 从键盘上输入的整数个数为(1~47):12 输入12个整数: 38 64 97 120 78 33 45 214 88 25 143 60 25 45 33 38 60 88 78 97 64 143 214 120 5.已知一个中缀算术表达式为: 3+4/(25-(6+15))*8@

⑴写出对应的后缀算术表达式。 解:3 4 25 6 15 + - /8 * + @ ⑵画出在转换成后缀表达式的过程中运算符栈的变化。 解:略 6.已知一个后缀算术表达式为: 24 8 + 3 * 4 10 7 - * / @ ⑴写出对应的中缀算术表达式。 解: (24+8)*3/(4*(10-7)) ⑵画出在进行后缀算术表达式求值的过程中数值栈的变化。 解:略 7.为了计算表达式的值: 把栈Stack类型定义为带模板的类型,该类型中包含顺序存储的栈和对栈的每一种基 本操作的实现。 解:把进行后缀表达式求值的Compute算法改写为使用Stack类的算法。 解:把进行中缀表达式转换为后缀表达式的Change算法改写为使用Stack类的算法。 解:写出计算C(n,k)的递归算法。 解:利用二维数组写出计算C(n,k)的非递归算法。 解:分析递归算法和非递归算法的时间复杂度和空间复杂度。 解: template<class ElemType> class Stack{ ElemType stack[StackMaxSize]; int top; public: void InitStack() //初始化栈对象,即把它置为空 { top=-1; } void ClassStack() //清除栈对象中的所有元素,使之成为一个空栈 { top=-1; } int StackEmpty() //判断栈对象是否为空,若是则返回1,否则返回0 { return top==-1; }

ElemType peek() //返回栈对象的栈顶元素,但不移动栈顶指针 { if(top==-1){ cerr<<"Stack is empty!"<<end1; exit(1); } return stack[top]; } void push(const ElemType& item) //元素item进栈,即插入到栈顶 if(top==StackMaxSize-1){ cerr<<"Stack overflow!"<<end1; exit(1); } top++; stack[top]=item; } ElemType Pop() //删除栈顶元素并返回之 { if(top==-1){ cerr<<"Stack is empty!"<<end1; exit(1); } ElemType temp=stack[top]; top--; return temp; } } float Compute(char* str) { Stack<float> s;//定义元素类型为float的栈 S.InitStack(); istrstream ins(str); char ch; float x; ins>>ch; while(ch!='@') { //扫描每一个字符并进行相应处理 switch(ch)

{ cass'+': X=S.Pop()+S.Pop(); break; cass'-': X=S.Pop(); X=S.Pop()-X; break; cass'*': X=S.Pop()*S.Pop(); break; cass'/': X=S.Pop(); if(X!=0.0) X=S.Pop()/X; else{ cerr<<"Divide by 0!"<<end1; exit(1); } break; default://读入的必为一个浮点数的最高位数字 ins.putback(ch); ins<<X; } S.Push(X); ins>>ch; } if(!S.StackEmpty()) { x=s.Pop(); if(!S.StackEmpty()) return X; else{ cerr<<"expression error!"<<end1; exit(1); } } else{ cerr<<"Stack is empty!"<<end1; exit(1); } }

void Change(char* s1,char* s2) { Stack<char>R;//定义元素类型为char的栈 R.InitStack(); R.push('@'); int i,j; i=0; j=0; char ch=s1[i]; while(ch='@') { if(ch=='') ch=s1[++i]; else if(ch=='('){ R.Push(ch); ch=s1[++i]; } else if(ch==')'){ while(R.peek()!='(') s2[j++]=R.Pop(); R.Pop(); ch=s1[++i]; } else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){ char w=R.peek(); while(precedence(w)>=Precedence(ch){ s2[j++]=w; R.Pop();w=R.Peek(); } R.Push(ch); ch=s1[++i]; } else{ while(isdigit(ch)||ch=='.'){ s2[j++]=ch; ch=s1[++i]; } s2[j++]=''; } } ch=R.Pop(); while(ch!='@'){

s2[j++]=ch; ch=R.Pop(); } s2[j++]='@'; s2[j++]='\0'; } 8.编写把十进制正整数转换为十六进制数输出的算法。 解: void Transform(long num) //把一个正整数num转为一个十六进制数输出 { Stack a; InitStack(a); while(num!=0){ int k=num % 16; Push(a,k); num/=16; } while(!StackEmpty(a)) { int X=Pop(a); if(x<10) cout<<x; else{ switch(x) { cass 10: cout<<'A'; break; cass 11: cout<<'B'; break; cass 12: cout<<'C'; break; cass 13: cout<<'D'; break; cass 14: cout<<'E'; break; cass 15:

cout<<'F'; } } } cout<<end1; } 9.编写把十进制正整数转换为S进制(2≤S≤9)数输出的递归算法,然后若把425转换为六进制 数,画出每次递归调用前和返回后系统栈的状态。 解: 只给出递归算法,画图从略。 void Transform(long num,int s) //把十进制正整数转换为S进制数的递归算法 { int k; if(num!=0){ k=num%S; Transfrom(num/S,S); cout<<k; } } 10.裴波那契(Fibonacci)数列的定义为:它的第一项和第二项均为1,以后各项为其前两项之和。 若裴波那契数列中的第n项用Fid(n)表示,则计算公式为: 1 (n=1或n=2) Fib(n)= Fib(n-1)+Fib(n-2) (n>=2) 试编写计算Fib(n)的递归算法和非递归算法,并分析它们的时间复杂度和空间复杂度。 解: 递归算法为: long Fib(int n) { if(n==1||n==2) //终止递归条件 return 1; else return Fib(n-1)+Fib(n-2); } 非递归算法为 long Fib1(int n) { int a,b,c;//C代表当前项,a和b分别代表当前项前面的第2项和第1项 a=b=1; //给a和b赋初值1 if(n==1||n==2) return 1;

else for(int i=3;i<=n;i++){ c=a+b; //求出当前项 a=b;//把前面第1项赋给前面第2项 b=c;//把当前项赋给前面第1项 } return c;//返回所求的第n项 } 11.根据代数中的二项式定理,二项式(x+y)n的展开式的系数序列可以表示成 图4-1那样的三角形,其中除每一行最左和最右两个系数等于1以外,其余各数均等于上一 行左右两系数之和。这个系数三角形称作杨辉三角形。 (x+y)0 (x+y)1 (x+y)2 (x+y)3 (x+y)4 (x+y)5 (x+y)6 (x+y)7 (x+y)8 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 图4-1 杨辉三角形

设C(n,k)表示杨辉三角形中第n行(n≥0)的第k个系数(0≤k≤n),按照二项式定理,C(n,k) 可递归定义为: 1 (k=0或k=n) C(n,k)= C(n-1,k-1)+C(n-1,k) (n>=2) int C(int n,int k) //求出指数为n的二项展开式中第k项(0<=k<=n)系数的递归算法 { if(k==0||k==n) return 1; else return C(n-1,k-1)+C(n-1,k); } int C1(int n,int k) //求出指数为n的二项展开式中第k项(0<=k<=n)系数的非递归算法

{ typedef int b[15]; //定义一维整型数组类型[15]为b,其尺寸要大于参数n b*a=new b[n+1]; //动态分配具有b类型的一维数组,其尺寸为n+1,这样a就指向了一个具有 //[n+1][15]的二维数组。 for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) //外循环每循环一次计算出指数为i的二项展开式的所有系数,内循环每循环 //一次计算出此展开式中第j项的系数 if(j==0||j==1) a[i][j]=1; else a[i][j]=a[i-1][j-1]+a[i-1][j]; return a[n][k]; //返回指数为n的二项展开式中第k项的系数 } 递归时间复杂度和空间复杂度分别为O(2n)和O(n),非递归算法的时间复杂 度和空间复杂度均为O(n2)。 12.利用堆栈编写出求解迷宫问题的非递归算法。 解: 设描述迷宫中当前位置的结构如下 struct item {//定义描述迷宫中当前位置的结构 int x,y,d; //x和y分别表示当前位置的行坐标和列坐标,d表示移动到下一步的方向 }; 此题的算法如下: void Seekpath(int m,int n) //查找m*n迷宫从入口(1,1)到出口(m,n)的一条通路 { mark[1][1]=1; Stack S;//栈的元素类型应定义为item InitStack(s); items temp; temp.x=1;temp.y=1;temp.d=-1; push(s,temp);//将入口点压入栈 while(!stackEmpty(s)) { //每循环一次从查找的路径中退回一步 temp=Pop(S);//将保存的上一个位置出栈 int x=temp.x;int y=temp.y;int d=temp.d+1; //沿着该位置的下一个方向前进

while(d<4) {//按顺时针方向试探着前进 if(x==m&&y==n)//到达出口,按逆序输出路径中每个位置的坐标,然后返回 { cout<<m<<""<<n<<end1; while(!StackEmpty(S)){ temp=Pop(S); cout<<temp.x<<""<<temp.y<<end1; } return; } int g=x+move[d][0];int h=y+move[d][1]; //按方向d前进,求出下一个位置的坐标 if(mase[g][h]==0&&mark[g][h]==0) {//对未访问过的可通行的下一个位置,应将当前位置进栈,并将下一个位置 //变为当前位置,否则改变沿当前位置前进的方向 mark[g][h]=1; temp.x=x;temp.y=y;temp.d=d; Push(S,temp); x=g;y=h;d=0; //进入一个新位置后,重新从初开始方向东开始 } else d++; } } cout<<"不存在从入口到出口的通路"<<end1; } 调用此算法的完整程序如下。 #include<iostream.h> #include<stdlib.h> const int StackMaxSize=30; struct item {//定义描述迷宫中当前位置的结构 int x,y,d;//x和y分别表示当前位置的行坐标和列坐标,d表示移动到下一步的 //方向 }; typedef items ElemType; //定义栈中元素的类型为items类型 struct stack{ ElemType stack[StackMaxSize]; int top; }; #include"stack.h"//保存栈基本操作算法的头文件

const M=10,N=10; //定义M和N常量,由它们决定迷宫的最大尺寸 int maze[M+2][N+2];//定义保存迷宫数据的数组 int mark[M+2][N+2];//定义保存访问标记的数组 int move[4][2]={{0,1},{0,-1},{-1,0}}; //行下标0,1,2,3分别代表东,南,西,北方向 void SeekPath(int m,int n) //查找m*n迷宫中从入口(1,1)到出口(m,n)的一条通路 {//函数体在此省略 } void main(void) { int i,j; int m,n; //输入迷宫尺寸 do{ cout<<"输入迷宫的行数m和列数n:"; cin>>m>>n; if(m>M||n>N)cout<<"重新输入m和n的值."<<end1; }while(m>M||n>N); //输入迷宫数据 for(i=0;i<m+2;i++) for(j=0;j<n+2;j++) cin>>maze[i][j]; //初始化mark数组 for(i=0;i<m+2;i++) for(j=0;j<n+2;j++) mark[i][j]=0; //求解maze迷宫中从入口(1,1)到出口(m,n)的一条路径 Seekpath(m,n); } 13.编写一个递归算法,输出自然数1~n这n个元素的全排列。 分析:由排列组全的知识可知,n个元素的全排列共有n!种,如对于1,2,3这三个元素,其全排 列为123,132,213,231,321,312,共3!=6种。n!种可分解为n*(n-1)!种,而(n-1)!种又可分解 为(n-1)(n-2)!种,依次类推。对于n个元素 ,可把它们分别放入到n个位置上,让第一个元素 依次取每一个元素,共有n种不同的取法,对其后n-1个位置上的n-1个元素,共有(n-1)!种不 同的排列,所以总共有n(n-1)!种不同的排列;同样, 解: 对n个元素的全排列是一个递算法,具体描述如下。 void Permute(int a[],int s,int n) //对a[s]~a[n-1]中的n-s个元素进行全排列,s的初始值为0 { int i,temp;

if(s==n-1) { //当递归排序到最后一个元素时结束递归,输出a中保存的一种排列 for(i=0;i<n;i++) cout<<a[i]<<""; cout<<""; } else //继续递归排列 for(i=s;i<n;i++) { //每循环一次使a[s]取一个新值,并对其后的所有元素进行递归排序 temp=a[s];a[s]=a[i];a[i]=temp; //交换a[s]与a[i]的元素值 Permute(a,s+1,n); //对a[s+1]~a[n-1]中的元素进行递归排序 temp=a[s];a[s]=a[i];a[i]=temp; //恢复a[s]与a[i]的原有值 } } 调用此算法的完整程序如下。 #include<iostream.h> const int UpperLimit=6;//定义全排列的元素个数的最大值 void Permute(int a[],int s,int n) //对a[s]~a[n-1]中的n-s个元素进行全排列,s的初值为0 { }//函数体在此省略 void main(void) { int a[UpperLimt];//定义存储n个整型元素的数组 int n; cout<<"Enter a number'n'between 1and" <<UpperLimit<<":"; cin>>n;//输入待全排的元素的个数 for(int i=0;i<n;i++) a[i]=i+1; //给数组a赋初值 cout<<end1; Permute(a,0,n);//对数组a中的n个元素(即1-n)进行全排列 cout<<end1; } 14.根据 解: 略 15.假定用于顺序存储一个队列的数组的长度为N,队首和队尾指针分别为front和rear ,写出求此队列长度(即所含元素个数)的公式。

解: 队列长度的计算公式为: (N+rear-front)%N 16.假定在一个链接队列中只设置队尾指针,不设置队首指针,并且让队尾结点的指针域 指向队首结点(称此为循环链队),试分别写出在循环链队上进行插入和删除的算法。 解: 插入操作的算法如下。 void QInsert(LNode*&Rear,const ElemType& item) //使新元素item的值插入到循环链队中 { LNode*newptr=new Lnode; //得到一个由newptr指针所指向的新结点 if(newptr==NULL){ cerr<<"Memory allocation failare"<<end1; exit(1); } newptr->data=item;//把item的值赋给新结点的值域 if(Rear==NULL) Rear=newptr->next=newptr; //若链队为空,则新结点即是队首结点又是队尾结点 else{ newptr->next=Rear->next; //使新结点的指针域指向队首结点 Rear->next=newptr; //使队尾结点的指针域指向新结点 Rear=newptr; //使新结点成为新的队尾结点 } } 删除操作的算法如下。 ElemType QDelete(LNode*&Rear) //从循环链队中删除队首元素 { if(Rear==NULL){ cerr<<"Linked queue is empty!"<<end1; exit(1); } LNode* p=Rear->next; //使p指向队首结点 if(p==Rear) Rear=NULL; //若链队中只有一个结点,则删除后队尾指针为空 else

Rear->next=p->next; //使队尾结点的指针域指向队首结点的后继结点 ElemType temp=p->data;//暂存队首元素 delete p;//回收原队首结点 return temp;//返回被删除的队首元素 } 类别:数据结构 .

第五章 树和二叉树 1.对于一棵具有n个结点的树,该树中所有结点的度数之和为 n-1 。 2.假定一棵三叉树的结点个数为50,则它的最小深度为 5 ,最大深度为 50 。 3.在一棵高度为h的四叉树中,最多含有 4-1/3 h结点。 4.在地棵三叉树中,度为3的结点数有2个,度为2的结点数有1个,度为1的结点数为2个 ,那么度为0的结点数有 6 个。 5.一棵深度为5的满二叉树中的结点数为 31 个,一棵深度为3的满四叉树中的结点数为 21 个。 6.假定一棵树的广义表示为A(B(C,D(E,F,G),H(I,J))),则树中所含的结点数为 10 个,树的深度为 4 个,树的度为 3 。 7.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J))),则度为3,2,1,0的结点数分 别为 2 、 1 、 1 和 6 个。 8.假定一棵树的广义表示为A(B(C,D(E,F,G),H(I,J))),则结点H的双亲结点为 B 个, 孩子结点为 I和J 。 9.在一棵二叉树中,假定双亲结点数为5个,单分支结点数为6个,则叶子结点数为 6 个。 10.对于一棵二叉树,若一个结点的编号为i,则它的左孩子结点的编号为 2i ,右孩子 结点的编号为 2i+1 ,双亲结点编号为 i/2 。 11.在一棵二叉树中,第5层上的结点数最多为 16 。 12.假定一棵二叉树的结点数为18,则它的最小深度为 5 ,最大深度为 18 。 13.一棵二叉树的广义表表示为a(b(e,d),e(f(,g))),则e结点的双亲结点为 a ,左孩 子结点为 f ,右孩子结点为 空 。 14.一棵二叉树的广义表表示为a(b(e,d),e(f(,g))),它含有双亲结点 2 个,单分支结 点 2 个,叶子结点 3 个。 15.对于一棵含有40个结点的理想平衡树,它的高度为 6 。 16.假一定一棵二叉树顺序存储在一维数组a中,则a[i]元素的左孩子元素为 a[2i] ,右 孩子元素为 a[2i+1] ,双亲元素(i-1)为 a[i/2] 。

17.假定一棵二叉树顺序存储在一维数组a中,但让编号为1的结点存入a[0]元素中, 让编号为2的结点存入a[1]元素中,其余类推,则编号为i结点的左孩子结点对应的 存储位置为 2i-1 ,若编号为i结点的存储位置用j表示,则其左孩子结点对 应的存储位置为 2j+1 。 18.若对一棵二叉树从0开始进行结点编号,并按此编号把它顺序存储到一维数组a中, 即编号为0的结点存储到a[0]中,其余类推,则a[i]元素的左孩子元素为 a[2i+1] , 右孩子元素为 a[2i+2] ,双亲元素(i->0)为 a[(i-1)/2] 。 19.对于一棵具有n个结点的二叉树,对应二叉链接表中指针总数为 2n 个,其中 n-1 个用于指向孩子结点, n+1 个指针空闲着。 20.一棵二叉树广义表表示为a(b(d(,h)),c(e,f(g,i(k)))),该树的结点数为 10 个, 深度为 5 。 21.在一棵高度为5的理想平衡树中,最少含有 16 个结点,最多含有 31 个 结点。 22.在一棵高度为h的理想平衡树中,最少含有 2h-1个结点,最多 含有 2h-1个结点。 23.假定一棵二叉树广义表表示为a(b(c),d(e,f)),则对它进行的先序遍历结果为 a b c d e f ,中序遍历结果为 c b a e d f,后序遍历结果为 c b e f d a,按层遍历结果为 a b d c e f。 24.假定一棵普通树的广义表表示为a(b((e),c(f(h,i,j),g),d),则先根遍历结果为 a b e c f h i j g d,按层遍历结果为 a b c d e f g h i j。 二、普通题 1. 解:略 2. 解:略 3.已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点 ,.....,nm个度为m的结点,问树中有多少个叶子结点? 解: 设叶子结点数为n0,则树中结点数和总度数分别为 结点数=n0+n1+n2+...+nm 总度数=n1+2n2+...+m×nm 根据树的性质1可知,结点数等于总度数加1,所以得到

m n0=1+∑((i-1)×ni) i=2 4.画出由三个结点a,b,c组成的所有不同结构的二叉树,共有多少种不同的结构?每一种结 构又对应多少种不同的值的排列次序? 解: 由三个结点a,b,c组成的所有不同结构的二叉树如下图所示,共有5种不同的结构,每一 种结构对应6种不同的值的排列次序。 a a a a a /\ / / \ \ b c b b b b / \ / \ c c c c 5.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A[1]~A[n]元素中,试编写一 个算法打印出编号为i的结点的双亲和所有孩子。 解: void Request(int a[],int n,int i) //从数组A中打印出编号为i的结点的双亲和孩子 { if(i>n){ cerr<<"编号为"<<i<<"的结点不存在!"<<end1; exit(1); } cout<<"current element:"<<A[i]<<end1; int j=i/2; //下标为j的结点是下标为i结点的双亲 if(j>0) cout<<"parent:"<<A[j]<<end1; else cout<<"树根结点没有双亲结点!"<<end1; if(2*i<n){ cout<<"left child:"<<A[2*i]<&Lt;end1; cout<<"right child:"<<A[2*i+1]<<end1; } else if(2*i==n){ cout<<"left child:"<<A[2*i]<<end1; cout<<"no right child!"<<end1; } else cout<<"no children!"<<end1;

} 6.已知一棵二叉树如下图所示,试分别画出它的不带双亲指针的链接存储结构的示意图和 存储于数组的链接存储映像(假定按层次依次为各结点分配下标位置)。 解: 25 / \ 16 37 / /\ 8 30 48 /\ \ 28 32 60 /\ \ 26 29 35 在数组中的二叉树存储映像如下所示。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...BTreeMaxSize data 25 16 37 8 30 48 28 32 60 26 29 35 left 1 2 4 5 0 7 0 10 0 0 0 0 0 right 13 3 0 6 0 8 9 11 12 0 0 0 0 14 0 7.写出对图5-3所示的二叉树分另按前序、中序、后序遍历时得到的结点序列。 解: 前序遍历为 25,16,8,37,30,28,26,29,32,35,48,60 中序遍历为 8,16,25,26,28,29,30,32,35,37,48,60 后序遍历为 8,16,26,29,28,35,32,30,60,48,37,25 8.写出对二叉树进行中序遍历的非递归算法。 解: void InorderN(BTreeNode*BT) //对二叉树进行中序遍历的非递归算法 { BTreeNode* s[10];//定义用于存储结点指针的栈 int top=-1;定义栈顶指针并赋初值使s栈为空 BTreeNode* p=BT;//定义指针p并使树根指针为它的初值 while(top!=-1||p!=NULL) {//当栈非空或p指针非空时执行循环 while(p!=NULL){ top++; s[top]=p; p=p->left;

} if(top!=-1){ p=s[top]; top--; cout<<p->data<<''; p=p->right; } } } 9.编写一算法,求出一棵二叉树中所有结点数和叶子结点,假定分别用变参C1和C2统计所 有结点数和叶子结点数,初值均为0。 解: void Count(BTreeNode* BT,int& C1,int& C2) //分别统计出二叉树中所有结点数和叶子结点数 { if(BT!=NULL){ C1++;//统计所有结点 if(BT->left==NULL&&BT->right==NULL) C2++; //统计叶子结点数 Count(BT->left,C1,C2); Count(BT->right,C1,C2); } } 10.编写具有下列功能的每个函数: 把在内存中生成的一棵二叉树写入到一个磁盘文件中,该函数声明为 void WriteFile(char* fname,BTreeNode*BT); 解: 根据从键盘上输入的一棵二叉树广义表表示建立一棵二叉树bt; 把bt二叉树写入到磁盘文件"a:xxkl.dat"中; 把磁盘文件"a:xxkl.dat"中保存的二叉树恢复到内存中,并由bt指向树根结点; 以广义表的形式输出以bt为树根指针的二叉树。 解: 写出先根遍历得到的结点序列; 写出按层遍历得到的结点序列; 画出转换后得到的二叉树和二叉链表。 解: void WriteFile(char* fname,BTreeNode*BT) //把由BT指针所指二叉树按照层次遍历的次序存储结点到文件fname中 { ofstream ofs(fname,ios::binary);

//把由fname所指字符串作为文件名的文件定义为输出文件流ofs,并按二进制方 //式打开 LinkQueue HQ;InitQueue(HQ); //定义一个链接队列并进行初始化,该链接队列中结点值的类型应为二叉树结点 //的类型 BTreeNode* p; if(BT!==NULL)QInsert(HQ,BT){ //将树根指针插入到队列中 while(! QueueEmpty(HQ)){ p=QDelete(HQ); //从队列中删除一个元素并赋给指针 ofs.write((char*)p,sizeof(*p)); //把p指针所指结点写入到文件中 if(p->left!=NULL)QInsert(HQ,p->left); //若p结点存在左孩子,则左孩子指计入队 if(p->right!=NULL)QInsert(HQ,p->right); //若p结点存在右孩子,则右孩子指计入队 } ofs.closs();//关闭文件流对象所对应的文件 } 2.把存储到磁盘文件中的一棵二叉树恢复到内存存中,该函数声明为 void WriteFile(char* fname,BTreeNode*&BT); 解: void WriteFile(char* fname,BTreeNode*&BT) //把fname文件中按层扫描存储的二叉树恢复到内存中,并由引用指针BT指向树根结点 { ifstream ifs(fname,ios::in | ios::nocreate | ios::binary); //把fname文件定义为输入文件流ifs,并按二进制方式打开 if(! ifs){cout<<"File not open!"<<end1;exit(1);} LinkQueue HQ; InitQueue(HQ); //定义一个链接队列并进行初始化 BTreeNode *p1,*p2; int b=sizeof(*p1); //把二叉树结点的大小赋给b,作为读取文件的基本单位 ifs.seekg(0,ios::end); //把文件指针移到结束位置 int n=ifs.tellg()/b; //求出文件中所存二叉树的结点数并赋给n ifs.seekg(0); //将文件指针移到文件开始位置,以便从头开始读取每个结点 if(n==0){ifs.close();BT=NULL;return;} //如果文件为空,则把BT置空后返回,用文件中的第一个结点构成树根结点并将

//该结点指针插入队列中 p1=new BTreeNode; ifs.read((char*)p1,b); BT=p1; QInsert(HQ.p1); n--; //依次用文件中的每个结点构成新结点并把它插入到双亲结点的左孩子或右孩子位置 while(n) { //当读完文件中的结点后循环结束 p2=QDelete(HQ);//从队列中删除队首元素并赋给p2 if(p2->left!=0) {//需要给p2结点添加左孩子,并使左孩子指针进队 p1=new BTreeNode; ifs.read((char*)p1,b); p2->left=p1; Qinsert(HQ,p1); n--; } if(p2->right!=0) { //需要给p2结点添加右孩子,并使右孩子指针进队 p1=new BTreeNode; ifs.read((char*)p1,b); p2->right=p1; QInsert(HQ,p1) n--; } } ifs.close();//关闭ifs对应的磁盘文件 } 11.编写一个完整的程序实现下列功能: #include<iostream.h> #include<fstream.h> #include<strstrea.h> #include<stdlib> struct BTreeNode {//定义二叉树结点类型 char data; //定义结点值的类型为整型 BTreeNode *left; BTreeNode *right; }; typedef BTreeNode* ElemType;//定义链接队列中结点值的类型为二叉树结点的指针类型 struct LNode{ElemType data;LNode* next;};

//定义链接队列中结点的类型 struct LinkQueue{LNode* front;LNode*rear;}; //定义一个链接队列的存储类型 #include"linkqueue.h"//包含对链接队列的各种运算 #include"btree.h"//包含二叉树的各种运算 void WriteFile(char* fname,BTreeNode* BT) //把由BT指针所指二叉树按照层次遍历的次序存储结点到文件fname中 { //函数体略 } void ReadFile(char* fname,BTreeNode*&BT) //把fname文件中按层扫描存储的二叉树恢复到内存中,并由引用指针BT //指向树根结点 { //函数体略 } void main() { BtreeNode *bt; InitBTree(bt); while(1) { cout<<"功能菜单:"<<end1; cout<<'\t'<<"1.建立二叉树"<<end1; cout<<'\t'<<"2.二叉树存盘"<<end1; cout<<'\t'<<"3.由文件恢复二叉树"<<end1; cout<<'\t'<<"4.以广义表形式输出二叉树"<<end1; cout<<'\t'<<"5.结束程序运行"<<end1; cout<<end1; int m; cout<<"输入你的选择(1-5):"; do cin>>m;while(m<1||m>5); switch(m){ case 1: char a[50]; cout<<"输入以'@'字符作为结束符的二叉树广义表表示:"<<end1; cin>>ws;//跳过键盘输入缓冲区中的空白字符 cin.getline(a,50); createBTree(bt,a); break; case 2: WriteFile("a:xxkl.dat",bt); break;

case 3: ReadFile("a:xxkl.dat",bt); break; case 4: PrintBTree(bt);cout<<end1; break; default; break; } if(m==5)break; } } 12.对于图5-16所示的树: 略 13.假定一棵树采用标准形式存储,试写出广义表形式输出树的算法。 解: void printGTree(GTreeNode* GT) //以广义表形式输出按标准方式存储的三叉树 { if(GT!=NULL){//若树不为空则进行如下处理 cout<<GT->data<<'';//输出根结点的值 if(GT->t[0]||GT->t[1]||GT->t[2]){ cout<<'('; printGTree(GT->t[0]);//输出第一棵子树 cout<<','; printGTree(GT->t[1]);//输出第二棵子树 cout<<','; printGTree(GT->t[2]);//输出第三棵子树 cout<<')'; } } } 14.假定采用标准形式存储,试写出求其深度的算法。 解: int GTreeDepth(GTreeNode* GT) //求一棵普通树的深度 { if(GT==NULL)//空树的深度为0 return 0; else{

int max=0;//用来保存子树中的最大深度 for(int i=0;i<3;i++){ int d=GTreeDepth(GT->t[i]); //计算出一棵子树的深度并赋给变量d if(d>max)max=d; } return max+1; //返回树的深度,它等于子树的最大深度加1 } } 10.在一份电文中共使用五种字符:a、b、c、d、e ,它们的出现频率依次为4、7、5、2、9 ,试画出对应的编码哈夫曼树(请按照左子树根结点的权小于等于右子树根结点的权的次序构 造),求出每个字符的哈夫曼编码,并求出传送电文的长度。 解: 五种字符的哈夫曼编码依次为001,10,00,010,11。传送电文的总长度为60。

类别:数据结构.

.

第六章 二叉树的应用

一、填空题 1.从二叉搜索树中查找一个元素时,其时间复杂度大致为 C 。 A O(n) B O(1) C O(log2n) D O(n2) 2.向二叉搜索树中插入一个元素时,其时间复杂度大致为 B 。 A O(1) B O(log2n) C O(n) D O(nlog2n) 3.根据n个元素建立一棵二叉搜索树时,其时间复杂度大致为 D 。 A O(n) B O(log2n) C O(n2) D O(nlog2n) 4.从堆中删除一个元素的时间复杂度为 C 。 A O(1) B O(n) C O(log2n) D O(nlog2n) 5.向堆中插入一个元素的时间复杂度为 A 。 A O(log2n) B O(n) C O(1) D O(nlog2n) 6.权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为 D 。 A 24 B 48 C 72 D 51 二、填空题 1.在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定 小于 该结点的值,右子树 上所有结点的值一定 大于 该结点的值。 2.对一棵二叉搜索树进行中序遍历时,得到结点序列是一个 有序序列 。 3.从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明 查找成功 , 若元素的值小于根结点的值,则继续向 左子树 查找,若元素的值大于根结点的值,则继续 向 右子树 查找。 4.在一个堆的顺序存储中,若一个元素的下标为i,则它的左孩子元素的下标为 2i+1 , 右孩子元素的下标为 2i+2 。 5.在一个小根堆中,堆顶结点的值是所有结点中的 最小值 ,在一个大根堆中,堆顶 结点的值是所有结点中的 最大值 。 6.当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层 向上 调整,直到被 调整到 堆顶 位置为止。 7.当从一个小根堆中删除一个元素时,需要把 堆尾 元素填补到 堆顶 位置, 然后再按条件把它逐层 向下 调整。

8.在哈夫曼编码中,若编码长度只允许小于等于4,则除了已对两个字符编码为0和10外, 还可以最多对 4 个字符编码。 三、普通题 1.已知一组元素(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉树。 解:略 2.已知一棵二叉排序树如图6-11所示,若从中依次删除72,12,49,28结点,试分别画出每删除一 个结点后得到的二叉排序树。 解:略 28 / \ 12 49 \ /\ 16 34 72 / / 30 63 3.设在一棵二叉排序树的每个结点中,含有关键字key域和统计相同关键字结点个数的count域, 当向该树插入一个元素时,若树中已存在与该元素的关键字相同的结点,则就使该结点的count 域增1,否则就由该元素生成一个新结点而插入到树中,并使其count域置为1,试按照这种插入 要求编写一个算法。 解: void Insert(BTreeNode*&BST,ElemType& item) //向二叉排序树中插入一个不重复元素item,若树中存在该元素,则将一配结点值域中的 //count域的值加1即可 { //从二叉排序树中查找关键字为item.key的结点,若查找成功则指针t指向该点结点,否则 //指针s指向待插入新结点的双亲结点 BTreeNode *t=BST,*S=NULL; while(t!=NULL){ s=t; if(item.key==t->data.key) break; else if(item.key<t->data.key) t=t->left; else t=t->right; } //元素已存在,则将其值域中的count域的值增1,否则建立新结点并插入到合适位置 if(t!=NULL) t->data.count++;

else{ BTreeNode* p=new BTreeNode; p->data=item; p->data.count=1; p->left=p->right=NULL; if(s==NULL) BST=p; else{ if(item.key<s->data.key) s->left=p; else s->right=p; } } } 4.编写一个非递归算法求出二叉排序树中的关键字最大的元素。 解: ElemType FindMax(BTreeNode* BST) //从二叉排序树中返回关键字最大的元素 { if(BST==NULL){ cerr<<"不能在空树上查找最大值!"<<end1; exit(1); } BTreeNode* t=BST; while(t->right!=NULL) t=t->right; return t->data; } 5.假定一棵二叉排序树被存储在具有ABTList数组类型的一个对象BST中,试编写出以下 算法。 1.初始化对象BST。 解: void InitBTree(ABTList BST) { //将树置空 BST[0].left=0; //建立空闲链接表 BST[0].right=1; for(int i=1;i<BTreeMaxSize-1;i++) BST[i].right=i+1;

BST[BTreeMaxSize-1].right=0; } 2.向二叉树排序树中插入一个元素。 解: void Insert(ANTList BST,int&t,const ElemType& item) //向数组中的二叉排序树插入一个元素item的递归算法,变参t初始指向树根结点 { if(t==0)//进行插入操作 { //取出一个空闲结点 int p=BST[0].right; if(p==0){ cerr<<"数组空间用完!"<<end1; exit(1); } //修改空闲链表的表头指针,使之指向下一个空闲结点 BST[0].right=BST[p].right; //生成新结点 BST[p].data=item; BST[p].left=BST[p].right=0; //把新结点插入到确定的位置 t=p; } else if(item.key<BST[t].data.key) Insert(BST,BST[t].left,item); //向左子树中插入元素 else Insert(BST,BST[t].right,item); //向右子树中插入元素 } void Insert(ABTList BST,const ElemType& item) //向数组中的二叉排序树插入一个元素item的非递归算法 { //为新元素寻找插入位置 int t=BST[0].left,parent=0; while(t!=0){ parent=t; if(item.key<BST[t].data.key) t=BST[t].left; else t=BST[t].right; }

//由item生成新结点并修改空闲链表的表头指针 int p=BST[0].right; if(p==0){ cerr<<"数组空间用完!"<<end1; exit(1); } BST[0].right=BST[p].right; BST[p].data=item; BST[p].left=BST[p].right=0; //将新结点插入到二叉排序树中的确定位置上 if(parent==0) BST[o].left=p; else if(item.key<BST[parent].data.key) BST[parent].left=p; else BST[parent].right=p; } 3.根据数组a中的n个元素建立二叉排序树。 解: void CreateBSTree(ABTList BST,ElemType a[],int n) //利用数组中的元素建立二叉排序树的算法 { for(int i=0;i<n;i++) Insert(BST,BST[0].left,a[i]); } 4.中序遍历二叉排序树。 解: void Inorder(ABTList BST,int t) //对数组中的二叉树进行中序遍历的递归算法 { if(t!=0){ Inorder(BST,BST[t].left); cout<<BST[t].data.key<<''; Inorder(BST,BST[t].right); } } void Inorder(ABTList BST) //对数组中的二叉树进行中序遍历的非递归算法 { int s[10];//定义用于存储结点指针的栈 int top=-1; //定义栈顶指针并赋初值使s栈为空

int p=BST[0].left;//定义指针p并使树根指针为它的初值 while(top=-1||p!=0) {//当栈非空或p指针非0时执行循环 while(p!=0){ top++; s[top]=p; p=BST[p].left; } if(top!=-1){ p=s[top]; top--; cout<<BST[p].data.key<<''; p=BST[p].right; } } } 5.写出一个完整程序调用上述算法。 解: #include<iostream.h> #include<stdlib.h> const int BTreeMaxSize=50; struct student{ int key; int rest; }; typedef student ElemType; //定义二叉排序树中元素的类型为student记录型 struct ABTreeNode{//定义二叉排序树的结点类型 ElemType data; int left,right; }; typedef ABTreeNode ABTList[BTreeMaxSize]; //定义保存二叉排序树的数组类型,各算法同上,在此省略 void main() { student a[8]={{36},{54},{25},{30},{43},{18},{50},{28}}; //为简单起见在每个元素中只给出关键字 ABTList bst; InitBTree(bst);//初始化数组bst //利用数组a在数组bst上建立一个二叉排序树 CreateBSTree(bst,a,8); cout<<"中序:"<<end1;

Inorder(bst,bst[0].left); cout<<end1; } 该程序的运行结果为: 中序: 18 25 28 30 36 43 50 54 类别:数据结构 .

.

第七章 图习 题 七

一、填空题 1.在一个图中,所有顶点的读数之和等于所有边数的 2 倍。 2.在一个具有n个顶点的无向完全图中,包含有 n(n-1)/2 条边,在一个具有n个顶点的所有 向完全图中,包含有 n(n-1) 条边。 3.在一个具有n个顶点的无向图中,要连通所有顶点则至少需要 n-1 条边。 4.表示图的三种存储结构为 邻接矩阵 、 邻接表 和 边集数组 。 5.对于一个具有n个顶点的图,若采用邻接矩阵表示,则其矩阵大小为 n2。 6.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别为 e 和 2e 条。 7.在有向图的邻接表和逆邻接表表示中,每个顶点邻接表分别链接着该点的所有出边 和 入边 结点。 8.对于一个具有n个顶点和e条边的有向图和无向图,若采用边集数组表示,则存于数组中的边数分别为 e 和 e 条。 9.对于一个具有n个顶点和e条边的无向图,当分别采用邻接矩阵,邻接表和边集数组表示时,求任一顶点 数的时间复杂度依次为 O(n) 、O(e/n) 和O(e)。 10.假定一个图具有n个顶点和e条边,则采用邻接矩阵、邻接表和边集数组表示时,其相应的空间复杂度 分别为O(n2)、O(n+e)和O(e)。 11.对用邻接矩阵表示的图进行任一种遍历时,其时间复杂度为O(n2),对用邻接表 表示的图进行任一遍历时,其时间复杂度为O(e) 。 12.对于图7-1(a)所示的无向图,假定用邻接矩阵表示,则从顶点v0开始进行深度优先搜索遍历得 到的顶点序列为0,1,4,2,5,3;从顶点v0开始进行广度优先搜索遍历得到的顶点序列 为0,1,2,3,4,5。 13.对于图7-1(b)所示的有向图,假定用邻接矩阵表示,则从顶点v0开始进行深度优先搜索遍历得 到的顶点序列为A,B,C,D,E;从顶点v0开始进行广度优先搜索遍历得到的顶点序列为 A,B,C,E,D。 14.对于一个有n个顶点和e条边的连通图,其生成树中的对点数和边数分别为 n 和n-1。 15.对于图7-5(a)所示的带权图,其最小生成树的权为 22 。 16.对于图7-5(a)所示的图,若从顶点v0出发,则按照普里姆算法生成的最小生成树中,依次得到 的各条边为(0,1)5,(1,3)3,(3,2)6,(1,4)8。 17.对于图7-5(a)所示的图,若按照克鲁斯卡算法产生最小生成树,则得到的各条边依次为(1,3)3,(0,1)5 ,(2,3)6,(1,4)8 。 18.假定用一给数组d[n]存储一个AOV网中用于拓朴排序的顶点入度,则值为0的元素被链接成为一个 栈 。 二、普通题 3.对于图7-25(a)和(b),按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得 到的顶点序列和按广度优先搜索遍历得到的顶点序列。 假定它们均采用邻接矩阵表示;假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序 链接的。

解:采用邻接矩阵表示得到的顶点序列如下表所示:采用邻接表表示得到的顶点序列如下表所示:画出最小生成树并求出它的权; 解:从顶点v0出发,按照普里姆法并入最小生成树中各边的次序写出各条边; 解:按照克鲁斯卡尔算法并入最小生成树中各边的次序写出各条边。 解: 图 深度优先序列 广度优先序列 (a) 0,1,2,8,3,4,5,6,7,9 0,1,4,2,7,3,8,6,5,9 (b) 0,1,2,5,8,4,7,3,6 0,1,3,4,2,6,7,5,8 图 深度优先序列 广度优先序列 (a) 0,4,3,8,9,5,6,7,1,2 0,4,1,3,7,2,8,6,9,5 (b) 0,4,7,5,8,3,6,1,2 0,4,3,1,7,5,6,2,8 4.对本章第3节中的dfsl算法做适当的修改,得到输出图的深度做出先生成树中各条边的算法。 解: void dfstree(adjmatrix GA,int i,int n) { visited[i]=True; for(int j=0;j<n;j++) if(i!=j&&GA[i][j]!=MaxValue&&!visited[j]) { cout<<'('<<i<<','<<j<<')'; cout<<GA[i][j]<<end1; dfstree(GA,j,n); } } 5.假定采用邻接矩阵表示,编写出进行深度优先遍历的非递归算法。 解: void dfss(adjmatrix GA,int i,int n) { stack s; Initstack(s); push(s,i); while(!StackEmpty(s)){ int k=pos(s); if(!visited[k]){ cout<<k<<''; visited[k]=True; for(int j=0;j<n;j++) if(k!=j&&GA[k][j]!=MaxValue&&!visited[j]) push(s,j); } } } 6.对于图7-26: 略 (0,1)6,(1,6)4,(6,2)9,(2,3)5,(3,4)10,(0,5)12 (1,6)4,(2,3)5,(0,1)6,(2,6)9,(3,4)10,(0,5)12 7.对于图7-27(图略),试给出一种拓朴序列,若在它的邻接表存储结构中,每个顶点邻接表中的 边结点都是按照终点序号从大到小链接的,则按此给出唯一一种拓朴序列。 解: 唯一一种拓朴序列:1,4,0,2,3,5,7,6,8,9 类别:数据结构 .

.

第八章查找习 题 八

一、单选题 1.以顺序查找方法从长度为n的线性表中查找一个元素时,平均查找长度为(n+1)/2,时间复 杂度为O(n) 。 2.以二分查找方法从长度为n的线性表中查找一个元素时,平均查找长度小于等于 ┍log2(n+1)┑ ,时间复杂度为O(log2n)。 3.以二分查找方法从长度为12的有序表中查找一个元素时,平均查找长度为37/12。 4.以二分查找方法查找一个线性表时,此线性表必须是顺序存储的有序表。 5.从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时,其查找长度 分别为 1 和 3 。 6.对于二分查找所对应的判定树,它即是一棵二叉搜索树,又是一棵理想平衡树 。 7.假守对长度n=50的有序表进行二分查找,则对应的判断树高度为6 ,判定树前5层的结点数 为 31 ,最后一层的结点数为 19 。 8.在索引表中,每个索引向至少包含有 索引值 域和 子表开始 域这两项。 9.假定一个线性表为(12,23,74,55,63,40,82,36),若按key%3条件进行划分,使得同一 余数的元素成为一个子表,则得到的三个子表分别为(12,63,36)、(55,40,82)和(23,74)。 10.假定一个线性表为("abcd","baabd","beef","cfg","ahij","bkwte","ccdt","aayb"), 若按照字符串的第一个字母进行划分,使得同一个字母被划分在一个子表中,则得到的a,b,c 三个子表的长度分别为 3 、 3 和 2 。 11.在索引表中,若一个索引项对应主表中的一条记录,则称此索引为 稠密 索引,若对应主 表中若干条记录,则称此索引为 稀疏 索引。 12.在稀疏索引表上进行二分查找时,若当前查找区间为空,则不是返回-1表示查找失败,而 是返回该区间的 下限值(即low值) 。 13.假定长度n=100的线性表进行索引查找,并假定每个子表的长度为n1/2,则进行索引查找的 平均查找长度为 11 ,时间复杂度为 O(n1/2)。 14.若对长度n=1000的线性表进行二级索引存储,每级索引表中的索引项是下一级20个记录的 索引,则一级索引表的长度为 500 ,二级索引表的长度为 25 . 15.在线性表的 散列 存储中,无常找到一个元素的前驱或后继元素.

16.在线性表的 链接 存储中,对每一个元素只能采用顺序查找. 17.假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函数,若分别采用线 性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为 2 和 4/3 . 18.假定要对长度n=100的线性表进行散列存储,并采用链接法处理冲突,则对于长度m=20的散列 表,每个散列地址的单链表的长度分别为 5 . 19.在线性表的散列存储中,装填因子α又称为装填系数,若用m表示散列表的长度,n表示待散列存 储的元素的个数,则α等于 n/m 。 20.在线性表的散列存储中,处理冲突有 开放定址法 和 链接法 两种方法。 21.对于线性表(18,25,63,50,42,32,90)进行散列存储时,若选用H(K)=K%9作为散列函数,则散 列地址为0的元素有 3 个,散列地址为5的元素有 2 个。 22.对于一个含有N个关键字的m阶B_树,其最小高度为Гlogm(N+1)┐,最大高度为1+—log—m/2— (N+1/2)—。 23.已知一棵3阶B_树中含有50个关键字,则该树的最小高度为 4 ,最大高度为 5 。 24.在一棵9阶的B_树上中,每个非树根结点的关键字数目最少为 4 个,最多为 8 个。 25.在一棵m阶B_树上,每个非树根结点的关健字数目最小为┌m/2┐-1 个,最多为 m-1 个,其子树 目最小为┌m/2┐,最多为 m 。 26.在一棵B_阶树中,所有叶子结点都处在 同一层 上,所有叶子结点中空指针等于所有 关键字 总数 加1。 27.在对m阶B_树插入元素的过程中,每向一个结点插入一个索引项(叶子结点中的索引项为关键字 和空指针)后,若该结点的索引项数等于 m 个,则必须把它分裂为 两 个结点。 28.在从m阶的B_树删除元素的过程中,当一个结点被删除掉一个索引项后,所含索引项等于┌m/2┐ -2个,并且它的左右兄弟结点中的索引项数均等于┌m/2┐-1个,则必须进行结点合并。 29.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度 增加1 。 30.从一棵B_树删除元素的过程中,若最终引起树根结点的合并,则新树比原树的高度 减少1 。 二、普通题 2.编写一个非递归算法,在稀疏有序索引表中二分查找出给定值K所对应的索引项,即索引值刚好大于 等于K的索引项,返回该索引项的star域的值,若查找失败则返回-1。 解: int Binsch(indexlist B,int m,IndexkeyType k) {

int low=0,hight=m=-1; while(low<=hight){ int mid=(low+hight)/2; if(k==B[mid].index) return B[mid].start); else if(k<B[mid].index) hight=mid-1; else low=mid+1; } if(low<m)return B[low].start; else return -1; } 5.假定有一个100×100的稀疏矩阵,其中1%的元素为非零元素,现要求对其非零元素进行散列存储 ,使之能够按照元素的行、列值存取矩阵元素(即元素的行、列值联合为元素的关键字),试采用除 留余数法构造散列函数和线性探查法处理冲突,分别写出散列表和查找散列表的算法。 分析:由题意可知,整个稀疏矩阵中非零元素的个数为100。为了散列存储这100个非零元素,需要 使用一个作为散列的一维数组,该数组中元素的类型应为: struct ElemType{ int row;//存储非零元素的行下标 int col;//存储非零元素的列下标 float val;//存储非零元素值 }; 假定用HT[m]表示这个散列,其中m为散列表的长度,若取装填因子为0.8左右,则令m为127为宜 (因为127为质数)。 按题目要求,需根据稀疏矩阵元素的行下标和列下标存取散列表中的元素,所以每个元素的行下 标和列下标同时为元素的关键字。假定用x表示一个非零元素,按除留余数法构造散列函数,并考虑 尽量让得到的散列地址分布均匀,所以采用的散列函数为: H(x)=(13*x.row+17*x.col)%m 解: 根据以上分析,建立散列表的算法如下: int Create(ElemType HT[],int m) //根据稀疏矩阵中100个非零元素建立长度为m的散列表 { int i,d,temp; ElemType x; for(i=0;i<m;i++) {//散列表初始化,使关键字域被置为-1,元素值域置为0 HT[i].row=-1; HT[i].col=-1; HT[i].val=0; } for(i=1;i<=100;i++)

{//每循环一次从键盘上输入一个非零元素并插入到散列表中 cout<<i<<":"; cin>>x.row>>x.col>>x.val;//输入非零元素 d=(13*x.row+17*x.col)%m;//计算初始散列地址 temp=d; while(HT[d].val!=0){//线性探查存储位置,此循环条件也可用HT[d].row!=-1或 //HT[d].col!=-1来代替 d=(d+1)%m; if(d==temp)//无插入位置返回0 return 0; } HT[d]=x;//非零元素存入下标d位置 } return 1;//全部元素插入成功后返回1 } 在散列表上进行查找的算法如下: int Search(ElemType HT[],int m,int row,int col) { //采用与插入时使用的同一散列函数计算散列地址 int d=(13*row+17*col)%m; //采用线性探查法查找行、列下标分别为row和col的元素 while(HT[d].val!=0) {//此循环条件也可用HT[d].row!=-1或HT[d].col!=-1代替 if(HT[d].row==row&&HT[d].col==col) return d;//查找成功后返回元素的下标 else d=(d+1)&m; if(d==temp) return -1; } //查找失败返回 -1 return -1; } 类别:数据结构 .3

.

第九章排序习 题 九

一、填空题 1.每次从无序表中取出一个元素,把它插入到有序表中的适当位置,此种排序方法叫做 插入 排序; 每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端,此种排序方法叫做 选择 排序。 2每次直接或通过基准元素间接比较两个元素,若出现逆序排列时就交换它们的位置,此种排序 方法叫做交换排序,每次使两个相邻的有序表合并成一个有序表的排序方法叫做二路归并排序。 3在直接选择排序中,记录比较次数的时间复杂度为 O(n2),记录移动次数的时间复 杂度为 O(n) 。 4在堆排序的过程中,对n个记录建立初始堆需要进行[n/2]次筛运算,由初始堆到堆排序结束, 需要对树根结点进行n-1次筛运算。 5在堆排序过程中,对任一分支结点进行筛运算的时间复杂度为O(log2n), 整个堆排序过程的时间复杂度为O(nlog2n)。 6假定一组的记录的排序码为(46,79,56,38,40,84),则利用堆排序方法建立的初始堆为(84,79,56, 38,40,46)。 7快速排序在平均情况下的时间复杂度为O(nlog2n),在最坏情况下的时间复杂度为 O(n2)。 8快速排序在平均情况下的空间复杂度为O(log2n),在最坏情况下的空间复杂度为 O(n) 。 9在快速排序方法中,进行每次划分时,是从当前待排序空间的 两端 向 中间 依次查找出处于逆 序的元素并交换之,最后将基准元素交换到一个确定位置,从而以该位置把当前区间划分为前后两个子区间。 10假定一组记录的排序码为(46,79,56,38,40,80),对其进行快速排序的一次划分的结果为[38 40]46[56 79 84]。 11假定一组记录的排序码为(46,79,56,38,40,80),对其进行快速排序过程中,对应二叉树的深度为 4 ,分支点结点数为 4 。 12在二路归并排中,对n个记录进行归并的趟数为 [log2n] 。 13在归并排序中,进行每趟归并的时间复杂度为O(n),整个排序过程的时间复杂度为O(nlog2n), 空间复杂度为 O(n) 。 14对20个记录进行归并排序时,共需要进行 5 趟归并,在第三趟归并时是把长度为 4 的有序表 两两归并为长度为 8 的有序表。 15假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中,第二趟归并后的结果

为[38 46 56 79][40 84]。 类别:数据结构 .


相关文章:
数据结构算法课程设计任务书
(3)参考文献: 1)数据结构实用教程(第二版) 徐孝凯编著 2)谭浩强,C 程序设计...而在完成这次试验时也出现了很多问 题,例如,程序设计的界面不够好,以及忘记...
数据结构课程设计任务书
(第三版)》 ,谭浩强,清华大学出版社,2005 参考资料 年2月 [4] 《数据结构实用教程》 ,徐孝凯,清华大学出版社,2006 年 8月 [5] 《数据结构》 语言版) (...
2012-9-12《数据结构》课程学习指导_吕洁
2012 年秋季学期“数据结构”课程学习指导课件中使用的教材: 数据结构实用教程 (第二版) 》 徐孝凯 编著 清华大学 《 出版社 2006 年 9 月 第二版 参考书目:...
2010年春季学期《数据结构》课程学习指导
2010 年春季学期“数据结构”课程学习指导 季学期“数据结构”课件中使用的教材: 《 第二版) 课件中使用的教材: 数据结构实用教程 (第二版徐孝凯 编著 ...
《数据结构》课程教学大纲
专业基础课 学时:64 (英文) :Data Structure 适用层次:专升本 学分:4 一、...(1)数据结构实用教程(第二版) 作者:徐孝凯 编著 出版社:清华大学出版社 出版...
《数据结构》教案
数据结构实用教程(第二版)》,徐孝凯编著,清华大学出版社 2006 《数据结构辅导与提高实用教程(第二版)》,徐孝凯,清华大学出版社 2003 《数据结构》,谢楚屏等,...
《数据结构课程实验》教材第一次(1月)上网程序
此电子版由徐孝凯提供,受版权保护,只供下载者本人配合《数据结构实用教程》《数、 据结构课程实验》或《数据结构实用教程习题参考解答》三本教材使用,不得以任何...
数据结构与算法分析课程标准
数据结构这一门课的内容不仅是一般程序 《数据结构与算法分析 B》课程标准一、...2001 年 2 月 徐孝凯:《数据结构实用教程(第二版),清华大学出版社,2006 年 ...
数据结构课程设计拯救007
《数据结构与算法》. 北京?高等教育出版 社? 2004 [4] 徐孝凯. 《数据结构实用教程?第二版?》. 北京?清华大学出版社? 2006 附录 附录Ⅰ 为了记录 007 跳过...
数据结构报告
[5] 徐孝凯.数据结构实用教程[M].清华大学出版社,2006. 8 沈阳航空航天大学...课设报告 数据结构 暂无评价 46页 免费 数据结构实现报告答案 暂无评价 27页 ...
更多相关标签: