数据结构习题答案.docx

数据结构习题答案.docx

《数据结构习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构习题答案.docx（33页珍藏版）》请在冰点文库上搜索。

数据结构习题答案

习题1参考答案

一、单项选择题

1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B

二、填空题

1.线性结构，非线性结构

2.集合，线性，树，图

3.一对一，一对多或多对多

4.时间，空间

5.前趋，一，后继，多

6.有多个

7.一对一，一对多，多对多

8.O（

）

9.O（

）

10.O（

）

11.O（log

n）

12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。

13.事后统计，事前估计

三、算法设计题

1.O（

）2.O（

）3.O（n

）4.O（n）5.O（n）

习题2参考答案

一、单项选择题

1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C20．A

二、填空题

1．线性

2．n-i+1

3．相邻

4．前移，前，后

5．物理存储位置，链域的指针值

6．前趋，后继

7．顺序，链接

8．一定，不一定

9．线性，任何，栈顶，队尾，队头

10．单链表，双链表，非循环链表，循环链表

11．使空表和非空表统一；算法处理一致

12．O

（1），O（n）

13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇

14．2、3

15．O

（1）

三、简答题

1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。

若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。

2．线性表具有两种存储结构即顺序存储结构和链接存储结构。

线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：

而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。

3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：

这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。

4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。

因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。

5．设尾指针比设头指针好。

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

（1）。

若用头指针来表示该链表，则查找终端结点的时间为O（n）。

6．共有14种可能的出栈序列，即为：

ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA

7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。

当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。

对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。

一般地，要解决队列的上溢现象可有以下几种方法：

（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。

（2）要避免出现“假溢出”现象可用以下方法解决：

第一种：

采用移动元素的方法。

每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。

第二种：

每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。

第三种：

采用循环队列方式。

将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。

8．该算法的功能是：

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

四、算法设计题

1．算法思想为：

（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作；

（2）当i=0时，删除第一个结点：

（3）当０

算法描述如下：

delete（LinkList*q,inti）

{//在无头结点的单链表中删除第i个结点

LinkList*p,*s;

intj;

if（i<0）

printf（"Can'tdelete"）;

elseif（i==0）

{s=q;

q=q->next;

free（s）;

}

else

{j=0;s=q;

while（（j

=NULL））

{p=s;

s=s->next;

j++;

}

if（s==NULL）

printf（"Cant'tdelete"）;

else

{p->next=s->next;

free（s）;

}

}

}

2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。

算法描述如下：

intListLength（LinkList*L）

{//求带头结点的单链表的表长

　intlen=0;

　ListList*p;

　p=L;

　while（p->next!

=NULL）

{p=p->next;

　　　len++;

　}

　return（len）;

}

3．设单循环链表的头指针为head，类型为LinkList。

逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。

如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：

voidinvert（LinkList*head）

{//逆置head指针所指向的单循环链表

linklist*p,*q,*s;

q=head;

p=head->next;

while（p!

=head）//当表不为空时，逐个结点逆置

{s=q;

q=p;

p=p->next;

q->next=s;

}

p->next=q;

}

4．定义类型LinkList如下：

typedefstructnode

{intdata;

structnode*next,*prior;

}LinkList;

此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。

算法描述如下：

insert（LinkList*head）

{LinkList*p,*s,*q;

p=head->next;//p指向待插入的结点，初始时指向第一个结点

while（p!

=NULL）

{s=head;//s指向q结点的前趋结点

q=head->prior;//q指向由prior域构成的链表中待比较的结点

while（（q!

=NULL）&&（p->data>q->data））//查找插入结点p的合适的插入位置

{s=q;

q=q->prior;

}

s->prior=p;

p->prior=q;//结点p插入到结点s和结点q之间

p=p->next;

}

}

5．算法描述如下：

delete（LinkList*head,intmax,intmin）

{linklist*p,*q;

if（head!

=NULL）

{q=head;

p=head->next;

while（（p!

=NULL）&&（p->data<=min））

{q=p;

p=p->next;

}

while（（p!

=NULL）&&（p->data

p=p->next;

q->next=p;　

}

}

6．算法描述如下：

delete（LinkList*head,intmax,intmin）

{LinkList*p,*q;

q=head;

p=head->next;

while（p!

=NULL）

if（（p->data<=min）||（p->data>=max））

{q=p;

p=p->next;

}

else

{q->next=p->next;

free（p）;

p=q->next;

}

}

7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：

（1）插入（即入队）算法：

insert（LinkList*rear,elemtypex）

{//设循环链队列的队尾指针为rear,x为待插入的元素

LinkList*p;

p=（LinkList*）malloc（sizeof（LinkList））;

if（rear==NULL）//如为空队，建立循环链队列的第一个结点

{rear=p;

rear->next=p;//链接成循环链表

}

else//否则在队尾插入p结点

{p->next=rear->next;

rear->next=p;

rear=p;

}

}

