2010 —2011 年度第二学期计算机学院

一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分)

四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共12分)

1．如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图。

答案：

2． 试画出如下图所示无向网的邻接多重表存储结构图。

参：

五、求解问题(每小题8分，共32分)

1．如下图所示为n行2n-1列矩阵A[1..n，1..2n-1]，现以行为主序进行压缩存储到一维数组SA[1…m]中。（1）试问m值是什么？（2）假定非零元素A[i，j]保存在SA[k]中，试写出由下标(i，j)到k的转换公式。

答案：（1）m=n2

（2）k=(i-1) 2+i+j-n      (当 |j-n|2. 如下图所示为有序表（10，15，21，33，44，60，67，68，70，80）的判定树，试问该判定树是否正确？如果正确，说明理由，错误则指出错误处并给出正确结果。

答案：

注：没按序号作为结点值扣1分

3．试用元素序列(63、72、88、68、66、38、43),生成平衡二叉排序树T,(1)按步骤画出该平衡二叉排序树T,(2)写出平衡二叉排序树T的中序遍历序列,(3)假定每个元素的查找概率相等,计算查找成功时的平均查找长度。

答案：

（1）

（2）38，43，63，66，68，72，88

（3）ASL=（1+2*2+3*4）/7=17/7

4．已知图的邻接表法存储结构如下，从顶点A出发求图的深度遍历的结果。

 答案： ABDECF 

六、证明题(每小题5分，共10分)

1，证明在哈夫曼树种最小权值所对应的叶结点的层数正好是哈夫曼树的高度。

略

2．证明有n个结点的完全二叉树的高度为log2(n+1)。

略

七、编程题(6分)

1．已知大小为N的数组A[N]、B[N]分别存放着有N个结点的某二叉树的先根和中根遍历序列，试编写函数CreateBiTree构造该二叉树。相关说明如下：

参：

bitTree CreateBiTree(ElemType X[]，ElemType Y[N]，int n)

{

int i;

if (!n) return NULL;

T=(BitTree)malloc(sizeof(NODE));

T->data=X[0];

for(i=0; Y[i]==X[0] ;i++);

T->lchild= CreateBiTree(&X[1],Y,i);

T->rchild= CreateBiTree(&X[i+1],&Y[i+1],n-i-1);

Return T;

}

八、阅读并改进算法(每小题4分，共8分)

（1）. 阅读上面的算法程序，叙述算法的功能，并给出算法的时间与空间复杂度。

答案：输入一个数k，在有序序列中找2个数，使其和等于k

T(n)= O(n)    S(n)= O(n)

（2）改写算法，使改进算法的时间和空间效率尽可能提高。

参：

#include#define MAXSIZE 13main(){ int a[MAXSIZE]= ={1,4,5,6, 8,10,11,13,15,20 };  int k,i,j;  scanf("%d",&k);  i=0,j=MAXSIZE-1;  while(ik j--;  else i++;  }  if(i下载本文