算法与数据结构-参考答案-A卷

石家庄铁道大学2013-2014学年第1学期

2012级本科期末考试答案（A）

12345678910

CACBBCBDDB

（15分）（酌情给分）

（1）赫夫曼树（7分）

FE

（2）每个字母的赫夫曼编码（3分）

A:010B:101C:00D:011E:10001F:10000G:1001H:1

（3）赫夫曼树存储结构的终态（5分）

结点iweightparentIchildrchild

10.091100

20.161200

30.201300

40.121100

50.03900

60.02900

70.081000

80.301400

90.051065

100.131297

110.211314

120.2914102

130.4115311

140.5915128

15101314

2.（10分）（酌情给分）

（1）构造Hash表（8分）

下标0123456789101112131415

数据26133426933923115138

比较12122111112

次数

(2)ASLsucc=(1/11)(1*7+2*4)=1.36(2分)

3.（10分）（酌情给分）

（1）邻接矩阵。（5分）

0023000000

2000000915

3000011006

00001100004

00900000000

0015640000

（2）最小生成树（给出简要的构造过程）（5分）

构造过程:

第1步第2步

第5步

4.40分）（酌情给分）

（1）采用快速排序算法每趟排序结束后关键字序列的状态。（5分）

下标012345678910

初始序列{391281262451701945}

第1趟排序结果39(1912812624}39{705145}

第2趟排序结果19{6112}19{2824}39{705145}

第3趟排序结果6{1}6{12)19{2824)39{705145}

第4趟排序结果28161219{24}2839{705145)

第5趟排序结果70161219242839{4551}70

第6趟排序结果4516121924283945{51)70

（2）采用二路归并排序算法每趟排序结束后关键字序列的状态。（5分）

初始序列139J[1J[28][12][6J124][51J[70][19J[45

第1趟排序结果[139][1228][624][5170][1945]

第2趟排序结果[1122839][6245170][1945]

第3趟排序结果[16122428395170][1945]

第4趟排序结果[161219242839455170J

（1）二叉树（分析写出过程）（6分）

A

分析过程：

前序遍历序列：ABDHEICFJGK

中序遍历序列：DHB1EAJFCKG

A的左子树的前序遍历序列：BDHEIA的右子树的前序遍历序列：CFJGK

A的左子树的中序遍历序列：DHBIEA的右子树的中序遍历序列：JFCKG

B的左子树的前序遍历序列：DHC的左子树的前序遍历序列：FJ

B的左子树的中序遍历序列：DHC的左子树的中序遍历序列：JF

B的右子树的前序遍历序列：EIC的右子树的前序遍历序列：GK

B的右子树的中序遍历序列：IEC的右子树的中序遍历序列：KG

(2)后序遍历序列：HDIEBJFKGCA(4分)

(3)森林：(5分)

1.单链表问题答案(答案不惟一)

TypedefstructNode{

chardata;

delete(q);

structnode*next;

}Node,*LinkList;)

elsep=p->next;

〃没有头结点的代码实现

)

voiddelete_node(LinkListL)

(

2.二叉树问题(答案不惟一)

LinkListp,q;

TypedefstructBitNode)

P=L;

intdata;

while(p->next!=NULL)

StructBitNode*lchild,*rchild;

(

}BitNode,*BiTree;

q=p->next;

intcount(BiTreet,inta)

if(q->data>