一、 选择题 1.C 2.D 3.C 4.C 5.A 6.C 7.C 8.C 9.A 10.A 二、 填空题 1. 三元数组存储、十字链表 2. 一对一、一对多 3. 2n-1
4. 计算简单，散列之后得到的元素分布均匀 5. 前驱、后继 6. N0 7. 66
【解答】10*（1+1+1）*2+3*2=66 8. L->next=L 9. 44
【解答】1*9+2*7+3*（2+5）=44 10. （15,40,95,20,50,70） 三、 判断题 1. X 2. √ 3. X 4. √ 5. √ 6. √ 7. X 8. √ 9. X 10. X 四、 简答题 1. 这里给出简单的求解步骤： 从顶点0开始，那么分析可知，第一个结点应该选择1，那么0->1 的距离=1 第二个节点选择3，为0->3的距离=3
第三个节点选择2为0->3->2的距离为3+2=5
第四个结点选择6，为0->3->2->4的距离为3+2+1=6 2. 1)画出的完全二叉树如下所示： 2)大根堆序列为：75、65、40、50、10、7、5、43、27
3)第一趟排序之后的序列为： 3. 算法的功能为： 计算二叉树中节点值为0的节点的个数 4. 构造过程如下： 5. 1)画出二叉树得： 2) 先序遍历结果：ABDGCEHIF 中序遍历结果：DGBAHEICF 后序遍历结果：GDBHIEFCA
6.（1）散列的结果图如下： 2）25 18 53
3）平均查找长度为： （1*5+2*2+3*1+4*1）/9=16/9 五、 程序填空题 1. （1）p!=NULL
（2）p=p->next
（3）p->next=q->next （4）free(q)
2. （5）j（8）a[j]=temp （9）flag==0 六、 算法题 1. 直接是折半查找的算法实现： int bisearch(int r[ ], int n,int k){int low=0,mid,high=n-1; while(low<=high){
mid=(low+high)/2; if(r[mid].key==k)
return(mid+1); else if(r[mid].key>k)
high=mid-1;
else
low=mid+1; }
return(0);
}
2. 代码如下： // 给出结构体 typedef struct arcnode{ int adjvex;
struct arcnode*next; }arcnode;
typedef struct { int vertex;
arcnode*firstarc; }vexnode;
vexnode adjlist[max]; // 整体的算法代码 void toposort(int n){ int queue[max]; int front=0,rear=0; int v,w,m; arcnode*p; m=0;
for(v=1;v<=n;v++) if(adjlist[v].vertex==0) { rear=(rear+1)%max; queue[rear]=v; } printf(\"the toposort:\\n\"); while(front!=rear){ front=(front+1)%max; v=queue[front]; printf(\"%d \ m++; p=adjlist[v].firstarc; while(p!=NULL) { w=p->adjvex; adjlist[w].vertex--; if(adjlist[w].vertex==0){ rear=(rear+1)%max; queue[rear]=w; } p=p->next; } } if(m
