数据结构课后习题答案

参考答案

第一章、绪论

一、选择题 1 B；2 A； 3 B； 4 C ；5 C； 6 B；7 C；8 C； 9 D； 10 B。

二、填空题1、存储 ；2、无 ，1，无，1； 3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；

7、顺序结构，链式结构，索引结构，散列结构；8、顺序。

三、问答题与算法题

1、3 ；

2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ; T4 ( n ) = 1.5 n 2 + O ( n ) 。T4 ( n ) 较优，T3 ( n )较劣。

3、见课本。

第二章 线性表

一、选择题 1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.

二、填空题 1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。

三、问答题与算法题

1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指

针出发可以找到链表中所有结点的信息。

头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。

其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。

首结点：是链表的第一个结点。

2、(1)基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

3、尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)

4、S=P->Prior; P->Prior=S->Prior; S->Prior->Next=P; S->Prior=P; S->Next=P->Next; P->Next=S;S->Next->Prior=S;

5、:将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针

6、15，26，51，37，48，,55。

7、CreatList_L(LinkList &L int n) {

L= (LinkList) molloc (sizeof (Lnode));//头结点

L->next==NULL; q=L;

For(i=1;i<=n;++i)

41

{ P= (LinkList) molloc (sizeof (Lnode));

Scanf(&(p->data));

p->next=NULL; q->next=p; q=p;}

returen OK;

}

8、Void sinsert(Sqlist &S, int x)

{int i=0; n=S.Length;

while(x<S.elem[i]&& i<n) i++; //查找插入点

if(i==n) S.elem[n]=x; //插在最后一个结点的后面

else {for(j=n-1;j>=i;j++)

S.elem[j+1]=S.elem[j]; //元素后移

S.elem[i]=x; //插入

}

}

9、int ListLength(LinkList L)

{q=L->next; i=0;

while(q)

{i++; q=q->next; }

return i;

10、int delete(LinkList &L, int x) {

p=L->next; //p为定位指针

q=L; //q为定位指针的前导

while((p->data!=x) && p)

{ q=p; //q前进

p=p->next; //p前进

}

if(!q) return ERROR; //查找失败

q->next=p->next ;

free(p);

return OK;

}

11、void mergelist(linklist &La, linklist Lb)

{pa=La->next; pb=Lb->next;pc=La;

while (pa && pb)

if (pa->data< pa->data) {pc->next=pa;pc=pa;pa=pa->next;}

else if(pa->data== pa->data) {pc->next=pa; pc=pa; pa=pa->next; pb=pb->next;} else ({pc->next=pb;pc=pb;pb=pb->next;}

pc->next=pa? pb:pb;

}

12、Void invertlinklist(linklist &L)

{if(!L) return OK; //空表

p=L->next;

if(!p) return OK; //仅有一个结点的表

else{q=p->next; //q指向p的后继

42

p->next=NULL;

while(q)

{ r=q->next ; //r指向q的后继

q->next=p; //逆置

p=q; //p前进

q=r; //q前进

}

L=p; //第一个结点

}

}

13、Void delDuplicate(int A[]，int & n)

{ for(i=0;i<n-1;i++)

for(j=i+1;j<=n-1;j++)

if(a[i]==a[j])

{n--;

for(k=j+1;k<=n-1;k++)

a[k-1]=a[k];

}

}

第三章 栈和队列

一、选择题1A；2D；3C；4C；5D；6C；7C；8B；9C；10C；11Ｄ，Ｂ；12Ｄ；13Ｂ。

二、填空题

1、栈顶；2、满，空，n；3、后进先出，先进先出；4、头；5、L->next==NULL，S.top==S.base， S.top-S.base==S.stacksize，L==NULL，Q.front==Q.rear，（Q.rear＋１）%maxQsize ==Q.front;

6、Q.rear-Q.front+n)%n；7、1nC2n；8、n－１。 n?1

三、问答题与算法题

1、 １３２４；

2、(1) int push_L(Linkstack &s SelemType e)

{ p= (LinkStack) molloc (sizeof (Snode));

if(!p) return ERROR;

p->data=e;

p->next=s;

s=p;

Return Ok;

}

(2)int pop_L(Linkstack &s SelemType &e)

{ if(!S) return ERROR;

q=s;

e=s->data;

s=s->next;

free(q);

Retuen Ok;

}

43

3、(1)int EnQueue_L(Queueptr &QL QelemType e) { p= Queueptr} molloc (sizeof (Qnode));

if(!p) return ERROR;

p->data=e;

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

QL->next->next= p;

Retuen Ok;

}

(2)int DeQueue_L(Queueptr &QL QelemType &e) { if(QL->next==QL)} return ERROR;

p= QL->next

while(p->next!=QL) p =p->next;

p->next=QL->next;

e=QL->next;

free(QL);

QL=p;

Return Ok;

}

4、(1) 栈S元素反序存放；

(2) 把栈s1复制到s2；

(3) 把栈S中值等于m的元素删除；

(4) 队列Q元素反序存放;

(5) 链表中的元素反序存放；

5、Int hw4(LinkList L)

{ initstack(S);

bool=1;n=0;

p=L->next;

while(p){n++; p=p->next;} //求串长

p=L->next; //p指向第一个结点 for(i=0; i<n/2; i++) {push(S,p->data); p=p->next;} if(n%2==1) p=p->next; //对照解法1

while(p&&bool)

{pop(S,ch);

if(ch!=p->data) bool=0;

p=p->next;

}

return bool;

｝

6、void ClearStack( LinkStack &S)。

{while(!S)

{p=s;

s=s->next;

free(p);

44

}

return OK;

}

7、int Stacksize( LinkStack S)。

{ n=0;

p=s;

While(!p)

{n++;

p=p->next;

}

return n;

}

8、见４、(5)

第四章 串

一、选择题

1 B；2B；３D；4 B；5C；6 D。

二、填空题

１、空格串；2、静态分配的顺序串、动态分配顺序串、块连串；3、?\0? 4、块的大小；

5、２；6、StrAssing，StrCompare，StrLength，Concat，SubString；7、13,6；8、模式，目标（主）。

三、问答题与算法题

1、 ●空串是指不包含任何字符的串，它的长度为零。

空格串是指包含一个或多个空格的串，空格也是字符, 长度不为零。

●串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含

子串的串就称为主串。

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为

模式串，两者是相对的。

2、(１) "Stocktom, March51999"；(２) 正数；(３) 正数；(４)１８

3、void StrInsert(char *S, char *T, int i)

{//将串T插入到串S的第i个位置上

char *Temp;

if(i<=strlen(S))

{Temp=(char *)malloc(sizeof(char[Maxsize])); // 设置一个临时串

strcpy(Temp,&S[i]); //将第i位起以后的字符拷贝到临时串中

strcpy(&S[i], T); /将串T拷贝到串S的第i个位置处，覆盖后面的字符

strcat(S,Temp); //把临时串中的字符联接到串S后面

free( Temp );

}

}

４、void StrDelete(char *S, int i , int m) //串删除

{ char Temp[Maxsize]; //定义一个临时串

if(i+m<strlen(S))

45