试仿照三元的抽象数据类型分别写出抽象数据类型复数....doc

《试仿照三元的抽象数据类型分别写出抽象数据类型复数....doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章1.1试仿照三元组的抽象数据类型分别写出抽象数据类型复数的定义。1.2设n为正整数，试确定下列各程序段中前置以记号#的语句的频度。1.i=1;k=0;While(i<=n-1){#k+=10*i;i++;}2.i=1;k=0;do{#k+=10*i;i++;}While(i<=n-1);3.i=1;k=0;While(i<=n-1){i++;#k+=10*i;}4.k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)#k++;}5.for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)#x+=delt

2、a;;6.i=1;j=0;While(i+j<=n){#if(i>j)j++;elsei++;}7.x=n;y=0;While(x>=(y+1)*(y+1)){#y++;}8.x=91;y=100;While(y>0){#if(x>100){x-=10;y--;}elsex++;}1.3试写一算法，自大至小依次输出顺序读入的三个整数X、Y和Z的值。第二章2.1填空题1.在顺序表中插入或删除一个元素，需要平均移动（）个元素，具体移动的元素个数与（）有关。2.顺序表中逻辑上相邻的元素的物理位置（）相邻。单链表中逻辑上相邻的元素的物理位置（）相邻。3.在单链表中，除了第一个元素（首元结

3、点）外，任一结点的存储位置由（）指示。4.已知L是无表头结点的单链表，且P结点既不是首元结点，又不是尾元结点，则：（1）在P结点后插入S结点的语句序列是（）；（2）在P结点前插入S结点的语句序列是（）；（3）在表首插入S结点（S为表中第一个结点）的语句序列是（）；（4）在表尾插入S结点的语句序列是（）；5.已知L是带表头结点的非空单链表，且P结点既不是首元结点，又不是尾元结点，则：（1）删除P结点的直接后继结点的语句序列是（）；（2）删除P结点的直接前驱结点的语句序列是（）；（3）删除P结点的语句序列是（）；（4）删除首元结点的语句序列是（）；（5）删除尾元结点的语句序列是（）；

4、2.2设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2.3已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有值大于mink且小于maxk的元素。同时释放被删结点的空间，并分析你的算法的时间复杂度。（mink和maxk是给定的两个参数）2.4试写一算法，实现顺序表的就地逆置。即利用原表空间将线性表（a1，a2，…an）逆置为（an…，a2，a1）。2.5试写一算法，实现单链表的就地逆置。2.6．已知P结点是某双向链表的中间结点，则：（1）在P结点后插入S结点的语句序列是（）；（2）在P结点前插入S结点

5、的语句序列是（）；（3）删除P结点的直接后继结点的语句序列是（）；（4）删除P结点的直接前驱结点的语句序列是（）；（5）删除P结点的语句序列是（）；2.7．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A和B归并成一个按元素值递减有序（或非递增有序，允许A表和B表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。第三章3.1选择题。1.一个栈的入栈序列是a、b、c、d、e，则栈不可能的输出顺序是______A、edcbaB、decbaC、dceabD、abcde2.若已知一个栈的入栈序列是1，2，3，……，n，

6、其输出序列为p1，p2，p3，……pn，若p1=n,则pi=________A、iB、n=iC、n-i+1D、不确定3.判定一个顺序栈ST(当前分配的存储单元个数为M0)为空的条件是：_______A、ST.TOP！=0B、ST.TOP==0C、ST.TOP！=M0D、ST.TOP==ST.BASE4.判定一个顺序栈ST(当前分配的存储单元个数为M0)为满的条件是：_______A、ST.TOP！=M0B、ST.TOP==0C、ST.BASE！=M0D、ST.TOP-ST.BASE=M05.一个队列的入列序列是1，2，3，4，则队列的输出序列是_______A、4,3,2,1B、

7、1,2,3,4C、1,4,3,2D、3,2,4,16.判断一个顺序队列QU（最多的元素个数为m0）为空的条件是______A、QU.rear-QU.front==m0B、QU.rear-QU.front-1==m0C、QU.front==QU.rearD、QU.rear+1=QU.front7.判断一个顺序队列QU（最多的元素个数为m0）为满的条件是______A、QU.rear-QU.front==m0B、(QU.rear+1)%m0==QU.frontC、QU.front==