sum=s;
习题答案
1.11.C,A2.B,D3.C4.C,A5.C,B
1.21.线性结构、树形结构、图形结构，非线性结构
2.没有、1、没有、1
3.前驱、1、后续、任意多个
4.任意多个
5.一对一、一对多、多对多
6.有穷性、确定性、可行性、输入、输出
7.最大语句频度：
n2，时间复杂度：
.0（n2）
8.最大语句频度：
n（n+1）/2，时间复杂度：
.O（n2）
9.最大语句频度：
n3，时间复杂度：
.O（n3）
习题2线性表
2.1单项选择题
1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100,每
个元素的长度为2,则第5个元素的地址是。
A.110B.108C.100D.120
2.线性表的顺序存储结构是一种一的存储结构，而链式存储结构是一种___的存储结构。
A.随机存取B.索引存取C.顺序存取D.散列存取
3.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确B.不正确
4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址o
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续或不连续都可以
5.在以下的叙述中，正确的是o
A.线性表的顺序存储结构优于链式存储结构
B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C.线性表的链式存储结构适用于频繁插入/删除数据元素的情况
D.线性表的链式存储结构优于顺序存储结构
6.每种数据结构都具备三个基本运算：
插入、删除和查找，这种说法o
A.正确B.不正确
7.不带头结点的单链表head为空的判定条件是。
A.head==NULLB.head->next==NULL
C.head->next==headD.head!
=NULL
8.带头结点的单链表head为空的判定条件是。
A.head==NULLB.head->next==NULL
C.head->next==headD.head!
=NULL
9.非空的循环单链表head的尾结点（由p所指向）满足。
A.p->next==NULLB.p==NULL
C.p->next==headD.p==head
10.在双向循环链表的p所指结点之后插入s所指结点的操作是o
A.p->nextt=s;s->prior=p;p->next->prior=s;s->next=p->next;
B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;
C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p
之间插入s结点，则执行。
A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;
B.q->next=s;s->next=p;C.p->next=s;s->next=q;
12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，
则执行。
A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;
C.s->next=p->next;p=s;C.p->next=s;s->next=p;
13.在一个单链表中，若删除p所指结点的后续结点，则执行—。
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;
2.2填空题（将正确的答案填在相应的空中）
1.单链表可以做的链接存储表示。
2.在双链表中，每个结点有两个指针域，一个指向,另一个指向。
3.在一个单链表中p所指结点之前插入一个s（值为e）所指结点时，可执行
女口下操作：
q=head;while（q->next!
=p）q=q->next;
s=newNode/*生成新结点*/;s->data=e;
q->next=;〃填空
s->next=;〃填空
4.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：
q=p->next;p->next=;//填空
free（;〃填空
5.在一个单链表中p所指结点之后插入一个s所指结点时，应执行
s->next=和p->next=的操作。
2.3算法设计题：
1.设顺序表va中的数据元数递增有序。
试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,….an逆置为（an,an-1,….,a1。
3.已知线性表中的元素以值递增有序排列，并以单链表作存储结构。
试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。
4.试写一算法，实现单链表的就地逆置（要求在原链表上进行）。
习题答案
2.11.B2.A,C3.B4.D5.C6.A7.A
8.B9.C10.D11.B12.B13.A
2.21.线性结表2.前驱结点、后继结点
3.s,p4.q->next,q5.p->next,s
习题3栈和队列
3.1单项选择题
1.一个栈的入栈序列a,b，c，d，e，贝U栈的不可能的输出序列是。
A.edcbaB.decbaC.dceabD.abcde
2.若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为p1,p2,p3,…,
pn，若p1=n,贝Upi为。
A.iB.n=iC.n-i+1D.不确定
3.栈结构通常采用的两种存储结构是。
A.顺序存储结构和链式存储结构
B.散列方式和索引方式
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
S（最多元素为m）为空的条件是_
B.S.top==0C.S.top!
=m
S（最多元素为m）为栈满的条件是
A.先进先出B.先进后出
7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（不带空的头结点）
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;
8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值,则执行。
（不带空的头结点）
A.x=HS;HS=HS—>next;B.x=HS—>data;
C.HS=HS—>next;x=HS—>data;D.x=HS—>data;HS=HS—>next;
9.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是。
A.4，3，2，1B.1，2，3，4
C.1，4，3，2D.3，2，4，1
10.判定一个循环队列Q（最多元素为m）为空的条件是。
A.rear-front==mB.rear-front-1==m
C.front==rearD.front==rear+1
11.判定一个循环队列Q（最多元素为m,m==Maxsize-1）为满的条件是。
A.（（rear-front）+Maxsize）%Maxsize==m
B.rear-front-1==mC.front==rearD.front==rear+1
12.循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和
rear,贝U当前队列中的元素个数是。
A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front
13.栈和队列的共同点是。
A.都是先进后出B.都是先进先出
C.只允许在端点处插入和删除元素D.没有共同点
3.2填空题（将正确的答案填在相应的空中）
1.向量、栈和队列都是结构，可以在向量的位置插入和删除元素；
对于栈只能在插入和删除元素；对于队列只能在插入元素和删除
2.向一个长度为n的向量的第i个元素（Ki需向后移动个元素。
3.向一个长度为n的向量中删除第i个元素（Ki4.向栈中压入元素的操作是。
5.对栈进行退栈时的操作是。
6.在一个循环队列中，队首指针指向队首元素的。
7.从循环队列中删除一个元素时，其操作是。
8.在具有n个单元的循环队列中，队满时共有元素。
9.一个栈的输入序列是12345,贝U栈的输出序列43512是。
10.一个栈的输入序列是12345,则栈的输出序列12345是。
3.3算法设计题：
1.输入一个任意的非负十进制整数，输出与其等值的八进值数。
2.按照四则运算加、减、乘、除和幕运算（0优先关系的惯例，并仿照
教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A-B*C/D+EIF
3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
习题答案
3.1
6.BA7.C8.B9.C10.C
2.n-i+13.n-i
5.先取出元素，后移动栈顶指针
7.先移动队首元素，后取出元素
10.可能的
1.C2.C3.A4.B5.D
11.A12.A13.C
3.21.线性、任何、栈顶、队尾、队首
4.先移动栈顶指针，后存入元素
6.前一个位置
8.n-19.不可能的
习题4串
4.1单项选择题
1•以下叙述中正确的是。
A.串是一种特殊的线性表B.串的长度必须大于零
C.串中无素只能是字母D.空串就是空白串
2•空串与空格串是相同的，这种说法。
A.正确B.不正确
3•串是一中特殊的线性表，其特殊性体现在。
A.可以顺序存储B.数据元素是一个字符
C.可以链接存储D.数据元素可以是多个字符
4.设有两个串p和q,求q在p中首次出现的位置的运算称作。
A.连接B.模式匹配
C.求子串D.求串长
5.设串s仁’ABCDEFGs2='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的结果串是。
A.BCDEFB.BCDEFG
C.BCPQRSTD.BCDEFEF
6.设串的长度为n,则它的子串个数为。
A.nB.n（n+1）C.n（n+1）/2D.n（n+1）/2+1
4.2填空题（将正确的答案填在相应的空中）
1.串的两种最基本的存储方式是。
2.两个串相等的充分必要条件是。
3.空串是，其长度等于。
4.空格串是，其长度等于。
5.设s=TAM~A~TEACHER，其长度是。
4.3判断题
1.串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。
（）
2.子串定位函数的时间复杂度在最坏情况下为O（n*m）,因此子串定位函数没有实际使用的价值。
（）
3.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。
（）
4.4算法设计题
1.编写算法，从串s中删除所有和串t相同的子串。
2.编写算法，实现串的基本操作Replace（&S,T,V）。
3.写一个递归算法来实现字符串逆序存储，要求不另设存储空间。
习题答案
4.11.A2.B3.B4.B5.D6.C
4.2
1.顺序存储方式和链接存储方式
2.两个串的长度相等且对应位置的字符相同
3.零个字符的串、零
4.由一个或多个空格字符组成的串、其包含的空格个数
5.14
4.2xxx
4.4
3.voidreverse（chararr[]）
{charch;
inti=1;
do{cin>>ch;
reverse（arr）;
arr[i]=ch;
i++;
}while（ch!
='#'&&i}
习题5数组和广义表5.1单项选择题
1.常对数组进行的两种基本操作是。
A.建立与删除B.索引和修改C.对数据元素的存取和修改D.
查找与索引
2.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字
节）组成的串，行下标i的范围从0到8,列下标j的范围从0到9,则存放M至少需要①个字节；M数组的第8列和第5行共占②—字节。
1A.90B.180C.240D.540
2A.108B.114C.54D.60
3.二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9,从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是—o
A.80B.100C.240D.270
4.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9,从首地址SA开始连续存放在存储器内，该数组按行存放时，
数组元素A[7][4]的起始地址为o
A.SA+141B.SA+144C.SA+222D.SA+225
5.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列
下标j从0到9,从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为o
A.SA+141B.SA+180C.SA+222D.SA+225
6.稀疏矩阵一般的压缩存储方法有两种，即。
A.二维数组和三维数组B.三元组与散列
C.三元组与十字链表D.散列和十字链表
7.若用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标
互换，就完成了对该矩阵的转置运算，这种观点
A.正确B.不正确
8•设矩阵A是一个对称矩阵，为节省存储，将其下三角部分按行序存放在
一维数组B[0..n（n+1）/2]中，对下三角部分中任一元素科（i>j），在一组数组B
的下标位置k的值是。
A.i（i-1）/2+j-1B.i（i-1）/2+jC.i（i+1）/2+j-1D.i（i+1）/2+j
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]采用行序为主方式存储，每个元素占4个存储
单元，并且A[10][5]的存储地址是1000,则A[18][9]的地址是。
4.有一个10阶对称矩阵A，采用压缩存储方式（以行为主存储，且
LOC（A[0][0]）=0）,J则A[8][5]的地址是。
40
5.设n行n列的下三角矩阵A已压缩到一维数组S[0..n*（n+1）/2]中,若按行序为主存储，则A[i][j]对应的S中的存储位置是oi（i+1）/2+j
6.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的
、和项。
7.—个稀疏矩阵如图所示，则对应的三元数组表示为o
一0020_
3000
00—15
0000^
8.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按为主
序、辅序的次序排列。
9.二维或多维数组，分为按和种不同的
存储方式.
5.3应用题：
1.已知一个稀疏矩阵如下图所示：
040-0000000-3001
0-70002
000T600
具有6行X7列的一个稀疏矩阵
（1）写出它的三元组线性表；
（2）给出它的顺序存储表示；
（3）给出它的转置矩阵的三元组线性表和顺序存储表示；
5.4算法设计题：
1.假设稀疏矩阵A和B均以三元组顺序表作为存储结构。
试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
习题答案
5.11.C2.D,A3.C4.C5.B6.C7.B8.D
5.21.LOC（A[0][0]）+（n*i+j）*k2.200+（6*20+12）=326
3.1000+（（18-10）*6+（9-5））*4=1208
4.415.i（i+1）/2+j6•行号，列号，元素值
7.
i
j
v
0
2
2
1
0
3
2
2
-1
2
「3
5
8.行，列
9.行优先顺序存储，列优先顺序存储
5.3
（1）（（0,1,4）,（1,3,-3）,（1,6,1）,（2,0,8）,（3,3,5）,（4,1,-7）,（4,5,2）,（5,3,6））
i
j
v
0
「1
4
1
3
-3
1
6
1
2
「0
8
3
3
5
4
「1
-7
4
5
2
5
「3
6
（3）
习题6树和二叉树6.1单项选择题
1.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种
说法。
B
A.正确B.错误
2.假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶
子结点数为个。
BA.15B.16C.17D.47
3.按照二叉树的定义，具有3个结点的不同形状的二叉树有种。
C
A.3B.4C.5D.6
4.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种
说法。
A
A.正确B.错误
5.深度为5的二叉树至多有结点。
C
A.16B.32C.31D.10
6.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包
含的结点数至少为__。
B
A.2hB.2h-1C.2h+1D.h+1
7.对一个满二叉树，m个树叶，n个结点，深度为h，则。
D
I—
A.n=h+mB.h+m=2nC.m=h-1D.n=2-1
8.
任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序
14.一棵二叉树如图6.2所示，其中序遍历的序列为。
B
A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh
15.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件
是。
B
图6.6一棵二叉树的顺序存储数组t
5.深度为k的完全二叉树至少有个结点。
至多有个结点，若按自上而
下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是
0
6.在一棵二叉树中，度为零的结点的个数为no,度为2的结点的个数为n2,
则有no=。
7.一棵二叉树的第i（i>1）层最多有个结点；一棵有n（n>0）个结点的
满二叉树共有个叶子和个非终端结点。
8.结点最少的树为，结点最少的二叉树为。
9.现有按中序遍历二叉树的结果为abc，问有种不同形态的二叉树可以得
到这一遍历结果，这些二叉树分别是。
10.
由如图6.7所示的二叉树，回答以下问题：
⑴其中序遍历序列为;
⑵其前序遍历序列为
⑶其后序遍历序列为
6.3简答题
1.根据二叉树的定义，具有三个结点的二叉树有别画出。
2.假设一棵二叉树的先序序列为EBADCFHGIKJ中序序列为AB
升级会员 