苏州大学数据结构课程期中考试答案文档格式.docx
《苏州大学数据结构课程期中考试答案文档格式.docx》由会员分享，可在线阅读，更多相关《苏州大学数据结构课程期中考试答案文档格式.docx（10页珍藏版）》请在冰点文库上搜索。
{
Node*new_rear=newNode（item）;
if（new_rear==NULL）returnoverflow;
if（rear==NULL）front=rear=new_rear;
;
else{
rear->
next=new_rear;
；
rear=new_rear;
}
returnsuccess;
5、如果一个函数直接或间接地调用自己，则称这个函数是一个递归函数。
6、在一个长度为n的顺序表中的第position（0≤position<
n）个位置删除某个元素时，需移动n-position-1个元素。
7、在线性表改进的单链表实现方法中，我们定义了一个current指针指向最近访问过的结点，请解释这样做的好处：
在对表中元素进行访问时，不需要每次都从头开始，在顺序访问或从前往后的访问中能提供操作效率。
8、用抽象数据类型对数据结构进行的ADT定义通常包含两个内容，分别是这种数据结构的逻辑结构定义以及基本操作集。
9、Evaluatethepostfixexpression:
2431+*+,whereeachnumberrepresentsanoperandandeachsymbolof+and*representsanoperator,pleasegivetheresultoftheexpressiononthefollowingline18。
10、在高级语言中为了实现函数之间的相互调用，需要用到栈作为辅助数据结构来存放调用记录（invocationrecord），调用记录中主要包含该调用函数的局部变量、参数和函数返回地址。
二、应用题（46分）
1、说明线性表、栈与队列的异同点。
（9分）
相同点：
都是线性结构，都是逻辑结构的概念。
都可以用顺序存储或链表存储；
栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：
1运算规则不同
线性表可以在任何合法位置进行插入和删除；
栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；
队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
2用途不同
线性表用于处理更一般的数据处理场合；
堆栈用于子程调用和保护现场；
队列用于多道作业处理、资源分配等。
2、Acircularqueuehastheprobleminwhichitisnoteasytodistinguishbetweenfullandemptyqueues.
Drawtwosituationstoillustratethisfrontandrearpointersshouldbeinthesamepositionineachsituation.
Giveansolutiontodistinguishbetweenfullandemptyqueues.（9分）
答：
用损失一个空间的方法，
即人为地将队满条件修改为：
front=（rear+2）%maxqueue;
队空条件不变，仍为：
front=（rear+1）%maxqueue;
3、WhatiswrongwiththefollowingattempttousethecopyconstructortoimplementtheoverloadedassignmentoperatorforalinkedStack?
voidStack:
operator=（constStack&
original）
Stacknew_copy（original）;
top_node=;
Answer
（1）Theassignmenttop_node=;
leavestheformernodesofthelefthandsideoftheassignmentoperatorasgarbage.应该回收的空间没回收，结果丢了变成垃圾！
（2）Moreover,whenthefunctionends,thestaticallyallocated
Stacknew_copywillbedestructed,thiswilldestroythenewlyassignedlefthandsideoftheassignmentoperator.
把需要赋值不该回收的空间回收了。
4、简述顺序线性表和链式线性表两种存储结构的优缺点和适用场合。
（10分）
顺序表的缺点：
Overflow,可能溢出
Mustdeterminethemaximumamountofthelist,必须确定表的最大长度
Insertwillcausemoving.插入删除带来元素的移动
顺序表的优点：
Randomaccess随机存取,读写效率为O
（1）
适用场合：
whentheentriesareindividuallyverysmall;
元素个体较小
whenthesizeofthelistisknownwhentheprogramiswritten;
表长能事先确定
whenfewinsertionsordeletionsneedtobemadeexceptattheendofthelist;
很少在非尾部位置插入和删除
whenrandomaccessisimportant经常需要根据位序进行读写
链表的优点：
Don’tworryaboutoverflow不需要担心溢出
Dynamicstructure动态的结构，不需事先申请空间
Insertonlyneedchangethelinks.插入删除只引起指针的变化
链表的缺点：
Thelinksalsotakespace.链域也占空间，使存储密度降低
Nottosuitedtorandomaccess.不能做到随机存取，读写效率为O（n）
whentheentriesarelarge;
元素个体较大
whenthesizeofthelistisnotknowninadvance;
不能事先确定
whenflexibilityisneededininserting,deletingandrearrangingtheentries经常需要做插入、删除和元素的重排
5、为了求解两个一元多项式的和，需要将多项式存储到计算机中。
请设计多项式的逻辑结构和存储结构，说明你这样设计的原因。
多项式的逻辑结构：
1、由Term元素构成的线性表。
2、Term是一个结构体，包含有一个非零项的系数和指数
3、此线性表为递减有序表，按各非零项的指数递减有序。
4、在做多项式加法时，从两个多项式的头上删除相应的非零项结点，进行指数的比较，生成相应的项结点，插入到结果表的尾部，所以，这个操作的特点是头上删除，尾部插入，所以可将多项式设计为一个队列。
多项式的存储结构：
用链式结构比较合适。
事先不知道多项式的长度，多项式系数不连续，建议采用链式结构。
三、算法设计题（26分）
1、设stack类接口定义如下，
classStack{
public:
Stack（）;
boolempty（）const;
Error_codepop（）;
Error_codetop（Stack_entry&
item）const;
Error_codepush（constStack_entry&
item）;
intsize（）;
voidclear（）;
private:
……
}
使用以上栈的方法，设计外部函数bottom（）。
要求:
如果栈非空，则返回栈底的数据元素；
如果栈空，返回错误代码fail。
注意在实现bottom（）后不能破坏栈原来的内容，你所书写的代码不能依赖于栈的具体存储方式，即必须使用上述的栈方法。
提示：
可以使用临时栈来实现算法。
请用以下函数原型进行设计。
（8分）
Error_codebottom（Stack&
s,Stack_entry&
Stacktemp;
Stack_entryt;
if（））returnfail;
while（!
（））{
（t）;
（）;
item=t;
2、假设用不带current指针的简单单链表作为线性表List的存储结构。
（1）为List类添加一个递归成员函数，统计表中值为item的结点的个数。
例如：
线性表为：
（7，2，1，7，2，3，6，5）
统计链表中值为7的结点数，返回结果应为2。
template<
classList_entry>
voidList<
List_entry>
:
rec_count（Node<
*head,List_entryitem,int&
count）
if（head==NULL）
return;
else
if（head->
entry==item）
count++;
rec_count（head->
next,item,count）;
（2）为List添加一个成员函数，删除线性表中所有值为item的结点。
原线性表为：
删除7之后的表为：
（2，1，2，3，6，5）
请按以下函数原型进行设计，其中count返回被删除的元素的个数。
Error_codeList<
removealloccurance（List_entryitem,int&
Node<
*p,*q;
count=0;
p=head;
while（p!
=NULL）
if（p->
entry!
=item）
break;
else{
head=p->
next;
deletep;
count++;
p=head;
//删除表首与item相同的结点，可能有多个连续相同的结点
//若此时已为空表，则返回
q=head;
p=head->
//表长大于等于1
//q,p分别为链表的0号和1号结点（如果1号结点不存在，则p为空），
//0号结点的值肯定不是item
//以下要求保证p,q保持前后相邻
if（p->
entry==item）{
q->
next=p->
deletep;
//删除p结点
p=q->
//维护p的值
}
else
{
q=p;
p=p->
//q,p分别向后移动
升级会员 