厦门大学数据结构与算法(陈海山)期末习题答案解析
-
作业：
1-1,7,8
2-1
，
2,4,7,9,11,13
，
19
3-2,3
，
7,8,13,14
4-3,9,13
5-1,2,6,8
5-1,2,6,7
，
8
，
12,14,17
习题
1
绪论
1-1
名词解释：数据结构。
数据结构
：相互之间存在一定
关系
的数据元素的集合
1-2
数据结构的基本逻辑结构包括哪四种
?
⑴
集合：
数据元素之间就是
“
属于同一个集合
”
⑵
线性结构：数据元素之间存在着一对一的线性关系
⑶
树结构：数据元素之间存在着一对多的层次关系
⑷
图结构：数据元素之间存在着多对多的任意关系
1-3
数据结构一般研究的内容不包括
(
)
。
(A)
集合的基本运算
(B)
数据元素之间的逻辑关系
(C)
在计算机中实现对数据元素的操作
(D)
数据元素及其关系在计算机中的表示
选
D
数据的逻辑结构、数据的存储结构、数据的运算
1-4
算法包括哪五种特性
?
2.
算法的五大特性：√
⑴
输入：一个算法有零个或多个输入。
⑵
输出：一个算法有一个或多个输出。
⑶
有穷性：一个算法必须总是在执行
有穷步之后结束，且每一步都在有穷时间内完成。
⑷
确定性：
算法中的每一条指令必须有确切的含义，
对于相同的输入只能得到相同的输出。
⑸
可行性：算法描
述的操作可以通过已经实现的基本操作执行有限次来实现。
1-5
简述算法及其时间复杂度。
1.
算法（
Algorithm
）
:
是对
特定问题
求解步骤的一种描述，是
指令
的
有限序列
。
算法复杂度
(Algorithm
C
omplexity)
：算法占用机器资源的多少，主要有算法运
行所需的机器时间和所占用的存储空间。
时间复杂度
(Time Complexity)
：算法运行所需要的执行时间，
T(n)=
O(f(n))
。
空间复杂度
(Space Complexity)
：算法运行所需要的存储空间度量，
S(n)=
O(f(n))
。
1-6
设数组
A
中只存放正数和负数。试设计算法，将
A
中的负数调整到前半区
间，正数调整到后半区间。分析算法的时间复杂度。
A[n+1]
For(int i=n-1,j=0;i>j;i--)
{
If(a[i]>0) continue;
Else {
A[n]=A[i];
A[i]=A[j];
A[j]=A[n];
J++;
}
}
时间复杂度为
O(n)
1-7
将上
三角矩
阵
A=(aij)n
n
的
非
0
元素逐
行存于
B[(n*(n+1)/2]
中
，使得
B[k]=aij
且
k=f1(i)+f2(j)+c
(f1, f2
不含常数项
)
，试推导
函数
f1, f2
和常数
c
。
k+1=1+2+3+
„
+(i-1)+j
k=1/2*i*(i-1)+j-1;
1-8
描述下列递归函数的功能。
int F(int m, int n)
{
if (n>m) return F(n,
m);
else if (n==0) return m;
else
{
r=m%n;
return
F(n, r);
}
}
求
<
/p>
m
与
n
的最大公
约数
1-9
编写递归算法：
0
，
m=0
且
n
≥
0
g(m,
n)=
g(m-1, 2n)+n
，
m>0<
/p>
且
n
≥
0
double g(double
m,double
n)
{
If(m==0&&n>=0)
return 0;
else
return g(m-1,2*n)+n;
}
1-10
将下列递归过程改写为非递归过程。
void test(int &s)
{
int x;
scanf
(
“
%d
”
,
&x);
if (x==0) s=0;
else
{
test(s);
s+=x;
}
}
习题
2
表
2-1
如果长度为
n
的线性表采用顺序存储结构存储，则在第
i (1
≤<
/p>
i
≤
n+1)
个
位置
插入一个新元素的算法的时间复杂度为
(
)
。
(A)
O(1)
(B) O(n)
(C) O(nlog2n)
(D) O(n2)
B
需要让线性表移动
n+1-i
个
2-2
在一个
有
127
个元素的顺序表中插入一个新元素，要求保持顺序表元
素的原
有
(
相对
)
顺序不变，则平均要移动
(
)
个元素。
(A) 7
(B) 32
(C) 64
(D)
127
C
n/2+1
2-3
将关键字
< br>2
，
4
，
6
，
8
，
1
0
，
12
，
1
4
，
16
依次存放于一维数组
A[0...7]
中，如
果采用折半查找方法查
找关键字，
在等概率情况下查找成功时的平均查找长度为
(
)
。
(A)
21/8
(B) 7/2
(C)
4
(D) 9/2
A
3,2,3,1,3,2,3,4
公式法
1*2^0+2*2^1+3
*2^2+
„
+i*2^(n-1);
2-4
已知顺序表
L
递增有序。设计一个算法，将
a
和
b
插入
L
中，要求保持
L
递增有序且以较高
的效率实现。
先用折半查找法查询位置，然后移动
void insert(int L[],int a,int b)//a
{
int i=0,p,q;
n=
length(L);//L
现有长度
//
查找确定
a
、
b
的位置
<
br>为每个数据元素所占用的存储单元数。
<
br>n <
br>个结点构建链栈 <
br>个数据元素， <
br>(
<
br>中第
<
br>L 的第二个节点，接着用 <
br>p <
br>P65 <
br>F <
br>3 3
for(;i
{
if( L[i]<=a&&(a
{
p =
i+1; //a
的最终位置
n++;
break;
}
}
for(;i
{
if(
L[i]<=b&&(b
{
q = i+2;
//b
的最终位置
n++;
break;
}
}
//
移动元
素，插入
a
，
b
for(i=n+1;i>q;i--)
L[i] = L[i-2];
L[q] =
b;//
插入
b
for(i=q-1;i>p;i--)
L[i] =
L[i-1];
L[p] =
a;//
插入
a
}
2-5
简单描述静态查找和动态查找的区别。
A
静态查找表只查找
B
、静态查找表不改变数据元素集合内的数据元素
C
、动态查找表不只查找
D
、动态查找表还插入或删除集合内的数据元素
2-6
综合比较顺序表和链表。
(1)
存储空间利用率高——只存储元素值。
(
2)
随机存取——可以通过计算来确定顺序表中第
i
个数据元素的存储地址
Li
=
L0+(i-1)*m,
其中，
L0
为第一个数据元素的存储地址，
m
(3)
插入和删除数据元素会引起大量结点移动
.
顺序表：内存中地址连续
长度不可变更
支持随机查找
可以在
O(1)
内查找元素
适用于需要大量访问元素的
而少量增
添
/
删除元素的程序
链表
：内存中地址非连续
长度可以实时变化
不支持随机查找
查找元素时间复杂度
O
（
n
）
适用于需要进行大量增
添
/
删除元素操作
而对访问元素无要求的程序
2-7
解释链表的“头指针、头结点和首元素结点”三个概念。
“头指针”是指向头结点的指针。
头结点
是为了操作
的统一、方便而设立的，放在首元素结点之前，其数
据域一般无意义（当然有些情况下也
可存放链表的长度、用做监视哨等等）
。
“首元结点”也就是第一元素结点，它是头结点后边的第一个结点。
2-8
描述下列算法的主要功能是
(
)
。
①
构造头结点
L
，取
q=L;
②
产生<
/p>
1
个结点
p;
③
q
−
>next=p;
④
输入
p
−
>dat
a
的值
;
⑤
取
q=p;
⑥
重复执
行②至⑤
n
次
;
⑦
p
−
>next=NULL;
(A)
通过输入
个数据元素构建链表
L
(B)
采用前插法，在链表
L
中输入
n
个数据元素
(C)
通过产生
n
L
，
q
为栈顶指针
(D)
在链队列
L
中输入
n
q
为队尾指针
A
2-9
设
L
是不带头结点的单链表的头指针，
k
是一个正整数，则下列算法的主要
功能是
)
。
LinkSearch (LinkList L, int
k)
{
k0=0;
p=L->next;
//
next
为单链表的指针域
q=p;
while ( p
)
{
if
(k0<=k) k0++;
else
q=q->next;
p=p->next;
}
q->next=0;
}
(A)
计算单链表
L
的长度
(B)
查找单链表
L
中倒数第
k
个结点
(C)
删除单链表
L
中最后面的
k
个结点
(D)
将单链表
L
k
个结点
q
的指针置
0
只遍历一次的高效算法
（排除法）
B
2-10
设链表
不带头结点，试分析算法的功能。
A(Linklist &L)
{
if
(L && L->next)
{
Q=L;
L=L->next;
P=L;
while
(P->next) P=P->next;
P->next=Q;
Q->next=NULL;
}
}
//A
算法结束
将链表的第一个结点接到最后一个结点后面
2-11
设两个循环链表的长度分
别为
n
和
m
，
则将这两个循环链表连接成一个循
环链表，最好的时间复杂度为
(
)
。
(A)
O(1)
(B) O(n)
(C) O(m)
(D)
O(min(n
，
m))
A
首先取一个指针
p
指向
la
的第一个节点（不包括头节点，头节点是空）
，然后让<
/p>
la
头指针指向
lb
lb
的第一个节点填充
lb
的头节点，最后
将
la
头节点
next
指向
如下图：
还是不明白请自己看
ppt
第二章
2-12
设有
6
个数据元素
A
，<
/p>
B
，
C
，
D
，
E
，
F
依次进栈。如果
6
个数
据元素的出栈
顺序为
B
，
C
，
D
，
，
E
，
A
，则该栈的最小容量为
(
)
。
(A)
2
(B) 3
(C) 4
(D) 5
B
操作
栈内元素
A
，
B
入栈
A,B
B
出栈
A
C
入栈
A,C
C
出栈
A
D
入栈
A,D
D
出栈
A
E,F
入栈
A,E,F
F
出栈
A,E
E
出栈
A
A
出栈
因此栈的最小容量只需
3
出栈顺序
B
B,C
B,C,D
B,C,D,F
B,C,D,F,E
B,C,D,F,E,A
2-13
设进栈序列为
123
，试给出所有可能的出栈序列。
所有可能的出栈序列为：
1,2,3
（
1
入栈，
1
出栈，
2
入栈，
2
出栈，
3
入栈，
出栈）
1,3,2
（
1
入栈，
1
出栈，
2,3,
入栈，
出栈，
2
出栈）
2,1,3
（
1,2
入栈，
2
出栈，
1
出栈，
3
入栈，
3
出栈）
2,3,1
（
1,2
入栈，
2
出栈，
3
入栈，
3<
/p>
出栈，
1
出栈）
3,2,1
（
1,2,3
入栈，
3
出栈，
2
出栈，
1
出栈）
<
/p>
注意：唯一只有
3,1,2
不可能出现，
因为
3
要先出栈，前面
1,2,3
要按顺序一起入栈，因此不可
能出现
1
在
2
的前面，后面的题目也是一样。
原则就是只要后入栈的先出栈，
那么这个元
素前面入栈的元素一定按照入栈顺序的反序排列
2-14 <
/p>
如果进栈序列为
123456
，能否得到
出栈序列
435612
和
135426
?
435612
不能得到
6
的后面不可能出现
1,2
< br>的出栈顺序
135426
能够得到
2-15
简述算法的功能
(
设数据元素类型为
int)
：
< br>
void proc(LinkQueue *Q)
{
LinkStack
S;
InitStack(S);
while(!EmptyQueue(Q) )
{
DeleteQueue(Q,
d);
Push(S,d);
}
while(!EmptyStack(S) )
{
Pop(S,
d);
InsertQueue(Q,
d);
}
}
将链队列中的顺序倒过来
如原来
ABCDEF
，执行完这个算法之后是
FEDCBA
2-16
按照格式要求给出调用
F(3,'A','B','C')
的运行结果：
void F(int n,
char x, char y, char z)
{
if (n==1)
printf(
%c
%cn
else
{
F(n-1, x, z, y);
printf(
%c
%cn
F(n-1, y, x, z);
}
}
自己去计算，类似汉诺塔
1
A->C
2
A->B
1
C->B
3
A->C
1
B->A
2
B->C
1
A->C
2-17
已知一维数组
B[0..20]
用于存储一个下三角
矩阵
A
元素。设
A
中第一个元
素的下标为
1
，
1
，则数组元素
B[10]
< br>对应
A
中下标为
(
)
的元素。
(A) 2
，
5
(B)
4
，
3
(C) 5
，
1
(D)
6
，
1
C
因此
B
中第
1
0
个元素，也就是
B[9]
对应
A[4][4]
[B[10]
对应
A
中是
A[5][1]
2-18
已知
An
< br>
n
为稀疏矩阵。
试从时间和空
间角度比较，
采用二维数组和三元组
顺序表两种存储结构计算∑
aij
的优缺点。
< br>稀疏矩阵为
n
行
n
列
.
1)
采用二维数组存储，其空间复杂度为Ｏ
(n
×
n)
；因为要将所有的矩阵元素累加起来，所
以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ
(n
×<
/p>
n)
。
2)
采用三元组顺序表进行压缩存储
，假设矩阵中有
t
个非零元素，其空间复杂度为Ｏ
(t)
，
将所有的矩阵元素累加起来只需将三元组顺
序表扫描一遍，其时间复杂度亦为Ｏ
(t)
。当
t
<<
< br>n
×
n
时，采用三元组顺序表存
储可获得较好的时、空性能。
2-19
链地址法是
Hash
表的一种处理冲突的方法，
它是将所有哈希地址相同的数
据元素都存放在同一个链表中。关于链地址法
的叙述，不正确的是
(
)
。
(A)
平均查找长度较短
pptP165
上面有表述
(B)
相关查找算法易于实现
查找的时候只
需找到哈希地址的那条链，
再顺着那条链
遍历下去就可以实现。
(C)
链表的个数不能少于数据元素的个数
可以少于，很明显
(D)
更适合于构造表前无法确定表长的情况
链表的特点之一‘
C
2-20
设哈希
(Hash)
函数
H(k)=
(3k)%11
，用线性探测再散列法处理冲突，
di=i
。已
知为关键字序列
22
< br>，
41
，
53
< br>，
46
，
30
< br>，
13
，
01
< br>，
67
构造哈希表如下：
哈希地址
0
1
2
3
4
5
6
7
8
9
10
关键字
22
41
30
01
53
46
13
67
则在等概率情况下查找成功时的平均查找长度是
(
)
。
(A)
2
(B) 24/11
(C) 3
(D) 3.5
有公式
ASL=1/2(1+1/(1-a)) =
1/2(1+1/(1+11/3))=7/3
其中
a =
8/11
（实际填入的数量
/
线性表的
大小）
2-21
有
100
个不同的关键字拟存放在哈希表
L
中。
处理冲突的方法为线性探测再
散列法，其平均查
找长度为
。试计算
L
的长度
(
一个素数
)
，要求在等
概
率情况下，查找成功时的平均查找长度不超过
3
。
素数表：
101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167
。
设线性表
L
长度
ln,
有
:
α
=100/ln<=0.8
求出
ln
>=125,
即由题意选择
127
这个
素数
习题
3
树
3-1
若深度为
5
< br>的完全二叉树第
5
层有
3
个叶子结点，
则该二叉树一共有
(
)
个结
点。
(A) 8
(B) 13
(C) 15
(D)
18
D
利用公式
前四层有
2^5-1 = 15
个节点
，总共为
15+3=18
个。
3-2
设树
T
的度为
4
，其中度为
1
，
2
，
< br>3
和
4
的结点个数分别为
4
，
2
，
1
，
1
则
T
中的叶子数为
(
)
。
(A)
5
(B) 6
(C) 7
(D) 8
一共有
1*4+2*2+3+4=1
5
个度，
4+2+1+1=8
个节点<
/p>
叶子为
15-8+1=8
解析：节点数
=
度数
+
1
此题也可用画图法（图略）
3-3
已知二叉树
T
中有
50
个叶子结点，试计
算
T
的总结点数的最小值。
由于是二叉树，
那么可知欲使节点数
最小，
则该二叉树需满足至多存在一个结点
的入度为
1
（即——使每两个结点都有一个父节点）
。
50/2=25,
（
25-1
）
/2=12
12/2=6
6/2=3
(3
+1
)/2=2
2/2=1
红色部分
+1
为之前
25
个结点归根时剩下的
1
个。
那么总共有
50+25+12+6+3+2+1=99
个结点
节点数
/2+1
=
叶子数
3-4
已知一棵度为
k
的树中，有
n1
个度为
1<
/p>
的结点，
n2
个度为
2
的结点，„，
nk
个度为
k
的结点。试计算该树的叶子结点数。
解析：节点数
=
度数
+1
mn
n
+
1
k
k
0
0
k
k
叶子结点为
3-5
对于任意非空二叉树，要设计出其后序遍历的非递归算
法而不使用栈结构，
最适合的方法是对该二叉树采用
(
)
存储结构。
(A)
二叉链表
(B)
三叉链表
(C)
索引
(D)
顺序
B
解析：三叉链表比二叉链表多一个指向父结点的指针
3-6
一棵二叉树的叶子结点在其
先序、中序和后序序列中的相对位置
(
)
。
(A)
肯定发生变化
(B)
可能发生变化
(C)
不会发生变化
(D)
无法确定
B
解析：举例子说明即可
3-7
设二叉树
T
< br>按照二叉链表存储，试分析下列递归算法的主要功能。
int F(BiTree T)
{
if
(!T) return 0;
if (!T->Lchild && !T->Rchild) return 1;
return
F(T->Lchild)+F(T->Rchild);
}
求二叉树
T
的叶子结点数
int F(BiTree
T)
{
if (!T) return 0;
if (!T->Lchild &&
!T->Rchild) return 1;
return F(T->Lchild)+F(T->Rchild)+1;
}
求二叉树
T
的结点数
3-8
已知二叉树
T
的先序序列为
ABCDE
F
，中序序列为
CBAEDF,
则<
/p>
T
的后序
序列为
(
)
。
(A)
CBEFDA
(B) FEDCBA
(C) CBEDFA
(D)
不确定
A
3-9
简述由先序序列和中序序列构造二叉树的基本操作方法。
1
）取先序遍历序列的第一个值，用
该值构造根结点，，然后在中序遍历序列中查找与该元
素相等的值，
这样就可以把序列分为三部分：
左子树
（如果有）
、
根结点和右子树
（如果有）
< br>。
2
）将两个序列都分成三部
分，这样就分别形成了根结点的左子树和右子树的先序遍历和后
序遍历的序列。
3
）重复
1
）和
2
）步骤，直至所有结点都处理完就可以完
整构成一颗二叉树了。
3-10
已知二叉树的先序序列为
ebadcfhgikj
，中序序列为
abcdefghijk
，试画出该<
/p>
二叉树。
e
b
f
a
d
h
c
g
i
k
j
3-11
已知二叉树
T
的中序序列和后序序列分别为
(
中序
) 3, 7, 11,
14, 18, 22, 27, 35
(
后序
) 3, 11, 7,
14, 27, 35, 22, 18
试画出二叉树
T
。
18
14
22
7
35
3
11
27
3-12
已知二叉树
T
按照二叉链表存储，设计算法，计算
T
中叶子结点的数目。
int F(BiTree T)
{
if
(!T) return 0;
if (!T->Lchild && !T->Rchild) return 1;
return
F(T->Lchild)+F(T->Rchild);
}
3-13
已知二叉树
T
按照二叉链表存储，设计算法，交换
T
的左子树和右子树。
递归：
Int
ExchangeBTree(BiTree T)
{
temp=(BiTree) malloc(sizeof(BiTNode));
if(!T) return;
if(!T->lchild&&!T->rchild) return;
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
ExchangeBTree(T->lchild);
ExchangeBTree(T->rchild);
}
3-14
先序后继线索化算法是根据二叉链表建立先序后继线
索二叉链表，其基本
原则是在前驱空指针域中写入后继线索，即将右子树的
(
)
指针写入左子树的
最后一个叶子结点右指针域。
(A)
线索
(B)
根结点
(C)
前驱结点
(D)
后继结点
C
3-15
设计算法，在先序线索二叉树中，查找给定结点
p
在先序序
列中的后继。
线索二叉树：
根据某次遍历
,
在二叉树中的相关空指针域都写入线索
(
后
继线索
或前驱线索
)
，即成为线索二叉
树。
线索二叉树可理解为已经线索化的二叉树。
< br>先序后继：
先序遍历中得到的后继
(
先序前驱
,
中序后继
,
中序前驱
,
后序后
继
,
后序前驱
)
。
线索二叉树的存储结构
typedef struct Node {
Type data
；
//
数据元素域
struct Node *Lchild
；
< br>//
左孩子域
struct Node *Rchild
；
< br>//
右孩子域
int Tag
；
//0:
分支结点
, 1:
叶子结点
} BiTNode
，
*BiTree
；
findBirthNode(BiTNode p)
{
If(p->tag==0)//p
的左子树非空
,
指向左子树
Return
p->Lchild;
Else
//p
为空，后驱则是右子树
Return p->Rchild;
}
3-16
设计一种二进制编码，
使传送数据
<
/p>
a
，
act
，<
/p>
case
，
cat
，
ease
，
sea
，
seat
，
state
，
tea
的二进制编码长度最短。
要求描述：
(1)
数据对象；
a,c,t,s,e
(2)
权值集；
8,3,5,5,6
(3)
哈夫曼树；略
(4)
哈夫曼编码。
00,010,011,10,1
1
3-17
按照“逐点插入方法”建立一个二叉排序树，树的形状取决于
(
)
。
(A)
数据序列的存储结构
(B)
数据元素的输入次序