1、1苏州大学 数据结构 课程期中考试（共 6 页）学院 计算机 专业 计算机科学与技术 成绩_班级 11 计科 学号_姓名_日期 2012.11_一、 填空（14*2 分）1、下列算法的时间复杂度是 O( ) 。nx=n;y=0;while (x=y*y)y=y+1;2、 对于顺序存储的栈，因为栈的空间是有限的，在进行 入栈 运算时，可能发生栈的上溢（overflow） ，在进行 出栈 _运算时，可能发生栈的下溢(underflow) 。3、以顺序结构实现的双栈类中，其私有数据成员数组 S0.n-1存放两个栈中的所有元素，top1 和 top2 分别指向两个栈的栈顶位置，入栈 1 时 top1
2、由小到大，入栈 2 时 top2 由大到小，则判断双栈栈满的条件是 top1+1=top2 ，双栈栈空的条件是 top1=-1 if (new_rear = NULL) return overflow;if (rear = NULL) front=rear=new_rear; ;else rear-next=new_rear; ；rear = new_rear;return success;5、如果一个函数直接或间接地 调用 自己，则称这个函数是一个递归函数。26、在一个长度为 n 的顺序表中的第 position（0positionvoid List : rec_count(Node *he
3、ad,List_entry item,int 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=0;p=head;wh
4、ile (p!=NULL)if ( p-entry!=item )break;elsehead=p-next;delete p;count+;p=head;/删除表首与 item 相同的结点，可能有多个连续相同的结点if (head=NULL)10return 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;
