期末考试试题答案(草稿)
描写夏天的词语-南京林业大学教务处
期末考试试题答案(草稿)
部门： xxx
时间： xxx
制作人：xxx
整理范文，仅供参考，可下载自行修改
《数据结构》试题 <开卷）
姓名 班级
<电信系本科2002级 2003年12月）
题号
题分
得分
得 分
一
32
二
38
三
30
总分
100
一、回答下列问题 (每题4分，共32分>
1.
对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？
答：
最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1
个叶子。
2.
已知一棵二叉树的中序序列和后序序列分别为：
DBGEACHF和DGEBHFCA，
则该二叉树的前序序列是什么？cw7grDewXf
答：是：ABDEGCFH
3. 设有1000个无序的元素，需排出前10个最大<小）的
元素，你认为采用哪
种排序方法最快？为什么？
答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结
果，
时间效率为O(nlog2n>； 即O<1000log21000）=O(10000>
锦标赛排序的准确比较次数为：
堆排序的准确比较次数为：
若用冒泡排序也较快，
最多耗费比较次数为
4.
在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数
值。
答：
5. 中序遍历的递归算法平均空间复杂度为多少？
答：
要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空
间复杂度为O(log2n>
6. 欲将无序序列<24, 79, 13, 36, 70, 96, 12,
10, 36*, 49,
100, 27）中的关键码按升序重新排列，请写出快速排序第
一趟排序的结
果序列。另外请画出堆排序<小根堆）的初始堆。cw7grDewXf
答：①快速排序第一趟排序的结果序列为：10， 12， 13， [24]， 70， 96,
36, 79, 36*, 49, 100, 27cw7grDewXf
<注意要按振荡式逼近算法实现）
②
堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开
24
79 13
36 70 96 12
10 36*49 100 27
始，自下而上调整,而且要排成小根堆！
初始堆序列为： 10，24，12，79，
49，27，13，36，36*, 70,
100, 96cw7grDewXf
无序堆
有序初始堆
10
24 12
79 49 27 13
36 36*70 100
96
cw7grDewXf
7. 已知一组关键字为<10， 24，
32， 17， 31， 30， 46， 47， 40，
63，
49），设哈希函数cw7grDewXf
H
答：
0
49
1
40
2
3
4
17
5
31
6
32
7
30
8
46
9
47
10
10
11
24
12
63
8. 算法复杂度O<1）的含义是什么？
答：它表示与输入的元素规模无关，是一个常数<但不一定是1）。
或：它表示该算法执行时耗
费时间的长短或占用辅助空间的多少与元素个数n
无关，若能达到这样的时间效率或空间效率，将是最理想的算法。cw7grDewXf
得
分
二、综合题<4小题，共38分）
1.
下图为某无向图
的邻接表，按教材算法7.5和7.6分别写出深
度优先搜索和广度优先搜索的结果，并画出逻辑结构图
。
(10分> cw7grDewXf
1
2
3
4
5
6
7
8
9
10
A
B
C
D
E
F
G
H
I
J
^
5
3
2
1
3
2
9
8
8
^
^
^
^
^
7
6
3
10
^
^
^
7
^
答：深度优先搜索
广度优先搜索
这是有着4个连通分量的非连通图。
A
E
B C F
G
H I
D J
2.
设A～H 8个字符出现的概率为: ={0.10, 0.16, 0.01, 0.02,
0.29,
0.10, 0.07, 0.25}, 设计最优二进制码并计算平均码长。如果
设计最优
三进制编码<即可用0,1,2三种符号进行编码），画出最优三叉树并计算平
均码长
。 (10分> cw7grDewXf
0 1.00
0 0.45
0.55
0 0.20 0.25 0.26
0.29
0 0.10 0.10
0 0.03 0.07 A 0.10 0.16
0.01 0.02
若按教材算法，合并规律应当如下：
A：001
B: 101
C: 00000
D: 00001
E: 11
F: 100
G: 0001
H: 01
平均码长为：
ΣPiWi=
=3×<0.1＋0.16＋0.1）
＋5×<0.01+0.02）
+2×<0.29+0.25）
+4×0.07
=2.59
答：最优二进制编码不惟一，但WPL惟一。cw7grDewXf
cw7grDewXf
1.00
0.55 0.45
0.26 0.29 0.20 0.25
0.10 0.16
0.03 0.07 0.10 0.10
0.01
0.02
A：100
B: 001
C:
00000
D: 00001
E: 01
F: 101
G:
0001
H: 11
平均码长仍为：
ΣPiWi=2.59
1.00
0 1 2
0.29 0.51
0 0.20 2
0 0.03 0.07 0.10 0.10 0.16 0.25
0.01 0.02
编码为：
A：02
B: 21
C: 000
D: 001
E: 1
F:
20
G: 01
H: 22
对三进制编码，由于总共有8个字符，8%3=2,
故第一次构建最优树只有2个结
点，则最优三叉树为cw7grDewXf
cw7grDewXf
3.
给定一个由n个关键字不同的记录构成的序列
，你能否用2n-3次比较找出
n个元素中的最大值和最小值？如果有，请描述你的方法。最快需多少次
比
平均码长为：
ΣPiWi=1×0.29+2×(0.1+0.16+0.10+0.07+0.25>+
3×(0.01+0.02>=0.29+1.36+0.09=1.74
较？<无需写算法）
(8分>cw7grDewXf
答：可以实现。选用锦标赛算法。两两元素比较，淘汰较小的
，形如一棵二叉
树。树根为最大值<此时用掉n-1次比较？）。而最小者一定位于首次被淘汰
之列。故只有 n2个。一共需n-1+ n2次比较。cw7grDewXf
4.
分析下面算法中l和h变量表示什么含义？初始调用时，l和h应取什么
值？其中p为指向二叉
树的根结点，如果去掉形参中的“&”符号，会得到
Void ABC(Bitree
p
, int
l
, int &
h
>
{ if
p≠NIL then
{
l
=
l
+1;
if
l
>
h
then
h
=
l
;
ABC(
p
->Lchild,
l
,
h
>;
ABC(
p
->Rchild,
l
,
h
>;
}
}
此题含义是：求树的深度
反而比从叶子往上计算要简单。
什么结果？
(10分>cw7grDewXf
解：依分析，l、h表示二叉树的层次数和深度。
开始调用时，应为ABC
正确结果。
这里的int &h应当理解为push形参，每次返回就要return 实参。所以l和
h
其实是每一层当前的状态。L代表当前结点所在的层数<从根结点计算起）；
而h代表当前结点所在的深
度。cw7grDewXf
附：教材求深度的函数如下：
int
BTreeDepth(Btree *BT> *BT为二叉树某结点的指针
{int
leftdep, rightdep; 设左右两个深度层次计数器
if(BT==NULL> return(0>; 当前结点指针为空则立即返回else
{ leftdep= BTreeDepth(BT->left>;
遍历当前结点左子树
rightdep=BTreeDepth(BT->right>;
遍历当前结点右子树
if(
leftdep>rightdep>return(leftdep+1>; 从叶子计数
else return(rightdep+1>;
}
得 分
}
BTreeDepth
三、 算法设计题<每题10分，共30分）
1. 试用C或类C语言编写一高效算法，将一顺序存储的线性表<设元素均为
整
型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。
cw7grDewXf
解： void SortA(sqlist &L>
{ int
i=0, zerosum =0;
if(==0> return(0>; 空表
else {
for( i=1; i<=; i++>
{if
(L.v[i]<>0> L.v[i- zerosum]= L.v[i];
非空表时
特别浪费！cw7grDewXf
zerosum++;
}
while(zerosum!=0>{
L.v[i]= =0;
zerosum--} 表的后部补0} return(ok>
}
以上算法在非空表时特别浪费！
解： void SortA(sqlist
&L>
{ int i=0,zerosum =0;
if(= =0>
return(0>; 空表则不执行
while(i<=&&(L.v[i]<>0> i++;
非空表则不移动if(i>>
return(ok>;
else{i++;
zerosum++; 若有零元素则统计和移动for( i;
i<=;
i++>
{if (L.v[i]= =0> zerosum++;
else
L.v[i- zerosum]= L.v[i]; };
非零元素顺序前移
while(zerosum!=0>{
L.v[i]= =0;
zerosum--} 表的后部补0} return(ok>
解2：
void SortA(sqlist &L>
{ int i=0,zerosum
=0;
if(= =0> return(0>; 空表则不执行
while(i<=&&(L.v[i]<>0> i++; 非空表则不移动if(i>>
return(ok>;
if(i>> return(ok>;
i++; zerosum++; 一定有零元素
for( i;
i<=; i++>
{if (L.v[i]<>0> L.v[i- zerosum]=
L.v[i];
zerosum++;
}
while(zerosum!=0>{
L.v[i]= =0;
zerosum--} 表的后部补0} return(ok>
2.
试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。
解： void
SortA(sqlist &A, int n>
{ if(n==0>
return(0>; 空表
if (a[1]
{ for( i=1;
i<=n2; i++> if (a[i]>a[2*i]||
a[i]>a[2*i+1]>return(-1>;cw7grDewXf
return(minleap>
};
else
{
for( i=1; i<=n2; i++> if (a[i]
return(“maxleap”>
};
}
3. 一棵二叉树的繁
茂度定义为各层结点数的最大值与树的高度的乘积。试写
一高效算法，求二叉树的繁茂度。cw7grD
ewXf
法一：要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每
一层的结点个数之后,再从计数器中挑出最大值。cw7grDewXf
typedef
struct {
BTNode node; int layer;
layer是结点所在层数 } BTNRecord, r
int
Width(Bitree T >{ 求树宽
int count[ ];
增开count向量，存放各层对应的结点数
InitQueue(Q>;
队列初始化，Q的元素为BTNRecord类型
EnQueue(Q,{T, 0}>;
根结点入队, 0 表示count[0]，下标值
while(!QueueEmpty(Q>>
{ DeQueue(Q, r>; 结点出队 count[]++;
出队时再
把结点对应层的计数器加if(->lchild>
EnQueue(Q,{->lchild,
+1}>; cw7grDewXf
if(->rchild> EnQueue(Q,{->rchild,
+1}>;cw7grDewXf
} 按层序入队时要随时标注结点所在层号
h=; 最后一个队列元素所在层就是树的高度
for(maxn=count[0], i=1; h; i++>
if(count[i]>maxn> maxn=count[i]; 求出哪一层结点数最多
return (h*maxn>} Width
附加题：<15分）
法二：若不用辅助数组，不用层数分量也可以，关键在于如何区别层与层。有两种方法：
一、通过比较指针判断是否到达新的一层的开始; 二、通过比较指针判断是否到达当前层的末尾.
由于方法一对新的一层的开始点不易确定，比较次数要多于第二种，因此推荐第二种。
对任意种类的树都适用，二叉树类似可得。
算法如下：
------------
--------------------------------------------------
----------------------------
TreeWidth
求树的宽度
不用辅助数组，不用层数分量
思路：
1.以两个整型变量存宽度，一个表示当前层的节点数，一个表示当前已知最大宽度，当遍历
完
一层后立即判断两者大小，保留大者。
2.通过比较指针判断是否到达本层的末尾，以确定层与层间的关系。
----------
--------------------------------------------------
-------------------------------
int
TreeWidth(TreeNode * T>
{
int iMaxCount=0,
iRecCount=0;iRecCount当前层的节点数,iMaxCount当前已知最大宽度
TreeNode * pP=T,*
pLastChild=T;pP指向当前节点,pFirstChild指向本层最末节点
InitQueue(Q>;队列初始化，Q的元素为TreeNode*类型
EnQueue(Q,T>;根结点入队
while(!QueueEmpty(Q>>
{
DeQueue(Q,pP>;结点出队
iRecCount++;出队时再把结点所在层的计数器加1
if(hasChild(pP>>
EnQueue(Q,pP->Child>;有孩子则孩子入队
if(pP=pLastChild>若到达本层的末尾
{先决定iMaxCount，再重置iRecCount 求繁茂度不能清零此变量。
iMaxCount=max(iMaxCount,iRecCount>;
iRecCount=0;
QueueTail(Q,pLastChild>;
读出队尾元素，注意不是出队!!!
既已到本层末尾，又已将其孩子入队(若有的话>，则队尾元素必为下一层的最末元素
}
}
return iMaxCount;
设p、t分别表示两棵没有度为1 的结
点的二叉树。设计一种算法，找出p和
t中最大的同构子树并分析算法的时间复杂度<无需写出算法，描
述思路即
可）。cw7grDewXf
注：“同构”是指两个二叉树不仅结点数相同
、并且它们的左右子树之间的关
系也相同，但各结点的数据值可以不同。cw7grDewXf
“最大的同构子树”即结点最多的同构子树。
解： 我们把一棵二叉
树用树描述符来表示，则问题会变得容易解决。所谓树
描述符，即对每个结点按二叉树先序遍历并输出结
点的度。例如
左边二叉树的描述符为202202000.在此描述符中，如果一个子
串的字符
数等于此子串中每个数字之和加1，则此子串一定是一
个子树。cw7grDewXf
如上面的字符串中，2202000是一个子树，因为他有7个字符，每个字符数字
和为2+2+2=
6.
同理，20200,200也是子树。
问题转化为两个字符串中寻找满足上述条件的最长公共子串。
最长公共子串的算法已有<见习
题），只需在此算法中加上判断此子串是否是
一个子树的条件即可。
判断一个子串是否为一个子树的复杂度为O
是否为子树的过程可以和求最长公共子串相
结合，即在求最长公共子串中完
成。cw7grDewXf
则求最大同构子树的复杂度为O(mn>。
申明：
所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。