数据结构 马睿 孙丽云 习题答案Word格式文档下载.docx
《数据结构 马睿 孙丽云 习题答案Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构 马睿 孙丽云 习题答案Word格式文档下载.docx（46页珍藏版）》请在冰点文库上搜索。
7、先进后出，加1，减1
8、满，空，n
9、线性结构
10、4
三、判断题
1.、错
2、错
3、对
4、错
5、对
6、错
7、错
四、解答题
4、列车进入一个栈式结构的车站，开出车站有14可能的顺序：
abcd;
abdc
adcb
acdb,acbd
bdca,
bcda,bcad
bacd,badc
cdba,
cbda,cbad,
dcba
列车进入一个队列式结构的车站，开出车站有1可能的顺序：
abcd
5、6,24
7、staxy
8、char
9、第一个循环：
队列Q中的元素依次出队，出队后即进栈S
第二个循环：
栈S中的元素依次出栈，出栈后即进入队列Q
第4章串
1、A2、D3、C4、C5、D
二、简答题
1、含零个字符的串称为空串，用Φ表示，串的长度为0。
而空格串是由一个或多个空格组成的串，串的长度为所含空格的个数。
由串中任意连续字符组成的子序列称为该串的子串。
包含子串的串相应地被称为主串。
假如一个串S=“a0a1a2…an-1”（n≥0），其中：
S为串名，用双引号括起来的内容为串的值，双引号本身不是串的值。
2、当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串才相等。
3、19，7，good，e，0，3，”Iamagoodteacher”，”agoodyestea”
4、
j
1
2
3
4
5
6
模式串
a
b
c
next[j]
-1
三、算法题
1、
voidAssign（string*s,stringt）//s为串指针类型的参数
{//将串变量t的值赋给串变量s
inti;
for（i=0;
i<
t.curlen;
i++）
s.str[i]=t.str[i];
s.curlen=t.curlen;
}
2、略
3、略
Lstring*Insert（Lstring*s,intpos,Lstring*t）//在串s的第pos字符之前插入串t
{
intk;
Lstring*str_temp,*p1=s->
next,*p2=t->
next,*q,*r;
str_temp=（Lstring*）malloc（sizeof（Lstring））;
str_temp->
next=NULL;
r=str_temp;
if（pos<
0||pos>
s.curlen）//参数不正确时返回空串
returnstr_temp;
for（k=0;
k<
pos;
k++）{//将s的前pos-1个结点复制到str_temp
q=（Lstring*）malloc（sizeof（Lstring））;
q->
str=p1->
str;
r->
next=q;
r=q;
p1=p1->
while（p2!
=NULL）{
q=（Lstring*）malloc（sizeof（Lstring））;
q->
str=p2->
r->
r=q;
p2=p2->
while（p1!
=NULL）{//将*p1及其后的结点复制到str_temp
p1=p1->
returnstr_temp;
5、
Lstring*Delete（Lstring*s,intpos,intlen）
{//从串s中删去从第pos个字符起长度为len的子串
intk;
Lstring*str_temp,*p=s->
next,*q,*r;
str_temp=（Lstring*）malloc（sizeof（Lstring））;
str_temp->
r=str_temp;
if（pos<
length（s）-1||len<
0||pos+len-1>
length（s））
//参数不正确时返回空串
k++）{//将s的前pos-1个字符复制到str_temp
str=p->
p=p->
for（k=0;
len;
k++）//p沿next跳len个结点
while（p!
=NULL）{//将*p及其后的结点复制到str_temp
第5章数组和广义表
一、选择题
1、C2、A3、A4、B5、B6、C7、B8、C9、C10、B
二、填空题：
1、线性结构 顺序结构
2、以行为主序 以列为主序
3、（d1-c1+1）*（d2-c2+1）
4、326
【解析】采用列主序时，LOC（A[6][12]）=LOC（A[0][0]+（12*10+6）*1=326
5、答:
913
6、42
【解析】A[8][5]前有8行，第0行1个元素，第1行2个元素，…，第7行8个元素，共（1+8）*8/2=36个元素，第8行前有5个元素，所以A[8][5]的地址为36+5+1=42。
7、答:
K=[i（i-1）/2]+j,当i≥j时K=[n（n+1）/2]+1,当i<
j时
8、2210
9、（x,y,z）
10、GetTail（GetTail（GetTail（GetHead（GetTail（LS）））））
11、5?
?
三、操作题
1、设数组元素A[i][j]存放在起始地址为Loc（i,j）的存储单元中。
∵Loc（2,2）=Loc（0,0）+2*n+2=644+2*n+2=676.
∴n=（676-2-644）/2=15
∴Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692.
2、
（1）数组B共有1＋2+3+?
+n=（n+1）*n/2个元素。
（2）只存下三角部分时，若i?
j，则数组元素A[i][j]前面有i-1行（1?
i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，?
，第i-1行有i-1个元素。
在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为：
1+2+?
+（i-1）+j=（i-1）*i/2+j
若i<
j，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。
在数组B的第（j-1）*j/2+i位置中找到。
如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为：
当i?
j时，=i*（i+1）/2+j
当i<
j时，=j*（j+1）/2+i
3、
（1）Head（Tail（Tail（L1）））
（2）Head（Head（Tail（L2）））
（3）Head（Head（Tail（Tail（Head（L3）））））
（4）Head（Head（Tail（Tail（L4））））
（5）Head（Tail（Head（L5）））
（6）Head（Head（Tail（Head（Tail（L6）））））
4、由于线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括3个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序排列，这个线性表用顺序的方法存储在连续的存储区，则对应的三元组为
其十字链表形式为：
１
^
＾６６
０
ａ
＾＾＾６６
ｂ
ｃ
＾
ｄ
5、
6、L=（a,（b,c）,（d,（e）））
四、算法题
1、【算法分析】从前向后找零元素A[i]，从后向前找非零元素A[j]，将A[i]与A[j]交换。
【算法源代码】
voidmove（intA[],intn）
{inti=0,j=n-1;
inttemp;
while（i<
j）
{
while（A[i]!
=0）i++;
while（A[j]==0）j--;
if（i<
{temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
2、【算法分析】为保证算法的时间复杂度为O（m+n），即需要对数组A和B的数据元素仅扫描一次就能生成C数组，我们可采用设三个下标指针i,j,k初始时分别指向A数组的最后一个元素（A数组的最大值）、B数组的第一个元素（B数组的最大值）、C数组将存放最大值的位置，然后比较A与B数组的最大值大者放C数组k所指单元；
在上述比较中若A数组i所指单元数大，则送完后i前移，否则j所指单元数送完后j后移，同时k前移，直到把A与B数组的所有元素扫描完。
#definem3
#definen4
voidMerge（intA[],intB[],intC[]）
{inti,j,k;
i=m-1;
j=0;
k=m+n-1;
while（（i>
=0）&
&
（j<
=n-1））
{if（A[i]>
B[j]）
{C[k]=A[i];
i--;
else
{C[k]=B[j];
j++;
k--;
while（i>
=0）{C[k]=A[i];
i--;
k--;
while（j<
=n-1）{C[k]=B[j];
j++;
}
3、【算法分析】三元组表示中要求按行的顺序存放，所有转置过程不能直接将行下标和列下标转换，还必须使得列按顺序存放。
因此在A中首先找出第一列中的所有元素，它们是转置矩阵中第一行非0元素，并把它们依次放在转置矩阵三元组数组B中；
然后依次找出第二列中的所有元素，把它们依次放在数组B中；
按照同样的方法逐列进行，直到找出第n列的所有元素，并把它们依次放在数组B中。
voidtranspose（TSMatrixA,TSMatrix*B）
/*A是稀疏矩阵的三元组形式，B是存放A的转置矩阵的三元组数组*/
{inti,j,k;
B->
mu=A.nu;
nu=A.mu;
tu=A.tu;
if（B->
tu>
0）
{j=1;
for（k=1;
=A.nu;
k++）
for（i=1;
=A.tu;
if（A.data[i].col==k）
{B->
data[j].row=A.data[i].col;
B->
data[j].col=A.data[i].row;
data[j].e=A.data[i].e;
4、【算法分析】在求广义表深度的递归算法中，若结点为原子则深度为0，若是空表深度为1，否则返回头指针与尾指针所指广义表的深度最大值。
intGlist_Getdeph（GlistL）
{intm,n;
if（!
L->
tag）return0;
elseif（!
L）return1;
m=Glist_Getdeph（L->
ptr.hp）+1;
n=Glist_Getdeph（L->
ptr.tp）;
returnm>
n?
n:
n;
第6章树
一．选择题
1、B2、A3、B4、A5、C6、CA7、B8、B9、D10、B
11、B12、B13、B14、A15、C16、D17、A18、A19、C20、D
二．填空题
1．[1]前驱[2]一个前驱结点[3]后继[4]后继
2.n-1
3.n0=n2+1
4.[1]2[2]10[3]11
5.[1]A[2]DGF[3]BE[4]AC[5]B
[6]ACE[7]右[8]左[9]2[10]4
6.250
7.1
8.2n0-1
9.[1]D[2]F
10.[1]GEACBDF[2]1
11.[1]InOrderTraverse（T->
left）[2]printf（T->
data）[3]InOrderTraverse（T->
right）
12.
。
三．判断题
3．√4．×
5．×
6．√7．×
8．√9．×
10．√
四．操作题
1．
（1）
（2）GCABFED
（3）
（4）（5）
（6）
2．
3．
（1）所有结点均没有左孩子的二叉树。
（2）所有结点均没有右孩子的二叉树
（3）只有一个根结点的二叉树
4．证明：
当n=1时，前序序列和中序序列均只有一个元素且相同，即为根，由此唯一地确定了这颗二叉树。
假设n<
m-1时，结论成立，现证明当n=m时也成立。
设前序序列为：
a1，a2，…，am，中序序列为：
b1，b2，…，bm。
因为前序序列由前序遍历得到，则a1为根结点元素；
又中序序列由中序遍历得到，则在中序序列中必能找到和a1相同的元素并设为bj（1≤j≤m）,由此可得{b1，…，bj-1}为左子树的中序序列，{bj+1，…，bm}为右子树的中序序列。
（1）若j=1即b1为根，此时二叉树的左子树为空，{a2，…，am}即为右子树的前序序列，{b2，…，bm}即为右子树的中序序列，右子树的结点数为m-1，由此，这两个序列唯一确定了右子树，也唯一确定了二叉树。
（2）若j=m即bm为根，此时二叉树的右子树为空，{a2，…，am}即为左子树的前序序列，{b2，…，bm}即为左子树的中序序列，同
（1），这两个序列唯一确定了左子树，也唯一确定了二叉树。
（3）2≤j≤m-1，则子序列{a2，…，aj}和{b1，…，bj-1}分别为左子树的前序序列和中序序列，这两个序列唯一确定了左子树；
子序列{aj+1，…，am}和{bj+1，…，bm}分别为右子树的前序序列和中序序列，这两个序列唯一确定了右子树；
由此，证明了知道一棵二叉树的前序序列和中序序列，就能唯一地确定一棵二叉树。
5．
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
6．
A
B
（a）
（b）
C
（c）
（d）
E
F
I
J
D
H
G1
K
（e）
7．
9
16
20
34
54
18
WPL=1*5+3*5+5*4+9*3+16*2+20*1
=119
A:
01
B:
0001
C:
001
D:
1
E:
00001
F:
00000
8．
d
-
*
+
f
e
/
波兰式：
-+a*b-cd/ef
逆波兰式：
abcd-*+ef/-
五．算法设计题
//-------二叉树的二叉链表存储表示-----
typedefstructBiTNode{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTree;
1．
intNodes（BiTreebt）/*求以bt为根的二叉树中度为1的结点数目*/
{if（bt==NULL）return0;
/*bt为空时，结点数为0*/
elseif（（bt->
lchild==NULL）&
（bt->
rchild==NULL））
return0;
/*只有根节点时，结点数为0*/
elseif（（bt->
lchild==NULL）||（bt->
rchild==NULL））
return（1+Nodes（bt->
lchild）+Nodes（bt->
rchild））;
/*返回当前根节点和左或右子树中满足条件的节点数目*/
elsereturn（Nodes（bt->
/*返回左右子树中满足条件的节点数目*/
}//Nodes
voidLeafPath（BiTreeT,intnum）
{/*求二叉树根结点T到所有叶子结点的路径*/
/*用数组path存储路径（不包括T在内），其中已有的元素个数为num，其初值为0*/
BiTreep;
inttop,i;
if（T==NULL）/*如果二叉树为空，则给出相应信息，算法结束*/
{printf（"
二叉树为空!
"
）;
return;
if（T->
lchild==NULL&
T->
rchild==NULL）
printpath（path,T,num）;
/*输出路径*/
{
path[num+1]=T;
/*将T放到路径中*/
LeafPath（T->
lchild,num+1）;
rchild,num+1）;
其中printpath函数代码如下：
voidprintpath（BiTNode*path[],BiTreeT,intnum）
printf（"
%c：
T->
data）;
for（inti=1;
=num;
i++）printf（"
%c"
path[i]->
%c\n"
3．
voidPreOrderTraverse（BiTreeT,inthigh）
{/*设二叉树的根指针为T，T所指结点的层次为high*/
if（T）
{printf（"
（%c,%d）"
data,high）;
PreOrderTraverse（T->
lchild,high+1）;
rchild,high+1）;
4．BiTreechange（BiTreeT）/*二叉树左右子树交换递归算法*/
{BiTreep;
if（T!
=NULL）
if（T->
lchild!
=NULL||T->
rchild!
{
p=（BiTree）malloc（sizeof（BiTNode））;
p->
data=T->
rchild=NULL;
lchild=T->
lchild;
T->
rchild;
rchild=p->
lchild=change（T->
lchild）;
rchild=change（T->
rchild）;
}
returnT;
BiTNode*Node（BiTreebt）
{/*求二叉树T的后序序列的第一个结点的指针，采用非递归算法*/
StackElemTypestack[BiTree_Max_Size];
/*定义顺序栈*/
inttop;
top=-1;
/*栈初始化*/
p=bt;
while（p）/*二叉树非空，根结点及其tag标记0一同入栈，然后遍历其左子树*/
{top++;
stack[top].T=p;
if（top!
=-1）returnstack[top].T;
elsereturnNULL;
BiThrNode*PreOrder_Next（BiThrNode*p）{
//在先序后继线索二叉树中查找结点p的先序后继，并返回指针
if（p->
Ltag==0）returnp->
elsereturnp->
}//PreOrder_Next
voidPreOrderTraverse_Thr（BiThrTreeT）
BiThrNode*p;
p=T;
=NULL）
{Visit（p->
p=PreOrder_Next（T）;
typedefcharTElemType;
TElemTyped
升级会员 