数据结构A(参考答案).pdfVIP

2009级《数据结构》课程试题（A卷）参考答案

一、单选题：（每题2分，共30分）

DCDCCCABDBCCAAD

二、按要求解答下列问题：（每空5分，共30分）

1.算法效率和算法使用的策略、问题规模、书写语言、算法运行的软硬件环境等有关系，

简要说明使用算法时间复杂度度量算法效率的思想。

不考虑计算机硬件、软件有关的因素，认为一个特定算法运行工作量的大小只依赖于

问题的规模，即从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操

作重复的次数作为算法的时间度量。

2.证明：对任何一棵二叉树T，如果终端结点数为n0，度为2的结点数为n2，则n0=n2+1

设二叉树中度为1的结点数为n1，度为2的结点数为n2，二叉树中总结点数为n，因

二叉树中所有结点的度均小于或等于2，有

n＝n0＋n1＋n2

由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2n2

n＝n1＋2n2＋1

n0+n1+n2=n1+2n2+1

n0＝n2＋1

3.假设有5项活动，每项活动要求的前驱活动如下：

C1：无；C2：C1，C3；C3：C1；

C4：C3，C5C5：C2，C3；

试根据上述关系，（1）画出相应的有向图：（2）写出拓扑排序序列；

C1C2C5C4

C3

C1,C3,C2,C5,C4

共4页第1页

4.含12个结点的平衡二叉树的最大深度是多少（设根结点的深度为1）？画出一颗这样

的树。

最大深度是5

5.判别下面的每个结点序列是否表示一个堆，如果不是，请把它调整为一个堆。

（1）100，90，80，60，85，75，20，25

（2）100，70，50，20，90，75，60，25

(1)是

（2）不是100，90，75，25，70，50，60，20

6.关键字序列：22、41、53、46、30、13、01、67，h(key)=keymod11,表长为11，用

线性探测再散列处理冲突，试填写下表并计算每个关键字的冲突次数、比较次数和平

均查找长度。

012345678910

哈希表2201461367415330

冲突次数00013002

比较次数11124113

ASL=7/4

三、应用题：（每题10分，共10分）

已知AOE网如下图，解答下列问题：

（1）画出该AOE网的邻接表；

（2）指出该网的关键路径和该工程最早几天完成；

（3）如果要求整个工期提前2天完成，该如何安排各个活动的时间，写出所有可能

的调整方案？（说明：要求应该尽可能少地改变活动的原有时间，并假设每个

活动最多只能提前1天；）

共4页第2页

V2a5=6

a1=4

a3=2