第一章
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 (i>j) j++; else i++; } 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--; } 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 C、1,4,3,2 D、3,2,4,1
6.判断一个顺序队列QU（最多的元素个数为m0）为空的条件是______ A、QU.rear-QU.front==m0 B、QU.rear-QU.front-1==m0 C、QU.front= =QU.rear D、QU.rear+1=QU.front
7.判断一个顺序队列QU（最多的元素个数为m0）为满的条件是______ A、QU.rear-QU.front==m0 B、(QU.rear+1)%m0= =QU.front C、QU.front= =QU.rear D、QU.rear+1=QU.front
8.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数为_______ A、(rear-front+m)%m B、rear-front+1
C、rear-front-1 D、rear-front 9.栈和队列的共同点是_____
A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点
3.2．假设以顺序存储结构实现一个双向栈（即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两端）。试编写实现这个双向栈tws的三个操作：初始化操作IniStack(tws)、入栈操作push(tws,i,x)和出栈操作pop(tws,i,x) 的算法（其中i的值为0或1，分别用来指示设在数组两端的两个栈：0表示是对低地址端的栈进行操作，1表示是对高地址端的栈进行操作）。
3.3．假设以带头结点循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试用数据类型表示这种栈，并写出相应的队列初始化、入队和出队操作的算法。
第四章
4.1选择题
1、如下陈述中正确的是（ ）
A、 串是一种特殊的线性表B、 串的长度必须大于0 C、串中元素只能是字母D、空串就是空白串 2、设字符串s1=‘abcdefg’，s2=‘pqrst’，则运算s=strcat（substr（s1，2，length（s2）），substr（s1，length（s2），2））后串值为（ ）
A、‘bcdefef’B、‘bcpqrst’C、‘bcdefg’D、‘bcdef’ 3、以下论述正确的是（ ）
A、空串和空格串是相同的 B、串中元素只能是26个英文字母 C、空串是零个字符的串 D、空串长度为1 4、设某串长度为n，则它的子串个数是（ ）
A、 n B、 n（n+1） C、 n（n+1）/2 D、 n（n+1）/2+1 5、设字符串s=‘sciencestudy’，则进行运算scopy（p，substr（s，1，7）后得到（ ）
A、 p=‘science’ B、p=‘study’ C、s=‘science’ D、 s=‘study’
6、若串s=”software”，则其子串的个数是（ ）
A、8 B、9 C、36 D、37 7、
4.2填空题
1、串是一种特殊的线性表，其特殊性表现在_____________
2、设有两个串p和q，求q在p中首次出现的位置的运算称作________
3、设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号 i 的字符开始的j个字符组成的子串,len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果是___________
4、两个串相等的充分必要是_________
5、空串是______________，其长度等于_______ 1、空格串是__________其长度等于_______ 2、设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位序为 。
3、设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 次匹配成功。
第五章
5.1选择题
1、递归函数f(n)=f(n-1)+n(n>1)的递归出口是_______
A、f(1)=0 B、f(1)=1 C、f(0)=1 D、f(n)=n 2、递归函数f(n)=f(n-1)+n(n>1)的递归体是_______
A、f(1)=0 B、f(0)=1 C、f(n)=f(n-1)+n D、f(n)=n 3、将递归算法转换成对应的非递归算法时，通常需要采用________ A、栈 B、队列 C、链表 D、树
4、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围是从0到7，列下标j的范围从0到9，则存放M需要存储单元数为（ ）
A、360 B、480 C、240 D、320
5、假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ ）。（无第0行第0列元素）
Ａ、16902 B、16904 C、14454 D、答案A, B, C均不对 6、已知广义表A=（（a，b，c），（d，e，f）），则广义表A的表尾是（ ） Ａ、（d，e，f） B、（（d，e，f）） C、f D、（f）
7、设有一个二维数组A[10][15],数组按行存放，假设A[0][0]存放位置在644,每个元素占一个空间，则A[4][5]在（ ）位置.
A、 672 B、626 C、709 D、724 5.2填空题
1、已知二维数组A[m][n]采用行序为主方式存储，每个元素占据k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_________ 2、已知二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]单元的存储地址是200，则A[6][12]的地址是________
3、二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占四个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是_______ 4、广义表（（a）,a）的表头是________，表尾是________. 5、广义表（（a））的表头是_________，表尾是_________
6、广义表（a,b,c,d）的表头是_________,表尾是__________
7、广义表（a,(a,b),d,e((i,j),k)）的长度是________,深度是_______
8、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 9、GetHead((a,b),(c,d))=
10、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素A57的第一个字节地址 ；若按行存储时，元素A14的第一个字节地址 ；若按列存储时，元素A47的第一个字节地址为 。
11、GetHead【GetTail【((a,b),(c,d))】】= 。
12、三元组表中的每个结点对应于稀疏矩阵中的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。