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

第一章 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+=delta;; 6. i=1;j=0; While (i+j=n) { # if (ij) j++; else i++; } 7. x=n; y=0; While (x=(y+1)*(y+1)) { # y++; } 8. x=91; y=100; While (y0) { # if (x100) { x-=10; y--; } else x++; } 1.3 试写一算法，自大至小依次输出顺序读入的三个整数X、Y和Z的值。 第二章 2.1填空题 1.在顺序表中插入或删除一个元素，需要平均移动（ ）个元素，具体移动的元素个数与（ ）有关。 2.顺序表中逻辑上相邻的元素的物理位置（ ）相邻。单链表中逻辑上相邻的元素的物理位置（ ）相邻。 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）删除尾元结点的语句序列是（ ）； 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结点的语句序列是（ ）； （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、edcba B、decba C、dceab D、abcde 2.若已知一个栈的入栈序列是1，2，3，……，n，其输出序列为p1，p2，p3，……pn，若p1=n,则pi=________ A、i B、n=i C、n-i+1 D、不确定 3.判定一个顺序栈ST(当前分配的存储单元个数为M0)为空的条件是：_______ A、ST.TOP！=0 B、ST.TOP==0 C、ST.TOP！=M0 D、ST.TOP= =ST.BASE 4.判定一个顺序栈ST(当前分配的存储单元个数为M0)为满的条件是：_______ A、ST.TOP！=M0 B、ST.TOP==0 C、ST.BASE！=M0 D、ST.TOP-ST.BASE=M0 5.一个队列的入列序列是1，2，3，4，则队列的输出序列是_______ A、4,3,2,1 B、1,2,3,4