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

苏州大学 数据结构 课程期中考试（共6页）学院 计算机 专业 计算机科学与技术 成绩_班级 11计科 学号_姓名_日期 2012.11_一、 填空（14*2 分）1、下列算法的时间复杂度是 O() 。x=n;y=0;while (x=y*y)y=y+1;2、 对于顺序存储的栈，因为栈的空间是有限的，在进行 入栈 运算时，可能发生栈的上溢（overflow），在进行 出栈 _运算时，可能发生栈的下溢(underflow)。3、以顺序结构实现的双栈类中，其私有数据成员数组S0.n-1存放两个栈中的所有元素，top1和top2分别指向两个栈的栈顶位置，入栈1时top1由小到大，入栈2时top2由大到小，则判断双栈栈满的条件是 top1+1=top2 ，双栈栈空的条件是 top1=-1 & top2=n 。4、完成链式存储结构下Queue类的append方法，其中front和rear指针分别指示队首和队尾结点：Error_code Queue : append(const Queue_entry &item)Node *new_rear = new Node(item);if (new_rear = NULL) return overflow;if (rear = NULL) front=rear=new_rear; ;else rear-next=new_rear; ；rear = new_rear;return success;5、如果一个函数直接或间接地 调用 自己，则称这个函数是一个递归函数。6、在一个长度为n的顺序表中的第position（0positionn）个位置删除某个元素时，需移动 n-position-1 个元素。7、在线性表改进的单链表实现方法中，我们定义了一个current指针指向最近访问过的结点，请解释这样做的好处： 在对表中元素进行访问时，不需要每次都从头开始，在顺序访问或从前往后的访问中能提供操作效率。8、用抽象数据类型对数据结构进行的ADT定义通常包含两个内容，分别是这种数据结构的逻辑结构定义以及 基本操作集 。9、Evaluate the postfix expression: 2 4 3 1 + * + , where each number represents an operand and each symbol of + and * represents an operator, please give the result of the expression on the following line 18 。10、在高级语言中为了实现函数之间的相互调用，需要用到 栈 作为辅助数据结构来存放调用记录（invocation record），调用记录中主要包含该调用函数的局部变量、参数和 函数返回地址 。二、 应用题（46分）1、说明线性表、栈与队列的异同点。（9分）相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点： 运算规则不同线性表可以在任何合法位置进行插入和删除；栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 用途不同线性表用于处理更一般的数据处理场合；堆栈用于子程调用和保护现场；队列用于多道作业处理、资源分配等。2、A circular queue has the problem in which it is not easy to distinguish between full and empty queues.Draw two situations to illustrate this point.The front and rear pointers should be in the same position in each situation. Give an solution to distinguish between full and empty queues.（9分）答：用损失一个空间的方法，即人为地将队满条件修改为：front=(rear+2)%maxqueue;队空条件不变，仍为：front=(rear+1)%maxqueue;3、What is wrong with the following attempt to use the copy constructor to implement the overloaded assignment operator for a linked Stack?（9分）void Stack : operator = (const Stack &original)Stack new_copy(original);top_node = new_copy.top_node;Answer (1) The assignment top_node = new_copy.top_node; leaves the former nodes of the left hand side of the assignment operator as garbage.应该回收的空间没回收，结果丢了变成垃圾！(2) Moreover, when the function ends, the statically allocatedStack new_copy will be destructed, this will destroy the newly assigned left hand side of the assignment operator. 把需要赋值不该回收的空间回收了。4、简述顺序线性表和链式线性表两种存储结构的优缺点和适用场合。（10分）顺序表的缺点：Overflow,可能溢出Must determine the maximum amount of the list,必须确定表的最大长度Insert will cause moving .插入删除带来元素的移动顺序表的优点：Random access 随机存取, 读写效率为O(1)适用场合：when the entries are individually very small;元素个体较小when the size of the list is known when the program is written;表长能事先确定when few insertions or deletions need to be made except at the end of the list; 很少在非尾部位置插入和删除when random access is important 经常需要根据位序进行读写链表的优点：Dont worry about overflow 不需要担心溢出Dynamic structure 动态的结构，不需事先申请空间Insert only need change the links. 插入删除只引起指针的变化链表的缺点：The links also take space. 链域也占空间，使存储密度降低Not to suited to random access. 不能做到随机存取，读写效率为O(n)适用场合：when the entries are large; 元素个体较大when the size of the list is not known in advance; 不能事先确定when flexibility is needed in inserting, deleting and rearranging the entries经常需要做插入、删除和元素的重排5、为了求解两个一元多项式的和，需要将多项式存储到计算机中。请设计多项式的逻辑结构和存储结构，说明你这样设计的原因。（9分）多项式的逻辑结构：1、 由Term元素构成的线性表。2、 Term是一个结构体，包含有一个非零项的系数和指数3、 此线性表为递减有序表，按各非零项的指数递减有序。4、 在做多项式加法时，从两个多项式的头上删除相应的非零项结点，进行指数的比较，生成相应的项结点，插入到结果表的尾部，所以，这个操作的特点是头上删除，尾部插入，所以可将多项式设计为一个队列。多项式的存储结构：用链式结构比较合适。事先不知道多项式的长度，多项式系数不连续，建议采用链式结构。三、算法设计题（26分）1、设stack类接口定义如下， class Stack public:Stack() ;bool empty() const ;Error_code pop() ;Error_code top(Stack_entry &item) const;Error_code push(const Stack_entry &item) ;int size(); void clear() ;private:使用以上栈的方法，设计外部函数bottom()。要求:如果栈非空，则返回栈底的数据元素；如果栈空，返回错误代码fail。注意在实现bottom()后不能破坏栈原来的内容，你所书写的代码不能依赖于栈的具体存储方式，即必须使用上述的栈方法。提示：可以使用临时栈来实现算法。请用以下函数原型进行设计。(8分)Error_code bottom( Stack &s, Stack_entry &item)Stack temp;Stack_entry t;if (s.empty() return fail;while (!s.empty( ) s.top(t);s.pop( );temp.push(t);item=t;while (!temp.empty( ) temp.top(t);temp.pop( );s.push(t);return success;2、假设用不带current指针的简单单链表作为线性表List的存储结构。（1）为List类添加一个递归成员函数，统计表中值为item的结点的个数。例如：线性表为：（7，2，1，7，2，3，6，5）统计链表中值为7的结点数，返回结果应为2。（8分）template void List : rec_count(Node *head,List_entry item,int &count)if (head=NULL)return ;elseif (head-entry=item)count+; rec_count(head-next,item,count);(2)为List添加一个成员函数，删除线性表中所有值为item的结点。例如：原线性表为：（7，2，1，7，2，3，6，5）删除7之后的表为：（2，1，2，3，6，5）请按以下函数原型进行设计，其中count返回被删除的元素的个数。（10分）template Error_code List : removealloccurance(List_entry item,int &count)Node *p,*q;count=0;p=head;while (p!=NULL)if ( p-entry!=item )break;elsehead=p-next;delete p;count+;p=head;/删除表首与item相同的结点，可能有多个连续相同的结点if (head=NULL)return success;/若此时已为空表，则返回q=head;p=head-next;/表长大于等于1/q,p分别为链表的0号和1号结点（如果1号结点不存在，则p为空），/0号结点的值肯定不是item/以下要求保证p,q保持前后相邻while (p!=NULL)if (p-entry=item)q-next=p-next;delete p;count+;/删除p结点p=q-next;/维护p的值elseq=p;p=p-next;/q,p分别向后移动return success;10