数据结构讲义严蔚敏版第4章

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。

本章主要介绍了数据结构的基本概念和发展历程。

【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。

本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。

【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。

本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。

2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。

本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。

【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。

本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。

【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。

本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。

【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。

本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。

2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。

本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。

【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。

本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。

【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。

本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。

串-第4章-《数据结构题集》答案解析-严蔚敏吴伟民版习题集解析部分第4章串——《数据结构题集》-严蔚敏.吴伟民版源码使⽤说明链接☛☛☛课本源码合辑链接☛☛☛习题集全解析链接☛☛☛相关测试数据下载链接☛本习题⽂档的存放⽬录：数据结构\▼配套习题解析\▼04 串⽂档中源码的存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04源码测试数据存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04\Data⼀、基础知识题4.1❶简述空串和空格串（或称空格符串）的区别。

4.2❷对于教科书4.1节中所述串的各个基本操作，讨论是否可由其他基本操作构造⽽得，如何构造？4.3❶设s = ‘I AM A STUDENT’，t = ‘GOOD’，q = ‘WORKER’。

求：StrLength(s)，StrLength(t)，SubString(s, 8, 7)，SubString(t, 2, 1)，Index(s, ‘A’)，Index(s, t)，Replace(s, ‘STUDENT’, q)，Concat(SubString(s, 6, 2), Concat(t, SubString(s, 7, 8)))。

