s+=B[i][j];
sum=s;
10.下面程序段的时间复杂度是①O（log3n）。
i=1;
while（i<=n）
i=i*3;
1.3算法设计题:
1.试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.
习题答案
1.11.AB2.BD3.C4.AB5.CA6.CB7.B8.D
9.B10.B
1.21.线性结构、树形结构、图形结构、非线性结构
2.没有、1、没有、1
3.前驱、1、后续、任意多个
4.任意多个
5.一对一、一对多、多对多
6.有穷性、确定性、可行性、输入、输出
7.O（m*n）
8.O（n
）
9.O（n2）
10.log3n
习题
（二）顺序表示（线性表、栈和队列）
2.1单项选择题
1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是B。
A.110B.108C.100D.120
2.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C。
A.edcbaB.decbaC.dceabD.abcde
3.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为C。
A.iB.n=iC.n-i+1D.不确定
4.栈结构通常采用的两种存储结构是A。
A.顺序存储结构和链式存储结构
B.散列方式和索引方式
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
5.判定一个栈ST（最多元素为m0）为空的条件是B。
A.ST—>top!
=0B.ST—>top==0
C.ST—>top!
=m0D.ST—>top==m0
6.判定一个栈ST（最多元素为m0）为栈满的条件是D。
A.ST—>top！
=0B.ST—>top==0
C.ST—>top！
=m0D.ST—>top==m0
7.栈的特点是B，队列的特点是A。
A.先进先出B.先进后
8.一个队列的入列序列是1，2，3，4，则队列的输出序列是B。
A.4，3，2，1B.1，2，3，4
C.1，4，3，2D.3，2，4，1
9.判定一个队列QU（最多元素为m0）为空的条件是C。
A.QU—>rear—QU—>front==m0
B.QU—>rear—QU—>front-1==m0
C.QU—>front==QU—>rear
D.QU—>front==QU—>rear+1
10.判定一个队列QU（最多元素为m0,m0+1==Maxsize）为满队列的条件是A。
A.（（QU—>rear-QU—>front）+Maxsize）%Maxsize==m0
B.QU—>rear—QU—>front-1==m0
C.QU—>front==QU—>rear
D.QU—>front==QU—>rear+1
11.判定一个循环队列QU（最多元素为m0）为空的条件是A。
A.QU—>front==QU—>rear
B.QU—>front！
=QU—>rear
C.QU—>front==（QU—>rear+1）%m0
D.QU—>front！
=（QU—>rear+1）%m0
12.判定一个循环队列QU（最多元素为m0）为满队列的条件是C。
A.QU—>front==QU—>rear
B.QU—>front！
=QU—>rear
C.QU—>front==（QU—>rear+1）%m0
D.QU—>front！
=（QU—>rear+1）%m0
13.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是A。
A.（rear-front+m）%mB.rear-front+1
C.rear-front-1D.rear-front
14.栈和队列的共同点是C。
A.都是先进后出B.都是先进先出
C.只允许在端点处插入和删除元素D.没有共同点
2.2填空题（将正确的答案填在相应的空中）
1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队首插入元素和队尾删除元素。
2.向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素。
3.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动n-i个元素。
4.向栈中压入元素的操作是先移动栈顶指针，后存入元素。
5.对栈进行退栈时的操作是先取出元素，后移动栈顶指针。
6.在一个循环队列中，队首指针指向队首元素的前一个位置。
7.从循环队列中删除一个元素时，其操作是先移动队首元素，后取出元素。
8.在具有n个单元的循环队列中，队满时共有n-1个元素。
9.一个栈的输入序列是12345，则栈的输出序列43512是不可能的。
10.一个栈的输入序列是12345，则栈的输出序列12345是可能的。
2.3算法设计题:
设顺序表va中的数据元数递增有序。
试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,….an）逆置为（an,an-1,….,a1）。
按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A-B*C/D+E↑F
习题答案
2.11.B2.C3.C4.A5.B6.D7.BA8.B9.C
10.A11.A12.C13.A14.C
2.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i
4.先移动栈顶指针，后存入元素5.先取出元素，后移动栈顶指针
6.前一个位置7.先移动队首元素，后取出元素
8.n-19.不可能的10.可能的
习题三链表（线性表、栈和队列）
3.1单项选择题
1.不带头结点的单链表head为空的判定条件是A。
A.head==NULLB.head—＞next==NULL
C.head—＞next==headD.head!
=NULL
2.带头结点的单链表head为空的判定条件是B。
A.head==NULLB.head—＞next==NULL
C.head—＞next==headD.head!
=NULL
3.非空的循环单链表head的尾结点（由p所指向）满足C。
A.p—＞next==NULLB.p==NULL
C.p—＞next==headD.p==head
4.在循环双链表的p所指结点之后插入s所指结点的操作是D。
A.p—＞right=s;s—＞left=p;p—＞right—＞left=s;s—＞right=p—＞right;
B.p—＞right=s;p—＞right—＞left=s;s—＞left=p;s—＞right=p—＞right;
C.s—＞left=p;s—＞right=p—＞right;p—＞right=s;p—＞right—＞left=s;
D.s—＞left=p;s—＞right=p—＞right;p—＞right—＞left=s;p—＞right=s;
5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行C。
A.s—＞next=p—＞next;p—＞next=s;
B.p—＞next=s—＞next;s—＞next=p;
C.q—＞next=s;s—＞next=p;
D.p—＞next=s;s—＞next=q;
6.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行B。
A.s—＞next=p;p—＞next=s;
B.s—＞next=p—＞next;p—＞next=s;
C.s—＞next=p—＞next;p=s;
D.p—＞next=s;s—＞next=p;
7.在一个单链表中，若删除p所指结点的后续结点，则执行A。
A.p—＞next=p—＞next—＞next；
B.p=p—＞next;p—＞next=p—＞next—＞next；
C.p—＞next=p—＞next;
D.p=p—＞next—＞next；
9.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较D个结点。
A.nB.n/2C.（n-1）/2D.（n+1）/2
10.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是B。
A.O
（1）B.O（n）C.O（n2）D.O（nlog2n）
11.给定有n个元素的向量，建立一个有序单链表的时间复杂度是C。
A.O
（1）B.O（n）C.O（n2）D.O（nlog2n）
12.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行C。
（不带空的头结点）
A.HS—＞next=s;
B.s—＞next=HS—＞next;HS—＞next=s;
C.s—＞next=HS;HS=s;
D.s—＞next=HS;HS=HS—＞next;
13.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行D。
（不带空的头结点）
A.x=HS;HS=HS—＞next;B.x=HS—＞data;
C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;
3.2填空题（将正确的答案填在相应的空中）
1.单链表是线性表的链接存储表示。
2.可以使用双链表表示树形结构。
3.在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后续结点。
4.在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：
⑴s—＞next=p—＞next;
⑵p—＞next=s;
⑶t=p—＞data;
⑷p—＞data=s—＞data;
⑸s—＞data=t;
5.在一个单链表中删除p所指结点时，应执行以下操作：
q=p—＞next;
p—＞data=p—＞next—＞data;
p—＞next=p—＞next—＞next;
free（q）;
6.带有一个头结点的单链表head为空的条件是head—＞next==NULL。
7.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s—＞next=p—＞next和p—＞next=s的操作。
8.非空的循环单链表head的尾结点（由p所指向），满足条件p—＞next=head。
9.在栈顶指针为HS的链栈中，判定栈空的条件是HS==NULL。
10.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是O
（1）；在给定值为x的结点后插入一个新结点的时间复杂度是O（n）。
3.3算法设计题:
1.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。
试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。
2.试写一算法，实现单链表的就地逆置。
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
习题答案
3.11.A2.B3.C4.D5.C6.B7.A9.D
10.B11.C12.C13.D
3.21.线性表2.双链表
3.前驱结点、后续结点
4.p—＞next、s—＞data、t
5.p—＞next—＞next
6.head—＞next==NULL
7.p—＞next、s
8.p—＞next=head
9.HS==NULL
11.O
（1）、O（n）
习题四串
4.1单项选择题
1.空串与空格串是相同的，这种说法B。
A.正确B.不正确
2.串是一中特殊的线性表，其特殊性体现在B。
A.可以顺序存储B.数据元素是一个字符
C.可以链接存储D.数据元素可以是多个字符
3.设有两个串p和q，求q在p中首次出现的位置的运算称作B。
A.连接B.模式匹配
C.求子串D.求串长
4.设串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））的结果串是D。
A.BCDEFB.BCDEFG
C.BCPQRSTD.BCDEFEF
4.2填空题（将正确的答案填在相应的空中）
1.串的两种最基本的存储方式是顺序存储方式和链接存储方式。
2.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
3.空串是零个字符的串，其长度等于0。
4.空格串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。
5.设s=’I︺AM︺A︺TEACHER’,其长度是14。
4.3算法设计题:
1．编写算法，从串s中删除所有和串t相同的子串。
2.编写算法，实现串的基本操作Replace（&S,T,V）。
习题答案
4.11.B2.B3.B4.D
4.21.顺序存储方式和链接存储方式
2.两个串的长度相等且对应位置的字符相同
3.零个字符的串、零
4.由一个或多个空格字符组成的串、其包含的空格个数
5.14
习题五数组
5.1单项选择题（其中A[i..j]表示下标从i到j）
1.常对数组进行的两种基本操作是C。
A.建立与删除B.索引和修改
C.查找和修改D.查找与索引
2.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要①D个字节；M的第8列和第5行共占②B个字节。
①A.90B.180C.240D.540
②A.108B.114C.54D.60
4.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是C。
A.80B.100C.240D.270
5.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为C。
A.SA+141B.SA+144C.SA+222D.SA+225
6.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为B。
A.SA+141B.SA+180C.SA+222D.SA+225
5.2填空题（将正确的答案填在相应的空中，其中A[i,j]表示下标从i到j）
1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC（A[0][0]），则A[i][j]的地址是LOC（A[0][0]）+（n*i+j）*k。
2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是326。
3.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是1208。
5.3算法设计题:
1.假设稀疏矩阵A和B均以三元组顺序表作为存储结构。
试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
2.假设系数矩阵A和B均以三元组顺序表作为存储结构。
试写出满足以下条件的矩阵相加的算法：
假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A，B之外的附加空间，你的算法能否达到O（m+n）的时间复杂度？
其中m和n分别为A，B矩阵中非零元的数目。
3．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。
4．求下列广义表操作的结果：
（1）GetTail[GetHead[（（a,b）,（c,d））]];
（2）GetTail[GetHead[GetTail[（（a,b）,（c,d））]]]
5.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子banana分别从下列广义表中分离出来.
（1）L
=（（（apple）））,（（pear））,（banana）,orange）;
（2）L
=（apple,（pear,（banana）,orange））;
习题答案
5.11.C2.D,B4.C5.C6.B
5.21.LOC（A[0][0]）+（n*i+j）*k
2.326
3.1208
习题六树和二叉树
6.1单项选择题
1.如图8.7所示的4棵二叉树，C不是完全二叉树。
2.如图8.8所示的4棵二叉树，B是平衡二叉树。
3.在线索化二叉树中，t所指结点没有左子树的充要条件是B。
A.t—＞left=NULLB.t—＞ltag=1
C.t—＞ltag=1且t—＞left=NULLD.以上都不对
4.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法B。
A.正确B.错误
5.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法A。
A.正确B.错误
6.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法B。
A.正确B.错误
7.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为B。
A.2hB.2h-1C.2h+1D.h+1
8.如图8.9所示二叉树的中序遍历序列是B。
A.abcdgefB.dfebagcC.dbaefcgD.defbagc
9.已知某二叉树的后序遍历序列是dabec，
升级会员 