《数据结构与算法（徐凤生）》习题答案

《数据结构与算法》

习题答案

目录

第1章 —————————————————— 2

第2章 —————————————————— 7 第3章 —————————————————— 13 第4章 —————————————————— 21 第5章 —————————————————— 26 第6章 —————————————————— 32 第7章 —————————————————— 42 第8章 —————————————————— 54 第9章 —————————————————— 60 第10章 ——————————————————64

2

习题1

1.解释下列术语：数据、数据元素、数据对象、数据结构。

解：数据是用于描述客观事物的数值、字符以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合，是计算机操作的对象的总称。

数据元素是数据的基本单位，它是数据中的一个“个体”。有时，一个数据元素可有若干数据项组成，。数据项是数据的不可分割的最小单位。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。 数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合。

2.数据类型和抽象数据类型是如何定义的？两者有何异同？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？

解：数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如，C语言中的整型变量，其值为某个区间上的整数(依赖于机器)，定义在其上的操作为加、减、乘、除和取模等算术运算。

抽象数据类型(Abstract Data Type，简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，“整数”是一个抽象数据类型，其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。

抽象数据类型和数据类型实质上是一个概念，只是抽象数据类型的范围更广，除了已有的数据类型外，抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。ADT的定义取决于它的一组逻辑特性，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部的使用。

抽象数据类型的最重要的特点是抽象和信息隐蔽。抽象的本质是抽取反映问题本质的东西，忽略非本质的细节，从而使所设计的数据结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐蔽数据存储和操作实现的细节，使用者仅需了解抽象操作，或界面服务，通过界面中的服务来访问这些数据。

一个含抽象数据类型的软件模块通常应包含定义、表示和实现三部分。 3.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 解：数据元素之间的关系在计算机中有四种不同的表示方法：

(1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。

(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。

(3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。

(4)哈希(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不

3

能顺序存储，也不能折半存取。

4.简述数据结构的三个层次、五个要素。

解：数据结构的三个层次是指抽象、实现和评价三个层次，五个要素是指逻辑结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面。

5.举一个数据结构的例子，说明其逻辑结构、存储结构及其运算三个方面的内容。并说明数据的逻辑结构、存储结构及其运算之间的关系。

解：例如复数数据结构，其逻辑结构是复数的表示，而存储结构是指复数在计算机内的表示，运算是指对复数初始化、相加等操作。

数据的逻辑结构反映数据元素之间的逻辑关系。数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。

6.设n为整数，试给出下列各程序段中标号为@的语句的频度。 （1）i=1; while(i

（3）i=1;k=0; while(i<=n-1){ i++; @ k+=10*i; }

（4）i=1;j=0; while(i+j<=n){ @ if(i>j)j++;

else i++;

}

（5）x=n;y=0;//n是不小于1的常数 while(x>=(y+1)*(y+1)){ @ y++; }

（6）x=91;y=100;

4

while(y>0){

@ if(x>100){x-=10;y--;}

else x++;

} 解：（1）?

n?1n?1?；（2）n-1；（3）n-1；（4）??；（5）?n?；（6）100 227.调用下列C函数f(n)，回答下列问题：

（1）试指出f(n)值的大小，并写出f(n)值的推导过程。 （2）假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。 int f(int n){ int i,j,k,sum=0; for(i=1;ii-1;j--)

for(k=1;k

return (sum); }

解：第一层for循环判断n+1次，往下执行n次，第二层for执行次数为(n+(n-1)+(n-1)+?+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：

i= 1 2 3 ? n j=n n n n ? n j=n-1 n-1 n-1 n-1 ? ? ? ? j=3 3 3 3 j=2 2 2 j=1 1

执行次数为(1+2+?+n)+(2+3+?+n)+?+n=n*n(n+1)/2-n(n*n-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15，sum=29，sum=41，sum=50，sum=55(每个sum占一行)。

8.试写一算法，从小到大依次输出顺序读入的3个整数x、y和z的值。 解：void print_descending(int x,int y,int z){//按从大到小顺序输出三个数

int temp;

scanf(\ if(x

5

} }

13.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 解：

void Delete(LinkList &L){ LNode *p,*q,*pre; p=L->next;pre=L;q=p; while(p->next!=NULL){ }

pre->next=q->next; delete q; }

14.已知两个单链表La和Lb，其元素递增排列。编写一算法，将La和Lb归并成一个单链表Lc，其元素递减排列（允许表中有相同的元素），要求不另辟新的空间。

解：

void interaction(LinkList &La, LinkList Lb){ LNode *pa,*pb,*s; pa=La->next; pb=Lb->next; La->next=NULL; delete Lb; while(pa&&pb)

if(pa->datadata){s=pa;pa=pa->next;s->next=La->next;La->next=s;} else {s=pb;pb=pb->next;s->next=La->next;La->next=s;}

if(p->next->datadata){pre=p; q=p->next;} p=p->next;

while(pa){s=pa;pa=pa->next;s->next=La->next;La->next=s;} while(pb){s=pb;pb=pb->next;s->next=La->next;La->next=s;} }

15.设以带头结点的双向循环链表表示的线性表L?(a1,a2,?,ai?1,ai,ai?1,?,an)。试写一时间复杂度为O(n)的算法，将L改造为L?(a1,a3,?,an,?,a4,a2)。

解：

void OEReform(CirDuLinkList &L){ DuLNode *p; p=L->next;

11

while(p->next!=L&&p->next->next!=L){ }

if(p->next==L)p->next=L->prior->prior; else p->next=L->prior; p=p->next;

while(p->prior->prior!=L){ }

p->next=L;

for(p=L; p->next!=L; p=p->next)p->next->prior=p; L->prior=p; }

16.设有一双向循环链表，每个结点除有prior、data和next三个域外，还有一个访问频度域frep。在链表被起用之前，频度域frep的值为0，而每当对链表进行一次LocateElem(L，e)的操作后，被访问的结点的频度域frep的值增1，同时调整链表中结点之间的顺序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试写出符合上述要求的LocateElem操作的算法。

p->next=p->prior->prior; p=p->next;

p->next=p->next->next; p=p->next;

解：

void LocateElem(CirDuLinkList &L,int x){

DuLNode *p=L->next,*q; while(p->data!=x&&p)p=p->next; if(p){ } }

12

p->frep++; q=p->prior;

while(q->frepfrep&&q!=L) q=q->prior; if(q!=p->prior){

p->prior->next=p->next;p->next->prior=p->prior; q->next->prior=p;p->next=q->next; q->next=p;p->prior=q;

}

习题3

1.名词解释：栈、队列、循环队列。

解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。

队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最后插入的元素最先删除，故栈也称先进先出表。最先入队的元素最先删除，故队列也称先进先出表。

用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。

2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。

解：输入序列为1，2，3，4，5，6，不能得到4，3，5，6，1，2，其理由是：输出序列最后两个元素是1，2，前面四个元素（4，3，5，6）得到后，栈中元素剩下1，2，且2在栈顶，栈底元素1不可能在栈顶元素2出栈之前出栈。

得到序列1，3，5，4，2，6的过程是：1入栈并出栈；然后2和3依次入栈，3出栈，部分输出序列是1，3；紧接着4和5入栈，5，4和2依次出栈，此时输出序列为1，3，5，4，2；最后6入栈并出栈，得到最终结果序列是1，3，5，4，2，6。

3.试证明：若借助栈由输入序列1，2，?，n得到序列p1，p2，?，pn(它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形：存在着i

解：如果ipj的情况，则说明要将pj压到pi之上，也就是在pj出栈之后pi才能出栈。这说明，对于i

4.当函数f递归调用自身时，函数f内定义的局部变量在函数f的2次调用期间是否占用同一数据区？为什么？

解：函数f递归调用自身时，函数f内定义的局部变量在函数f的2次调用期间不占用同一数据区。每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。

5.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值。 解：循环队列的数据结构略。 typedef struct{ ElemType *elem; int front; int rear; }SqQueue,Q;

13

（1）初始状态: Q.front=Q.rear=0; （2）队列空: Q.front=Q.rear=0;

（3）队列满: Q.front=(Q.rear+1)%MAXSIZE;

6.设一个双端队列，元素进入该队列的次序为1，2，3，4.求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。

解：既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是：4，2，3，1。

7.简述以下算法的功能。 (1)void algo1(Stack S){ int i,n,A[255]; n=0;

while(!StackEmpty(S)){n++;Pop(S,A[n]);}; for(i=1;i<=n;i++)Push(S,A[i]); }

(2)void algo2(Stack S,int e){ Stack T;int d;

InitStack(T);

while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);} while(!StackEmpty(T)){Pop(T,d);Push(S,d);} }

(3)void algo3(Queue &Q){//栈和队列的元素类型均为int Stack S;int d;

InitStack(T);

while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);} while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);} }

解：（1）将栈中元素逆置。 （2）将栈中的0元素删除。 （3）将队列中元素逆置。

8.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中不含字符@，且序列2是序列1的逆序列。

解：

int IsReverse(){//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 SqStack s; char c,x;

14

InitStack(s);

while((c=getchar())!='&')Push(s,c); while((c=getchar())!='@'){ }

if(!StackEmpty(s))return 0; return 1; }

9.在火车调度站的入口处有n节硬席或软席车厢(分别以H和S表示)等待调度，试写一算法，输出对这n节车厢进行调度的操作(即入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。

解：typedef char SS[MAX];

void Train_arrange(SS &train){//这里用字符串train表示火车,'H'表示硬席,'S'表示软席 SqStack s; char *p,*q,c; p=train; q=train; InitStack(s); while(*p){ }

while(!StackEmpty(s)){ } }

10.试写出求递归函数F(n)的递归算法，并消除递归：

Pop(s,c);

*(q++)=c;//把'H'接在后部

if(*p=='H')Push(s,*p);//把'H'存入栈中 else *(q++)=*p; //把'S'调到前部 p++;

if(StackEmpty(s))return 0; Pop(s,x);

if(x!=c)return 0;

n?0?n?1 F(n)???n?F(n/2)n?0解：

int F_recursive(int n,int &s){//递归算法 if(n<0) return ERROR;

15

习题4

1.名词解释：串、空串、空格串、子串。

解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。

空串是不含任何字符的串，其长度为0。

空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。 串中任意连续的若干字符组成的子序列称为该串的子串。

'\“ab?abcaabcbca?a”“caab”“bcb”2.已知三个字符串分别为S?，S?，S?。利用串的基

“caabcbca?aca?a”本运算得到结果串为S?，要求写出得到结果串S3所用的函数及执行算法。

'\“caabcbca?a”“ca?a”解：串S可看作由以下两部分组成：和，设这两部分分别叫串s1和s2，

'\要设法从S、S、S中得到这两部分，然后使用连接操作连接s1和s2得到S。

i=index();//

s1=substr(S,i,length(S)-i+1);//取出串s1

'\'\“bcb”“ca?a”j=index(S,S);//求串S在串S中的起始位置，S串中后是

s2=substr(S,j+3,length(S)-j-2);//形成串s2

\\S'\=concat(s1,s2);

3.已知字符串S1中存放一段英文，写出算法format(S1,S2,S3,n)，将其按给定的长度n格式化成两端对齐的字符串S2，其多余的字符存入S3。

解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n格式化为两端对齐的字符串”，即长度为n且首尾字符不能为空格字符。算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n，第n个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。

void format(char *S1,char *S2,char *S3,int n){ char *p=S1,*q=S2; int i=0;

while(*p!= '\\0'&&*p==' ')p++;//滤掉S1左端空格

if(*p== '\\0'){printf(\字符串S1为空串或空格串\\n\

while(*p!= '\\0'&&i

p--;//p指针也后退

while(*p!= '\\0'&&*p==' ')p++;//往后查找一个非空格字符作为串S2的尾字符 if(*p== '\\0'){printf(\串S1没有%d个两端对齐的字符串\\n\*q=*p;//字符串S2最后一个非空字符

21

}

*(++q)= '\\0';//S2字符串结束标记

q=S3;p++;//将S1串其余部分送字符串S3 while(*p!= '\\0'){*q=*p;q++;p++;} *q= '\\0';//置串S3结束标记 }

4.假设采用定长顺序存储结构表示串，编写算法，求串S的含不同字符的总数和每个字符的个数。 解：typedef struct { char ch; int num;

}mytype;

void StrAnalyze(SString S){//统计串S中字符的种类和个数 int i,j; char c;

mytype T[100]; //用结构数组T存储统计结果 for(i=1;i<=S[0]+1;i++)T[i-1].ch='\\0'; for(i=1;i<=S[0];i++){

c=S[i];j=0;

while(T[j].ch&&T[j].ch!=c)j++; //查找当前字符c是否已记录过 if(T[j].ch) T[j].num++; else {T[j].ch=c;T[j].num=1;}

}//for

for(j=0;T[j].ch;j++)

printf(\

}//StrAnalyze

5.假设采用定长顺序存储结构表示串，编写算法，从串S中删除所有和串T相同的子串。 解：

void SubString_Delete(SString &s,SString t,int &num){//从串s中删除所有与t相同的子串,num为删除次数

int i,j,k;

for(i=1;i<=s[0]-t[0]+1;i++){

for(j=1;j<=t[0]&&s[i+j-1]==t[j];j++); if(j>t[0]){//找到了与t匹配的子串

for(k=i;k<=s[0]-t[0];k++)s[k]=s[k+t[0]]; //左移删除 s[0]-=t[0];num++;

22

}

}//for

}//Delete_SubString

6.编写算法，实现堆存储结构的串的置换操作Replace(&S,T,V)。

解：void HString_Replace(HString &S,HString T,HString V,int & num){//堆结构串上的置换操作,返回置换次数

int i,j,k,m;

for(i=0;i<=S.length-T.length;i++){

for(j=i,k=0;k

if(T.length==V.length)

for(m=1;m<=T.length;m++) S.ch[i+m-1]=V.ch[m-1]; //新子串长度与原子串相同时:直接替换

else if(T.length=i+T.length;m--)

S.ch[m+V.length-T.length]=S.ch[m];

for(m=0;m

}

else{ //新子串长度小于原子串时:先将后部左移 }

S.length+=V.length-T.length; i+=V.length;num++;

for(m=i+V.length;m

S.ch[m]=S.ch[m-V.length+T.length];

for(m=0;m

}//if

}//for

}//HString_Replace

7.编写算法，实现堆存储结构的串基本操作Concat(&S,S1,S2)。

解：void HString_Concat(HString s1,HString s2,HString &t) {//将堆结构表示的串s1和s2连接为新串t

int i,j;

if(t.ch) free(t.ch);

t.ch=new char[s1.length+s2.length];

for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];

23

for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1]; t.length=s1.length+s2.length; }//HString_Concat

8.假设以块链结构表示串，试编写判别给定字符串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S))。

解：int LString_Palindrome(LString L) {//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0

InitStack(S);

p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k<=S.curlen;k++){

if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串 else if(k>(S.curlen+1)/2){

Pop(S,c); //将后半段的字符与栈中的元素相匹配 if(p->ch[i]!=c) return 0; //失配 }

if(++i==CHUNKSIZE) { //转到下一个元素,当为块中最后一个元素时,转到下一块 p=p->next; i=0; } }//for

return 1; //成功匹配 }//LString_Palindrome

“abcabaa”“abcaabbabcabaacbacba”9.令S?，T?，试分别求出它们的next函数值和nextval函数值。

解：

j 串S next[j] nextval[j] 1 a 0 0 2 b 1 1 3 c 1 1 4 a 1 0 5 b 2 1 6 a 3 3 7 a 2 2

J 串T next[j] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 a b c a a b b a b c 0 1 1 1 2 2 3 1 2 3 a 4 0 b 5 5 a 3 3 a 2 2 c 2 2 b 1 1 a 1 0 c b 2 1 2 1 a 1 0 Nextval[j] 0 1 1 0 2 1 3 0 1 1 “adbadabbaabadabbadada”“adabbadada”10.已知主串S?，模式串T?，写出模式串的nextval函

24

数值，并由此画出KMP算法匹配的全过程。

解：

j 串T nextval[j] 1 2 3 4 5 6 7 8 9 a d a b b a d a d 0 1 0 2 1 0 1 0 4 10 a 0 匹配过程略。

25

本文来源：https://www.bwwdw.com/article/b2gt.html