苏州大学_数据结构_课程期中考试答案.doc

《苏州大学_数据结构_课程期中考试答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、......苏州大学数据结构课程期中考试（共6页）学院计算机专业计算机科学与技术成绩____________________班级11计科学号_____________姓名_____________日期2012.11_一、填空（14*2分）1、下列算法的时间复杂度是O()。x=n;y=0;while(x>=y*y)y=y+1;2、对于顺序存储的栈，因为栈的空间是有限的，在进行入栈运算时，可能发生栈的上溢（overflow），在进行出栈_运算时，可能发生栈的下溢(underflow)。3、以顺序结构实现的双栈类中

2、，其私有数据成员数组S[0..n-1]存放两个栈中的所有元素，top1和top2分别指向两个栈的栈顶位置，入栈1时top1由小到大，入栈2时top2由大到小，则判断双栈栈满的条件是top1+1>=top2，双栈栈空的条件是top1==-1&&top2==n。4、完成链式存储结构下Queue类的append方法，其中front和rear指针分别指示队首和队尾结点：Error_codeQueue::append(constQueue_entry&item){Node*new_rear=newNode(item);

3、if(new_rear==NULL)returnoverflow;if(rear==NULL)front=rear=new_rear;;else{rear->next=new_rear;；rear=new_rear;}returnsuccess;}5、如果一个函数直接或间接地调用自己，则称这个函数是一个递归函数。专业word可编辑.......6、在一个长度为n的顺序表中的第position（0≤position

4、中，我们定义了一个current指针指向最近访问过的结点，请解释这样做的好处：在对表中元素进行访问时，不需要每次都从头开始，在顺序访问或从前往后的访问中能提供操作效率。8、用抽象数据类型对数据结构进行的ADT定义通常包含两个内容，分别是这种数据结构的逻辑结构定义以及基本操作集。9、Evaluatethepostfixexpression:2431+*+,whereeachnumberrepresentsanoperandandeachsymbolof+and*representsanoperator,plea

5、segivetheresultoftheexpressiononthefollowingline18。10、在高级语言中为了实现函数之间的相互调用，需要用到栈作为辅助数据结构来存放调用记录（invocationrecord），调用记录中主要包含该调用函数的局部变量、参数和函数返回地址。一、应用题（46分）1、说明线性表、栈与队列的异同点。（9分）相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点：①运算规则不同

6、线性表可以在任何合法位置进行插入和删除；栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同专业word可编辑.......线性表用于处理更一般的数据处理场合；堆栈用于子程调用和保护现场；队列用于多道作业处理、资源分配等。专业word可编辑.......2、Acircularqueuehastheprobleminwhichitisnoteasytodistinguishbetweenfullandemptyqueu

7、es.Drawtwosituationstoillustratethispoint.Thefrontandrearpointersshouldbeinthesamepositionineachsituation.Giveansolutiontodistinguishbetweenfullandemptyqueues.（9分）答：用损失一个空间的方法，即人为地将队满条件修改为：front=(rear+2)%maxqueue;队空条件不变，仍为：front=(rear+1)%maxqueue;专业word可编辑.

8、......3、WhatiswrongwiththefollowingattempttousethecopyconstructortoimplementtheoverloadedassignmentoperatorforalinkedStack?（9分）voidStack::operator=(constStack&original){Stacknew_copy(original);top_node