（2）删除（即出队）算法：

delete（LinkList*rear）

{//设循环链队列的队尾指针为rear

if（rear==NULL）//空队

printf（"underflow\n"）;

if（rear->next==rear）//队中只有一个结点

rear=NULL;

else

rear->next=rear->next->next;//rear->next指向的结点为循环链队列的队头结点

}

8．只要从终端结点开始往前找到第一个比x大（或相等）的结点数据，在这个位置插入就可以了。

算法描述如下：

intInsertDecreaseList（SqList*L,elemtypex）

{inti;

if（（*L）.len>=maxlen）

{printf（“overflow"）;

return（0）;

}

for（i=（*L）.len;i>0&&（*L）.elem[i-1]

（*L）.elem[i]=（*L）.elem[i-1];//比较并移动元素

（*L）.elem[i]=x;

（*L）.len++;

return

（1）;

}

习题3参考答案

一、单项选择题

1．B2．D3．C4．D5．B6．C7．D8．C9．D

二、填空题

1.固定长度，设置长度指针

2.两个串的长度相等，对应位置的字符相等

3.“BCDEDE”

4.含n个字符的有限序列（n≥0）

5.不含任何字符的串，仅含空格字符的字符串

三、算法设计题

1．算法描述为：

intdelete（r,s,t,m）//从串的第m个字符以后删除长度为t的子串

charr[];

ints,t,m;

{inti,j;

for（i=1;i<=m;i++）

r[s+i]=r[i];

for（j=m+t-i;j<=s;j++）

r[s-t+j]=r[j];

return

（1）;

}//delete

2．算法思想为：

（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；

（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较；

（3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。

设单链表类型为LinkList；注意，此时类型LinkList中的data成分为字符类型。

LinkStringfind（s,t）

LinkString*s,*t;

{LinkString*ps,*pt;

ps=s;

while（ps!

=NULL）

{pt=t;

while（（pt!

=NULL）&&（ps->data!

=pt->data））

pt=pt->next;

if（pt==NULL）

ps=NULL;

else

{ps=ps->next;

s=ps;

}

}

returns;

}//find

习题4参考答案

一、单项选择题

1.A2.A3.A4.B5.BA6.C7.A8.A9.C10.C11.C12.C13.B14.D15.A16.B

二、填空题

1.线性结构，顺序结构，以行为主序，以列为主序

2.i×n+j个元素位置

3.5，3

4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））

5.n×（n+1）/2

6.e

7.41

8.head（head（tail（Ls）））

9.（d

-c

+1）×（d

-c

+1）×（d

-c

+1）

10.913

三、判断题

1.×2.√3.√4.√5.×6.×7.√8.×9.×10.√11.√12.√13.×14.√15.√

习题5参考答案

一、单项选择题

1.C2.B3.C4.D5.B6.D7.C8.B9.B10.B11.A12.D13.A14.B15.A

二、判断题

1.×2.√3.×4.√5.×6.√7.√8.√9.×10.×

三、填空题

1.3，4，6，1，1，2，A，F，G

2.n+1

3.完全，

，最大，n

4.55

5.中序

6.2n，n-1，n+1

7.n2+1

8.2k-1，2k-1，2k-1

9.5

10.2h-1

11.单支树，完全二叉树

12.2i，2i+1，i/2（或i/2）

13.2n，n-1，n+1

14.带权路径长度最小

15.结点数为0，只有一个根结点的树

16.二叉链表，三叉链表

17.双亲结点

18.指向结点前驱和后继信息的指针

19.1，RChild

20.孩子表示法，双亲表示法，长子兄弟表示法

四、应用题

1.解答：

图5-15

根据给定的边确定的树如图5-15所示。

其中根结点为a；

叶子结点有：

d、m、n、j、k、f、l；

c是结点g的双亲；

a、c是结点g的祖先；

j、k是结点g的孩子；

m、n是结点e的子孙；

e是结点d的兄弟；

g、h是结点f的兄弟；

结点b和n的层次号分别是2和5；

树的深度为5。

2.解答：

度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。

3.解答：

　略

4.解答：

先序序列：

ABDHIEJKCFLG

中序序列：

HDIBJEKALFCG

后序序列：

HIDJKEBLFGCA

5.解答：

（1）第i层上的结点数目是mi-1。

（2）编号为n的结点的父结点如果存在，编号是（（n-2）/m）+1。

（3）编号为n的结点的第i个孩子结点如果存在，编号是（n-1）*m+i+1。

（4）编号为n的结点有右兄弟的条件是（n-1）%m≠0。

其右兄弟的编号是n+1。

6.解答：

（1）先序序列和中序序列相同的二叉树为：

空树或者任一结点均无左孩子的非空二叉树；

（2）中序序列和后序序列相同的二叉树为：