4.4❶已知下列字符串a = ‘THIS’,　f = ‘A SAMPLE’,　c = ‘GOOD’,　d = ‘NE’,b = ‘ ’.s = Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))),t = Replace(f, SubString(f, 3, 6), c),u = Concat(SubString(c, 3, 1), d),g = ‘IS’,v = Concat(s, Concat(b, Concat(t, Concat(b, u)))),试问：s，t，v，StrLength(s)，Index(v, g)，Index(u, g)各是什么？4.5❶试问执⾏以下函数会产⽣怎样的输出结果？void demonstrate(){StrAssign(s, ‘THIS IS A BOOK’);Replace(s, SubString(s, 3, 7), ‘ESE ARE’);StrAssign(t, Concat(s, ‘S’));StrAssign(u, ‘XYXYXYXYXYXY’);StrAssign(v, SubString(u, 6, 3));StrAssign(w, ‘W’);printf(‘t=’, t, ‘v=’, v, ‘u=’, Replace(u, v, w));}//demonstrate4.6❷已知：s = ‘(XYZ)+*’,t = ‘(X+Z)*Y’。

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r{StrAssign(r,''); //初始化r为空串for(i=Strlen(s);i;i--){StrAssign(c,SubString(s,i,1));StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中}}//String_Reverse4.11void 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<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现if(i==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_Subtract4.12int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数{for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串{ //分别把T的前面和后面部分保存为head和tailStrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));StrAssign(S,Concat(head,V));StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串i+=Strlen(V); //当前指针跳到插入串以后n++;}//ifreturn n;}//Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place',T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?4.13int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++)if(!StrCompare(SubString(s,i,Strlen(t)),t)){StrAssign(head,SubString(S,1,i-1));StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));StrAssign(S,Concat(head,tail)); //把head,tail连接为新串n++;}//ifreturn n,}//Delete_SubString4.14Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new{Initstack(s); //s的元素为Stringtype类型for(i=1;i<=Strlen(str);i++){r=SubString(str,i,1);if(r为字母) push(s,r);else{if(StackEmpty(s)) return ERROR;pop(s,a);if(StackEmpty(s)) return ERROR;pop(s,b);StrAssign(t,Concat(r,b));StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c push(s,c);}}//forpop(s,new);if(!StackEmpty(s)) return ERROR;return OK;}//NiBoLan_to_BoLan分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.4.15void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本{for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i];}//StrAssign4.16char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数{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];}//StrCompare4.17int 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]<V[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}//forreturn n;}//String_Replace4.18typedef struct {char ch;int num;} mytype;void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数{mytype T[MAXSIZE]; //用结构数组T存储统计结果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]={c,1};}//forfor(j=0;T[j].ch;j++)printf("%c: %d\n",T[j].ch,T[j].num);}//StrAnalyze4.19void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r{r[0]=0;for(i=1;i<=s[0];i++){c=s[i];for(j=1;j<i&&s[j]!=c;j++); //判断s的当前字符c是否第一次出现if(i==j){for(k=1;k<=t[0]&&t[k]!=c;k++); //判断当前字符是否包含在t中if(k>t[0]) r[++r[0]]=c;}}//for}//Subtract_String4.20int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数{for(n=0,i=1;i<=s[0]-t[0]+1;i++){for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++);if(j>m) //找到了与t匹配的子串{for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除s[0]-=t[0];n++;}}//forreturn n;}//Delete_SubString4.21typedef 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;}//StringAssignvoid 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;}//StringCopychar StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t 时返回负数{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;}//StringCompareint StringLen(LString s)//求串s的长度(元素个数){for(i=0,p=s->next;p;p=p->next,i++);return i;}//StringLenLString * 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 //复制串sfor(r=t->next;r;r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;}//for //复制串tq->next=NULL;return p;}//ConcatLString * 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所对应的结点指针rfor(i=1;i<=len;i++,r=r->next){q->next=(LStrNode*)malloc(sizeof(LStrNode));q=q->next;q->ch=r->ch;} //复制串tq->next=NULL;return p;}//Sub_String4.22void LString_Concat(LString &t,LString &s,char c)//用块链存储结构,把串s插入到串t的字符c之后{p=t.head;while(p&&!(i=Find_Char(p,c))) p=p->next; //查找字符cif(!p) //没找到{t.tail->next=s.head;t.tail=s.tail; //把s连接在t的后面}else{q=p->next;r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个for(j=0;j<i;j++) r->ch[j]='#'; //原结点p包含c及其以前的部分for(j=i;j<CHUNKSIZE;j++) //新结点r包含c以后的部分{r->ch[j]=p->ch[j];p->ch[j]='#'; //p的后半部分和r的前半部分的字符改为无效字符'#'}p->next=s.head;s.tail->next=r;r->next=q; //把串s插入到结点p和r之间}//elset.curlen+=s.curlen; //修改串长s.curlen=0;}//LString_Concatint Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0{for(i=0;i<CHUNKSIZE&&p->ch[i]!=c;i++);if(i==CHUNKSIZE) return 0;else return i+1;}//Find_Char4.23int 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;}}//forreturn 1; //成功匹配}//LString_Palindrome4.24void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t{if(t.ch) free(t.ch);t.ch=malloc((s1.length+s2.length)*sizeof(char));for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];t.length=s1.length+s2.length;}//HString_Concat4.25int 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<T.length&&S.ch[j]==T.ch[k];j++,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<V.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<V.length;l++)S[i+l]=V[l];}else //新子串长度小于原子串时:先将后部左移{for(l=i+V.length;l<S.length+V.length-T.length;l++)S.ch[l]=S.ch[l-V.length+T.length];for(l=0;l<V.length;l++)S[i+l]=V[l];}S.length+=V.length-T.length;i+=V.length;n++;}//if}//forreturn n;}//HString_Replace4.26Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前{if(pos<1) return ERROR;if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));for(i=S.length-1;i>=pos-1;i--)S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置for(i=0;i<T.length;i++)S.ch[pos+i-1]=T.ch[pos]; //插入串TS.length+=T.length;return OK;}//HString_Insert4.27int Index_New(Stringtype s,Stringtype t)//改进的定位算法{i=1;j=1;while(i<=s[0]&&j<=t[0]){if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]])){ //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个i=i+j-2;j=1;}else{i++;j++;}}//whileif(j>t[0]) return i-t[0];}//Index_New4.28void LGet_next(LString &T)//链串上的get_next算法{p=T->succ;p->next=T;q=T;while(p->succ){if(q==T||p->data==q->data){p=p->succ;q=q->succ;p->next=q;}else q=q->next;}//while}//LGet_next4.29LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针{p=pos;q=T->succ;while(p&&q){if(q==T||p->chdata==q->chdata){p=p->succ;q=q->succ;}else q=q->next;}//whileif(!q){for(i=1;i<=Strlen(T);i++)p=p->next;return p;} //发现匹配后,要往回找子串的头return NULL;}//LIndex_KMP4.30void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度{for(maxlen=0,i=1;i<S[0];i++)//串S2向右移i格{for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动{if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数else k=0; //失配时k归零if(k>maxlen) //发现了比以前发现的更长的重复子串{lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录}}//for}//forif(maxlen){printf("Longest Repeating Substring length:%d\n",maxlen);printf("Position1:%d Position 2:%d\n",lrs1,lrs2);}else printf("No Repeating Substring found!\n");}//Get_LRepSub分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).4.31void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度{if(S[0]>=T[0]){StrAssign(A,S);StrAssign(B,T);}else{StrAssign(A,T);StrAssign(B,S);} //为简化设计,令S和T中较长的那个为A,较短的那个为Bfor(maxlen=0,i=1-B[0];i<A[0];i++){if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正{jmin=1;jmax=i+B[0];}//B有一部分在A左端的左边else if(i>A[0]-B[0]){jmin=i;jmax=A[0];}//B有一部分在A右端的右边else{jmin=i;jmax=i+B[0];}//B在A左右两端之间.//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.for(k=0,j=jmin;j<=jmax;j++){if(A[j]==B[j-i]) k++;else k=0;if(k>maxlen){lps1=j-k+1;lps2=j-i-k+1;maxlen=k; }}//for}//forif(maxlen){if(S[0]>=T[0]){。

《数据结构（C语言版第2版）》（严蔚敏著）第四章练习题答案第4章串、数组和广义表1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若答案：B（2）串下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储答案：B解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。

（3）串“ababaaababaa”的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345答案：C（4）串“ababaabab”的nextval为（）。

A．010104101B．010102101 C．010100011 D．010101011答案：A（5）串的长度是指（）。

A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数答案：B解释：串中字符的数目称为串的长度。

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。

A．808 B．818 C．1010 D．1020答案：B解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。

（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。

A．BA+141 B．BA+180 C．BA+222 D．BA+225答案：B解释：以列序为主，则LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。

第一章绪论一、选择题1.组成数据的基本单位是A数据项B数据类型C数据元素D数据变量2.数据结构是研究数据的以及它们之间的相互关系;A理想结构,物理结构B理想结构,抽象结构C物理结构,逻辑结构D抽象结构,逻辑结构3.在数据结构中,从逻辑上可以把数据结构分成A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科;① A数据元素B计算方法C逻辑存储D数据映像② A结构B关系C运算D算法5.算法分析的目的是;A 找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性6.计算机算法指的是①,它必须具备输入、输出和②等5个特性;① A计算方法B排序方法C解决问题的有限运算序列D调度方法② A可执行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构;2.算法就是程序;3.数据元素是数据的最小单位;4.算法的五个特性为：有穷性、输入、输出、完成性和确定性;5.算法的时间复杂度取决于问题的规模和待处理数据的初态;三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____;2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点;3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________;4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________;5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系;6.算法的五个重要特性是_______、_______、______、_______、_______;7.数据结构的三要素是指______、_______和________;8.链式存储结构与顺序存储结构相比较,主要优点是________________________________;9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构;四、算法分析题1.求下列算法段的语句频度及时间复杂度参考答案：一、选择题1. C 3. C 4. A、B 5. C 、B二、判断题:1、√2、×3、×4、×5、√三、填空题1、线性、树形、图形、集合；非线性网状2、没有；1；没有；13、前驱；1；后继；任意多个4、任意多个5、一对一；一对多；多对多6、有穷性；确定性；可行性；输入；输出7、数据元素；逻辑结构；存储结构8、插入、删除、合并等操作较方便9、顺序存储；链式存储四、算法分析题fori=1; i<=n; i++forj =1; j <=i ; j++x=x+1;分析：该算法为一个二重循环,执行次数为内、外循环次数相乘,但内循环次数不固定,与外循环有关,因些,时间频度Tn=1+2+3+…+n=nn+1/2有1/4≤Tn/n2≤1,故它的时间复杂度为Ｏn2, 即Ｔn与n2 数量级相同; 2、分析下列算法段的时间频度及时间复杂度for i=1;i<=n;i++for j=1;j<=i;j++for k=1;k<=j;k++x=i+j-k;分析算法规律可知时间频度Tn=1+1+2+1+2+3+...+1+2+3+…+n由于有1/6 ≤ Tn/ n3 ≤1,故时间复杂度为Ｏn3第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是A110 B108C100 D1202. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素;A64B63 C D73.线性表采用链式存储结构时,其地址;A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续与否均可以4. 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行As->next=p;p->next=s; B s->next=p->next;p->next=s;Cs->next=p->next;p=s; Dp->next=s;s->next=p;5.在一个单链表中,若删除p所指结点的后续结点,则执行Ap->next=p->next->next; Bp=p->next; p->next=p->next->next;Cp->next=p->next; Dp =p->next->next;6.下列有关线性表的叙述中,正确的是A线性表中的元素之间隔是线性关系B线性表中至少有一个元素C线性表中任何一个元素有且仅有一个直接前趋D线性表中任何一个元素有且仅有一个直接后继7.线性表是具有n个的有限序列n≠0A表元素B字符C数据元素D数据项二、判断题1.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同;2.如果没有提供指针类型的语言,就无法构造链式结构;3.线性结构的特点是只有一个结点没有前驱,只有一个结点没有后继,其余的结点只有一个前驱和后继;4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值;5.要想删除p指针的后继结点,我们应该执行q=p->next ；p->next=q->next；freeq;三、填空题1.已知P为单链表中的非首尾结点,在P结点后插入S结点的语句为：_______________________ ;2.顺序表中逻辑上相邻的元素物理位置相邻, 单链表中逻辑上相邻的元素物理位置_________相邻;3.线性表L＝a1,a2,...,an采用顺序存储,假定在不同的n＋1个位置上插入的概率相同,则插入一个新元素平均需要移动的元素个数是________________________4.在非空双向循环链表中,在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;______________________;5.已知L是无表头结点的单链表,是从下列提供的答案中选择合适的语句序列,分别实现：1表尾插入s结点的语句序列是_______________________________2 表尾插入s结点的语句序列是_______________________________1.p->next=s;2.p=L;3.L=s;4.p->next=s->next;5.s->next=p->next;6.s->next=L;7.s->next=null;8.whilep->next= Q p=p-next;9.whilep->next=null p=p->next;四、算法设计题1.试编写一个求已知单链表的数据域的平均值的函数数据域数据类型为整型;2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数;3.某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价格、数量和链指针三个域;现出库销售m台价格为h的电视机,试编写算法修改原链表;4.某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价格、数量和链指针三个域;现新到m台价格为h的电视机,试编写算法修改原链表;5.线性表中的元素值按递增有序排列,针对顺序表和循环链表两种不同的存储方式,分别编写C函数删除线性表中值介于a与ba≤b之间的元素;6.设A=a0,a1,a2,...,an-1,B=b0,b1,b2,...,bm-1是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数;若n=m,且ai= bi 0≤i<n ,则A=B；若n<m ,且ai=bi 0≤i<n ,则A<B；若存在一个j, j<m ,j<n ,且ai=bi 0≤i<j , 若aj<bj,则A<B,否则A>B;试编写一个比较A和B的C函数,该函数返回-1或0或1,分别表示A<B或A=B或A>B;7.试编写算法,删除双向循环链表中第k个结点;8.线性表由前后两部分性质不同的元素组成a0,a1,...,an-1,b0,b1,...,bm-1,m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成b0,b1,...,bm-1,a0,a1,...,an-1,分析两种存储方式下算法的时间和空间复杂度;9.用循环链表作线性表a0,a1,...,an-1和b0,b1,...,bm-1的存储结构,头指针分别为ah和bh,设计C函数,把两个线性表合并成形如a0,b0,a1,b1,…的线性表,要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度;10.试写出将一个线性表分解为两个带有头结点的循环链表,并将两个循环链表的长度放在各自的头结点的数据域中的C函数;其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中;11.试写出把线性链表改为循环链表的C函数;12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数;参考答案：一、选择题1. B 3. D 4. B 5. A 7、C二、判断题:参考答案：1、×2、√3、×4、×5、√三、填空题1、s->next=p->next; p->next=s;2、一定；不一定3、n/24、q->prior=p;5、16 32 2 91 7四、算法设计题1、include ""include ""typedef struct node{int data;struct node link;}NODE;int averNODE head{int i=0,sum=0,ave; NODE p;p=head;whilep=NULL{p=p->link;++i;sum=sum+p->data;}ave=sum/i;return ave;}2、include ""include ""typedef struct node{int data; / 假设数据域为整型/struct node link;}NODE;void del_linkNODE head,int x / 删除数据域为x的结点/ {NODE p,q,s;p=head;q=head->link;whileq=head{ifq->data==x{p->link=q->link;s=q;q=q->link;frees;}else{p=q;q=q->link;}}}3、void delNODE head,float price,int num {NODE p,q,s;p=head;q=head->next;whileq->price<price&&q=head{p=q;q=q->next;}ifq->price==priceq->num=q->num-num; elseprintf"无此产品"; ifq->num==0{p->next=q->next; freeq;}}4、include ""include ""typedef struct node {float price;int num;struct node next;}NODE;void insNODE head,float price,int num {NODE p,q,s;p=head;q=head->next;whileq->price<price&&q=head{p=q;q=q->next;}ifq->price==priceq->num=q->num+num;else{s=NODE mallocsizeofNODE;s->price=price;s->num=num;s->next=p->next;p->next=s;}}5、顺序表：算法思想：从0开始扫描线性表,用k记录下元素值在a与b之间的元素个数,对于不满足该条件的元素,前移k个位置,最后修改线性表的长度;void delelemtype list,int n,elemtype a,elemtype b{int i=0,k=0；whilei<n{iflisti>=a&&listi<=b k++;elselisti-k=listi;i++;}n=n-k; / 修改线性表的长度/}循环链表:void delNODE head,elemtype a,elemtype b{NODE p,q;p= head;q=p->link; / 假设循环链表带有头结点/ whileq=head && q->data<a{p=q;q=q->link;}whileq=head && q->data<b{r=q;q=q->link;freer;}ifp=qp->link=q;}6、define MAXSIZE 100int listAMAXSIZE,listBMAXSIZE; int n,m;int compareint a,int b{int i=0;whileai==bi&&i<n&&i<mi++;ifn==m&&i==n return0;ifn<m&&i==n return-1;ifn>m&&i==m return1;ifi<n&&i<mifai<bi return-1;else ifai>bi return1;}7、void delDUNODE head,int i{DUNODE p;{head=head->next;head->prior=NULL;return0;}Else{forj=0;j<i&&p=NULL;j++p=p->next;ifp==NULL||j>i return1;p->prior->next=p->next;p->next->prior=p->proir;freep;return0;}8.顺序存储:void convertelemtype list,int l,int h / 将数组中第l个到第h个元素逆置/ {elemtype temp;fori=h;i<=l+h/2;i++{temp=listi;listi=listl+h-i;listl+h-i=temp;}}void exchangeelemtype list,int n,int m; {convertlist,0,n+m-1;convertlist,0,m-1;convertlist,m,n+m-1;}该算法的时间复杂度为On+m,空间复杂度为O1 链接存储:不带头结点的单链表typedef struct node{elemtype data;struct node link;}NODE;void convertNODE head,int n,int m{NODE p,q,r;int i;p=head;q=head;fori=0;i<n-1;i++q=q->link; /q指向an-1结点/r=q->link;q->link=NULL;whiler->link=NULLr=r->link; /r指向最后一个bm-1结点/head=q;r->link=p;}该算法的时间复杂度为On+m,但比顺序存储节省时间不需要移动元素,只需改变指针,空间复杂度为O1typedef struct node{elemtype data;struct node link;}NODE;NODE unionNODE ah,NODE bh {NODE a,b,head,r,q;head=ah;a=ah;b=bh;whilea->link=ah&&b->link=bh {r=a->link;q=b->link;a->link=b;b->link=r;a=r;}ifa->link==ah /a的结点个数小于等于b的结点个数/{a->link=b;whileb->link=bhb=b->link;b->link=head;}ifb->link==bh /b的结点个数小于a的结点个数/{r=a->link;a->link=b;b->link=r;}returnhead;}该算法的时间复杂度为On+m,其中n和m为两个循环链表的结点个数.10.typedef struct node{elemtype data;struct node link;}NODE;void analyzeNODE a{NODE rh,qh,r,q,p；int i=0,j=0；/i为序号是奇数的结点个数j为序号是偶数的结点个数/ p=a；rh=NODE mallocsizeofNODE；/rh为序号是奇数的链表头指针/qh=NODE mallocsizeofNODE; /qh为序号是偶数的链表头指针/r=rh;q=qh;whilep=NULL{r->link=p;r=p;i++;p=p->link;ifp=NULL{q->link=p;q=p;j++;p=p->link;}}rh->data=i;r->link=rh;qh->data=j;q->link=qh;}11.typedef struct node {elemtype data;struct node link;}NODE;void changeNODE head {NODE p;p=head;ifhead=NULL{whilep->link=NULLp=p->link;p->link=head;}}12.typedef struct node {elemtype data;struct node link;}NODE;void delNODE x,NODE y{NODE p,q;elemtype d1;p=y;q=x;whileq->next=NULL / 把后一个结点数据域前移到前一个结点/ {p->data=q->data;q=q->link;p=q;p->link=NULL; / 删除最后一个结点/freeq;}第三章栈和队列一、选择题1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是;A edcbaBdecbaCdceab Dabcde2.栈结构通常采用的两种存储结构是;A 线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构3.判定一个栈ST最多元素为m0为空的条件是;A ST-〉top=0 BST-〉top==0CST-〉top=m0 DST-〉top=m04.判定一个栈ST最多元素为m0为栈满的条件是;AST->top=0 BST->top==0CST->top=m0-1DST->top==m0-15.一个队列的入列序列是1,2,3,4,则队列的输出序列是;A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,16.循环队列用数组A0,m-1存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是Arear-front+m%m B rear-front+1 Crear-front-1Drear-front7.栈和队列的共同点是A 都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点8.表达式ab+c-d的后缀表达式是;Aabcd+-Babc+d- Cabc+d-D-+abcd个元素a1,a2,a3和a4依次通过一个栈,在a4进栈前,栈的状态,则不可能的出栈序是Aa4,a3,a2,a1 Ba3,a2,a4,a1Ca3,a1,a4,a2 Da3,a4,a2,a110.以数组Q0..m－1存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是Arear－qulen Brear－qulen＋mCm－qulen D1＋rear＋m－qulen% m二、填空题1.栈的特点是_______________________,队列的特点是__________________________;2.线性表、栈和队列都是_____________________结构,可以在线性表的______________位置插入和删除元素,对于栈只能在________插入和删除元素,对于队列只能在_______插入元素和_________删除元素;3.一个栈的输入序列是12345,则栈有输出序列12345是____________;正确/错误4.设栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过一个栈,一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1则栈S至少应该容纳_____个元素;三、算法设计题1.假设有两个栈s1和s2共享一个数组stackM,其中一个栈底设在stack0处,另一个栈底设在stackM-1处;试编写对任一栈作进栈和出栈运算的C函数pushx,i和popi,i=l,2;其中i=1表示左边的栈,,i=2表示右边的栈;要求在整个数组元素都被占用时才产生溢出;2.利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算写出模拟队列的插入和删除的C函数;一个栈s1用于插入元素,另一个栈s2用于删除元素.参考答案：一、选择题1. C 3. B 4. B 5. B 7、C 8、C 9、C 10、D二、填空题1、先进先出；先进后出2、线性；任何；栈顶；队尾；对头3、正确的4、3三、算法设计题1.define M 100elemtype stackM;int top1=0,top2=m-1;int pushelemtype x,int i{iftop1-top2==1 return1; /上溢处理/elseifi==1 stacktop1++=x;ifi==2stacktop2--=x;return0;}int popelemtype px,int iifi==1iftop1==0 return1; else{top1--;px=stacktop1;return0;}elseifi==2iftop2==M-1 return1; else{top2++;px=stacktop2;return0;}}elemtype s1MAXSIZE,s2MAZSIZE; int top1,top2;void enqueueelemtype x{iftop1==MAXSIZE return1;else{pushs1,x;return0;}}void dequeueelemtype px{elemtype x;top2=0;whileemptys1{pops1,&x;pushs2,x;pops2,&x;whileemptys2{pops2,&x;pushs1,x;}}第四章串一、选择题1.下列关于串的叙述中,正确的是A一个串的字符个数即该串的长度B一个串的长度至少是1C空串是由一个空格字符组成的串D两个串S1和S2若长度相同,则这两个串相等2.字符串"abaaabab"的nextval值为A0,1,01,1,0,4,1,0,1 B0,1,0,0,0,0,2,1,0,1C0,1,0,1,0,0,0,1,1 D0,1,0,1,0,1,0,1,13.字符串满足下式,其中head和tail的定义同广义表类似,如head‘xyz’=‘x’,tail‘xyz’= ‘yz’,则s= ; concatheadtails,headtailtails= ‘dc’; Aabcd Bacbd Cacdb Dadcb4.串是一种特殊的线性表,其特殊性表现在A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符5．设串S1=‘ABCDEFG’,s2=‘PQRST’,函数CONCATX,Y返回X和Y串的连接串,SUBSTRS,I,J 返回串S从序号I开始的J个字符组成的字串,LENGTHS返回串S的长度,则CONCATSUBSTRS1,2,LENGTHS2,SUBSTRS1,LENGTHS2,2的结果串是ABCDEF B BCDEFG CBCPQRST DBCDEFEF二、算法设计1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpys1,s2;2.在一般链接存储一个结点存放一个字符方式下,写出采用简单算法实现串的模式匹配的C 语言函数int L_indext,p;参考答案：一、选择题1. A 3. D 4. D 5. D二、算法设计1.顺序存储：include ""define MAXN 100char sMAXN;int S_strlenchar s{int i;fori=0;si='\0';i++;returni;}void S_strcpychar s1,char s2 include "" typedef struct node{char data;struct node link;}NODE;int L_indexNODE t,NODE p{NODE t1,p1,t2;int i;t1=t;i=1;whilet1=NULL{p1=p;t2=t1->link;whilep1->data==t1->data&&p1=NULL{p1=p1->link;t1=t1->link;}ifp1==NULL returni;i++;t1=t2;}return0;}第五章数组和广义表一、选择题1. 常对数组进行的两种基本操作是A建立与删除B索引和修改C查找和修改D查找与索引2.二维数组M的元素是4个字符每个字符占一个存储单元组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素的起始地址相同;AM24BM34CM35DM443.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是;A80B100C240D2704.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A74的起始地址为;ASA+141BSA+144CSA+222DSA+2255.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A47的起始地址为;ASA+141BSA+180CSA+222DSA+2256.稀疏矩阵一般的压缩存储方法有两种,即;A 二维数组和三维数组B三元组和散列C三元组和十字链表D散列和十字链表7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点;A正确B错误8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B1,nn-1/2中,对下三角部分中任一元素ai,ji<=j,在一组数组B的下标位置k的值是;Aii-1/2+j-1Bii-1/2+jCii+1/2+j-1 Dii+1/2+j二、填空题1.己知二维数组Amn采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOCA00,则A00的地址是_____________________;2.二维数组A1020采用列序为主方式存储,每个元素占一个存储单元,并且A00的存储地址是200,则A612的地址是________________;3.有一个10阶对称矩阵A,采用压缩存储方式以行序为主,且A00=1,则A85的地址是__________________;4.设n行n列的下三角矩阵A已压缩到一维数组S1..nn+1/2中,若按行序为主存储,则Aij对应的S中的存储位置是________________;5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A00的存储地址为1000,元素A13的存储地址为___________,该数组共占用_______________个存储单元;三、算法设计1.如果矩阵A中存在这样的一个元素Aij满足条件:Aij是第i行中值最小的元素,且又是第j 列中值最大的元素,则称之为该矩阵的一个马鞍点;编写一个函数计算出1×n的矩阵A的所有马鞍点;只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王;n 和m由键盘输入,打印出最后剩下的猴子号;编写一程序实现上述函数;3.数组和广义表的算法验证程序编写下列程序:1求广义表表头和表尾的函数head和tail;2计算广义表原子结点个数的函数count_GL;3计算广义表所有原子结点数据域设数据域为整型〉之和的函数sum_GL;参考答案：一、选择题1. C 3. C 4. C 5. B 7、B 8、B二、填空题1、locA00+ni+jk2、3323、424、ii+1/2+j+15、1039；72三、算法设计题1.算法思想：依题意,先求出每行的最小值元素,放入minm之中,再求出每列的最大值元素,放入maxn之中,若某元素既在mini中,又在maxj中,则该元素Aij便是马鞍点,找出所有这样的元素,即找到了所有马鞍点;因此,实现本题功能的程序如下:include <>define m 3define n 4void minmaxint amn{int i1,j,have=0;int minm,maxn;fori1=0;i1<m;i1++/计算出每行的最小值元素,放入minm之中/{mini1=ai10;forj=1;j<n;j++ifai1j<mini1 mini1=ai1j;}forj=0;j<n;j++/计算出每列的最大值元素,放入maxn之中/{maxj=a0j;fori1=1;i1<m;i1++ifai1j>max j maxj=ai1j;}fori1=0;i1<m;i1++forj=0;j<n;j++ifmini1==maxj{printf"%d,%d:%d\n",i1,j,ai1j;have=1;}ifhave printf"没有鞍点＼n";}2.算法思想:本题用一个含有n个元素的数组a,初始时ai中存放猴子的编号i,计数器似的值为0;从ai开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出ai值退出圈外的猴子的编号,同时将ai的值改为O以后它不再参加报数,计数器值重新置为0;该函数一直进行到n 只猴子全部退出圈外为止,最后退出的猴子就是大王;因此,现本题功能的程序如下:include ""main{int a100;int count,d,j,m,n; scanf"%d %d",&m,&n;/ n>=m/ forj=0;j<n;j++aj=j+1;count=0;d=0;whiled<nforj=0;j<n;j++ifaj=0{count++;ifcount==m{printf"% d ",aj;aj=0;count=0;}}}3.include ""include ""typedef struct node { int tag;union{struct node sublist; char data;}dd;struct node link;}NODE;NODE creat_GLchar s {NODE h;char ch;s++;ifch='\0'{h=NODEmallocsizeofNODE; ifch==''{h->tag=1;h->=creat_GLs;}Else{h->tag=0;h->=ch;}}elseh=NULL;ch=s;s++;ifh=NULLifch==','h->link =creat_GLs; elseh->link=NULL; returnh;}void prn_GLNODE p {ifp=NULL{ifp->tag==1{printf"";ifp-> ==NULL printf" ";elseprn_GLp-> ;}elseprintf"%c",p->;ifp->tag==1printf"";ifp->link=NULL{printf",";prn_GLp->link;}}}NODE copy_GLNODE p{NODE q;ifp==NULL returnNULL;q=NODE mallocsizeofNODE; q->tag=p->tag;ifp->tagq-> =copy_GLp-> ;elseq-> =p->;q->link=copy_GLp->link;returnq;}NODE headNODE p /求表头函数/{returnp->;}NODE tailNODE p /求表尾函数/{returnp->link;}int sumNODE p /求原子结点的数据域之和函数/ { int m,n;ifp==NULL return0;else{ ifp->tag==0 n=p->;elsen=sump->;ifp->link=NULLm=sump->link;else m=0;returnn+m;}}int depthNODE p /求表的深度函数/ {int h,maxdh;NODE q;ifp->tag==0 return0;elseifp->tag==1&&p->==NULL return 1; else{maxdh=0;whilep=NULL{ifp->tag==0 h=0; else{q=p->;h=depthq;}ifh>maxdhmaxdh=h; p=p->link;}returnmaxdh+1;}}main{NODE hd,hc;char s100,p;p=getss;hd=creat_GL&p; prn_GLheadhd;prn_GLtailhd;hc=copy_GLhd;printf"copy after:";prn_GLhc;printf"sum:%d\n",sumhd;printf"depth:%d\n",depthhd;}第六章树和二叉树一、选择题1.在线索化二叉树中,t所指结点没有左子树的充要条件是At-〉left==NULL Bt-〉ltag==1Ct-〉ltag=1且t-〉left=NULLD以上都不对2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法A正确B错误C不同情况下答案不确定3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法A正确B错误C不同情况下答案不确定4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法A正确B错误C不同情况下答案不确定5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为;A2h B2h-1C2h+1Dh+16.已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac,它的前序遍历序列是;Aacbed BdecabCdeabc Dcedba7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的A前序B中序C后序D层次序8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是;Abdgcefha Bgdbecfha Cbdgaechf Dgdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值;这种说法A正确B错误C不同情况下答案不确定10.按照二叉树的定义,具有3个结点的二叉树有种;A3B4C5D611.在一非空二叉树的中序遍历序列中,根结点的右边A只有右子树上的所有结点B只有右子树上的部分结点C只有左子树上的部分结点D只有左子树上的所有结点12.树最适合用来表示;A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A不发生改变B发生改变C不能确定D.以上都不对14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用存储结构;A二叉链表B广义表存储结构C三叉链表D顺序存储结构15.对一个满二叉树,m个树叶,n个结点,深度为h,则An=h+m Bh+m=2nCm=h-1Dn=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为Auwvts BvwutsCwuvts Dwutsv17.具有五层结点的二叉平衡树至少有个结点;A10B12C15D17二、判断题1.二叉树中任何一个结点的度都是2;2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树;3.一棵哈夫曼树中不存在度为1的结点;4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2三、填空题1.指出树和二叉树的三个主要差别___________,___________,_______________;2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是____________3.若结点A有三个兄弟包括A本身,并且B是A的双亲结点,B的度是_______________4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域;5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________;6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列_________________;7.找出满足下列条件的二叉树1先序和中序遍历,得到的结点访问顺序一样;_________________________2后序和中序遍历,得到的结点访问顺序一样;_________________________3先序和后序遍历,得到的结点访问顺序一样;__________________________8.一棵含有n个结点的k叉树,可能达到的最大深度和最小深度各是多少____________________9.一棵二叉树有67个结点,这些结点的度要么是0,要么是2;这棵二叉树中度为2的结点有______________________个;10.含有100个结点的树有_______________________________________条边;四、问答题1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树;若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:1第k层结点数1≤k≤h;2整棵树结点数;3编号为i的结点的双亲结点的编号;4编号为i的结点的第j个孩子结点若有的编号;2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：n0=k-1n1+13.已知一组元素为50,28,78,65,23,36,13,42,71,请完成以下操作:1画出按元素排列顺序逐点插入所生成的二叉排序树BT;2分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数;3画出在BT中删除23〉后的二叉树;4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数;5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9;1试画出对应的编码哈夫曼树要求左子树根结点的权小于等于右子树根结点的权;2求出每个字符的晗夫曼编码;3求出传送电文的总长度;4并译出编码系列101的相应电文;五、算法设计已知一棵具有n个结点的完全二叉树被顺序存储在一维数组An中,试编写一个算法输出Ai结点的双亲和所有孩子;参考答案：一、选择题1. B 3. A 4. B 5. B 7、A 8、D 9、B 10、C 11、A 12、C 13、A 14、C 15、D 16、C 17 C。

第4章串在非数值处理、事务处理等问题常涉及到一系列的字符操作。

计算机的硬件结构主要是反映数值计算的要求，因此，字符串的处理比具体数值处理复杂。

本章讨论串的存储结构及几种基本的处理。

4.1 串类型的定义一、串的基本概念串（字符串）：是零个或多个字符组成的有限序列。

记作：S＝‘a1a2…a n’，其中S是串名，a i（1≤i≤n）可以是数字、字母或其他字符。

串值：单引号括起来的字符序列。

【注意】单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。

串长：串中所包含的字符个数。

空串（空的字符串）：长度为零的串，它不包含任何字符。

空格串（空白串）：构成串的所有字符都是空格的串。

【注意】空串和空白串的不同，一个是不含任何字符，一个是含字符，但只含空格字符。

子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。

子串的序号：将子串在主串中首次出现时的该子串的首字符对应在主串中的序号，称为子串在主串中的序号（或位置）。

例如，设有串A和B分别是：A＝‘这是不是字符串’，B＝‘是’，则B是A的子串，A为主串。

B在A中出现了两次，其中首次出现所对应的主串位置是2。

因此，称B在A 中的序号为2。

【注意】特别地，空串是任意串的子串，任意串是其自身的子串。

串相等：两个串的长度相等，且各个对应位置的字符都相同（串值相等）。

通常在程序中使用的串可分为两种：①串常量，和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。

②串变量，和其他类型的变量一样，其值是可以改变。

二、串的抽象数据类型定义4.2 串的表示和实现串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。

串的存储方式取决于将要对串所进行的操作。

串在计算机中有3种表示方式：定长顺序存储表示：将串定义成字符数组，利用串名可以直接访问串值。

用这种表示方式，串的存储空间在编译时确定，其大小不能改变。

堆分配存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。

数据结构（ C语言版）（第 2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第 7 章查找 (54)第 8 章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0 ，± 1，± 2，, } ，字母字符数据对象是集合C={‘A’，‘B’， , ，‘Z’，‘ a’，‘ b’， , ，‘z ’} ，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。