2014年北方工业大学数据结构期中考试卷

二、按要求做题（15分）

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针

if(L&&L->next){

q=L；L=L－>next；p=L；

S1： while(p－>next) p=p－>next；

S2： p－>next=q；q－>next=NULL；

}

return L；

}

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；

（3）设链表表示的线性表存放的数据为（1,2, …,10）, 写出算法执行后的返回值所表

示的线性表。

三．运算题(共61分)

1. (18分)（i）已知一棵二叉树的中序遍历DBGEACF，后序遍历为DGEBFCA，求这棵二叉树及其前序遍历。

(ii) 给定一个二叉树前序和后序遍历，能恢复出二叉树吗？为什么？

(iii) 写出下面这棵树的中序和后序遍历

2014年北方工业大学数据结构期中考试卷

2. (5分) 计算运行下列程序后m的值：

n=10; m=0;

for(i=1;i<=n;i++)

for(j=2*i; j<=n; j++)

m=m+2;

3. （10分） 编号为1,2,3的三辆列车，顺序开进一个链式结构的站台，则开出车站的顺序可能有哪些？共有多少种？

4．（10分）请画出图的邻接矩阵和邻接表。

2014年北方工业大学数据结构期中考试卷

5.（18分）设给定一个权值集合W=(3, 4，5, 6， 8) （i） 要求根据给定的权值集合构造一棵哈夫曼树

（ii） 计算哈夫曼树的带权路径长度及相应的哈夫曼编码。 （iii） 简要介绍构造哈夫曼树的算法