空树或者任一结点均无右孩子的非空二叉树；

（3）先序序列和后序序列相同的二叉树为：

空树或仅有一个结点的二叉树。

7.解答：

后序序列：

ACDBGJKIHFE

8.解答：

先序序列：

ABCDGEIHFJK

9.解答：

先根遍历：

ABCDEFGHIJKLMNO

后根遍历：

BDEFCAHJIGKNOML

森林转换成二叉树如图5-16所示。

10.解答：

构造而成的哈夫曼树如图5-17所示。

图5-16

图5-17

五、算法设计题

1.解答：

这个问题可以用递归算法，也可用非递归算法，下面给出的为非递归算法。

假设该完全二叉树的结点以层次为序，按照从上到下，同层从左到右顺序编号，存放在一个一维数组R[1..n]中，且用一个有足够大容量为maxlen的顺序栈作辅助存储，算法描述如下：

preorder（R）//先序遍历二叉树R

intR[n];

{introot;

SqStack*s;//s为一个指针栈，类型为seqstack，其中包含top域和数组data

s->top=-1;//s栈置空

root=1;

while（（root<=n）&&（s->top>-1））

{while（root<=n）

{printf（R[root]）;

s->top++;

s->data[s->top]=root;

root=2*root;

}

if（s->top>-1）//栈非空访问，遍历右子树

{root=s->data[s->top]*2+1;

s->top--;

}

}

}

2.解答：

考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。

算法中的front为队头指针，rear为队尾指针。

levelorder（BiTree*t）//按层次遍历二叉树t

{BiTree*que[maxnum];　　

intrear,front;

if（t!

=NULL）

{front=0;//置空队列

rear=1;

que[1]=t;

do

{front=front%maxsize+1;//出队

t=que[front];

printf（t->data）;

if（t->lchild!

=NULL）//左子树的根结点入队

{rear=rear%maxsize+1;

que[rear]=t->lchild;

}

if（t->rchild!

=NULL）//右子树的根结点入队

{rear=rear%maxsize+1;

que[rear]=t->rchild;

}

}while（rear==front）;//队列为空时结束

}

}

3.解答：

设该线索二叉树类型为bithptr，包含5个域：

lchild，ltag，data，rchild，rtag。

insert（p,s）//将s结点作为p的右子树插入

BiThrNode*p,*s;

{BiThrNode*q;

if（p->rtag==1）//无右子树，则有右线索

{s->rchild=p->rchild;

s->rtag=1;

p->rchild=s;

p->rtag=0;

}

else

{q=p->rchild;

while（q->ltag==0）//查找p所指结点中序后继，即为其右子树中最左下的结点

q=q->lchild;

q->lchild=p->rchild;

s->rtag=0;

p->rchild=s;

}

s->lchild=p;//将s结点的左线索指向p结点

s->ltag=1;

}

4.解答：

利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。

算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。

parentjudge（t,n）

BiTree*t;

intn;

{BiTree*que[maxnum];

intfront,rear;

BiTree*parent;

parent=NULL;

if（t）

if（t->data==n）

printf（“noparent!

”）;//n是根结点，无双亲

else

{front=0;//初始化队列

rear=1;

que[1]=t;//根结点进队

do

{front=front%maxsize+1;

t=que[front];

if（（t->lchild->data==n）||（t->rchild->data==n））//结点n有双亲

{parent=t;

front=rear;

printf（“parent”,t->data）;

}

else

{if（t->lchild!

=NULL）//左子树的根结点入队

{rear=rear%maxsize+1;

que[rear]=t->lchild;

}

if（t->rchild!

=NULL）//右子树的根结点入队

{rear=rear%maxsize+1;

que[rear]=t->rchild;

}

}

}while（rear==front）;//队空时结束

if（parent==NULL）

printf（“结点不存在”）;

}

}

习题6参考答案

一、单项选择题

1.A2.D3.D4.C5.B6.B7.B8.A9.C10.D11.C12.D13.A14.B15.B16.C17.A18.A19.B20.D21.A22.C23.B24.A

二、填空题

1.22.n（n-1）/2，n（n-1）

3.2，4　　4.n-1

5.邻接矩阵，邻接表6.1

7.k+18.3

9.n，n10.2e，e

11.出边，入边12.O（n），O（e/n）

13.O（n2），O（n+e）14.acdeb，acedb（答案不唯一）

15.acfebd，acefbd（答案不唯一）16.深度，广度

17.n，n-118.唯一

19.唯一20.aebdcf（答案不唯一）

三、应用题

1.深度优先搜索序列：

0,1,2,8,3,4,5,6,7,9

广度优先搜索序列：

0,1,4,2,7,3,8,6,5,9

2.深度优先搜索序列：

0,4,7,5,8,3,6,1,2

广度优先搜索序列：

0,4,3,1,7,5,6,2,8

3.深度优先搜索序列：

0,