《xx大学数据结构课程期中考试试题与答案》由会员分享，可在线阅读，更多相关《xx大学数据结构课程期中考试试题与答案（6页珍藏版）》请在金锄头文库上搜索。
1、 .wd.苏州大学数据构造课程期中考试共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由大到小，那么判断双栈栈满的条
2、件是top1+1=top2 ，双栈栈空的条件是top1=-1 & top2=n。4、完成链式存储构造下Queue类的append方法，其中front和rear指针分别指示队首和队尾结点：Error_code Queue : append(const Queue_entry &item)Node *new_rear = newNode(item);if (new_rear = NULL) return overflow;if (rear = NULL)front=rear=new_rear; ;else rear-next=new_rear; ；rear = new_rear;return su
3、ccess;5、如果一个函数直接或间接地调用自己，那么称这个函数是一个递归函数。6、在一个长度为n的顺序表中的第position0positionn个位置删除某个元素时，需移动n-position-1个元素。7、在线性表改进的单链表实现方法中，我们定义了一个current指针指向最近访问过的结点，请解释这样做的好处：在对表中元素进展访问时，不需要每次都从头开场，在顺序访问或从前往后的访问中能提供操作效率。8、用抽象数据类型对数据构造进展的ADT定义通常包含两个内容，分别是这种数据构造的逻辑构造定义以及 基本操作集。9、Evaluate the postfix expression:2 4 3
4、1 + * +,where each number represents an operand and each symbol of + and * represents an operator, please give the result ofthe expression on the following line18。10、在高级语言中为了实现函数之间的相互调用，需要用到栈作为辅助数据构造来存放调用记录invocation record，调用记录中主要包含该调用函数的局部变量、参数和函数返回地址。二、 应用题46分1、说明线性表、栈与队列的异同点。9分一样点：都是线性构造，都是逻辑构造的
5、概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。不同点： 运算规那么不同线性表可以在任何合法位置进展插入和删除；栈是只允许在一端进展插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进展插入、另一端进展删除运算，因而是先进先出表FIFO。 用途不同线性表用于处理更一般的数据处理场合；堆栈用于子程调用和保护现场；队列用于多道作业处理、资源分配等。2、A circular queue has the problem in which it is not easy to distinguish between full and e
6、mpty 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 w
7、ith 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 no
8、des 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、简述顺序线性表和链式线性表两种存储构造的优
9、缺点和适用场合。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 inser
10、tions 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 suite
11、d 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、 由T
12、erm元素构成的线性表。2、 Term是一个构造体，包含有一个非零项的系数和指数3、 此线性表为递减有序表，按各非零项的指数递减有序。4、 在做多项式加法时，从两个多项式的头上删除相应的非零项结点，进展指数的比较，生成相应的项结点，插入到结果表的尾部，所以，这个操作的特点是头上删除，尾部插入，所以可将多项式设计为一个队列。多项式的存储构造：用链式构造比较适宜。事先不知道多项式的长度，多项式系数不连续，建议采用链式构造。三、算法设计题26分1、设stack类接口定义如下， class Stackpublic:Stack() ;bool empty() const ;Error_code pop(
13、) ;Error_codetop(Stack_entry&item) const;Error_code push(const Stack_entry&item) ;int size(); void clear() ;private:使用以上栈的方法，设计外部函数bottom()。要求:如果栈非空，那么返回栈底的数据元素；如果栈空，返回错误代码fail。注意在实现bottom()后不能破坏栈原来的内容，你所书写的代码不能依赖于栈的具体存储方式，即必须使用上述的栈方法。提示：可以使用临时栈来实现算法。请用以下函数原型进展设计。(8分)Error_codebottom( Stack&s, Stack
14、_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 voidList : 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请按以下函数原型进展设计，其中coun
