14章习题答案DOC.docx
《14章习题答案DOC.docx》由会员分享，可在线阅读，更多相关《14章习题答案DOC.docx（21页珍藏版）》请在冰点文库上搜索。
14章习题答案DOC
一、名词解释（见教材）
数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵
二、填空
1、数据的逻辑结构被分为_集合结构_、_线性结构___、_树形结构__、__图形结构__4种。
2、数据的存储结构被分为_顺序结构__、链接结构_、索引结构_、和__散列结构__4种。
3、在定义某种数据结构时，其数据域的数据类型可分为简单类型和结构体类型两种，为增强其通用性，应将其再定义为通用数据类型。
4、如果将线性数据结构关系描述为1：
1，那么树型和图型数据结构应分别为1：
N、M：
N。
5、数据结构简单地说是指数据以及相互之间的联系。
6、算法应具备以下5个特性：
有穷性、正确性、可行性、输入和输出。
7、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f（n）表示，请问其中n的含义是处理问题的样本量。
8、对于一个单链表，在表头插入结点的时间复杂度为O
（1），在表尾插入元素的时间复杂度为O（n）。
9、在表长为n的顺序表中，在等概率情况下，插入和删除一个元素平均需移动表长的一半（即n/2）个元素，具体移动元素的个数与表长（n）和该元素在表中的位置有关。
10、顺序表的定义如下：
typedefintElemType;
structList{
ElemType*list;
intsize;
intMaxSize;
};
其中ElemType的含义是：
通用数据类型；size的含义是：
顺序表中元素的个数。
11、设单链表中指针p指向结点A，q指针指向其后继结点。
若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为p->next=q->next;。
12、栈的运算规则为后进先出，队列的运算规则为先进先出。
13、一个函数调用了自身，这是递归调用。
14、非零元素个数远远少于零元素个数的矩阵称为稀疏矩阵。
非零元素所在的行；t的含义是：
非零元素的个数。
三、选择题
1、顺序表物理结构中的存储单元（A）。
A.一定是连续的B.一定是不连续的
C.不一定是连续的D.经删除操作后不连续
2、对一个线性表的存取操作很少，而插入和删除操作较多时应采用B数据结构。
A．线性表B.队列C.图D.树
3、对一个线性表的随机读取操作较多时，应采用B存储结构。
A.静态顺序存储B.动态顺序存储C.动态链接存储D.静态链接存储
4、顺序表适用于（A）的场合。
A.频繁查询B.频繁插入与删除
C.问题规模较小D.问题规模较大
5、链表不具有的特点是（A）。
A．可随机访问任一元素B.插入、删除不需要移动元素
C.不必事先估计存储空间D.所需空间与线性表长度成正比
6、栈的插入和删除操作在（A）进行。
A．栈顶B．栈底C．栈顶或栈底D．任意位置
7、向一个顺序栈S（栈顶指针为top）中插入元素x时，首先要（B）。
A．S->stack[S->top]=x;B．S->top++;
C．S->top--;D．x=S->stack[S->top];
8、对一个顺序存储结构的栈，栈满的判断条件是（D）
A.S.top==-1B.S.top==0
C.S.top==MaxSizeD.S.top==MaxSize-1
9、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队满的条件是（C）
A.front==rearB.（front-1）%n==rear
C.（rear+1）%n==frontD.（rear-1）%n==front
10、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队空的条件是（A）
A.front==rearB.（front-1）%n==rear
C.（rear+1）%n==frontD.（rear-1）%n==front
11、队的插入操作在（C）进行。
A．队首B．队首或队尾C．队尾D．任意位置
12、下面程序段的时间复杂度为（C）。
for（inti=0;ifor（intj=0;ja[i][j]=i*j;
A．O（m2）B.O（n2）C．O（m×n）D.O（m+n）
13、一个求从1到正整数n之间所有正整数之和的单循环语句的时间复杂度为（B）。
A．O
（1）B.O（n）C．O（n2）D.O（n3）
14、下列是顺序存储线性表排序的算法
voidSort（List&L）
{
inti,j;
ElemTypex;
for（i=1;i{
x=L.list[i];
for（j=i-1;j>=0;j--）
if（xL.list[j+1]=L.list[j];
else
break;
L.list[j+1]=x;
};
}
问：
此算法的时间复杂性为：
B
A.O（n）B.（n2）C.（n*i）D.（n*j）
15、下面程序段的时间复杂度为（B）。
for（inti=1;i<=n;i++）
for（intj=1;j<=n;j++）
printf（“%d*%d=%d\n”,i,j,i*j）;
A．O（n）B.O（n2）C．O
（1）B.O（n3）
四、简答题
1、简述数据的逻辑结构和物理结构的关系
答：
数据结构是指数据元素之间逻辑关系的整体，是从具体问题抽象出来的数据模型，有线性结构、树型结构和图型结构三种类型。
物理结构是数据及其逻辑结构在计算机中的表示，分为顺序存储和非顺序存储两种类型。
数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。
一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。
2、叙述顺序表和链表在存储方式、空间占用、读取操作、插入和删除操作等方面的不同；
【答案要点】
1.两者的存储结构不同。
顺序用物理相邻实现逻辑相邻，大多用数组实现，链接存储用链接的方式实现逻辑相邻，物理上不一定相邻；
2.存储相同数量的数据，顺序存储占用空间小，链接存储占用空间大；
3.读取操作：
顺序存储为按元素序号随机访问，效率较高；链接存储为按元素序号顺序访问，效率较低；
4.插入和删除操作：
顺序存储要移动约半数元素，效率较低；链接存储不需移动现有元素，效率较高；
3、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。
4、说明顺序存储的队列，在解决队满与队空的判断条件时，为什么将队首指针指向第一个元素之前？
这样解决后存储容量有什么变化？
5、用f（n）=n!
为例说明栈与递归算法之间的关系。
答：
（参考答案）
要点1：
栈只能在栈顶操作；
要点2：
递归算法是解决一个问题时，是通过解决与它具有相同解法的子问题而得到的；
要点3：
在进行递归调用时，计算机系统自动建立栈，用于存储递归调用参数（下例中的）n和返回地址（下例中的r）,进栈；
要点4：
当在一定条件下结束递归调用时，系统按照栈中存储的系数和返回地址逐步返回（出栈）到最初调用处，并得到最终结果。
要点4：
例：
求f（n）=n!
f（n）=1n=0
f（n）=n*f（n-1）n>0
当n=3时进栈退栈
n
f（n）
0
f（0）=1
1
1
1*f（1-1）
1*1=1
2
2*f（2-1）
2*1=2
3
3*f（3-1）
3*2=6
五、基本要求：
1、写出顺序表定义
2、写出链表结点定义
3、写出堆栈定义
4、写出循环顺序队列定义
5、写出链队定义
六、算法分析
以下有一组算法，请根据各算法的不同，回答不同的问题。
算法1：
//利用数组a[]排序
voidsort（inta[],intn）
{
inti,j,k,t;
for（i=0;i{
j=i;
for（k=i+1;kif（a[k]>a[j]）j=k;
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
问题1：
此算法的时间复杂度为：
O（n2）。
问题2：
此算法属于：
A.。
A.直接选择排序B.直接插入排序
算法2：
intFindList（structList*L,ElemTypex）
{
inti;
for（i=0;isize;i++）
if（L->list[i]==x）{
x=L->list[i];
returni;
}
return-1;
}
问题1、算法适用的数据结构？
问题2、算法功能？
问题3、算法返回？
问题4、算法有无健壮性？
若有，是哪（些）语句？
问题5、算法的关键语句是哪（些）语句？
问题6、算法的时间复杂度大O（）？
算法3：
//在链表的表尾插入一个元素
voidInsertLastList（structsNode**HL,ElemTypex）
{
structsNode*newp;
newp=malloc（sizeof（structsNode））;
if（newp==NULL）
{
printf（"Memoryallocationfailare!
\n"）;
exit
（1）;
}
newp->data=x;
newp->next=NULL;
if（*HL==NULL）
*HL=newp;
else{
structsNode*p=*HL;
while（p->next!
=NULL）
p=p->next;
p->next=newp;
}
}
问题1、算法适用的数据结构？
问题2、算法功能？
问题3、算法返回？
问题4、算法有无健壮性？
若有，是哪（些）语句？
问题5、算法的关键语句是哪（些）语句？
问题6、算法的时间复杂度大O（）？
算法4：
//根据数据结构的类型的定义分析算法
typedefintElemType;
structStackSq{
intMaxSize;
ElemType*stack;
inttop;
};
voidPush（structStackSq*S,ElemTypex）
{
if（）againMalloc（S）;
S->top++;
S->stack[S->top]=x;
}
问题1：
根据此算法定义的数据结构的类型，此算法的功能是向顺序栈中推入一个元素。
问题2：
if语句中的条件应为：
B.。
A.S.top==S.MaxSizeB.S.top==S.MaxSize-11
算法5：
ElemTypeOutQueue（structQueueSq*Q）
{
if（Q->front==Q->rear）
{
printf（"Queueisempty!
\n"）;
exit
（1）;
}
Q->front=（Q->front+1）%Q->MaxSize;
returnQ->queue[Q->front];
}
问题1、算法适用的数据结构？
问题2、算法功能？
问题3、算法返回？
问题4、算法有无健壮性？
若有，是哪（些）语句？
问题5、算法的关键语句是哪（些）语句？
问题6、算法的时间复杂度大O（）？
七、分析题
1、有一个顺序存储的栈，最大存储空间MaxSize=5，栈顶指针top，现有A、B、C、D四个元素。
要求1：
写出顺序存储栈结构定义。
要求2：
画出初始化状态。
要求3：
画出以上四个元素依次进栈后的状态。
要求4：
在要求3的基础上，画出三个元素出栈后，又有E、F二个元素进栈，画出队首、队尾指针位置。
要求5：
以下是从栈中删除元素，并将被删除的元素值由函数返回的算法，请填写算法中缺失的语句。
答1：
typedefcharElemType;
structStack{
ElemType*stack[];
inttop;
intMaxSize;
};
答2：
答3：
答4：
答5：
ElemTypePop（Stack&S）
{
if（S.top==-1）{
cerr<<"Stackisempty!
"<exit
（1）;
}
ElemTypetemp=S.stack[S.top];
S.top--;
returntemp;
}
2、有一个顺序存储的循环队列，最大存储空间为5，假设队首指针指向队首元素的前一个位置，队尾指针指向队尾元素，现队列中已有A、B、C、三个元素。
要求1：
已有顺序存储队列结构的定义，请填写定义中缺失的语句。
要求2：
填写出初始化算法语句。
要求3：
画出经初始化后，以上三个元素依次进队后，队首、队尾指针位置。
要求4：
画出以上三个元素依次出队后，元素D、E依次进队后队首、队尾指针位置。
要求5：
以下是向队列中插入元素的算法，在不考虑扩充空间的前提下，请填写算法中缺失的语句或语句缺失的部分。
答1：
TypedefintElemType;
structQueue{
intMaxSize;
intfront,rear;
ElemType*queue;
};
答2：
voidInitQueue（Queue&Q）
{
Q.front=Q.rear=0;
}
答3：
答4：
答5：
voidQInsert（Queue&Q,constElemType&item）
{
intk=（Q.rear+1）%QueueMaxSize;
if（k==Q.front）
{
cerr<<"Queueoverflow!
"<exit
（1）;
}
Q.rear=k;
Q.queue[k]=item;
}
八、写出下列中缀表达式的后缀表达式和栈的变化，并写出求值过程栈的变化。
1、35＋6×（27－6）＋6/2
2、16+5×27＋8－5×4
3、7×（5＋77）/2＋6×9
十一、使用栈在计算机语言的编译过程中进行语法检查，只检查C++程序中的花括号、方括号、圆括号是否配对，算法：
试分析流程图后对下面算法中横线上空缺的语句进行填充，并在//符号后对语句进行文字说明，将填充的内容填入到程序中的字母序列中。
intBracketsCheck（char*fname）
{
Stacka;
InitStack（a）;
charch;
while（ifstr>>ch）
{
switch（ch）
{
case'{':
case'[':
case'（':
Push（a,ch）;//A：
字符进栈
break;
case'}':
if（Peek（a）=='{'）//B：
读栈顶元素进行判断
Pop（a）;//C：
栈顶元素出栈
else
return0;
break;
case']':
if（D：
Peek（a）==’[‘）
Pop（a）;
else
return0;
break;
case'）':
if（Peek（a）=='（'）
E：
Pop（a）;
else
return0;
}
}
if（F：
StackEmpty（a））{
cout<<"ok!
"<return1;}
else{
cout<<"bad!
"<return0;}
十二、已知线性表A={a1、a2、……an}采用链接存储结构，其数据域由4个值域组成，假设依次为
charcode[]
charname[]
intmax
intmin
要求：
1、定义单链表结点（包括对数据域的定义）；
2、从单链表的表头删除一个结点。
（参考答案）
答1：
goods{charcode[5];
charname[15];
intmax;
intmin;
};
ypedefstructtgoodsElemType;
structsNode{ElemTypedata;
structsNode*next;
};
答2：
ElemTypeDeleteFirstList（structsNode**HL）
{
ElemTypetemp;
structsNode*p=*HL;
if（*HL==NULL）{
printf（"Deletingfromanemptylist!
\n"）;
exit
（1）;
}
*HL=（*HL）->next;
temp=p->data;
free（p）;
returntemp;
}
十三、画出P15【算法1－3】简单选择排序的流程图，并带入5个整型数值进行排序过程分析，写出排序在执行过程中数组元素的变化。
inti,j,k,x
i=0
N
iY
k=i
j=i+1
N
jY
b[j]Y
k=j
j++
b[i]b[k]
i++
end
十四、教材上的习题：
升级会员 