数据结构(马睿、孙丽云)习题答案

《数据结构(马睿、孙丽云)习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章绪论一、选择题1、C2、C3、C4、D5、B6、C二、判断题1．×2．×3．×4．×5．√6．×三、简答题（略）四、算法分析题：1.分析下列程序段中带标号“#”语句的执行频度（n为正整数）。（1）频度：n，时间复杂度：O（n）（2）频度：1，时间复杂度：O（1）（3）频度：n2，时间复杂度：O（n2）（4）频度：n/2-1，时间复杂度：O（n）（5）频度：11002．写出下列各程序段关于n的时间复杂度。（1）O（log3n）（2）O（n2）（3）O（n2）第2章线性表一、选择题1、A2.B3.C4.D5.C6.B7.A8.B9.B10.C二、填空题1.、线

2、性表2、前驱，后继3、p->next;s->data;t4、q->next5、head->next=NULL6、p->next,s7、p->next!=p8、O(1),O(n)第3章栈和队列一、选择题1、C2.C3.D4.C5.C6.D7.C8.B9.B10.D11.A12.B二、填空题1.、n-12、O(n)3、135424、2xy+1x-/*5、36、a2,a4,a1,a2,27、先进后出，加1，减18、满，空，n9、线性结构10、4三、判断题1.、错2、错3、对4、错5、对6、错7、错四、解答题4、列车进入一个栈式结构的车站，开出车站有14可能的顺序：ab

3、cd;abdcadcbacdb,acbdbdca,bcda,bcadbacd,badccdba,cbda,cbad,dcba列车进入一个队列式结构的车站，开出车站有1可能的顺序：abcd5、6,247、staxy8、char9、第一个循环：队列Q中的元素依次出队，出队后即进栈S第二个循环：栈S中的元素依次出栈，出栈后即进入队列Q第4章串一、选择题1、A2、D3、C4、C5、D二、简答题1、含零个字符的串称为空串，用Φ表示，串的长度为0。而空格串是由一个或多个空格组成的串，串的长度为所含空格的个数。由串中任意连续字符组成的子序列称为该串的子串。包含子串的串相应地被

4、称为主串。假如一个串S=“a0a1a2…an-1”(n≥0)，其中：S为串名，用双引号括起来的内容为串的值，双引号本身不是串的值。2、当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串才相等。3、19，7，good，e，0，3，”Iamagoodteacher”，”agoodyestea”4、j0123456模式串abcabaanext[j]-1000121三、算法题1、voidAssign(string*s,stringt)//s为串指针类型的参数{//将串变量t的值赋给串变量sinti;for(i=0;i

5、i]=t.str[i];s.curlen=t.curlen;}2、略3、略4、Lstring*Insert(Lstring*s,intpos,Lstring*t)//在串s的第pos字符之前插入串t{intk;Lstring*str_temp,*p1=s->next,*p2=t->next,*q,*r;str_temp=(Lstring*)malloc(sizeof(Lstring));str_temp->next=NULL;r=str_temp;if(pos<0

6、

7、pos>s.curlen)//参数不正确时返回空串returnstr_temp;for(k=0;

8、kstr=p1->str;q->next=NULL;r->next=q;r=q;p1=p1->next;}while(p2!=NULL){q=(Lstring*)malloc(sizeof(Lstring));q->str=p2->str;q->next=NULL;r->next=q;r=q;p2=p2->next;}while(p1!=NULL){//将*p1及其后的结点复制到str_tempq=(Lstring*

9、)malloc(sizeof(Lstring));q->str=p1->str;q->next=NULL;r->next=q;r=q;p1=p1->next;}returnstr_temp;}5、Lstring*Delete(Lstring*s,intpos,intlen){//从串s中删去从第pos个字符起长度为len的子串intk;Lstring*str_temp,*p=s->next,*q,*r;str_temp=(Lstring*)malloc(sizeof(Lstring));str_temp->next=NULL;r=str_temp;if(pos<

10、0

11、

12、pos>lengt